K-Means क्लस्टरिंग वेक्टर क्वांटीकरण की एक विधि है, जो मूल रूप से सिग्नल प्रोसेसिंग से आती है, जो अवलोकनों के एक समूह को k क्लस्टरों में विभाजित करती है, जहाँ प्रत्येक अवलोकन निकटतम माध्य वाले क्लस्टर से संबंधित होता है, जिसे क्लस्टर सेंट्रोइड के रूप में जाना जाता है। इसके परिणामस्वरूप डेटा स्थान का वोरोनोई कोशिकाओं में विभाजन होता है। यह एल्गोरिथ्म मशीन लर्निंग में ग्राहक विभाजन, छवि संपीड़न और पैटर्न पहचान जैसे कार्यों के लिए व्यापक रूप से उपयोग किया जाता है, और यह कृत्रिम बुद्धिमत्ता और डेटा विश्लेषण में एक आधारभूत तकनीक है।
K-means का उद्देश्य विद-इन-क्लस्टर सम ऑफ स्क्वेयर्स (WCSS) को कम करना है, जो प्रत्येक बिंदु और उसके क्लस्टर सेंट्रोइड के बीच वर्गित यूक्लिडियन दूरियों का योग है। यह समान क्लस्टर के भीतर बिंदुओं के जोड़ीवार वर्गित विचलनों को कम करने के बराबर है। हालाँकि, k-means वर्गित यूक्लिडियन दूरियों को कम करता है, नियमित यूक्लिडियन दूरियों को नहीं; बाद वाले के लिए अधिक कठिन वेबर समस्या को हल करने की आवश्यकता होगी। यूक्लिडियन दूरी न्यूनीकरण के लिए, k-मेडियन्स या k-मेडॉइड्स जैसे विकल्प अधिक उपयुक्त हैं।
इष्टतम k-means क्लस्टरिंग खोजने की समस्या कम्प्यूटेशनल रूप से कठिन (NP-hard) है, लेकिन कुशल अनुमानी एल्गोरिथ्म स्थानीय इष्टतम पर तेज़ी से अभिसरण करते हैं। सबसे सामान्य दृष्टिकोण लॉयड का एल्गोरिथ्म है, जो पुनरावृत्त रूप से बिंदुओं को निकटतम सेंट्रोइड को सौंपता है और फिर सेंट्रोइड्स को निर्धारित बिंदुओं के माध्य में अद्यतन करता है। यह पुनरावृत्त शोधन गाऊसी मिश्रण मॉडल के लिए उपयोग किए जाने वाले अपेक्षा-अधिकतमीकरण एल्गोरिथ्म के समान है, लेकिन k-means तुलनीय स्थानिक विस्तार के क्लस्टर खोजने की प्रवृत्ति रखता है, जबकि गाऊसी मिश्रण विभिन्न आकारों की अनुमति देते हैं।
एल्गोरिथ्म और कार्यान्वयन
मानक k-means एल्गोरिथ्म k सेंट्रोइड्स के प्रारंभिक सेट से शुरू होता है, जिसे यादृच्छिक रूप से या अभिसरण में सुधार के लिए k-means++ जैसी विधियों का उपयोग करके चुना जा सकता है। एल्गोरिथ्म अभिसरण तक दो चरणों को दोहराता है: असाइनमेंट, जहाँ प्रत्येक अवलोकन को निकटतम सेंट्रोइड वाले क्लस्टर को सौंपा जाता है, और अद्यतन, जहाँ प्रत्येक सेंट्रोइड को उसके क्लस्टर के सभी बिंदुओं के माध्य के रूप में पुनर्गणना किया जाता है। अभिसरण आमतौर पर तब पहचाना जाता है जब असाइनमेंट अब नहीं बदलते हैं या जब WCSS सुधार एक सीमा से नीचे गिर जाता है।
कई प्रकार मौजूद हैं, जिनमें बड़े डेटासेट के लिए मिनी-बैच k-means और टेक्स्ट डेटा के लिए गोलाकार k-means शामिल हैं। k का चुनाव अक्सर एल्बो विधि, सिल्हूट विश्लेषण या गैप स्टैटिस्टिक का उपयोग करके निर्धारित किया जाता है। एल्गोरिथ्म की समय जटिलता लगभग O(nkd*i) है, जहाँ n अवलोकनों की संख्या है, d आयामीता है, और i पुनरावृत्तियों की संख्या है।
अन्य विधियों से संबंध
K-means एक अनुपयोगी (unsupervised) एल्गोरिथ्म है, जिसका अर्थ है कि इसे लेबल किए गए डेटा की आवश्यकता नहीं होती है। इसका k-निकटतम पड़ोसी (k-NN) क्लासिफायर के साथ एक ढीला संबंध है, जो एक पर्यवेक्षित तकनीक है। k-means द्वारा प्राप्त क्लस्टर केंद्रों पर 1-निकटतम पड़ोसी क्लासिफायर लागू करने से नए डेटा को मौजूदा क्लस्टरों में वर्गीकृत किया जाता है; इसे निकटतम सेंट्रोइड क्लासिफायर या रोक्कियो एल्गोरिथ्म के रूप में जाना जाता है। यह संबंध इस बात पर प्रकाश डालता है कि अनुपयोगी क्लस्टरिंग पर्यवेक्षित कार्यों का समर्थन कैसे कर सकती है।
K-means गाऊसी मिश्रण मॉडल (GMM) से भी संबंधित है। दोनों डेटा मॉडल करने के लिए क्लस्टर केंद्रों का उपयोग करते हैं, लेकिन GMM क्लस्टरों को विभिन्न आकार और आकार रखने की अनुमति देते हैं, जबकि k-means समान विचरण के गोलाकार क्लस्टर मानता है। परिणामस्वरूप, k-means सरल और तेज़ है लेकिन कम लचीला है।
अनुप्रयोग और सीमाएँ
K-means कई डोमेन में उपयोग किया जाता है। अमेज़न वेब सर्विसेज और गूगल क्लाउड में, यह उपयोगकर्ता व्यवहार का विश्लेषण करने और संसाधन आवंटन को अनुकूलित करने के लिए एक सामान्य उपकरण है। कंप्यूटर विज़न में, इसका उपयोग छवि विभाजन और रंग क्वांटीकरण के लिए किया जाता है। विपणन में, यह खरीद पैटर्न के आधार पर ग्राहकों को विभाजित करता है। यह एल्गोरिथ्म गहन शिक्षण फीचर निष्कर्षण और जनरेटिव एआई डेटा प्रीप्रोसेसिंग जैसी अधिक जटिल विधियों के लिए एक निर्माण खंड भी है।
हालाँकि, k-means की सीमाएँ हैं। इसके लिए क्लस्टरों की संख्या k को पहले से निर्दिष्ट करना आवश्यक है, जो हमेशा ज्ञात नहीं होती। यह प्रारंभिक सेंट्रोइड चयन के प्रति संवेदनशील है, हालाँकि k-means++ इसे कम करता है। यह मानता है कि क्लस्टर उत्तल और आइसोट्रोपिक हैं, जो वास्तविक दुनिया के डेटा के लिए सही नहीं हो सकता है। आउटलायर सेंट्रोइड्स को विकृत कर सकते हैं, और एल्गोरिथ्म स्थानीय इष्टतम पर अभिसरण कर सकता है। इन मुद्दों के बावजूद, इसकी सरलता और दक्षता इसे एक लोकप्रिय विकल्प बनाती है।
ऐतिहासिक संदर्भ और विकास
K-means एल्गोरिथ्म पहली बार 1956 में ह्यूगो स्टीनहॉस द्वारा प्रस्तावित किया गया था और बाद में 1957 में बेल लैब्स में स्टुअर्ट लॉयड द्वारा परिष्कृत किया गया (हालाँकि 1982 तक प्रकाशित नहीं हुआ)। "k-means" नाम 1967 में जेम्स मैकक्वीन द्वारा गढ़ा गया था। तब से, कई सुधार विकसित किए गए हैं, जिनमें बेहतर आरंभीकरण के लिए k-means++ और स्केलेबिलिटी के लिए मिनी-बैच प्रकार शामिल हैं। यह एल्गोरिथ्म मशीन लर्निंग पाठ्यक्रम में एक प्रमुख तत्व बना हुआ है और scikit-learn और TensorFlow जैसी प्रमुख लाइब्रेरीज़ में लागू किया गया है।