Unifying Information-Theoretic and Pair-Counting Clustering Similarity

तकनीकी सारांश: सूचना-सैद्धांतिक (Information-Theoretic) और युग्म-गणना (Pair-Counting) क्लस्टरिंग समानता का एकीकरण

समस्या विवरण
क्लस्टरिंगों की तुलना करना अनसुपरवाइज्ड मॉडलों के मूल्यांकन के लिए मौलिक है, फिर भी अभ्यासकर्ता अक्सर विभिन्न समानता सूचकांकों (similarity indices) के बीच महत्वपूर्ण असहमति का सामना करते हैं। यह क्षेत्र वर्तमान में दो प्रमुख परिवारों में विभाजित है: युग्म-गणना माप (जैसे रैंड इंडेक्स, एडजस्टेड रैंड इंडेक्स, जैकार्ड), जो अव्यवस्थित युग्मों (unordered pairs) पर तत्वों की सहमति का मूल्यांकन करते हैं, और सूचना-सैद्धांतिक माप (जैसे म्यूचुअल इंफॉर्मेशन, वेरिएशन ऑफ इंफॉर्मेशन), जो क्लस्टर सह-घटन (co-occurrences) की पूर्ण कंटिंजेंसी टेबल (contingency table) के माध्यम से निर्भरता को एकत्रित करते हैं। ये परिवार एक ही विभाजन (partition) के लिए अक्सर भिन्न निष्कर्ष प्रस्तुत करते हैं, जिससे व्याख्या अस्पष्ट हो जाती है। हालांकि पिछले कार्यों ने अक्षिअोमैटिक (axiomatic) अंतर या ज्यामितीय स्थानीय तुल्यता की पहचान की है, लेकिन एक एकीकृत विश्लेणात्मक ढांचे की कमी थी जो यह समझा सके कि ये माप क्यों भिन्न होते हैं—विशेष रूप से उनके वेटिंग सिद्धांतों (weighting principles) और सैंपलिंग स्पेस के संबंध में।

कार्यप्रणाली
यह शोध पत्र एक साझा स्वतंत्रता आधार रेखा (independence baseline) और उनके अंतर्निहित गणितीय संरचनाओं के विस्तार के माध्यम से इन दोनों परिवारों को एकीकृत करने वाला एक विश्लेणात्मक ढांचा विकसित करता है।

1. स्वतंत्रता के चारों ओर अवशिष्ट विस्तार (Residual Expansion around Independence):
   लेखक एक तटस्थ संदर्भ मॉडल को परिभाषित करते हैं जहाँ दो क्लस्टरिंग स्वतंत्र होते हैं, जिसे अपेक्षित प्रायिकता $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$ द्वारा पहचाना जाता है। वे इस आधार रेखा से विचलन का विश्लेषण अवशेषों (residuals) $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$ का उपयोग करके करते हैं।

• म्यूचुअल इंफॉर्मेशन (MI): शोध पत्र स्वतंत्रता आधार रेखा के आसपास MI का एक सटीक टेलर सीरीज़ विस्तार (Taylor series expansion) व्युत्पन्न करता है। अग्रणी पद एक सीमांत रूप से भारित द्विघात रूप (marginally weighted quadratic form) ($\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$) है, जो एक पियर्सन $\chi^2$ सांख्यिकी के अनुरूप है। यह वेटिंग उन सेल्स (cells) में विचलन को अधिक महत्व देती है जिनमें अपेक्षित द्रव्यमान (expected mass) कम होता है (दुर्लभ प्रतिच्छेदन)।
• युग्म-गणना सूचकांक (जैसे रैंड इंडेक्स): रैंड इंडेक्स को एक सीमांत आधार रेखा (संयोग सहमति) और एक अवशिष्ट पद में विघटित किया गया है। यह दिखाया गया है कि अवशिष्ट घटक एक भारहीन द्विघात रूप ($\sum \delta_{ij}^2$) और एक रैखिक संरेखण पद है। MI के विपरीत, युग्म-गणना माप अपेक्षित द्रव्यमान द्वारा विभाजित नहीं होते हैं, जिसका अर्थ है कि वे बड़े क्लस्टरों द्वारा हावी होते हैं और अल्पसंख्यक क्लस्टरों में सुसंगत संरेखण को कम महत्व देते हैं।

