📊 statistics

Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

यह शोध पत्र डेप्थ-बेस्ड लोकल सेंटर क्लस्टरिंग (DLCC) का प्रस्ताव करता है, जो एक लचीला ढांचा है जो बहुविध (multimodal) और गैर-उत्तल (non-convex) डेटा संरचनाओं को संभालने में पारंपरिक विधियों की सीमाओं को संबोधित करने के लिए केंद्रों की पहचान करने और विभिन्न आकारों के क्लस्टर बनाने के लिए स्थानीय डेटा डेप्थ का उपयोग करता है।

मूल लेखक: Siyi Wang, Alexandre Leblanc, Paul D. McNicholas

प्रकाशित 2026-01-22

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

CC BY 4.0

मूल लेखक: Siyi Wang, Alexandre Leblanc, Paul D. McNicholas

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

कल्पना कीजिए कि आपके पास रंग-बिरंगी कंचों (marbles) का एक विशाल डिब्बा है जो आपस में मिल गए हैं। कुछ लाल हैं, कुछ नीले हैं, कुछ हरे हैं, और वे हर तरह के पैटर्न में बिखरे हुए हैं: कुछ बहुत घनी छोटी गेंदों की तरह हैं, कुछ लंबे घुमावदार साँपों की तरह हैं, और कुछ एक-दूसरे के बिल्कुल बगल में मिले हुए हैं। आपका काम उन कंचों को ढेर में छाँटना है जो इस आधार पर कि वे एक-दूसरे के साथ कैसे "जुड़े" हैं। इसे डेटा वैज्ञानिक क्लस्टरिंग (clustering) कहते हैं।

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

यह शोध पत्र एक नई, अधिक स्मार्ट छँटाई मशीन पेश करता है जिसे DLCC (डेप्थ-बेस्ड लोकल सेंटर क्लस्टरिंग) कहा जाता है। यह कैसे काम करती है, इसे सरल उपमाओं के माध्यम से समझते हैं:

1. "ग्लोबल" नियमों के साथ समस्या

अधिकांश पुराने तरीके पूरे डिब्बे को एक साथ देखते हैं और सभी पर एक ही नियम लागू करते हैं।

"केंद्र" की समस्या: कल्पना कीजिए कि आप एक डोनट का केंद्र ढूँढने की कोशिश कर रहे हैं। यदि आप केवल मध्य बिंदु देखते हैं, तो आप खाली छेद में पहुँच जाएँगे, न कि आटे (dough) पर। इसी तरह, यदि कोई क्लस्टर छल्ले (ring) के आकार का है, तो "केंद्र-आधारित" तरीका विफल हो जाता है।
"घनत्व" (Density) की समस्या: कल्पना कीजिए कि एक भीड़ है जहाँ कुछ लोग कंधे से कंधा मिलाकर खड़े हैं, और अन्य एक पार्क में फैले हुए हैं। एक तरीका जो केवल "भीड़भाड़" वाले स्थानों को देखता है, वह पार्क में फैले लोगों को पूरी तरह से मिस कर सकता है।

2. DLCC का समाधान: "स्थानीय पड़ोस" (Local Neighborhoods)

DLCC पूरे डिब्बे को एक साथ नहीं देखता। इसके बजाय, यह एक जासूस की तरह काम करता है जो डिब्बे के चारों ओर घूमता है और पूछता है, "तुम्हारे पड़ोसी कौन हैं?"

"दर्पण" वाली ट्रिक (डेटा डेप्थ): यह पता लगाने के लिए कि कौन सा केंद्र में है, DLCC एक चतुर ट्रिक का उपयोग करता है। कल्पना कीजिए कि आप एक कंचा चुनते हैं और उसके पीछे एक दर्पण रखते हैं। आप बाकी सभी कंचों के प्रतिबिंब को देखते हैं। यदि आपका कंचा प्रतिबिंब के बिल्कुल बीच में है, तो वह एक "गहरा" (deep) या "केंद्रीय" बिंदु है। यदि वह किनारे पर है, तो वह "उथला" (shallow) है।
स्थानीय केंद्र (Local Centers): DLCC अपने प्रत्येक छोटे पड़ोस के लिए यह प्रक्रिया करता है। यह पूछता है, "इस विशिष्ट छोटे समूह में, सबसे केंद्रीय कौन है?" इन केंद्रीय बिंदुओं को "स्थानीय केंद्र" (Local Centers) कहा जाता है।
- उपमा: एक शहर के बारे में सोचें। एक "ग्लोबल सेंटर" शहर हॉल हो सकता है। लेकिन एक "लोकल सेंटर" एक विशिष्ट मोहल्ले का सबसे लोकप्रिय कॉफी शॉप हो सकता है। DLCC कॉफी शॉप्स को ढूँढता है, न कि केवल शहर हॉल को।

