🤖 machine learning

Individual Fairness in Hierarchical Clustering

यह शोध पत्र पदानुक्रमित क्लस्टरिंग (hierarchical clustering) के लिए एक व्यक्तिगत निष्पक्षता ढांचा (individual fairness framework) प्रस्तुत करता है जो $k$ -निकटतम पड़ोस के भीतर स्थानीय विरूपण (local distortion) को सीमित करता है, व्यवहार्यता के लिए आवश्यक न्यूनतम स्लैक (slack) को अभिलक्षणिक बनाता है और स्थानीय एवं वैश्विक प्राप्ति (realizability) के बीच एक मौलिक $\Theta(\log n)$ पृथक्करण को प्रकट करता है।

मूल लेखक: Binita Maity, Shrutimoy Das

प्रकाशित 2026-08-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Binita Maity, Shrutimoy Das

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

डेटा विज्ञान की दुनिया में, शोधकर्ता अक्सर सूचनाओं के विशाल संग्रहों को समझने के लिए समान वस्तुओं को एक साथ समूहीकृत करने का प्रयास करते हैं। यह प्रक्रिया, जिसे क्लस्टरिंग (clustering) कहा जाता है, मिश्रित पत्थरों के एक विशाल ढेर को उनके रंग, वजन या बनावट के आधार पर छांटने के समान है। जबकि सरल समूहीकरण कुछ कार्यों के लिए अच्छा काम करता है, 'हाइरार्किकल क्लस्टरिंग' (hierarchical clustering) नामक एक अधिक परिष्कृत दृष्टिकोण डेटा का एक वंशावली वृक्ष (family tree) बनाता है। केवल वस्तुओं को अलग-अलग डिब्बों में रखने के बजाय, यह विधि एक नेस्टेड संरचना बनाती है, जो दिखाती है कि कैसे छोटे समूह बड़े समूहों में विलीन होते हैं, ठीक वैसे ही जैसे व्यक्तिगत परिवार कुलों का निर्माण करते हैं, जो फिर जनजातियों का निर्माण करते हैं। यह संरचना शक्तिशाली है क्योंकि यह विभिन्न स्तरों के विवरणों को प्रकट करती है, बहुत विशिष्ट से लेकर बहुत व्यापक तक। हालाँकि, इस शक्तिशाली उपकरण में एक छिपा हुआ दोष है: एक भव्य, वैश्विक चित्र बनाने की जल्दबाजी में, यह कभी-कभी पड़ोसियों के बीच के संबंधों को विकृत कर सकता है। दो वस्तुएं जो एक-दूसरे के बहुत करीब हैं, उन्हें अंतिम वृक्ष में बहुत दूर धकेला जा सकता है, या दो वस्तुएं जो काफी भिन्न हैं, उन्हें बहुत जल्दी एक साथ समूहबद्ध किया जा सकता है। यह विरूपण केवल एक गणितीय त्रुटि नहीं है; यह निष्पक्षता का मामला हो सकता है। यदि कोई प्रणाली दो बहुत समान व्यक्तियों के साथ केवल इसलिए अलग तरह से व्यवहार करती है क्योंकि पूरे वृक्ष के निर्माण का तरीका ऐसा था, तो यह व्यक्तिगत निष्पक्षता के एक मूल सिद्धांत का उल्लंघन करती है: कि समान व्यक्तियों के साथ समान व्यवहार किया जाना चाहिए।

