Single-linkage clustering
सांख्यिकी में, एकल-लिंकेज क्लस्टरिंग पदानुक्रमित क्लस्टरिंग के कई तरीकों में से एक है। यह बॉटम-अप फैशन (एग्लोमेरेटिव क्लस्टरिंग) में समूहों के समूह पर आधारित है, प्रत्येक चरण में दो समूहों को जोड़ता है जिसमें तत्वों की निकटतम जोड़ी होती है जो अभी तक एक ही समूह से संबंधित नहीं हैं। यह विधि लंबे पतले समूहों का उत्पादन करती है जिसमें एक ही समूह के आस-पास के तत्वों की दूरी कम होती है, लेकिन एक समूह के विपरीत छोर पर तत्व अन्य समूहों के दो तत्वों की तुलना में एक दूसरे से बहुत दूर हो सकते हैं। डेटा के कुछ वर्गों के लिए, इससे उन वर्गों को परिभाषित करने में कठिनाइयाँ हो सकती हैं जो डेटा को उपयोगी रूप से उपविभाजित कर सकते हैं। हालाँकि, यह आकाशगंगा समूहों का विश्लेषण करने के लिए खगोल विज्ञान में लोकप्रिय है, जिसमें अक्सर पदार्थ के लंबे तार शामिल हो सकते हैं; इस अनुप्रयोग में, इसे फ्रेंड्स-ऑफ-फ्रेंड्स एल्गोरिदम के रूप में भी जाना जाता है। एग्लोमेरेटिव क्लस्टरिंग विधियों का अवलोकन एग्लोमेरेटिव क्लस्टरिंग प्रक्रिया की शुरुआत में, प्रत्येक तत्व अपने स्वयं के समूह में होता है। तब समूहों को क्रमिक रूप से बड़े समूहों में जोड़ा जाता है, जब तक कि सभी तत्व एक ही समूह में समाप्त नहीं हो जाते। प्रत्येक चरण में, सबसे कम दूरी से अलग किए गए दो समूहों को जोड़ा जाता है। दो समूहों के बीच की दूरी निर्धारित करने के लिए उपयोग किया जाने वाला कार्य, जिसे लिंकेज फ़ंक्शन के रूप में जाना जाता है, वह है जो एग्लोमेरेटिव क्लस्टरिंग विधियों को अलग करता है। एकल-संयोजन समूह में, दो समूहों के बीच की दूरी तत्वों की एक जोड़ी द्वारा निर्धारित की जाती हैः वे दो तत्व (प्रत्येक समूह में एक) जो एक दूसरे के सबसे करीब हैं। इन जोड़ीदार दूरी में से सबसे छोटी दूरी जो किसी भी चरण पर बनी रहती है, दो समूहों का कारण बनती है जिनके तत्व शामिल होते हैं। विधि को निकटतम पड़ोसी क्लस्टरिंग के रूप में भी जाना जाता है। क्लस्टरिंग के परिणाम को एक डेंड्रोग्राम के रूप में देखा जा सकता है, जो उस अनुक्रम को दर्शाता है जिसमें समूहों का विलय किया गया था और जिस दूरी पर प्रत्येक विलय हुआ था। गणितीय रूप से, लिंकेज फंक्शन-क्लस्टर X और Y के बीच की दूरी D (X, Y)-को उस अभिव्यक्ति द्वारा वर्णित किया जाता है जहां X और Y समूहों के रूप में माने जाने वाले तत्वों के किसी भी दो समूह हैं, और d (x, y) दो तत्वों x और y के बीच की दूरी को दर्शाता है। निष्कपट एल्गोरिथ्म निम्नलिखित एल्गोरिथ्म एक समग्र योजना है जो एक निकटता मैट्रिक्स में पंक्तियों और स्तंभों को मिटा देता है क्योंकि पुराने समूहों को नए में विलय कर दिया जाता है। निकटता मैट्रिक्स में सभी दूरी शामिल हैं। क्लस्टरिंग को अनुक्रम संख्या निर्धारित की जाती है और यह-th क्लस्टरिंग का स्तर है। अनुक्रम संख्या m के साथ एक समूह को (m) दर्शाया जाता है और समूहों के बीच निकटता को और दर्शाया जाता है। एकल लिंकेज एल्गोरिथ्म निम्नलिखित चरणों से बना हैः स्तर और अनुक्रम संख्या वाले असंबद्ध क्लस्टरिंग से शुरू करें। वर्तमान क्लस्टरिंग में समूहों की सबसे समान जोड़ी खोजें, मान लीजिए कि जोड़ी, जहां वर्तमान क्लस्टरिंग में समूहों के सभी जोड़े पर न्यूनतम है। अनुक्रम संख्या बढ़ाएँः अगले समूह बनाने के लिए समूहों और एकल समूह में विलय करें। क्लस्टर्स के अनुरूप पंक्तियों और स्तंभों को हटाकर और नवगठित समूह के अनुरूप एक पंक्ति और स्तंभ जोड़कर, निकटता मैट्रिक्स को अद्यतन करने के लिए इस क्लस्टरिंग का स्तर निर्धारित करें। नए समूह और पुराने समूह के बीच निकटता को इस प्रकार परिभाषित किया गया है। यदि सभी वस्तुएँ एक समूह में हैं, तो रुकें। अन्यथा, चरण 2 पर जाएँ। कार्यशील उदाहरण यह कार्यशील उदाहरण पांच बैक्टीरिया के 5S राइबोसोमल आर. एन. ए. अनुक्रम संरेखण से संगणित एक जे. सी. 69 आनुवंशिक दूरी मैट्रिक्स पर आधारित हैः बेसिलस सबटिलिस (), बेसिलस स्टीयरोथर्मोफिलस (), लैक्टोबैसिलस विरिडेसेन्स (), एकोलेप्लाज्मा मोडिकम (), और माइक्रोकोकस ल्यूटियस ()। पहला कदम पहला क्लस्टरिंग आइए मान लें कि हमारे पास पाँच तत्व हैं और उनके बीच जोड़ीदार दूरी का निम्नलिखित मैट्रिक्स हैः इस उदाहरण में, का सबसे कम मान है, इसलिए हम तत्वों को क्लस्टर करते हैं और। पहला शाखा लंबाई का अनुमान आइए उस नोड को दर्शाते हैं जिससे और अब जुड़े हुए हैं। सेटिंग यह सुनिश्चित करती है कि तत्व और उनसे समान दूरी पर हैं। यह अल्ट्रामेट्रिसिटी परिकल्पना की अपेक्षा से मेल खाता है। शाखाएँ जुड़ती हैं और फिर लंबाई होती है (अंतिम डेंड्रोग्राम देखें) पहला दूरी मैट्रिक्स अद्यतन हम फिर प्रारंभिक निकटता मैट्रिक्स को एक नए निकटता मैट्रिक्स में अद्यतन करने के लिए आगे बढ़ते हैं (नीचे देखें), आकार में एक पंक्ति और एक स्तंभ द्वारा घटाया जाता है क्योंकि साथ के समूह के कारण। बोल्ड मान नई दूरी के अनुरूप होते हैं, जिसकी गणना पहले समूह के प्रत्येक तत्व और शेष तत्वों में से प्रत्येक के बीच न्यूनतम दूरी को बनाए रखते हुए की जाती हैः समान्तरित मान मैट्रिक्स अद्यतन से प्रभावित नहीं होते हैं क्योंकि वे पहले समूह में शामिल नहीं होने वाले तत्वों के बीच की दूरी के अनुरूप होते हैं। दूसरा चरण दूसरा क्लस्टरिंग अब हम पिछले तीन कार्यों को दोहराते हैं, जो नई दूरी मैट्रिक्स से शुरू होते हैंः यहाँ, और सबसे कम मान हैं, इसलिए हम तत्व के साथ और तत्व के साथ समूह को जोड़ते हैं। दूसरी शाखा की लंबाई का अनुमान आइए उस नोड को दर्शाते हैं जिससे, और अब जुड़े हुए हैं। अल्ट्रामेट्रिसिटी बाधा के कारण, शाखाएं या से, और से, और भी बराबर होती हैं और उनकी कुल लंबाई निम्नलिखित होती हैः हम गायब शाखा की लंबाई का अनुमान लगाते हैंः (अंतिम डेंड्रोग्राम देखें) दूसरा दूरी मैट्रिक्स अद्यतन हम फिर मैट्रिक्स को एक नए दूरी मैट्रिक्स में अद्यतन करने के लिए आगे बढ़ते हैं (नीचे देखें), आकार में दो पंक्तियों और दो स्तंभों द्वारा घटाया जाता है क्योंकि साथ और साथ के समूह के कारणः अंतिम चरण अंतिम मैट्रिक्स हैः तो हम समूहों में शामिल होते हैं और। आइए उस (मूल) नोड को दर्शाते हैं जिससे और अब जुड़े हुए हैं। शाखाएँ जुड़ती हैं और फिर उनकी लंबाई होती हैः हम शेष शाखा की लंबाई का अनुमान लगाते हैंः एकल-संबंध डेंड्रोग्राम डेंड्रोग्राम अब पूरा हो गया है। यह अतिमापी है क्योंकि सभी नोक (,,,, और) निम्न से समान दूरी पर हैंः इसलिए डेंड्रोग्राम अपने सबसे गहरे नोड द्वारा निहित है। एकल लिंकेज क्लस्टरिंग के लिए सरल एल्गोरिथ्म अनिवार्य रूप से न्यूनतम फैले हुए पेड़ों के लिए क्रुस्कल के एल्गोरिथ्म के समान है। हालांकि, एकल लिंकेज क्लस्टरिंग में, जिस क्रम में समूह बनते हैं, वह महत्वपूर्ण है, जबकि न्यूनतम फैले हुए पेड़ों के लिए जो मायने रखता है वह बिंदुओं के जोड़े का सेट है जो एल्गोरिथ्म द्वारा चुनी गई दूरी बनाते हैं। वैकल्पिक लिंकेज योजनाओं में पूर्ण लिंकेज क्लस्टरिंग, औसत लिंकेज क्लस्टरिंग (यूपीजीएमए और डब्ल्यू. पी. जी. एम. ए.) और वार्ड की विधि शामिल हैं। एग्लोमेरेटिव क्लस्टरिंग के लिए निष्कपट एल्गोरिथ्म में, एल्गोरिथ्म में अंतर-क्लस्टर दूरी की गणना करने के लिए एक अलग सूत्र का उपयोग करके एक अलग लिंकेज योजना को लागू किया जा सकता है। जिस सूत्र को समायोजित किया जाना चाहिए, उसे उपरोक्त एल्गोरिथ्म विवरण में बोल्ड टेक्स्ट का उपयोग करके हाइलाइट किया गया है। हालाँकि, अधिक कुशल एल्गोरिदम जैसे कि नीचे वर्णित एल्गोरिदम सभी लिंकेज योजनाओं के लिए समान रूप से सामान्यीकृत नहीं होते हैं। तेज एल्गोरिदम एकल-लिंकेज क्लस्टरिंग के लिए सरल एल्गोरिदम को समझना आसान है लेकिन समय की जटिलता के साथ धीमा है। 1973 में, आर. सिब्सन ने समय जटिलता और अंतरिक्ष जटिलता (दोनों इष्टतम) के साथ एक एल्गोरिथ्म का प्रस्ताव रखा जिसे स्लिंक के रूप में जाना जाता है। स्लिंक एल्गोरिथ्म दो कार्यों द्वारा क्रमांकित वस्तुओं के एक समूह पर एक समूह का प्रतिनिधित्व करता है। ये दोनों कार्य सबसे छोटे समूह को ढूंढकर निर्धारित किए जाते हैं जिसमें वस्तु और कम से कम एक बड़ी संख्या वाली वस्तु दोनों शामिल होती हैं। पहला कार्य, वस्तु को समूह में सबसे बड़ी संख्या वाली वस्तु के लिए मानचित्रित करता है। दूसरा कार्य, वस्तु को समूह के निर्माण से जुड़ी दूरी तक मानचित्रित करता है। इन कार्यों को दो सरणी में संग्रहीत करना जो प्रत्येक वस्तु संख्या को उसके कार्य मूल्य पर मैप करता है, जगह लेता है, और यह जानकारी क्लस्टरिंग को निर्धारित करने के लिए पर्याप्त है। जैसा कि सिबसन दिखाता है, जब वस्तुओं के सेट में एक नया आइटम जोड़ा जाता है, तो संवर्धित सेट के लिए नए एकल-लिंकेज क्लस्टरिंग का प्रतिनिधित्व करने वाले अद्यतन कार्यों को उसी तरह दर्शाया जाता है, जिसे समय पर पुराने क्लस्टरिंग से बनाया जा सकता है। स्लिंक एल्गोरिथ्म तब वस्तुओं पर एक-एक करके लूप करता है, उन्हें क्लस्टरिंग के प्रतिनिधित्व में जोड़ता है। एक वैकल्पिक एल्गोरिथ्म, जो एक ही इष्टतम समय और स्थान सीमा में चलता है, न्यूनतम फैले हुए पेड़ों के लिए निष्कपट एल्गोरिथ्म और क्रुस्कल के एल्गोरिथ्म के बीच समानता पर आधारित है। क्रुस्कल के एल्गोरिदम का उपयोग करने के बजाय, कोई भी प्राइम के एल्गोरिदम का उपयोग कर सकता है, बिना द्विआधारी ढेर के एक भिन्नता में जो दी गई वस्तुओं और दूरी के न्यूनतम फैले हुए पेड़ (लेकिन क्लस्टरिंग नहीं) के निर्माण में समय और स्थान लेता है। फिर, न्यूनतम फैले हुए पेड़ के किनारों द्वारा बनाए गए विरल ग्राफ पर क्रुस्कल के एल्गोरिथ्म को लागू करने से एक अतिरिक्त समय और स्थान में क्लस्टरिंग का उत्पादन होता है। क्लस्टर विश्लेषण भी देखें पूर्ण-लिंकेज क्लस्टरिंग पदानुक्रमित क्लस्टरिंग आणविक घड़ी पड़ोसी-जुड़ाव यूपीजीएमए डब्ल्यूपीजीएमए संदर्भ बाहरी लिंक मैटलैब क्लस्टर विश्लेषण एल्गोरिदम में उपयोग किए जाने वाले लिंक