3. कॉफी शॉप्स को समूहबद्ध करना

एक बार जब DLCC इन सभी स्थानीय "कॉफी शॉप्स" (Local Centers) को खोज लेता है, तो उसे उन्हें वास्तविक समूहों में व्यवस्थित करने की आवश्यकता होती है। यह दो अलग-अलग रणनीतियों का उपयोग करता है, जैसे पार्टी आयोजित करने के दो अलग-अलग तरीके:

"Min" रणनीति (एक रूढ़िवादी मेजबान): यह तब काम आती है जब समूह मोटे तौर पर एक ही आकार के हों और बहुत अधिक ओवरलैप न करते हों। यह उन कॉफी शॉप्स को समूह में डालती है जो एक-दूसरे के बहुत समान हैं। यह सख्त है और चीजों को व्यवस्थित रखती है।
"Max" रणनीति (डॉट-कनेक्ट-द-डॉट्स मेजबान): यह उन उलझी हुई स्थितियों के लिए है जहाँ समूह अजीब आकार के (जैसे साँप) होते हैं या बहुत अलग आकार के होते हैं। यह कॉफी शॉप्स को तब जोड़ता है जब उनके बीच समानता का कोई भी रास्ता मौजूद हो, भले ही वे दूर हों। यह उन घुमावदार साँप के आकार वाले क्लस्टर्स को खोजने की अनुमति देता है जिन्हें अन्य तरीके मिस कर देते हैं।

4. अंतिम सफाई

कभी-कभी, कॉफी शॉप्स को समूहबद्ध करने के बाद भी, कुछ कंचे बच जाते हैं जो पूरी तरह से फिट नहीं बैठते। DLCC केवल अनुमान नहीं लगाता। यह एक "वर्गीकरण" (classification) चरण का उपयोग करता है (एक स्मार्ट सहायक की तरह) जो सफलतापूर्वक छाँटे गए कंचों को देखता है और पूछता है, "अपने पड़ोसियों के आधार पर, तुम किस ढेर के सदस्य हो?"

यह विशेष क्यों है?

शोध पत्र का दावा है कि DLCC क्लस्टरिंग के लिए एक "स्विस आर्मी नाइफ" है।

यह आकारों को संभालता है: यह गोल ढेर, साँप के आकार के ढेर और छल्ले के आकार के ढेर को खोज सकता है।
यह आकार को संभालता है: यह 10 कंचों के ढेर और 10,000 कंचों के ढेर को एक साथ छाँट सकता है।
यह ओवरलैप को संभालता है: यह दो समूहों के बीच अंतर कर सकता है जो एक-दूसरे को छू रहे हैं।

कमी (सीमाएँ)

शोध पत्र अपनी सीमाओं के बारे में ईमानदार है:

यह गणनात्मक रूप से भारी है: क्योंकि इसे हर एक कंचे के "पड़ोस" की जाँच हर दूसरे कंचे के साथ करनी पड़ती है, इसलिए इसमें बहुत समय और कंप्यूटर पावर लगता है। यह हजारों के लिए बेहतरीन है, लेकिन अरबों के लिए संघर्ष कर सकता है।
इसे मानवीय स्पर्श की आवश्यकता है: आपको अभी भी मशीन को कुछ सेटिंग्स बतानी पड़ती है (जैसे कि एक "पड़ोस" कितना बड़ा होना चाहिए)। यह पूरी तरह से स्वचालित नहीं है।
"मैनिफ़ोल्ड" (Manifold) का मुद्दा: यदि डेटा एक बहुत ही पतले, मुड़ते हुए तार (3D स्पेस में 1D रेखा) जैसा है, तो "स्थानीय पड़ोस" का विचार भ्रमित हो सकता है, क्योंकि नज़दीक से देखने पर वह तार एक ठोस ब्लॉक जैसा लग सकता है।

