क्लस्टर विश्लेषण आंकड़ों की एक शाखा है जिसका कई वर्षों से व्यापक रूप से अध्ययन किया गया है। इस तकनीक का उपयोग करने का लाभ यह है कि किसी भी पृष्ठभूमि ज्ञान, जैसे कि अवधारणा पदानुक्रम का उपयोग किए बिना दिलचस्प संरचनाओं या समूहों को सीधे डेटा से खोजा जा सकता है।
PAM या CLARA जैसे आंकड़ों में उपयोग किए जाने वाले क्लस्टरिंग एल्गोरिदम को कम्प्यूटेशनल जटिलता की दृष्टि से अक्षम बताया गया है। दक्षता संबंधी चिंता के अनुसार, क्लस्टर विश्लेषण के लिए CLARANS (रैंडमाइज्ड सर्च पर आधारित क्लस्टरिंग लार्ज एप्लिकेशन) नामक एक नया एल्गोरिदम विकसित किया गया था।
PAM (Medoids के आसपास विभाजन) - यह मान रहा है कि n ऑब्जेक्ट हैं, PAM पहले प्रत्येक क्लस्टर के लिए एक प्रतिनिधि ऑब्जेक्ट ढूंढकर k क्लस्टर ढूंढता है। ऐसा प्रतिनिधि, जो क्लस्टर में केंद्र में स्थित बिंदु है, मेडॉइड के रूप में जाना जाता है।
k मेडोइड्स चुनने के बाद, एल्गोरिथम बार-बार मेडोइड्स का सबसे अच्छा विकल्प बनाने की कोशिश करता है जो वस्तुओं के सभी संभव जोड़े का विश्लेषण करता है जैसे कि एक वस्तु एक मेडॉइड है और दूसरी नहीं है। ऐसे प्रत्येक संयोजन के लिए क्लस्टरिंग गुणवत्ता के माप की गणना की जाती है।
एक पुनरावृत्ति में बिंदुओं का अच्छा विकल्प निम्नलिखित पुनरावृत्ति के लिए मध्यक के रूप में चुना जाता है। एकल पुनरावृत्ति की लागत O(k(n−k) 2 . है ) . इसलिए यह n और k के बड़े मानों के लिए कम्प्यूटेशनल रूप से काफी अक्षम है।
क्लारा (क्लस्टरिंग लार्ज एप्लिकेशन) - पीएएम और क्लारा एल्गोरिदम के बीच अंतर यह है कि निम्नलिखित नमूनाकरण पर आधारित है। वास्तविक डेटा का केवल एक छोटा सा क्षेत्र डेटा के प्रतिनिधि के रूप में चुना जाता है और PAM का उपयोग करके इस नमूने से मेडोइड्स चुने जाते हैं।
विचार यह है कि यदि नमूना काफी यादृच्छिक तरीके से चुना जाता है, तो यह पूरे डेटासेट का सही ढंग से प्रतिनिधित्व करता है और इसलिए, चुने गए प्रतिनिधि ऑब्जेक्ट (मेडोइड्स) समान होंगे जैसे कि पूरे डेटासेट से चुना गया हो।
क्लारा कई नमूने लेता है और इन नमूनों में से अच्छी क्लस्टरिंग का उत्पादन करता है। क्लारा PAM की तुलना में उच्च डेटासेट से निपट सकता है। प्रत्येक पुनरावृत्ति की जटिलता अब O(kS 2 . हो जाती है +k(n−k)), जहां S नमूने का आकार है।
CLARANS (यादृच्छिक खोज पर आधारित बड़े अनुप्रयोगों को समूहीकृत करना) - CLARANS एल्गोरिथ्म PAM और CLARA दोनों को केवल डेटासेट के सबसेट की खोज करके जोड़ता है और यह किसी भी समय किसी नमूने के लिए खुद को बाधित नहीं करता है। जबकि क्लारा के पास खोज के प्रत्येक चरण में एक निरंतर नमूना है, CLARANS खोज के प्रत्येक चरण में कुछ यादृच्छिकता के साथ एक नमूना तैयार करता है।
क्लस्टरिंग चरण को एक ऐसे ग्राफ की खोज के रूप में प्रस्तुत किया जा सकता है जहां प्रत्येक नोड एक संभावित समाधान है, यानी k मेडोइड्स का एक सेट। एकल मेडॉइड को बदलने के बाद प्राप्त क्लस्टरिंग को वर्तमान क्लस्टरिंग का पड़ोसी कहा जाता है।