पदानुक्रमित क्लस्टरिंग, जिसे पदानुक्रमित क्लस्टर विश्लेषण (HCA) के रूप में भी जाना जाता है, डेटा माइनिंग और सांख्यिकी में क्लस्टर विश्लेषण की एक विधि है जो क्लस्टरों का पदानुक्रम बनाने का प्रयास करती है। विभाजनकारी विधियों जैसे कि k-means के विपरीत, जिनमें क्लस्टरों की संख्या पहले से निर्दिष्ट करने की आवश्यकता होती है, पदानुक्रमित क्लस्टरिंग एक नेस्टेड संरचना उत्पन्न करती है जिसे विभिन्न संख्याओं के क्लस्टर प्राप्त करने के लिए किसी भी स्तर पर काटा जा सकता है। परिणाम आमतौर पर एक डेंड्रोग्राम में प्रस्तुत किए जाते हैं, जो एक वृक्ष-समान आरेख है जो विलय या विभाजन के अनुक्रम को दर्शाता है। यह दृष्टिकोण जीव विज्ञान, सामाजिक विज्ञान और मशीन लर्निंग जैसे क्षेत्रों में खोजपूर्ण डेटा विश्लेषण के लिए व्यापक रूप से उपयोग किया जाता है।
पदानुक्रमित क्लस्टरिंग का प्रमुख लाभ इसकी लचीलापन है: दूरी का कोई भी मान्य माप उपयोग किया जा सकता है, और अवलोकनों की स्वयं आवश्यकता नहीं होती, केवल दूरियों का एक मैट्रिक्स आवश्यक होता है। हालांकि, सिंगल-लिंकेज दूरी के विशेष मामले को छोड़कर, कोई भी एल्गोरिदम व्यापक खोज के बिना इष्टतम समाधान खोजने की गारंटी नहीं दे सकता, जिसकी समय जटिलता O(2^n) होती है।
एग्लोमेरेटिव और डिविसिव रणनीतियाँ
पदानुक्रमित क्लस्टरिंग रणनीतियाँ आम तौर पर दो श्रेणियों में आती हैं: एग्लोमेरेटिव और डिविसिव। एग्लोमेरेटिव क्लस्टरिंग, जिसे अक्सर "नीचे-से-ऊपर" दृष्टिकोण कहा जाता है, प्रत्येक डेटा बिंदु को एक व्यक्तिगत क्लस्टर के रूप में शुरू करती है। प्रत्येक चरण में, एल्गोरिदम चुनी गई दूरी मीट्रिक (जैसे, यूक्लिडियन दूरी) और एक लिंकेज मानदंड (जैसे, सिंगल-लिंकेज, कम्पलीट-लिंकेज) के आधार पर दो सबसे समान क्लस्टरों को विलय करता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि सभी डेटा बिंदु एक एकल क्लस्टर में संयोजित नहीं हो जाते या एक रोक मानदंड पूरा नहीं हो जाता। एग्लोमेरेटिव विधियाँ अपनी सरलता और छोटे से मध्यम आकार के डेटासेट के लिए कम्प्यूटेशनल दक्षता के कारण अधिक सामान्यतः उपयोग की जाती हैं।
डिविसिव क्लस्टरिंग, जिसे "ऊपर-से-नीचे" दृष्टिकोण के रूप में जाना जाता है, सभी डेटा बिंदुओं के साथ एक एकल क्लस्टर में शुरू होती है और पुनरावर्ती रूप से क्लस्टर को छोटे क्लस्टरों में विभाजित करती है। प्रत्येक चरण में, एल्गोरिदम एक क्लस्टर का चयन करता है और उसे दो या अधिक उपसमुच्चयों में विभाजित करता है, अक्सर परिणामी क्लस्टरों के बीच की दूरी को अधिकतम करने जैसे मानदंड का उपयोग करता है। डिविसिव विधियाँ कम सामान्य हैं लेकिन तब उपयोगी हो सकती हैं जब लक्ष्य पहले बड़े, विशिष्ट क्लस्टरों की पहचान करना हो। सामान्य तौर पर, विलय और विभाजन लालची तरीके से निर्धारित किए जाते हैं, जिसका अर्थ है कि एल्गोरिदम वैश्विक संरचना पर विचार किए बिना प्रत्येक चरण पर स्थानीय रूप से इष्टतम विकल्प बनाता है।
जटिलता और एल्गोरिदम
पदानुक्रमित एग्लोमेरेटिव क्लस्टरिंग (HAC) के लिए मानक एल्गोरिदम की समय जटिलता O(n^3) होती है और इसके लिए Ω(n^2) मेमोरी की आवश्यकता होती है, जो इसे मध्यम डेटासेट के लिए भी बहुत धीमा बनाती है। हालांकि, कुछ विशेष मामलों के लिए, O(n^2) जटिलता के इष्टतम कुशल एग्लोमेरेटिव तरीके ज्ञात हैं: सिंगल-लिंकेज के लिए SLINK और कम्पलीट-लिंकेज क्लस्टरिंग के लिए CLINK। हीप के साथ, सामान्य मामले का रनटाइम O(n^3) के बजाय O(n^2 log n) तक कम किया जा सकता है, अतिरिक्त मेमोरी आवश्यकताओं की कीमत पर। कई मामलों में, इस दृष्टिकोण की मेमोरी ओवरहेड्स इसे व्यावहारिक रूप से उपयोग करने के लिए बहुत बड़ी होती हैं। ऐसी विधियाँ मौजूद हैं जो क्वाडट्री का उपयोग करती हैं और O(n) स्थान के साथ O(n^2) कुल चलने का समय प्रदर्शित करती हैं।
व्यापक खोज के साथ डिविसिव क्लस्टरिंग O(2^n) है, लेकिन विभाजन चुनने के लिए तेज़ ह्यूरिस्टिक्स का उपयोग करना सामान्य है, जैसे कि k-means। ये ह्यूरिस्टिक्स कम्प्यूटेशनल व्यवहार्यता के लिए इष्टतमता का व्यापार करते हैं, जिससे डिविसिव विधियों को बड़े डेटासेट पर लागू किया जा सकता है।
दूरी मीट्रिक्स
जबकि लिंकेज मानदंड यह निर्धारित करता है कि अवलोकनों के सेटों के बीच असमानता की गणना कैसे की जाती है, अंतर्निहित दूरी मीट्रिक यह निर्धारित करती है कि व्यक्तिगत अवलोकनों के बीच असमानता कैसे मापी जाती है। चूंकि पदानुक्रमित क्लस्टरिंग दूरी के किसी भी मान्य माप की अनुमति देती है, मीट्रिक का चुनाव डेटा की प्रकृति द्वारा निर्देशित होता है और परिणामी क्लस्टरिंग पर महत्वपूर्ण प्रभाव डाल सकता है।
यूक्लिडियन दूरी निरंतर संख्यात्मक डेटा के लिए सबसे व्यापक रूप से उपयोग की जाने वाली मीट्रिक है। यह यूक्लिडियन स्थान में दो बिंदुओं के बीच सीधी-रेखा दूरी से मेल खाती है और अधिकांश सांख्यिकीय सॉफ्टवेयर में डिफ़ॉल्ट विकल्प है। मैनहट्टन दूरी (जिसे सिटी-ब्लॉक या L1 दूरी भी कहा जाता है) विशेषताओं में पूर्ण अंतरों का योग करती है। इसे अक्सर तब पसंद किया जाता है जब विशेषताओं को विभिन्न पैमानों पर मापा जाता है या जब डेटा में आउटलायर होते हैं, क्योंकि यह यूक्लिडियन दूरी की तुलना में बड़े विचलनों के प्रति कम संवेदनशील होती है। कोसाइन दूरी दो गैर-शून्य वैक्टरों के बीच कोणीय असमानता को मापती है और आमतौर पर पाठ विश्लेषण और अन्य उच्च-आयामी सेटिंग्स में उपयोग की जाती है।
लिंकेज मानदंड
लिंकेज मानदंड यह निर्धारित करता है कि दो क्लस्टरों के बीच की दूरी उनके व्यक्तिगत सदस्यों के बीच की दूरियों से कैसे गणना की जाती है। सिंगल-लिंकेज (या निकटतम-पड़ोसी) दो क्लस्टरों में किसी भी दो बिंदुओं के बीच न्यूनतम दूरी का उपयोग करता है, जो लंबे, श्रृंखला-जैसे क्लस्टर उत्पन्न करता है। कम्पलीट-लिंकेज (या सबसे दूर-पड़ोसी) अधिकतम दूरी का उपयोग करता है, जो कॉम्पैक्ट, गोलाकार क्लस्टर उत्पन्न करता है। एवरेज-लिंकेज सभी बिंदुओं के जोड़ों के बीच माध्य दूरी का उपयोग करता है, जो दोनों के बीच एक समझौता प्रदान करता है। वार्ड की विधि कुल भीतर-क्लस्टर विचरण को कम करती है, जिससे यह निरंतर डेटा के लिए लोकप्रिय हो जाती है। लिंकेज मानदंड का चुनाव परिणामी डेंड्रोग्राम के आकार और व्याख्या को नाटकीय रूप से बदल सकता है।
अनुप्रयोग और सीमाएँ
पदानुक्रमित क्लस्टरिंग कई क्षेत्रों में उपयोग की जाती है। जीव विज्ञान में, इसका उपयोग आनुवंशिक समानता के आधार पर फ़ाइलोजेनेटिक पेड़ों के निर्माण के लिए किया जाता है। विपणन में, यह ग्राहकों को समान व्यवहार वाले समूहों में विभाजित करने में मदद करता है। छवि विश्लेषण में, यह पिक्सेल या विशेषताओं को समूहित कर सकता है। कृत्रिम बुद्धिमत्ता में, पदानुक्रमित क्लस्टरिंग अक्सर खोजपूर्ण डेटा विश्लेषण के लिए एक अनुपयोगी शिक्षण तकनीक के रूप में और अन्य एल्गोरिदम के लिए एक पूर्व-प्रसंस्करण चरण के रूप में उपयोग की जाती है।
अपने लाभों के बावजूद, पदानुक्रमित क्लस्टरिंग की सीमाएँ हैं। एल्गोरिदम की लालची प्रकृति का अर्थ है कि एक बार विलय या विभाजन हो जाने के बाद, इसे पूर्ववत नहीं किया जा सकता, जिससे उप-इष्टतम परिणाम हो सकते हैं। मानक एल्गोरिदम की कम्प्यूटेशनल जटिलता इसके उपयोग को मध्यम आकार के डेटासेट तक सीमित करती है, हालांकि विशिष्ट लिंकेज मानदंडों के लिए अनुकूलित कार्यान्वयन मौजूद हैं। इसके अतिरिक्त, डेंड्रोग्राम की व्याख्या व्यक्तिपरक हो सकती है, और दूरी मीट्रिक और लिंकेज मानदंड का चुनाव डोमेन ज्ञान की आवश्यकता होती है।