2. उच्च-क्रम टुपल्स (Higher-Order Tuples) तक विस्तार:
   लेखक युग्म-गणना ढांचे को अव्यवस्थित युग्मों से आगे $k$-टुपल्स तक विस्तारित करते हैं। वे टकराव प्रायिकताओं (collision probabilities) की एक श्रेणी पेश करते, जो इस संभावना को परिभाषित करती है कि $k$ स्वतंत्र रूप से नमूने लिए गए तत्व एक ही क्लस्टर (या एक ही कंटिंजेंसी सेल) में गिरेंगे।

• $k=2$ के लिए, वे मानक युग्म-गणना मात्राओं को पुनः प्राप्त करते हैं।
• $k > 2$ के लिए, वे रेनी एंट्रॉपी कंट्रास्ट (Rényi entropy contrasts) $I^{(k)}$ का एक परिवार परिभाषित करते हैं, जो $k$-तत्वों के सह-निर्धारण (co-assignments) की निरंतरता के आधार पर सहमति को मापते हैं।
• यह एक सेतु बनाता है जहाँ युग्म-गणना, रेनी एंट्रॉपी से जुड़े व्यापक पदानुक्रम के दूसरे क्रम (order-two) का मामला है, जो समूह-स्तरीय सुसंगतता के अधिक कड़े परीक्षण प्रदान करता है।

3. तत्व-केंद्रित संबंध (Element-Centric Connection):
   यह शोध पत्र इस टुपल-काउंटिंग पदानुक्रम को एफिनिटी ग्राफ पर रैंड वॉक (random walks) पर आधारित तत्व-केंद्रित समानता से जोड़ता है। यह प्रदर्शित करता है कि सख्त विभाजनों (strict partitions) के लिए, $k$-टुपल टकराव प्रायिकताएं उस संभावना के अनुरूप होती हैं जहाँ एक रैंड वॉक $k$ चरणों के लिए एक क्लस्टर के भीतर रहता है, जो सैंपलिंग पदानुक्रम के लिए एक ज्यामितीय व्याख्या प्रदान करता है।

प्रमुख योगदान

• विश्लेषणात्मक सेतु: शोध पत्र एक कठोर व्युत्पत्ति प्रदान करता है जो यह दर्शाता है कि सूचना-सैद्धांतिक और युग्म-गणना दोनों ही एक ही कंटिजेंसी-टेबल अवशेषों के फलन हैं, जो मुख्य रूप से अपने वेटिंग स्कीम्स (संभाव्यता-भारित बनाम भारहीन) और सैंपलिंग स्पेस (एकल तत्व बनाम अव्यवस्थित युग्म) में भिन्न होते हैं।
• सहमति का पदानुक्रम: यह स्थापित करता है कि युग्म-गणना एक अलग प्रतिमान नहीं है, बल्कि एक व्यापक टकराव-गणना पदानुक्रम (collision-counting hierarchy - $k$-tuples) का दूसरा क्रम है जो रेनी एंट्रॉपी से जुड़ा हुआ है।
• विचलन की व्याख्यात्मकता: इन मापों को विघटित करके, शोध पत्र यह स्पष्ट करता है कि सूचकांकों के बीच असहमति (जैसे RI बनाम MI) मनमानी नहीं है, बल्कि स्पष्ट गणितीय विकल्पों से उत्पन्न होती है: क्या बड़े क्लस्टरों के व्यापक ओवरलैप पर जोर दिया जाए (युग्म-गणना) या छोटे क्लस्टरों में तीक्ष्ण, व्यवस्थित संरेखण पर (सूचना-सैद्धांतिक)।

परिणाम
नियंत्रित सिंथेटिक उदाहरणों के माध्यम से, शोध पत्र इन सैद्धांतिक अंतरों के व्यावहारिक निहितार्थों को प्रदर्शित करता है:

