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