भारतीय प्रौद्योगिकी संस्थान, गांधीनगर के शोधकर्ताओं की एक टीम ने डेटा के एक वृक्ष की वैश्विक संरचना और व्यक्तिगत बिंदुओं की स्थानीय निष्पक्षता के बीच इस तनाव की जांच करने का निर्णय लिया। उन्होंने एक मौलिक प्रश्न पूछा: क्या एक ऐसा पदानुक्रमित वृक्ष बनाना संभव है जो पड़ोसियों की स्वाभाविक निकटता का सम्मान करे बिना उनके संबंधों को बहुत अधिक खींचे या सिकोड़े? इसका उत्तर देने के लिए, उन्होंने इस समस्या को संभावना के परीक्षण के रूप में माना। उन्होंने केवल सबसे अच्छा वृक्ष बनाने का प्रयास नहीं किया; उन्होंने यह पूछा कि क्या एक ऐसा वृक्ष अस्तित्व में आ भी सकता है जो स्थानीय पड़ोसियों को एक उचित दूरी के भीतर रखते हुए एक वैध पदानुक्रम बनाता हो। उन्होंने पाया कि उत्तर विरूपण (distortion) के एक विशिष्ट थ्रेशोल्ड (सीमा) पर निर्भर करता है। यदि शोधकर्ता शून्य खिंचाव के साथ पूरी तरह से निष्पक्ष होने के लिए मजबूर करते, तो अक्सर वृक्ष बनाना ही असंभव हो जाता। गणित को काम करने के योग्य बनाने के लिए कुछ न्यूनतम "स्लैक" (slack), या अनुमत खिंचाव की आवश्यकता होती है।

शोधकर्ताओं ने पाया कि यह न्यूनतम खिंचाव एक यादृच्छिक संख्या नहीं है बल्कि डेटा की स्थानीय ज्यामिति द्वारा निर्धारित होता है। उन्होंने एक तीक्ष्ण सीमा (threshold) की पहचान की जो इस बात पर आधारित थी कि पड़ोसियों के बीच की दूरियां कितनी भिन्न होती हैं। यदि किसी एकल बिंदु के पड़ोसी एक-दूसरे से बहुत अलग दूरियों पर हैं, तो उन्हें सभी के साथ निष्पक्ष रूप से समायोजित करने के लिए वृक्ष को अधिक खिंचाव की आवश्यकता होती है। उन्होंने सिद्ध किया कि यदि आप इस विशिष्ट सीमा से कम खिंचाव के साथ एक वृक्ष बनाने का प्रयास करते हैं, तो कार्य गणितीय रूप से असंभव है। इसके अलावा, उन्होंने दिखाया कि यह सीमा स्थिर है; यदि डेटा थोड़ा बदलता है, तो आवश्यक खिंचाव भी केवल थोड़ा ही बदलता है, जिसका अर्थ है कि प्रणाली माप की छोटी त्रुटियों के प्रति सुदृढ़ है।

शायद सबसे आश्चर्यजनक खोज स्थानीय रूप से जो निष्पक्ष दिखता है और जो वैश्विक रूप से संभव है, उसके बीच का अंतर था। टीम ने विशिष्ट उदाहरणों का निर्माण किया जहाँ स्थानीय पड़ोस पूरी तरह से समान और सरल थे, जो सुझाव देते थे कि बिल्कुल भी खिंचाव की आवश्यकता नहीं होनी चाहिए। फिर भी, जब उन्होंने इन सरल स्थानीय समूहों के लिए पूर्ण वृक्ष बनाने का प्रयास किया, तो उन्होंने पाया कि अभी भी भारी मात्रा में खिंचाव की आवश्यकता थी। इन मामलों में, आवश्यक न्यूनतम खिंचाव वस्तुओं की कुल संख्या के लघुगणक (logarithm) के अनुपात में बढ़ गया। इसका अर्थ यह है कि भले ही प्रत्येक छोटा पड़ोस पूरी तरह से संतुलित दिखे, उन सभी पड़ोसों को एक एकल वृक्ष में जोड़ने की अत्यधिक जटिलता एक महत्वपूर्ण विरूपण पैदा करती है। यह खोज एक अंतर्निहित सीमा को प्रकट करती है: आप एक पदानुक्रमित संरचना में हमेशा एक पूर्णतः निष्पक्ष स्थानीय दृश्य और एक पूर्णतः सटीक वैश्विक दृश्य एक साथ नहीं रख सकते।

