📊 statistics

Randomizing the Number of Centers in k-means++

यह शोध पत्र प्रदर्शित करता है कि जबकि केंद्रों की एक निश्चित संख्या के लिए $k$ -means++ का सबसे खराब स्थिति वाला अपेक्षित सन्निकटन अनुपात (expected approximation ratio) $\Theta(\log k)$ है, यह एक स्थिर-गुणक सन्निकटन (constant-factor approximation) प्राप्त करता है जब केंद्रों की संख्या को एक सीमा से यादृच्छिक रूप से चुना जाता है, जिसके बाद डेटासेट को एक प्रतिपक्षी (adversary) द्वारा निर्धारित किया जाता है।

मूल लेखक: Vaclav Rozhon

प्रकाशित 2026-07-30

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

CC BY 4.0

मूल लेखक: Vaclav Rozhon

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

द ग्रेट डेटा स्क्रैम्बल: क्यों समूहों की संख्या का अनुमान लगाना सबसे अच्छी रणनीति हो सकती है

कल्पना कीजिए कि आप एक जासूस हैं जो शहर भर में बिखरे हुए हजारों सुरागों से जुड़े एक विशाल रहस्य को सुलझाने की कोशिश कर रहे हैं। आपका काम इन सुरागों को उनकी समानता के आधार पर अलग-अलग समूहों में वर्गीकृत करना है। शायद आप संदिग्धों को उनके अलबाई (alibi) के आधार पर समूहबद्ध कर रहे हैं, या लोगों में मौजूद तस्वीरों को व्यवस्थित कर रहे हैं। कंप्यूटर विज्ञान की दुनिया में, इसे क्लस्टरिंग (clustering) कहा जाता है, और इसे करने के लिए सबसे लोकप्रिय टूल k-means नामक एक एल्गोरिदम है। k-means में "k" उन समूहों की संख्या है जिन्हें आप बनाने का निर्णय लेते हैं। पेच यह है कि कंप्यूटर को प्रत्येक समूह के लिए एक "केंद्र" (center) चुनना होता है, और फिर यह उन केंद्रों को तब तक इधर-उधर घुमाता रहता है जब तक कि वे समूहों को सबसे अधिक अर्थपूर्ण न बना दें।

लेकिन यहाँ एक पेंच है: कंप्यूटर को शुरू करने से पहले यह जानने की आवश्यकता होती है कि कितने समूह बनाने हैं। यदि आप इसे वास्तव में 10 समूहों के बजाय 5 समूह बनाने के लिए कहते हैं, तो परिणाम एक अस्त-व्यस्त आपदा होगा। यदि आप इसे 5 के बजाय 20 कहते हैं, तो यह एकल समूहों को छोटे, बेकार टुकड़ों में विभाजित कर देगा। दशकों से, कंप्यूटर वैज्ञानिक एक विशिष्ट समस्या से जूझ रहे हैं: यदि आप समूहों की गलत संख्या चुनते हैं, तो एल्गोरिदम एक "लोकल ट्रैप" (स्थानीय जाल) में फंस सकता है, जिससे आपको एक ऐसा समाधान मिलता है जो ठीक तो है, लेकिन सर्वोत्तम संभव समाधान से बहुत दूर है। इस प्रक्रिया को शुरू करने का मानक तरीका, जिसे k-means++ कहा जाता है, आमतौर पर बहुत अच्छा होता है, लेकिन गणितीय रूप से, हम जानते थे कि यह कभी-कभी काफी अक्षम हो सकता है—विशेष रूप से, इसका प्रदर्शन समूहों की संख्या बढ़ने के साथ खराब हो सकता है, जो मोटे तौर पर उस संख्या के लघुगणक (logarithm) से संबंधित कारक द्वारा निर्धारित होता है। यह एक ऐसे जीपीएस (GPS) की तरह था जो अगले शहर की यात्रा के लिए तो बेहतरीन काम करता था, लेकिन अगर आप इसे पूरे देश की यात्रा की योजना बनाने के लिए कहते, तो यह पूरी तरह से खो जाता।

पेपर का बड़ा विचार: "शायद" की शक्ति