• संतुलित क्लस्टर: जब क्लस्टर का आकार संतुलित होता है और शोर (noise) सममित होता है, तो माप सहमत होते हैं, क्योंकि वेटिंग के अंतर कम हो जाते हैं।
• असंतुलित क्लस्टर: तीव्र वर्ग असंतुलन (class imbalance) के तहत, माप महत्वपूर्ण रूप से भिन्न होते हैं।
  • छोटा-छोटा असहमति (Small-Small Disagreements): जब दो छोटे अल्पसंख्यक क्लस्टरों के बीच तत्वों को बदला जाता है, तो सूचना-सैद्धांतिक माप (MI) तेजी से गिरते हैं क्योंकि वे अपेक्षित द्रव्यमान के व्युत्क्रम द्वारा विचलन को भारित करते हैं। युग्म-गणना माप (ARI) अपेक्षाकृत स्थिर रहते हैं क्योंकि वे बड़े, अपरिवर्तित क्लस्टरों द्वारा संचालित होते हैं।
  • बड़ा-छोटा असहमति (Big-Small Disagreements): जब एक बड़े और एक छोटे क्लस्टर के बीच तत्वों को बदला जाता है, तो सभी माप गिरते हैं, लेकिन अवशिष्ट विश्लेषण से पता चलता है कि युग्म-गणना माप बड़े क्लस्टर के व्यवधान के भारहीन द्विघात पद द्वारा संचालित होते हैं।
• उच्च-क्रम संवेदनशीलता: $k$-टुपल कंट्रास्ट ($I^{(k)}$) दिखाते हैं कि जबकि युग्म-गणना माप ($I^{(2)}$) विसरित (diffuse) और केंद्रित ओवरलैप के बीच अंतर नहीं कर सकते हैं (यदि युग्म गणना समान है), उच्च-क्रम टुपल्स ($I^{(3)}$, आदि) यह पता लगा सकते हैं कि क्या युग्मय सहमति सुसंगत समूह-स्तरीय संरचनाओं द्वारा समर्थित है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह एकीकरण मेट्रिक असहमति को एक बाधा से बदलकर व्याख्या योग्य साक्ष्य में बदल देता है कि प्रत्येक माप किन क्लस्टरिंग संरचनाओं पर जोर देता है।

• यह तर्क देता है कि कोई भी एक "सर्वश्रेष्ठ" माप नहीं है; बल्कि, कार्य के आधार पर सूचकांक का चयन किया जाना चाहिए। युग्म-गणना बड़े, सजातीय समूहों के बीच मोटे समझौते का सारांश देने के लिए उपयुक्त है। सूचना-सैद्धांतिक माप छोटे लेकिन व्यवस्थित संरेखण या अल्पसंख्यक उप-प्रकारों का पता लगाने के लिए बेहतर हैं। उच्च-क्रम टुपल सारांश यह परीक्षण करने के लिए एक मध्यवर्ती शासन (regime) प्रदान करते हैं कि क्या युग्म सहमति सुसंगत समूहों तक विस्तृत है।
• यह ढांचा सामान्यीकरण (normalization), संयोग सुधार (chance correction), और सैंपलिंग परिवर्तनशीलता को एक सामान्य सैद्धांतिक संरचना के भीतर ट्यून करने योग्य शासन के रूप में पुनर्गठित करता है, जिससे अभ्यासकर्ताओं को प्रथम सिद्धांतों के आधार पर सूचकांकों का चयन करने की अनुमति मिलती है।
• लेखक विनम्रतापूर्वक नोट करते हैं कि अवशिष्ट विस्तार स्वतंत्रता आधार रेखा के पास सबसे पारदर्शी है और उच्च-क्रम टुपल गणनाओं में परिमित नमूनों (finite samples) में डेटा की कमी (sparsity) की समस्या हो सकती है, जो भविष्य के कार्य के लिए परिमित-नमूना सुधारों और ओवरलैपिंग या सॉफ्ट क्लस्टरिंग के विस्तार का सुझाव देता है।