सारांश

संक्षेप में, DLCC डेटा को छाँटने का एक नया तरीका है जो सब कुछ एक आदर्श वृत्त या एक आदर्श भीड़ में फिट करने की कोशिश करना छोड़ देता है। इसके बजाय, यह समूहों को बनाने के लिए "दिल" खोजने हेतु छोटे, स्थानीय पड़ोसों को देखता है। यह लचीला, मजबूत है और वास्तविक दुनिया के अव्यवस्थित डेटा पर अच्छी तरह काम करता है, हालांकि इसे सही सेटिंग्स प्राप्त करने के लिए थोड़ी कंप्यूटिंग शक्ति और मानवीय मार्गदर्शन की आवश्यकता होती है।

तकनीकी सारांश: डेप्थ-बेस्ड लोकल सेंटर क्लस्टरिंग (DLCC)

समस्या विवरण
क्लस्टर विश्लेषण डेटा विज्ञान का एक मौलिक हिस्सा है, फिर भी मौजूदा पद्धतियाँ अक्सर वास्तविक दुनिया के डेटा वितरणों की विविधता के साथ संघर्ष करती हैं। पारंपरिक दृष्टिकोण आम तौर पर दो श्रेणियों में आते हैं, जिनमें से प्रत्येक की विशिष्ट सीमाएँ हैं:

सेंटर-आधारित पद्धतियाँ (जैसे k-means) प्रत्येक क्लस्टर के लिए एक एकल प्रतिनिधि बिंदु और गोलाकार आकृतियों का अनुमान लगाती हैं, जो उन्हें आउटलेर्स (outliers) के प्रति संवेदनशील बनाती हैं और गैर-उत्तल (non-convex) ज्यामिति को मॉडल करने में विफल रहती हैं।
डेंसिटी-आधारित पद्धतियाँ (जैसे DBSCAN, Mean Shift) मनमाने आकार को संभाल सकती हैं, लेकिन वे डेंसिटी एस्टीमेशन या निश्चित थ्रेशोल्ड पर निर्भर करती हैं, जो उच्च-आयामी स्थानों में या भिन्न घनत्व वाले क्लस्टरों में अस्थिर हो सकती हैं।
ग्राफ-आधारित पद्धतियाँ अक्सर बड़े पैमाने के डेटा पर कम्प्यूटेशनल निषेधों का सामना करती हैं या दूरी मेट्रिक के चयन के प्रति संवेदनशील रहती हैं।

इन प्रतिमानों (paradigms) में एक मुख्य सीमा "एक्सेम्पलर" (exemplars - प्रतिनिधि बिंदु) की परिभाषा है। अधिकांश पद्धतियाँ एक्सेम्पलर्स को दूरी या डेंसिटी मानदंडों से जोड़ती हैं जो विभिन्न आयामीताओं और ज्यामितिओं में सामान्य नहीं हो सकते हैं। इसके अलावा, जबकि सांख्यिकीय डेटा डेप्थ (statistical data depth) बहुभिन्नरूपी डेटा (multivariate data) के लिए एक मजबूत, केंद्र-से-बाहर का क्रम प्रदान करती है, ऐतिहासिक रूप से इसका उपयोग केवल एक सहायक उपकरण (जैसे कि इनिशियलाइजेशन के लिए) के रूप में किया गया है, न कि स्थानीय संरचना और मल्टीमोडैलिटी की पहचान करने वाले प्राथमिक तंत्र के रूप में। मानक डेप्थ फंक्शन सीधे मल्टीमोडल विशेषताओं को कैप्चर करने में विफल रहते हैं।