इन विचारों का परीक्षण करने के लिए, शोधकर्ताओं ने अपने द्वारा बनाए गए कृत्रिम डेटा और जनगणना आय रिकॉर्ड एवं क्रेडिट डेटा सहित वास्तविक दुनिया के डेटासेट पर अपने सिद्धांत को लागू किया। कृत्रिम परीक्षणों में, उन्होंने एक स्पष्ट टिपिंग पॉइंट (tipping point) देखा: अनुमत खिंचाव के एक निश्चित स्तर से नीचे, कोई वैध वृक्ष नहीं बनाया जा सकता था, लेकिन जैसे ही वे उस सीमा को पार करते, एक समाधान दिखाई देता। वास्तविक दुनिया के डेटा में, उन्होंने पाया कि जैसे-जैसे वे पड़ोसियों के थोड़े बड़े समूहों को देखते गए, आवश्यक खिंचाव अक्सर तेजी से स्थिर हो गया, जिससे पता चलता है कि वैश्विक कठिनाई छोटे पैमाने की ज्यामितीय विन्यास द्वारा निर्धारित होती है। उन्होंने अपने नए तरीके की तुलना पुराने, मानक तकनीकों से की, जो निर्माण प्रक्रिया के दौरान इन निष्पक्षता नियमों को लागू करता है। जबकि पुराने तरीकों ने विरूपण की एक सैद्धांतिक सीमा का वादा किया था, वे व्यवहार में बहुत बड़ी त्रुटियां उत्पन्न करते थे। इसके विपरीत, नया तरीका, जो डेटा की अपनी ज्यामिति द्वारा आवश्यक न्यूनतम संभव खिंचाव को प्राप्त करने में सक्षम था, यह सिद्ध करता है कि ऐसे वृक्ष बनाना संभव है जो पदानुक्रमित रूप से सुदृढ़ और स्थानीय रूप से निष्पक्ष दोनों हों, बशर्ते कि व्यक्ति आवश्यक, गणितीय रूप से परिभाषित विरूपण को स्वीकार करे।

यह कार्य निष्कर्ष निकालता है कि पदानुक्रमित क्लस्टरिंग में व्यक्तिगत निष्पक्षता केवल एक एल्गोरिदम को बदलने का मामला नहीं है, बल्कि यह डेटा का एक संरचनात्मक गुण है। स्थानीय समानताओं को संरक्षित करते हुए एक वैश्विक पदानुक्रम बनाने की एक कठोर सीमा है। शोधकर्ताओं ने मानचित्रित किया है कि वह सीमा कहाँ स्थित है, यह दिखाते हुए कि हालांकि हम विरूपण को पूरी तरह से समाप्त नहीं कर सकते, हम इसे काम करने के लिए आवश्यक सटीक न्यूनतम मात्रा की गणना कर सकते हैं। यह डेटा विश्लेषण में ट्रेड-ऑफ (समझौतों) को समझने का एक नया तरीका प्रदान करता है, यह सुनिश्चित करता है कि जब हम अपनी दुनिया को समझने के लिए इन जटिल वृक्षों का निर्माण करते हैं, तो हम व्यक्तिगत निष्पक्षता की लागत की स्पष्ट समझ के साथ ऐसा करें।

तकनीकी सारांश: पदानुक्रमित क्लस्टरिंग में व्यक्तिगत निष्पक्षता (Individual Fairness in Hierarchical Clustering)

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र शास्त्रीय पदानुक्रमित क्लस्टरिंग (hierarchical clustering) की एक मौलिक सीमा को संबोधित करता है: जबकि ये विधियाँ अल्ट्रामेट्रिक (ultrametrics) द्वारा परिभाषित मल्टी-रेज़ोल्यूशन प्रतिनिधित्व (डेंड्रोग्राम) उत्पन्न करती हैं, इनमें अक्सर व्यक्तिगत डेटा बिंदुओं के उपचार के संबंध में कोई गारंटी नहीं होती है। मानक दृष्टिकोण वैश्विक उद्देश्यों को अनुकूलित करते हैं या लालची लिंकेज नियमों (greedy linkage rules) का पालन करते हैं, जो स्थानीय समानताओं को इस तरह से विकृत कर सकते हैं जो विशिष्ट व्यक्तियों को असमान रूप से प्रभावित करता है। चूंकि पदानुक्रमित संरचनाएं ऊपर की ओर प्रसारित होती हैं, इसलिए स्थानीय पड़ोस में होने वाले शुरुआती विरूपण सभी मोटे स्तरों (coarser resolutions) को प्रभावित करते हैं।