यह पेपर, जिसे वाक्लेव रोझोन (Václav Rozhoň) ने लिखा है, एक दिलचस्प सवाल पूछता है: क्या होगा अगर हम समूहों की सटीक संख्या का अनुमान लगाने की कोशिश करना छोड़ दें? क्या होगा अगर, कंप्यूटर को समूहों की एक निश्चित संख्या चुनने के लिए मजबूर करने के बजाय, हम इसे संभावनाओं की एक सीमा में से यादृच्छिक (random) रूप से एक संख्या चुनने दें?

लेखक एक छोटा सा प्रयोग सेट करते हैं। कल्पना कीजिए कि एक खलनायक (एक "एडवर्सरी") एक चालाकी भरा डेटासेट बनाता है और समूहों की एक लक्षित संख्या चुनता है, जिसे हम K कह सकते हैं। लेकिन एल्गोरिदम को ठीक K समूहों का उपयोग करने के लिए मजबूर करने के बजाय, नियम बदल जाते हैं। अब एल्गोरिदम को समूहों की एक संख्या k चुनने की अनुमति है, जो K और 2K-1 के बीच की सीमा में से पूरी तरह से यादृच्छिक रूप से चुनी गई है। यह जासूस को यह बताने जैसा है कि, "आपको इस रहस्य को सुलझाना है, लेकिन आप अपने सुरागों को 10 से 19 अलग-अलग फोल्डरों में व्यवस्थित कर सकते हैं। बस उस सीमा में से कोई भी एक संख्या चुनें और शुरू हो जाएं।"

पेपर कुछ आश्चर्यजनक और विरोधाभासी सिद्ध करता है: जब आप एल्गोरिदम को इस सीमा में से समूहों की एक यादृच्छिक संख्या चुनने की अनुमति देते हैं, तो यह वास्तव में बहुत, बहुत बेहतर हो जाता है।

पुरानी दुनिया में, जहाँ समूहों की संख्या निश्चित थी, एल्गोरिदम का सबसे खराब प्रदर्शन (worst-case performance) समूहों की संख्या के लघुगणक (जिसे Θ(log k) लिखा जाता है) के समानुपाती था। इसका मतलब है कि जैसे-जैसे समस्या बड़ी होती गई, एल्गोरिदम की दक्षता काफी कम हो सकती थी। हालाँकि, इस नए "स्मूथड" सेटअप में जहाँ समूहों की संख्या को रैंडमाइज किया गया है, पेपर यह सिद्ध करता है कि एल्गोरिदम एक O(1)-approximation बन जाता है, जिसकी संभावना एक स्थिर (constant) होती है।

आइए इसे एक रूपक से समझते। कल्पना कीजिए कि आप एक चलते हुए लक्ष्य पर डार्ट (dart) फेंकने की कोशिश कर रहे हैं। यदि आप एक विशिष्ट स्थान (निश्चित k) पर निशाना साधते हैं, तो लक्ष्य फिसलन भरा हो सकता है, और आप बहुत अधिक चूक सकते हैं। लेकिन यदि आपको एक विस्तृत, सुरक्षित क्षेत्र (सीमा K से 2K-1) के भीतर किसी भी स्थान पर डार्ट फेंकने की अनुमति दी जाती है, तो पेपर दिखाता है कि आपके एक "स्वीट स्पॉट" (सुंदर स्थान) पर हिट करने की बहुत अधिक संभावना है। विशेष रूप से, लेखक सिद्ध करते हैं कि उपलब्ध संख्याओं में से आधे से अधिक के लिए, एल्गोरिदम एक ऐसा समाधान खोज लेगा जो आदर्श उत्तर के एक स्थिर कारक के भीतर है। यह अब कोई लघुगणकीय अव्यवस्था नहीं है; यह एक विश्वसनीय, उच्च-गुणवत्ता वाला समाधान है।

उन्होंने इसे कैसे सिद्ध किया: "बर्बाद" हुए डार्ट्स

इस निष्कर्ष तक पहुँचने के लिए, इस प्रक्रिया को "क्लस्टर्स को कवर करने" के खेल के रूप में समझें। लक्ष्य डेटा बिंदुओं के हर छिपे हुए क्लस्टर के भीतर एक केंद्र (एक डार्ट) रखना है।

पेपर दो मुख्य परिदृश्यों का विश्लेषण करता है:

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

