CURE (Clustering Using Representatives)
CURE का अर्थ है Clustering Using Representatives। यह एक क्लस्टरिंग एल्गोरिदम है जो बड़ी डेटा सेट्स, आउटलेयर्स, और गैर-गोलीय वास्तुकला और गैर-समान आकार के क्लस्टर्स को प्रबंधित करने वाले दृष्टिकोण बनाने के लिए कई तकनीकों का उपयोग करता है। CURE क्लस्टर से कई प्रतिनिधि पॉइंट्स का उपयोग करके एक क्लस्टर को परिभाषित करता है।
ये पॉइंट्स क्लस्टर की ज्यामिति और वास्तुकला को कैप्चर करेंगे। पहला प्रतिनिधि पॉइंट क्लस्टर के केंद्र से सबसे दूर के पॉइंट के रूप में चुना जाता है, जबकि शेष पॉइंट्स को इस तरह चुना जाता है कि वे पहले से चुने गए सभी पॉइंट्स से सबसे दूर हों। इस तरह, प्रतिनिधि पॉइंट्स अपेक्षाकृत अच्छी तरह से वितरित होते हैं। चुने गए पॉइंट्स की संख्या एक पैरामीटर है, लेकिन यह पाया गया कि 10 या अधिक का मान अच्छा काम करता है।
क्योंकि प्रतिनिधि पॉइंट्स चुने जाते हैं, उन्हें एक कारक, α द्वारा केंद्र की ओर सिकोड़ा जाता है। यह आउटलेयर्स के प्रभाव को कम करने में मदद करता है, जो आमतौर पर केंद्र से दूर होते हैं और इसलिए, अधिक सिकुड़ते हैं। उदाहरण के लिए, एक प्रतिनिधि पॉइंट जो केंद्र से 10 इकाई की दूरी पर था, 3 इकाइयों से बदल सकता है (α = 0.7 के लिए), जबकि 1 इकाई की दूरी पर एक प्रतिनिधि पॉइंट 0.3 इकाइयों से बदल जाएगा।
आउटलेयर उन्मूलन
CURE पदानुक्रमित क्लस्टरिंग प्रक्रिया की विशिष्ट विशेषताओं का लाभ उठाकर क्लस्टरिंग चरण में दो अलग-अलग बिंदुओं पर आउटलेयर्स को हटाता है। पहला, यदि एक क्लस्टर धीरे-धीरे बढ़ रहा है, तो इसका मतलब यह हो सकता है कि इसमें ज्यादातर आउटलेयर्स शामिल हैं, क्योंकि परिभाषा के अनुसार, आउटलेयर्स दूसरों से दूर होते हैं और अन्य पॉइंट्स के साथ बहुत बार संयोजित नहीं होंगे।
CURE में, आउटलेयर उन्मूलन की यह पहली प्रक्रिया आमतौर पर तब होती है जब क्लस्टर्स की संख्या प्रारंभिक पॉइंट्स की संख्या का 1/3 होती है। आउटलेयर उन्मूलन की दूसरी प्रक्रिया तब होती है जब क्लस्टर्स की संख्या K के क्रम पर होती है, वांछित क्लस्टर्स की संख्या। इस बिंदु पर, छोटे क्लस्टर्स को हटा दिया जाता है।
बड़े डेटासेट्स के लिए अनुकूलन
क्योंकि CURE की सबसे खराब स्थिति की जटिलता O(m²log m) है, इसे सीधे बड़े डेटासेट्स पर उपयोग नहीं किया जा सकता। CURE क्लस्टरिंग प्रक्रिया को तेज करने के लिए दो विधियों का उपयोग करता है। पहली विधि एक रैंडम सैंपल लेती है और सैंपल किए गए डेटा पॉइंट्स पर पदानुक्रमित क्लस्टरिंग लागू करती है। इसके बाद एक अंतिम पास होता है जो डेटा सेट में प्रत्येक शेष पॉइंट को निकटतम प्रतिनिधि पॉइंट वाले क्लस्टर को चुनकर क्लस्टर्स में से एक को असाइन करता है।
कुछ मामलों में, क्लस्टरिंग के लिए आवश्यक सैंपल बड़ा होता है और एक दूसरी अधिक तकनीक की आवश्यकता होती है। इस स्थिति में, CURE सैंपल डेटा को विभाजित करता है और प्रत्येक विभाजन में पॉइंट्स को क्लस्टर करता है। यह प्री-क्लस्टरिंग प्रक्रिया मध्यवर्ती क्लस्टर्स की क्लस्टरिंग और एक अंतिम पास द्वारा अनुसरण की जाती है जो डेटा सेट में प्रत्येक पॉइंट को क्लस्टर्स में से एक को असाइन करता है।
