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