लेखक "वेस्टेड सेंटर्स" (wasted centers - बर्बाद हुए केंद्र) की एक अवधारणा पेश करते हैं। कल्पना कीजिए कि आप एक घर के विभिन्न कमरों को कवर करने के लिए डार्ट फेंक रहे हैं। यदि आप एक ऐसे कमरे में डार्ट फेंकते हैं जो पहले से ही कवर है, तो वह एक "बर्बाद" थ्रो है। पेपर गणितीय रूप से सिद्ध करता है कि जब आप समूहों की संख्या को रैंडमाइज करते हैं, तो इन "बर्बाद" थ्रो की संख्या इतनी कम रहती है कि एल्गोरिदम फिर भी एक बेहतरीन समाधान खोज लेता है। वे संभावित संख्याओं की सीमा को ब्लॉक्स में विभाजित करते हैं और दिखाते हैं कि प्रत्येक ब्लॉक के भीतर, एल्गोरिदम लगातार अच्छा प्रदर्शन करता है।

निष्कर्ष

पेपर केवल यह सुझाव नहीं देता कि यह काम कर सकता है; यह एक कठोर गणितीय प्रमाण प्रदान करता है। यह दिखाता है कि एक सार्वभौमिक स्थिरांक (constant) C मौजूद है, जिससे किसी भी डेटासेट और किसी भी शुरुआती संख्या K के लिए, उन संभव मानों के सेट में से आधे से अधिक (विशेष रूप से, K/2 से अधिक मान) के लिए, एल्गोरिदम कम से कम 50% संभावना के साथ सर्वोत्तम संभव उत्तर के उस स्थिरांक कारक C के भीतर सफल होता है।

यह दृष्टिकोण में एक महत्वपूर्ण बदलाव है। यह सुझाव देता है कि वास्तविक दुनिया में, जहाँ हम अक्सर यह नहीं जानते कि हमें समूहों की सटीक संख्या कितनी चाहिए, समूहों की संख्या को "रैंडमाइज" करने का कार्य भ्रम का संकेत नहीं है—बल्कि यह एक शक्तिशाली रणनीति है। समूहों के आकार की एक सीमा को स्वीकार करके, हम वास्तव में अपने एल्गोरिदम को अधिक मजबूत और कुशल बनाते हैं। पेपर निष्कर्ष निकालता है कि अधिकांश व्यावहारिक उद्देश्यों के लिए, यदि आप समूहों के आकार की एक सीमा को स्वीकार करने के लिए तैयार हैं, तो मानक k-means++ एल्गोरिदम केवल "ठीक" नहीं है, बल्कि वास्तव में एक बहुत मजबूत, निरंतर-कारक (constant-factor) परफॉर्मर है।

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

तकनीकी सारांश: k-means++ में केंद्रों की संख्या को रैंडमाइज करना

समस्या विवरण
$k$ -means क्लस्टरिंग समस्या एक डेटासेट $X \subset \mathbb{R}^d$ को $k$ केंद्रों $C$ में विभाजित करने का प्रयास करती है ताकि वर्ग दूरी के योग $\phi(X, C) = \sum_{x \in X} \min_{c \in C} \|x - c\|^2$ को न्यूनतम किया जा सके। मानक सीडिंग एल्गोरिदम, $k$ -means++ [AV07], वर्तमान लागत योगदान के अनुपात में प्रायिकता (D $^2$ -सैंपलिंग) के साथ केंद्रों को लालची (greedily) तरीके से चुनता है। हालांकि यह व्यापक रूप से उपयोग किया जाता है, एक निश्चित $k$ के लिए $k$ -means++ का वर्स्ट-केस अपेक्षित सन्निकटन अनुपात (expected approximation ratio) $\Theta(\log k)$ है, जो कि एक ज्ञात टाइट बाउंड है [AV07, BR13, BJA16]। मौजूदा लोअर बाउंड्स विशिष्ट उदाहरणों का निर्माण करते हैं जो एक निर्धारित $k$ के लिए कठिन हैं, लेकिन वे यह प्रदर्शित करने में विफल रहते हैं कि एक ही निश्चित उदाहरण पास के $k$ मानों की एक श्रेणी के लिए एक साथ कठिन हो सकता है।

कार्यप्रणाली और सेटअप
यह शोध पत्र एक "बजट-स्मूदनिंग" (budget-smoothed) विश्लेषण मॉडल पेश करता है। $k$ को प्रतिकूल रूप से (adversarially) फिक्स करने के बजाय, प्रयोग इस प्रकार आगे बढ़ता है:

