Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
यह शोध पत्र यह प्रदर्शित करता है कि, फ्लैट क्लस्टरिंग के विपरीत जो क्लाइनबर्ग के असंभवता प्रमेय (Kleinberg's Impossibility Theorem) द्वारा बाधित है, पदानुक्रमित क्लस्टरिंग (hierarchical clustering) अपनी विविधता के बावजूद एक साझा संरचनात्मक आधार (common structural backbone) साझा करने वाले अनगिनत स्वीकार्य तरीकों के अस्तित्व के माध्यम से समृद्धि (richness), निरंतरता (consistency) और स्केल इनवेरिएंस (scale invariance) को एक साथ संतुष्ट कर सकती है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
डेटा साइंस की दुनिया में, क्लस्टरिंग (clustering) नामक एक मौलिक कार्य है। कल्पना कीजिए कि आपके पास वस्तुओं का एक संग्रह है—जैसे कि फलों का मिश्रण, या लोगों का एक समूह, या दस्तावेजों का एक सेट—और आप उन्हें उनकी समानता के आधार पर सार्थक समूहों में वर्गीकृत करना चाहते हैं। आपके पास कोई लेबल नहीं है जो आपको बता सके कि कौन सा सेब कौन सा है; आपके पास केवल एक माप है कि प्रत्येक वस्तु दूसरी वस्तु से कितनी भिन्न है। लक्ष्य यह है कि डेटा को स्वयं बोलने दिया जाए और इसकी छिपी हुई संरचना को प्रकट किया जाए। दशकों से, शोधकर्ताओं ने इसे करने के सबसे सटीक तरीके को परिभाषित करने का प्रयास किया है। उन्होंने नियमों का एक समूह प्रस्तावित किया है कि किसी भी अच्छे वर्गीकरण पद्धति को किन बुनियादी नियमों का पालन करना चाहिए। एक नियम यह है कि पद्धति को माप की इकाइयों की परवाह नहीं करनी चाहिए; चाहे आप दूरी को मीटर में मापें या मील में, समूह समान रहने चाहिए। दूसरा नियम यह है कि पद्धति इतनी लचीली होनी चाहिए कि यदि डेटा इसके अनुकूल हो, तो वह किसी भी संभावित समूहीकरण को खोज सके। तीसरा नियम यह है कि यदि आप एक समूह के भीतर की वस्तुओं को एक-दूसरे के अधिक समान बनाते हैं और समूहों के बीच की वस्तुओं को एक-दूसरे से अधिक भिन्न बनाते हैं, तो पद्धति अचानक उस समूह को तोड़ने का निर्णय नहीं ले सकती।
लंबे समय तक, यह माना जाता था कि कोई भी एकल पद्धति इन तीनों नियमों को एक साथ संतुष्ट नहीं कर सकती। क्षेत्र के एक प्रसिद्ध परिणाम ने दिखाया कि यदि आप अपने डेटा को केवल समूहों की एक सपाट परत (flat layer) में काटने के लिए मजबूर होते हैं—जैसे ताश की गड्डी को सूट के एकल ढेर में छाँटना—तो अनिवार्य रूप से आपको एक नियम तोड़ना ही पड़ेगा। या तो आपको डेटा के पैमाने (scale) को अनदेखा करना होगा, या आपको कुछ वैध समूहीकरणों को छोड़ना होगा, या आपको डेटा में थोड़े से बदलाव होने पर अस्थिर होना होगा। इसने एक ऐसी सीमा का अहसास कराया, जैसे कि सपाट समूहों में डेटा को छाँटने की प्रकृति ही त्रुटिपूर्ण हो। लेकिन क्या होगा यदि समाधान डेटा को एक एकल परत में जबरदस्ती डालने के बजाय, इसे एक पेड़ (tree) के रूप में विकसित होने देना हो? क्या होगा यदि आप केवल यह कहने के बजाय कि "ये समूह हैं," यह कह सकें कि "ये समूह हैं, और उन समूहों के भीतर छोटे समूह हैं, और उनके भीतर और भी छोटे समूह हैं"? यह पदानुक्रमित क्लस्टरिंग (hierarchical clustering) का विचार है, जहाँ आउटपुट एक नेस्टेड संरचना (nested structure) होता है न कि एक सपाट सूची।
एकोल पॉलिटेक्निक फेडरल डी लाउज़ेन (École Polytechnique Fédérale de Lausanne) और यूनिवर्सिटी ऑफ गुस्ताव एफ़िल (Université Gustave Eiffel) के शोधकर्ताओं की एक टीम ने अब यह दिखाया है कि यह पदानुक्रमित दृष्टिकोण सब कुछ बदल देता है। उन्होंने उन तीन सख्त नियमों को लिया जिन्होंने फ्लैट क्लस्टरिंग को असंभव बना दिया था और पूछा कि क्या वे नियमों को तब संतुष्ट कर सकते हैं जब आउटपुट एक पदानुक्रम (hierarchy) हो। उत्तर एक निश्चित 'हाँ' है। उन्होंने सिद्ध किया कि ऐसा करने का केवल एक तरीका नहीं है, बल्कि अनगिनत तरीके हैं जो इन तीनों नियमों को एक साथ संतुष्ट कर सकते हैं। वास्तव में, उन्होंने पाया कि इन वैध पद्धतियों का स्थान अविश्वसनीय रूप से विशाल और विविध है। यह इतना बड़ा है कि आप उन सभी को सूचीबद्ध भी नहीं कर सकते, और इस विशाल संग्रह के भीतर, कई पद्धतियाँ मौलिक रूप रूप से एक-दूसरे के साथ असंगत हैं। आप केवल उस "सर्वश्रेष्ठ" पद्धति को नहीं चुन सकते जो सब कुछ पूरी तरह से करती है, क्योंकि कोई भी एकल पद्धति अंतिम विजेता नहीं है जो अन्य सभी को परिष्कृत करती है।
शोधकर्ताओं ने केवल यह सिद्ध नहीं किया कि ये पद्धतियाँ मौजूद हैं; उन्होंने यह दिखाने के लिए कई पद्धतियाँ बनाईं कि वे कैसे काम करती हैं। उन्होंने डेटा को छाँटने के सामान्य तरीकों को देखा, जैसे कि वह विधि जो हमेशा पहले दो निकटतम वस्तुओं को जोड़ती है। उन्होंने पाया कि इस विधि का एक विशिष्ट संस्करण, जो एक साथ कई समूहों को जोड़ने की अनुमति देता है जब वे समान रूप से निकट हों, पूरी तरह से काम करता है। उन्होंने समूहों के बीच के अलगाव पर आधारित नई पद्धतियाँ भी बनाईं। एक पद्धति उन समूहों की तलाश करती है जहाँ वस्तुओं के भीतर की चीजें बाहर की किसी भी चीज़ की तुलना में बहुत अधिक करीब होती हैं। दूसरी पद्धति अलगाव के एक थोड़े अलग प्रकार की तलाश करती है। उन्होंने दिखाया कि ये सभी पद्धतियाँ वैध हैं, फिर भी वे अलग-अलग परिणाम देती हैं। कुछ पद्धतियाँ बहुत सख्त हैं और केवल सबसे स्पष्ट, अच्छी तरह से अलग किए गए समूहों को खोजती हैं। अन्य अधिक उदार हैं और कई सूक्ष्म संबंधों को खोजती हैं।
इस व्यापक विविधता के बावजूद, शोधकर्ताओं ने एक छिपे हुए क्रम की खोज की। हालांकि पद्धतियाँ बारीक विवरणों पर असहमत होती हैं, लेकिन वे सबसे स्पष्ट, अच्छी तरह से अलग किए गए ढांचों पर सहमत होती हैं। यदि आप किन्हीं दो वैध पद्धतियों को लेते हैं और उन समूहों को देखते हैं जिन पर वे दोनों सहमत हैं, तो आप एक स्पष्ट, विशिष्ट क्लस्टरों का एक साझा आधार (backbone) पाएंगे। इसका अर्थ है कि जबकि पद्धतियाँ डेटा के अव्यवस्थित, मध्यवर्ती हिस्से को संभालने में भिन्न हो सकती हैं, वे सभी एक ही ठोस नींव का सम्मान करती हैं। शोधकर्ताओं ने यह भी पता लगाया कि क्या चौथा नियम जोड़ने पर क्या होता है: कि यदि डेटा में पहले से ही एक पूर्ण पेड़ जैसी संरचना बनी हुई है, तो पद्धति को ठीक उसी पेड़ को खोजना चाहिए। इस सख्त आवश्यकता के साथ भी, पद्धतियों की विशाल विविधता बनी रहती है, लेकिन अब एक एकल, सबसे मोटे (coarsest) पद्धति के रूप में एक शुरुआती बिंदु है जो अन्य सभी के लिए आधार का काम करती है।
यह कार्य डेटा को व्यवस्थित करने के हमारे दृष्टिकोण को नया आकार देता है। यह दिखाता है कि किसी छँटाई पद्धति के लिए हमारी सभी इच्छाओं को संतुष्ट करने में असमर्थता ब्रह्मांड की एक मौलिक खामी नहीं है, बल्कि डेटा को एक एकल, सपाट परत में डालने की एक सीमा है। डेटा को नेस्टेड समूहों की कहानी बताने की अनुमति देकर, हम एक साथ सब कुछ प्राप्त कर सकते हैं। हमारे पास एक ऐसी पद्धति हो सकती है जो स्केल-इनवेरिएंट (scale-invariant), लचीली और स्थिर हो, और वह भी एक ही समय में। शोधकर्ताओं ने यह भी दिखाया कि ये पद्धतियाँ हमारे डेटा को प्रीप्रोसेस (preprocess) करने के सामान्य तरीकों के प्रति सुदृढ़ (robust) हैं, जैसे कि इकाइयों को बदलना या छाँटने से पहले संख्याओं को रूपांतरित करना। यह सुझाव देता है कि यह ढांचा केवल एक गणितीय जिज्ञासा नहीं है, बल्कि एक व्यावहारिक उपकरण है जिसका उपयोग वास्तविक दुनिया के पाइपलाइनों में किया जा सकता है। यह अध्ययन हमें एक ऐसे परिदृश्य की तस्वीर देता है जो दुनिया को छाँटने के अनगिनत वैध तरीकों से भरा हुआ है, जिनमें से सभी सबसे महत्वपूर्ण विशेषताओं पर सहमत हैं, फिर भी विवरणों पर विविध दृष्टिकोण प्रदान करते हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।