कार्यप्रणाली: DLCC फ्रेमवर्क
यह शोध पत्र डेप्थ-बेस्ड लोकल सेंटर क्लस्टरिंग (DLCC) का प्रस्ताव करता है, एक ऐसा फ्रेमवर्क जो ग्लोबल डिस्टेंस मेट्रिक्स या डेंसिटी एस्टीमेट्स पर निर्भर रहने के बजाय, स्थानीय केंद्रों को परिभाषित करने और समानता उपायों (similarity measures) का निर्माण करने के लिए सांख्यिकीय डेटा डेप्थ का लाभ उठाता है।

डेप्थ-आधारित समानता मैट्रिक्स (Depth-Based Similarity Matrix):
यूक्लिडियन दूरी के बजाय, DLCC स्पेशियल डेप्थ (Spatial Depth - SD) पर आधारित एक समानता मैट्रिक्स $S$ का निर्माण करता है। डेप्थ की अवधारणा को स्थानीय बनाने के लिए, विधि प्रत्येक अवलोकन $x_i$ के लिए एक रिफ्लेक्टेड डेटासेट $X_{Ri}$ को परिभाषित करती है, जिसमें मूल सैंपल $X$ और $x_i$ के माध्यम से सभी बिंदुओं का प्रतिबिंब शामिल है। चूंकि $x_i$ के लिए $X_{Ri}$ समरूपता का केंद्र है, इसकी डेप्थ अधिकतम (1) है। $X_{Ri}$ के सापेक्ष किसी अन्य बिंदु $x_j$ की डेप्थ, जिसे $D(x_j | X_{Ri})$ के रूप में दर्शाया गया है, $x_j$ और $x_i$ के बीच समानता के माप के रूप में कार्य करती है।

दक्षता: लेखकों ने इन डेप्थ्स को कुशलतापूर्वक गणना करने के लिए एक मैट्रिक्स-आधारित कार्यान्वयन पेश किया है, जो यूनिट वेक्टर सम और नॉर्म्स को प्रीकंप्यूट करके अनावश्यक गणनाओं को कम करता है, हालांकि सैद्धांतिक जटिलता $O(n^3)$ बनी रहती है।

स्थानीय केंद्र की पहचान (Local Center Identification):
प्रत्येक बिंदु $x_i$ के लिए, डेप्थ-आधारित समानता पर आधारित उसके $s-1$ निकटतम पड़ोसियों द्वारा एक आकार $s$ का पड़ोस $N_i$ परिभाषित किया जाता है। प्रत्येक पड़ोस के भीतर, उच्चतम स्थानीय रैंक (सबसे गहरा बिंदु) वाले बिंदु को एक लोकल सेंटर के रूप में पहचाना जाता है।

फिल्टरिंग: सभी स्थानीय केंद्र उपयोगी नहीं होते हैं। विधि दो मानदंडों के आधार पर उम्मीदवारों को फ़िल्टर करती है: (1) केंद्र को अपने पड़ोस के भीतर केंद्रीय होना चाहिए (रैंक $\le 2$ ), और (2) इसे विभिन्न पड़ोसों में बार-बार आना चाहिए (आवृत्ति $f > 1$ )। एक स्थिरता मानदंड, एवरेज नेबर-इंड्यूस्ड डेप्थ (AND), का उपयोग और अधिक मजबूत केंद्रों को चुनने के लिए किया जाता है।

ग्रुपिंग रणनीतियाँ (Grouping Strategies):
विभिन्न डेटा ज्यामिति को संभालने के लिए फिल्टर किए गए स्थानीय केंद्रों को दो अलग-अलग रणनीतियों का उपयोग करके समूहों में वर्गीकृत किया जाता है:

Min Strategy: केंद्रों को आपसी पड़ोस ओवरलैप के आधार पर रूढ़िवादी तरीके से समूहित करती है। यह संतुलित, अच्छी तरह से अलग किए गए, या ओवरलैपिंग उत्तल (convex) क्लस्टरों के लिए उपयुक्त है।
Max Strategy: केंद्रों को कनेक्टिविटी चेन्स के माध्यम से समूहित करती है जहाँ पड़ोस की समानता थ्रेशोल्ड $\delta$ से अधिक होती है। यह रणनीति गैर-उत्तल (non-convex) संरचनाओं और अत्यधिक असंतुलित क्लस्टर आकारों के लिए डिज़ाइन की गई है। इसमें "हर जगह गैर-उत्तल" क्षेत्रों (जैसे स्पाइरल) को अलग करने के लिए एक तंत्र शामिल है जो अलग-थलग पड़े स्थानीय केंद्रों की पहचान करता है।