लेखक पदानुक्रमित क्लस्टरिंग में व्यक्तिगत निष्पक्षता की समस्या को औपचारिक रूप देते हैं। मुख्य आवश्यकता यह है कि समान व्यक्तियों (मीट्रिक $d$ द्वारा परिभाषित) के साथ समान व्यवहार किया जाना चाहिए। विशेष रूप से, शोध पत्र इस बात की जांच करता है कि क्या ऐसा कोई अल्ट्रामेट्रिक प्रतिनिधित्व $u$ मौजूद है जो दो शर्तों को पूरा करता है:

प्रभुत्व (Domination): $u(i, j) \ge d(i, j)$ सभी युग्मों के लिए (कोई भी दूरी कम नहीं की जाती है)।
स्थानीय निष्पक्षता (Local Fairness): किसी भी बिंदु $i$ के $k$ -निकटतम पड़ोसी ( $k$ -NN) पड़ोस के भीतर, अल्ट्रामेट्रिक दूरी मूल मीट्रिक के सापेक्ष एक गुणक स्लैक (multiplicative slack) $\alpha$ (और योगात्मक स्लैक $\beta$ ) द्वारा सीमित है: $u(i, j) \le \alpha d(i, j) + \beta$ , सभी $j \in N_k(i)$ के लिए।

प्राथमिक उद्देश्य उस न्यूनतम गुणक स्लैक $\alpha^\star(d, k)$ को चरित्रित करना है जो ऐसे व्यवहार्य अल्ट्रामेट्रिक के अस्तित्व के लिए आवश्यक है।

2. कार्यप्रणाली और सैद्धांतिक ढांचा (Methodology and Theoretical Framework)

व्यवहार्यता परिदृश्य (Feasibility Landscape)

लेखक एक डोमिनेटेड अल्ट्रामेट्रिक खोजने की व्यवहार्यता का विश्लेषण करते हैं जो स्थानीय लिप्सचिट्ज़ (Lipschitz) बाधाओं का सम्मान करता है। वे आपसी (mutual) पड़ोस (जहाँ $j \in N_k(i)$ और $i \in N_k(j)$ ) और एकतरफा (one-sided) पड़ोस के बीच अंतर करते हैं।

प्रमुख सैद्धांतिक परिणाम (Key Theoretical Results)

स्थानीय आवश्यक स्लैक (उपपत्ति 1): लेखक एक स्थानीय विषमता अनुपात (local heterogeneity ratio), $\alpha^{\text{mut}}_k(d)$ को परिभाषित करते हैं, जो आपसी $k$ -निकटतम पड़ोसी सितारों के भीतर अधिकतम स्केल सेपरेशन को मापता है। वे सिद्ध करते हैं कि कोई भी व्यवहार्य गुणक स्लैक $\alpha$ इस शर्त को पूरा करना चाहिए कि $\alpha \ge \alpha^{\text{mut}}_k(d)$ । यह एक तीक्ष्ण स्थानीय सीमा स्थापित करता है; यदि स्लैक इस मान से नीचे है, तो निष्पक्षता गणितीय रूप से असंभव है।
स्थिरता (उपपत्ति 2): दिखाया गया है कि न्यूनतम स्लैक सीमा, $\ell_\infty$ वोंधित (bounded) विक्षोभों के तहत मीट्रिक के लिप्सचिट्ज़ स्थिर है, बशर्ते कि $k$ -निकटतम पड़ोसी की पहचान अपरिवर्तित रहे ( $\epsilon$ -स्थिर पड़ोस)।
रचनात्मक पर्याप्तता (उपपत्ति 3): शास्त्रीय ट्री-एम्बेडिंग सिद्धांत (विशेष रूप से [11] के परिणामों) का उपयोग करते हुए, लेखक सिद्ध करते हैं कि किसी भी $n$ -बिंदु मीट्रिक के लिए, $\alpha = O(\log n)$ स्लैक के साथ एक डोमिनेटिंग अल्ट्रामेट्रिक हमेशा मौजूद होता है। यह आवश्यक विरूपण (distortion) पर एक वैश्विक ऊपरी सीमा प्रदान करता है।
आंतरिक स्थानीय-वैश्विक अंतराल (प्रस्तावना 1): एक महत्वपूर्ण निष्कर्ष स्थानीय संरचना और वैश्विक व्यवहार्यता के बीच अलगाव है। लेखक मीट्रिक परिवारों (एक्सपैंडर ग्राफ पर आधारित) का निर्माण करते हैं जहाँ स्थानीय विषमता अनुपात मामूली ( $\alpha^{\text{mut}}_k(d) = 1$ ) है, फिर भी किसी भी डोमिनेटिंग अल्ट्रामेट्रिक के लिए $\Theta(\log n)$ विरूपण की आवश्यकता होती है। यह दर्शाता है कि स्थानीय निरंतरता वैश्विक व्यवहार्यता की गारंटी नहीं देती है।
एकदिष्टता (उपपत्ति 4): न्यूनतम व्यवहार्य स्लैक $\alpha^\star(d, k)$ , पड़ोस के आकार $k$ के संबंध में गैर-घटता (non-decreasing) है। स्थानीय निष्पक्षता बाधाओं को मजबूत करना (बढ़ता हुआ $k$ ) आवश्यक वैश्विक स्लैक को कम नहीं करता है।

