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