एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग
एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग एक बॉटम-अप क्लस्टरिंग दृष्टिकोण है जहां क्लस्टर्स के सब-क्लस्टर्स होते हैं, जिनके बदले में सब-क्लस्टर्स होते हैं, आदि। यह प्रत्येक ऑब्जेक्ट को उसके अपने क्लस्टर में रखकर शुरू होता है और फिर इन परमाणु क्लस्टर्स को तब तक बड़े और बड़े क्लस्टर्स में जोड़ता है जब तक कि सभी ऑब्जेक्ट्स एक ही क्लस्टर में न हों या जब तक एक निश्चित समाप्ति स्थिति की आवश्यकता न हो। कई पदानुक्रमित क्लस्टरिंग दृष्टिकोण इस प्रकार के उपयोग किए जाते हैं। वे केवल अपने क्लस्टर-बीच समानता के विवरण में भिन्न होते हैं।
उदाहरण: AGNES (एग्लोमरेटिव नेस्टिंग)
उदाहरण के लिए, AGNES (Agglomerative Nesting) नामक एक विधि सिंगल-लिंक तकनीकों का उपयोग करती है और इस प्रकार काम करती है। मान लें कि ऑब्जेक्ट्स के समूह एक आयत में रखे गए हैं। प्रारंभ में, प्रत्येक ऑब्जेक्ट को अपने स्वयं के क्लस्टर में रखा जाता है। इसलिए क्लस्टर्स को क्लस्टर में निकटतम ऑब्जेक्ट्स के बीच न्यूनतम यूक्लिडियन दूरी वाले क्लस्टर्स को मिलाने जैसे सिद्धांत के अनुसार चरण-दर-चरण जोड़ा जाता है।
डेंड्रोग्राम
पदानुक्रमित क्लस्टरिंग को एक ट्री-जैसे आरेख का उपयोग करके ग्राफिक रूप से दिखाया जाता है जिसे डेंड्रोग्राम कहा जाता है, जो क्लस्टर-सबक्लस्टर संबंधों और उस क्रम दोनों को दर्शाता है जिसमें क्लस्टर्स को जोड़ा गया था (एग्लोमरेटिव दृश्य) या विभाजित किया गया था (विभाजन दृश्य)।
बेसिक एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग एल्गोरिदम
- यदि आवश्यक हो तो निकटता मैट्रिक्स की गणना करें।
- दोहराएं
- सबसे निकट के दो क्लस्टर्स को मर्ज करें।
- नए क्लस्टर और मूल क्लस्टर्स के बीच निकटता को दर्शाने के लिए निकटता मैट्रिक्स को अपडेट करें।
- जब तक केवल एक क्लस्टर शेष न रह जाए।
क्लस्टर निकटता परिभाषाएं
क्लस्टर निकटता आमतौर पर एक विशिष्ट प्रकार के क्लस्टर के साथ परिभाषित की जाती है। उदाहरण के लिए, कई एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग तकनीकें, जिनमें MIN, MAX, और ग्रुप एवरेज शामिल हैं, क्लस्टर्स के ग्राफ-आधारित दृश्य से आती हैं।
MIN क्लस्टर निकटता को उन दो पॉइंट्स के बीच निकटता के रूप में परिभाषित करता है जो अलग-अलग क्लस्टर्स में हैं और सबसे निकट हैं, या ग्राफ विधियों का उपयोग करके, अलग-अलग नोड्स के सबसेट्स में दो नोड्स के बीच सबसे छोटा किनारा।
वैकल्पिक रूप से, MAX अलग-अलग क्लस्टर्स में दो सबसे दूर के पॉइंट्स के बीच निकटता को क्लस्टर निकटता मानता है या ग्राफ विधियों का उपयोग करके, अलग-अलग नोड्स के सबसेट्स में दो नोड्स के बीच सबसे लंबा किनारा।
जटिलता विश्लेषण
प्रस्तुत बेसिक एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग एल्गोरिदम के लिए एक निकटता मैट्रिक्स की आवश्यकता होती है। इसके लिए ½m² निकटताओं के भंडारण की आवश्यकता होती है (यह मानते हुए कि निकटता मैट्रिक्स सममित है) जहां m डेटा पॉइंट्स की संख्या है। क्लस्टर्स को ट्रैक करने के लिए आवश्यक स्थान क्लस्टर्स की संख्या के समानुपाती होता है, जो m-1 है, एकल तत्व क्लस्टर्स को छोड़कर। इसलिए, कुल स्थान जटिलता O(m²) है।
बेसिक एग्लोमरेटिव पदानुक्रमित क्लस्टरिंग एल्गोरिदम का विश्लेषण कम्प्यूटेशनल जटिलता के संबंध में भी सरल है। निकटता मैट्रिक्स की गणना के लिए O(m²) समय की आवश्यकता होती है। उस चरण के बाद, m-1 पुनरावृत्तियां होती हैं जिनमें चरण 3 और 4 शामिल हैं क्योंकि शुरुआत में m क्लस्टर्स होते हैं और प्रत्येक पुनरावृत्ति के दौरान दो क्लस्टर्स मर्ज किए जाते हैं।
