स्पार्सिफिकेशन (Sparsification)
m डेटा पॉइंट्स के लिए m by m निकटता मैट्रिक्स को एक घने ग्राफ के रूप में परिभाषित किया जा सकता है जिसमें प्रत्येक नोड कुछ अन्य से जुड़ा होता है और किन्हीं दो नोड्स के बीच किनारे का वजन उनकी जोड़ीदार निकटता का पालन करता है। हालांकि प्रत्येक ऑब्जेक्ट का प्रत्येक अन्य ऑब्जेक्ट के साथ समानता का कुछ तरीका होता है, अधिकांश डेटा सेट्स के लिए, ऑब्जेक्ट्स कुछ ऑब्जेक्ट्स के साथ अत्यधिक समान होते हैं और अधिकांश अन्य ऑब्जेक्ट्स के साथ कमजोर रूप से समान होते हैं।
इस विशेषता का उपयोग निकटता ग्राफ (मैट्रिक्स) को स्पार्सिफाई करने के लिए किया जा सकता है, वास्तविक क्लस्टरिंग प्रक्रिया शुरू करने से पहले कुछ कम-समानता (उच्च-असमानता) मानों को 0 पर सेट करके। स्पार्सिफिकेशन को लागू किया जा सकता है, उदाहरण के लिए, उन सभी लिंक्स को विभाजित करके जिनकी समानता (असमानता) एक परिभाषित थ्रेशोल्ड से नीचे (ऊपर) है या पॉइंट के k निकटतम पड़ोसियों के लिंक्स को बनाए रखकर। यह विधि जिसे k-निकटतम पड़ोसी ग्राफ के रूप में जाना जाता है, बनाती है।
स्पार्सिफिकेशन के लाभ
1. डेटा आकार कम होता है
क्लस्टर करने के लिए आवश्यक डेटा की मात्रा अत्यधिक कम हो जाती है। स्पार्सिफिकेशन निकटता मैट्रिक्स में 99% से अधिक प्रविष्टियों को हटा सकता है। तदनुसार, उन समस्याओं का आकार जिन्हें प्रबंधित किया जा सकता है, बढ़ाया जाता है।
2. क्लस्टरिंग बेहतर काम कर सकती है
स्पार्सिफिकेशन विधियां एक ऑब्जेक्ट के निकटतम पड़ोसियों के लिंक को रखती हैं जबकि अधिक विशिष्ट ऑब्जेक्ट्स के कनेक्शन को विभाजित करती हैं। यह निकटतम पड़ोसी सिद्धांत के अनुरूप है कि एक ऑब्जेक्ट के निकटतम पड़ोसी उसी वर्ग (क्लस्टर) से संबंधित होते हैं जैसे ऑब्जेक्ट स्वयं। यह शोर और आउटलेयर्स के प्रभाव को कम करता है और क्लस्टर्स के बीच अंतर को तेज करता है।
3. ग्राफ पार्टीशनिंग एल्गोरिदम का उपयोग किया जा सकता है
स्पार्स ग्राफ के मिन-कट पार्टीशनिंग को खोजने के लिए ह्यूरिस्टिक एल्गोरिदम पर बड़ी मात्रा में काम किया गया है, विशेष रूप से समानांतर कंप्यूटिंग और एकीकृत सर्किट के डिजाइन के क्षेत्र में। निकटता ग्राफ का स्पार्सिफिकेशन ग्राफ पार्टीशनिंग एल्गोरिदम को क्लस्टरिंग चरण के लिए उपयोग करना संभव बनाता है जैसे कि Opossum और Chameleon को ग्राफ पार्टीशनिंग की आवश्यकता होती है।
निकटता ग्राफ के स्पार्सिफिकेशन को वास्तविक क्लस्टरिंग एल्गोरिदम के उपयोग से पहले एक मूल चरण के रूप में माना जाना चाहिए। एक अच्छा स्पार्सिफिकेशन निकटता मैट्रिक्स को वांछित क्लस्टर्स से संबंधित कनेक्टेड घटकों में विभाजित छोड़ सकता है, लेकिन व्यवहार में, ऐसा होता है।
एक व्यक्तिगत किनारे के लिए दो क्लस्टर्स को जोड़ना या एक व्यक्तिगत क्लस्टर को कई डिस्कनेक्टेड सबक्लस्टर्स में विभाजित करना आसान है। वास्तव में, जब Jarvis-Patrick और SNN घनत्व-आधारित क्लस्टरिंग का उपयोग करते हैं, तो स्पार्स निकटता ग्राफ को एक नया निकटता ग्राफ देने के लिए बदला जाता है। इस नए निकटता ग्राफ को स्पार्सिफाई किया जा सकता है। क्लस्टरिंग एल्गोरिदम उस निकटता ग्राफ के साथ काम करते हैं जो इन सभी प्रीप्रोसेसिंग प्रक्रियाओं का परिणाम है।