एल्गोरिद्मिक दृष्टिकोण: FCAC

व्यवहार्य अल्ट्रामेट्रिक्स का निर्माण करने के लिए, शोध पत्र फेयरनेस कंस्ट्रेंड एग्लोमेरेटिव क्लस्टरिंग (FCAC) का प्रस्ताव करता है।

तंत्र (Mechanism): FCAC विलय चयन प्रक्रिया (merge selection process) के दौरान निष्पक्षता बाधाओं को लागू करके मानक एग्लोमेरेटिव क्लस्टरिंग को संशोधित करता है। यह लिंकेज स्कोर (जो विलय क्रम निर्धारित करता है) को विलय ऊंचाई असाइनमेंट (merge height assignment) से अलग करता है।
ऊंचाई असाइनमेंट (Height Assignment): विलय की ऊंचाई $h(A, B) = \max(\ell(A, B), \max_{i \in A, j \in B} d(i, j))$ के रूप में सेट की जाती है, जो यह सुनिश्चित करती है कि प्रभुत्व की स्थिति ( $u \ge d$ ) पूरी हो।
व्यवहार्यता जाँच (Feasibility Check): दो क्लस्टरों को मिलाने से पहले, एल्गोरिदम यह जाँचता है कि क्या प्रस्तावित ऊंचाई क्लस्टरों के बीच किसी भी पड़ोसी युग्म के लिए निष्पक्षता बाधा ( $h \le \alpha d(i, j) + \beta$ ) का उल्लंघन करती है।
जटिलता (Complexity): एल्गोरिदम वर्स्ट केस में $O(n^3 k)$ समय में चलता है। शोध पत्र नोट करता है कि अंतर्निहित व्यवहार्यता निर्णय समस्या की सटीक कम्प्यूटेशनल जटिलता निर्धारित करना एक खुला विषय बना हुआ है।

3. प्रयोगात्मक परिणाम (Experimental Results)

लेखक सिंथेटिक और वास्तविक दुनिया के डेटासेट (Gaussian mixtures, random 3-regular graphs, UCI Census Income, German Credit Data, और Iris) पर अपने सैद्धांतिक दावों को सत्यापित करते हैं।

