स्थानिक डेटा माइनिंग के लिए क्लस्टरिंग विधियाँ क्या हैं?

क्लस्टर विश्लेषण सांख्यिकी की एक शाखा है जिसका कई वर्षों से व्यापक अध्ययन किया गया है। इस तकनीक का लाभ यह है कि किसी भी पृष्ठभूमि ज्ञान, जैसे अवधारणा पदानुक्रम का उपयोग किए बिना, डेटा से सीधे दिलचस्प संरचनाएं या क्लस्टर खोजे जा सकते हैं।

सांख्यिकी में उपयोग किए जाने वाले क्लस्टरिंग एल्गोरिदम, जैसे PAM या CLARA, कम्प्यूटेशनल जटिलता के दृष्टिकोण से अक्षम बताए गए हैं। दक्षता चिंता के अनुसार, CLARANS (रैंडमाइज्ड सर्च पर आधारित बड़े अनुप्रयोगों का क्लस्टरिंग) नामक एक नया एल्गोरिदम क्लस्टर विश्लेषण के लिए विकसित किया गया था।

क्लस्टरिंग एल्गोरिदम

PAM (मेडॉइड्स के आसपास विभाजन - Partitioning around Medoids)

यह मानते हुए कि n वस्तुएं हैं, PAM पहले प्रत्येक क्लस्टर के लिए एक प्रतिनिधि वस्तु ढूंढकर k क्लस्टर ढूंढता है। ऐसा प्रतिनिधि, जो एक क्लस्टर में केंद्रीय रूप से स्थित बिंदु है, मेडॉइड के रूप में जाना जाता है।

k मेडॉइड्स चुनने के बाद, एल्गोरिदम वस्तुओं के सभी संभावित जोड़े का विश्लेषण करके मेडॉइड्स के सर्वोत्तम विकल्प को बनाने का बार-बार प्रयास करता है जैसे कि एक वस्तु एक मेडॉइड है और दूसरी नहीं है। क्लस्टरिंग गुणवत्ता का माप प्रत्येक ऐसे संयोजन के लिए गणना की जाती है।

एक पुनरावृत्ति में अच्छे बिंदुओं का विकल्प अगली पुनरावृत्ति के लिए मेडॉइड्स के रूप में चुना जाता है। एकल पुनरावृत्ति की लागत O(k(n-k)²) है। इसलिए यह बड़े n और k के मूल्यों के लिए कम्प्यूटेशनली काफी अक्षम है।

CLARA (बड़े अनुप्रयोगों का क्लस्टरिंग - Clustering Large Applications)

PAM और CLARA एल्गोरिदम के बीच अंतर यह है कि बाद वाला नमूनाकरण पर आधारित है। वास्तविक डेटा का केवल एक छोटा हिस्सा डेटा के प्रतिनिधि के रूप में चुना जाता है और PAM का उपयोग करके इस नमूने से मेडॉइड्स चुने जाते हैं।

विचार यह है कि यदि नमूना काफी यादृच्छिक तरीके से चुना जाता है, तो यह पूरे डेटासेट को सही ढंग से दर्शाता है और इसलिए, प्रतिनिधि वस्तुएं (मेडॉइड्स) चुनी जाएंगी जैसे कि पूरे डेटासेट से चुनी गई हों।

CLARA कई नमूने निकालता है और इन नमूनों में से सर्वोत्तम क्लस्टरिंग का आउटपुट देता है। CLARA PAM से बड़े डेटासेट से निपट सकता है। प्रत्येक पुनरावृत्ति की जटिलता अब O(kS² + k(n-k)) हो जाती है, जहां S नमूने का आकार है।

CLARANS (रैंडमाइज्ड सर्च पर आधारित बड़े अनुप्रयोगों का क्लस्टरिंग - Clustering Large Applications based upon RANdomized Search)

CLARANS एल्गोरिदम PAM और CLARA दोनों को जोड़ता है केवल डेटासेट के उपसमुच्चय की खोज करके और यह किसी भी दिए गए समय पर कुछ नमूने तक खुद को सीमित नहीं करता। जबकि CLARA में खोज के प्रत्येक चरण में एक स्थिर नमूना होता है, CLARANS खोज के हर चरण में कुछ यादृच्छिकता के साथ एक नमूना निकालता है।

क्लस्टरिंग चरण को एक ग्राफ की खोज के रूप में प्रस्तुत किया जा सकता है जहां प्रत्येक नोड एक संभावित समाधान है, यानी, k मेडॉइड्स का एक सेट। एक मेडॉइड को प्रतिस्थापित करने के बाद प्राप्त क्लस्टरिंग को वर्तमान क्लस्टरिंग का पड़ोसी कहा जाता है।