क्लस्टर निर्माण और वर्गीकरण (Cluster Formation and Classification):
एक बार स्थानीय केंद्रों के समूह बन जाने के बाद, प्रत्येक समूह के अद्वितीय पड़ोसियों का उपयोग करके अस्थायी क्लस्टर (temporary clusters) बनाए जाते हैं। बिंदुओं को समूह के केंद्रों बनाम अन्य समूहों के प्रति उनकी समानता के आधार पर स्कोर दिया जाता है। अस्पष्ट या बिना असाइन किए गए बिंदुओं को फिर बिल्ट-इन क्लासिफायर (k-Nearest Neighbors या Random Forests) का उपयोग करके वर्गीकृत किया जाता है, जो अस्थायी क्लस्टर लेबल पर प्रशिक्षित होते हैं, जिससे अतिरिक्त हाइपरपैरामीटर ट्यूनिंग के बिना मजबूत असाइनमेंट सुनिश्चित होता है।

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

नवल फ्रेमवर्क: DLCC पहला ऐसा तरीका है जो एक्सेम्पलर पहचान और समानता निर्माण दोनों के मूल में डेटा डेप्थ को रखता है, जो सीधे मल्टीमोडैलिटी को संबोधित करता है।
कुशल गणना: पेपर स्पेशियल डेप्थ के तहत डेप्थ-आधारित समानता मैट्रिक्स बनाने के लिए एक मैट्रिक्स-आधारित कार्यान्वयन विकसित करता है, जो नेइव (naive) कार्यान्वयन की तुलना में गणना को काफी तेज करता है।
लचीली ग्रुपिंग: दोहरी-रणनीति (Min/Max) दृष्टिकोण फ्रेमवर्क को विभिन्न क्लस्टर आकारों (convex बनाम non-convex) और घनत्व वितरणों के अनुकूल होने की अनुमति देता है।
व्यापक मूल्यांकन: लेखक एक पूर्ण एंड-टू-एंड प्रक्रिया प्रदान करते हैं, जिसमें पैरामीटर चयन दिशानिर्देश (CVDD इंडेक्स और विज़ुअलाइज़ेशन का उपयोग करके) और व्यापक अनुभवजन्य मूल्यांकन शामिल हैं।

प्रायोगिक परिणाम
लेखकों ने 12 सिंथेटिक डेटासेट्स और 13 वास्तविक-विश्व बेंचमार्क (उच्च-आयामी इमेज और माइक्रोअरे डेटा सहित) पर DLCC का मूल्यांकन किया।

प्रदर्शन: DLCC ने 7 सिंथेटिक डेटासेट्स पर पूर्ण रिकवरी प्राप्त की और सभी वास्तविक-विश्व बेंचमार्क में लगातार शीर्ष तीन में स्थान बनाया। इसने LW-k-means, EKM, R-MDPC, और ACLR जैसे प्रतिस्पर्धियों की तुलना में गैर-उत्तल आकृतियों, बदलते घनत्व और क्लास इम्बैलेंस को संभालने में बेहतर प्रदर्शन किया।
सीमाएँ देखी गईं: यह विधि उन "मैनिफोल्ड-जैसे" (manifold-like) संरचनाओं के साथ संघर्ष करती है जहाँ स्थानीय पड़ोस स्वाभाविक रूप से गैर-उत्तल होते हैं (जैसे "Atom" डेटासेट और "Blend" में स्पाइरल संरचनाएं)। इन मामलों में, यह धारणा कि स्थानीय केंद्र लगभग उत्तल पड़ोस में स्थित होते हैं, विफल हो जाती है।
स्केलेबिलिटी: हालांकि $\sim 10^4$ अवलोकनों तक के डेटासेट्स के लिए प्रभावी है, समानता मैट्रिक्स के निर्माण की $O(n^3)$ जटिलता बहुत बड़े पैमाने के डेटा के लिए एक बाधा बनी हुई है।

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