व्यवहार्यता सीमाएँ (Feasibility Thresholds): Gaussian mixtures पर प्रयोग व्यवहार्यता में एक तीक्षूर्ण संक्रमण दिखाते हैं। न्यूनतम व्यवहार्य स्लैक $\alpha^\star$ स्थानीय आपसी सीमा (5.08) की तुलना में काफी अधिक (17.46) था, जो पुष्टि करता है कि स्थानीय निरंतरता वैश्विक विरूपण आवश्यकताओं को कम आंकती है।
स्थानीय-वैश्विक अंतराल: Random 3-regular graphs पर, स्थानीय अनुपात $\alpha^{\text{mut}}_k(d)$ 1 बना रहा, जबकि न्यूनतम व्यवहार्य स्लैक $\alpha^\star$ , $n$ के साथ बढ़ता गया, जो प्रस्तावना 1 द्वारा अनुमानित $\Theta(\log n)$ अंतराल को अनुभवजन्य रूप से प्रदर्शित करता है।
स्केलिंग व्यवहार:
- विषम डेटासेट (जैसे Adult) में, $\alpha^\star$ नमूना आकार $n$ के साथ काफी बढ़ गया, जिससे पता चलता है कि दुर्लभ स्थानीय ज्यामितीय उल्लंघन वैश्विक विरूपण को बढ़ाने के लिए संचित होते हैं।
- अधिक स्थिर डेटासेट (जैसे German Credit) में, $n$ के बढ़ने के बावजूद $\alpha^\star$ अपेक्षाकृत स्थिर रहा।
अवरोध संतृप्ति (Obstruction Saturation): यह देखा गया कि न्यूनतम स्लैक $\alpha^\star$ छोटे पड़ोस के आकार ( $k \approx 3$ ) पर संतृप्त हो जाता है, जो यह संकेत देता है कि वैश्विक अल्ट्रामेट्रिक अवरोध छोटे पैमाने की ज्यामितीय विन्यासों द्वारा निर्धारित होता है।
एल्गोरिद्मिक तुलना: Adult डेटासेट ( $n=800$ ) पर, FCAC (MST-आधारित) संस्करण ने 1.00 का स्लैक प्राप्त किया, जबकि FRT एम्बेडिंग (एक मानक ट्री एम्बेडिंग विधि) ने FRT के सैद्धांतिक $O(\log n)$ गारंटी के बावजूद, 67.26 का औसत स्लैक दिया। यह सुझाव देता है कि डेटा-जागरूक निर्माण (विशेष रूप से MST-आधारित संस्करण) सामान्य एम्बेडिंग सीमाओं की तुलना में काफी बेहतर प्रदर्शन कर सकता है।

4. महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि यह पदानुक्रमित क्लस्टरिंग में व्यक्तिगत निष्पक्षता का पहला संरचनात्मक व्यवहार्यता विश्लेषण प्रदान करता है। इसका महत्व यहाँ निहित है:

निष्पक्षता को नया रूप देना: वैश्विक उद्देश्यों को अनुकूलित करने के बजाय अल्ट्रामेट्रिक्स की कठोर ज्यामिति के भीतर स्थानीय निष्पक्षता बाधाओं की व्यवहार्यता को चरित्रित करने पर ध्यान केंद्रित करना।
आंतरिक लागत को मापना: यह स्थापित करना कि पदानुक्रमित प्रतिनिधित्व में निष्पक्षता की लागत स्वाभाविक रूप से मीट्रिक विरूपण से जुड़ी है, विशेष रूप से कुछ मीट्रिक परिवारों के लिए स्थानीय समानता और वैश्विक अल्ट्रामेट्रिक वास्तविकता के बीच एक अपरिहार्य $\Theta(\log n)$ अलगाव की पहचान करना।
एल्गोरिद्मिक योगदान: एक रचनात्मक एल्गोरिदम (FCAC) प्रदान करना जो इन बाधाओं को लागू करता है और अनुभवजन्य रूप से प्रदर्शित करता है कि डेटा-जागरूक विधियाँ (विशेष रूप से MST-आधारित संस्करण) सामान्य एम्बेडिंग तकनीकों की तुलना में लगभग इष्टतम स्लैक प्राप्त कर सकती हैं।

लेखक निष्कर्ष निकालते हैं कि जबकि स्थानीय स्थितियाँ आवश्यक हैं, वे वैश्विक व्यवहार्यता निर्धारित करने के लिए पर्याप्त नहीं हैं, और आवश्यक न्यूनतम स्लैक डेटा की ज्यामितीय संरचना का एक मौलिक गुण है। भविष्य के कार्य के रूप में व्यवहार्यता समस्या की कम्प्यूटेशनल जटिलता को चरित्रित करने और अन्य मल्टी-स्केल प्रतिनिधित्वों तक ढांचे का विस्तार करने का सुझाव दिया गया है।