एक एडवरसरी (adversary) डेटासेट $X$ और एक बेस पैरामीटर $K$ को फिक्स करता है।
$k$ को अंतराल $\{K, \dots, 2K-1\}$ से यूनिफॉर्मली रैंडम तरीके से चुना जाता है।
मानक $k$ -means++ एल्गोरिदम को $k$ चरणों के लिए चलाया जाता है।
लागत $ALG_k(X)$ की तुलना उस विशिष्ट $k$ के लिए $OPT_k(X)$ से की जाती है।

विश्लेषण दो प्राथमिक तकनीकी उपकरणों पर निर्भर करता है:

ओवरसैंपलिंग अंतर्ज्ञान (Oversampling Intuition): उन परिणामों का लाभ उठाना [ADK09, Wei16, MRS20] जो सुझाव देते हैं कि $k$ -सेंटर ऑप्टिमम के लिए अधिक (more) केंद्र सैंपल करने से बेहतर सन्निकटन प्राप्त हो सकता है।
ब्लॉक पार्टिशनिंग (Block Partitioning): लेखक संभव क्लस्टर गणनाओं की श्रेणी $\{K, \dots, 2K-1\}$ ${K, \dots, 2 K - 1}$ को ऐसे "ब्लॉक्स" में विभाजित करते हैं जहाँ अनुकूलतम लागत $OPT_t(X)$ $O P T_{t} (X)$ , ब्लॉक की शुरुआत में लागत के एक स्थिर कारक (constant factor) के भीतर रहती है। यह एल्गोरिदम को दो व्यवस्थाओं (regimes) में विश्लेषण करने की अनुमति देता है:
1. स्थिर व्यवस्था (Stable Regime): एक ब्लॉक के भीतर, अनुकूलतम लागत महत्वपूर्ण रूप से नहीं गिरती है। यहाँ, एल्गोरिदम को ओवरसैंपलिंग तर्कों का उपयोग करके विश्लेषित किया जाता है, जिसमें अतिरिक्त चरणों को लाभकारी ओवरसैंपलिंग के रूप में माना जाता है।
2. ड्रॉप व्यवस्था (Drop Regime): ब्लॉक्स के बीच, अनुकूलतम लागत महत्वपूर्ण रूप से गिर जाती है। यहाँ, विश्लेषण दिखाता है कि $k$ -means++ उच्च प्रायिकता के साथ नए अनुकूलतम क्लस्टर्स को "हिट" करेगा, जिससे "बर्बाद" केंद्रों (ऐसे केंद्र जो पहले से कवर किए गए क्लस्टर्स में लैंड करते हैं) के संचय को रोका जा सके।

मुख्य योगदान और परिणाम
यह शोध पत्र स्थापित करता है कि इस स्मूदनिंग सेटिंग में, $k$ -means++ एक स्थिर-कारक सन्निकटन (constant-factor approximation) प्राप्त करता है।

प्रमेय 1: एक सार्वभौमिक स्थिरांक $C$ मौजूद है जो प्रत्येक परिमित गैर-रिक्त डेटासेट $X$ और प्रत्येक $K \ge 1$ के लिए, एक उपसमुच्चय $G \subseteq \{K, \dots, 2K-1\}$ का अस्तित्व सुनिश्चित करता है जहाँ $|G| > K/2$ , ऐसा कि प्रत्येक $t \in G$ के लिए:
$P\left[ \frac{ALG_t(X)}{OPT_t(X)} \le C \right] \ge \frac{1}{2}$
जहाँ प्रायिकता एल्गोरिदम की रैंडमनेस पर आधारित है।

परिणामस्वरूप, $k$ के यूनिफॉर्म चॉइस पर औसत निकालने पर, एल्गोरिदम $1/4$ से अधिक संयुक्त प्रायिकता के साथ $C$ -सन्निकटन प्राप्त करता है।

तकनीकी विवरण:

बर्बाद केंद्र (Wasted Centers): लेखक एक "बर्बाद" केंद्र को एक ऐसे क्लस्टर में सैंपल किए गए केंद्र के रूप में परिभाषित करते हैं जो पिछले केंद्र द्वारा पहले से कवर किया गया है। वे $z_t = \sum_{i<t} \frac{OPT_t(X)}{OPT_i(X)}$ के सापेक्ष अपेक्षित बर्बाद केंद्रों $R_t$ को बाउंड करते हैं।
प्रायिकता बाउंड्स: कॉइन टॉस के साथ एक कपलिंग तर्क का उपयोग करते हुए, लेम्मा 5 दिखाता है कि $e$ अतिरिक्त सैंपल्स के बाद एल्गोरिदम की लागत $\Lambda \cdot OPT_q(X)$ से अधिक होने की प्रायिकता $O(\frac{z_q}{e+1} + \frac{1}{\Lambda})$ है।
डिटरमिनिस्टिक पार्टिशनिंग: लेम्मा 6 इंडेक्स को ब्लॉक्स में एक डिटरमिनिस्टिक विभाजन प्रदान करता है जहाँ अनुकूलतम लागतों का अनुपात सीमित होता है, यह सुनिश्चित करता है कि अधिकांश $t$ के लिए, "ओवरसैंपलिंग" दूरी $t-q$ , लागत अनुपात को पार करने के लिए पर्याप्त है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह परिणाम व्यावहारिक उपयोग के परिदृश्यों के अनुरूप है जहाँ $k$ का सटीक मान अक्सर अज्ञात या लचीला होता है, और लक्ष्य केवल डेटासेट को काफी छोटे संख्या में क्लस्टर्स में विभाजित करना होता है। $O(1)$ और $O(\log k)$ के बीच का अंतर गैर-तुच्छ (nontrivial) $k$ के लिए सबसे अधिक प्रासंगिक है, और लेखक तर्क देते हैं कि अधिकांश व्यावहारिक रेंज के लिए $k$ , एल्गोरिदम वर्स्ट-केस फिक्स्ड-बजट बाउंड की तुलना में काफी बेहतर प्रदर्शन करता है।

यह कार्य फिक्स्ड-बजट गारंटियों और स्मूदनिंग एनालिसिस के बीच के अंतर को पाटता है। शास्त्रीय स्मूदनिंग एनालिसिस के विपरीत जो इनपुट ज्योमेट्री को विचलित (perturb) करता है [ST04], यह दृष्टिकोण बजट पैरामीटर को स्मूथ करता है। यह सबमॉड्यूलर मैक्सिमाइजेशन [RZ22] में बजट-स्मूदनिंग एनालिसिस से भी संबंधित है।

सीमाएं और खुले प्रश्न
लेखक स्पष्ट रूप से कहते हैं कि यह परिणाम स्थिर प्रायिकता (constant probability) के साथ मान्य है, न कि अपेक्षा (expectation) के रूप में। यह एक खुला प्रश्न बना हुआ है कि क्या विश्लेषण को यह दिखाने के लिए विस्तारित किया जा सकता है कि अपेक्षित सन्निकटन अनुपात $E[\frac{ALG_k(X)}{OPT_k(X)}]$ $O(1)$ है, जहाँ अपेक्षा $k$ के चुनाव और एल्गोरिदम की रैंडमनेस दोनों पर ली गई है।

लेखक नोट करते हैं कि प्रमाण किसी एकल मान पर प्रायिकता के ऊपरी बाउंड के अलावा बजट वितरण की यूनिफॉर्मिटी पर निर्भर नहीं करता है; इसलिए, अन्य वितरणों (जैसे ज्यामितीय) के लिए भी समान गारंटी लागू होती है। प्रारंभिक $O(\log \log k)$ तर्क लेखक द्वारा विकसित किया गया था, जबकि अंतिम $O(1)$ परिणाम और प्रस्तुतिकरण में AI टूल्स (GPT-5.6 और Claude Opus 5) की सहायता ली गई थी। प्रमेय का एक Lean फॉर्मलाइजेशन एक सार्वजनिक रिपॉजिटरी में उपलब्ध है।

द ग्रेट डेटा स्क्रैम्बल: क्यों समूहों की संख्या का अनुमान लगाना सबसे अच्छी रणनीति हो सकती है

पेपर का बड़ा विचार: "शायद" की शक्ति

उन्होंने इसे कैसे सिद्ध किया: "बर्बाद" हुए डार्ट्स

निष्कर्ष

इसी तरह के और पेपर