K-means क्लस्टरिंग वेक्टर क्वांटीकरण की एक विधि है, जो मूल रूप से सिग्नल प्रोसेसिंग से आती है, जो n अवलोकनों को k क्लस्टरों में विभाजित करती है, जहाँ प्रत्येक अवलोकन निकटतम माध्य (क्लस्टर केंद्र या सेंट्रॉइड) वाले क्लस्टर से संबंधित होता है। इसके परिणामस्वरूप डेटा स्थान का वोरोनोई कोशिकाओं में विभाजन होता है। यह एल्गोरिथ्म मशीन लर्निंग में अनपर्यवेक्षित डेटा विश्लेषण के लिए व्यापक रूप से उपयोग किया जाता है, जैसे ग्राहक विभाजन, छवि संपीड़न, और पैटर्न पहचान।
K-means क्लस्टर के भीतर विचरण को न्यूनतम करता है, जिसे वर्गित यूक्लिडियन दूरियों द्वारा मापा जाता है, लेकिन नियमित यूक्लिडियन दूरियों द्वारा नहीं, जो अधिक कठिन वेबर समस्या होगी। माध्य वर्गित त्रुटियों को अनुकूलित करता है, जबकि केवल ज्यामितीय माध्यिका यूक्लिडियन दूरियों को न्यूनतम करती है। उदाहरण के लिए, बेहतर यूक्लिडियन समाधान k-मेडियन्स और k-मेडॉइड्स का उपयोग करके पाए जा सकते हैं।
यह समस्या कम्प्यूटेशनल रूप से कठिन (NP-हार्ड) है; हालाँकि, कुशल अनुमानी एल्गोरिदम स्थानीय इष्टतम पर तेज़ी से अभिसरण करते हैं। ये आमतौर पर गाऊसी वितरणों के मिश्रणों के लिए अपेक्षा-अधिकतमीकरण एल्गोरिदम के समान होते हैं, जो k-means और गाऊसी मिश्रण मॉडलिंग दोनों द्वारा नियोजित पुनरावृत्त परिशोधन दृष्टिकोण के माध्यम से होते हैं। दोनों डेटा को मॉडल करने के लिए क्लस्टर केंद्रों का उपयोग करते हैं; हालाँकि, k-means क्लस्टरिंग तुलनीय स्थानिक सीमा के क्लस्टर खोजने की प्रवृत्ति रखती है, जबकि गाऊसी मिश्रण मॉडल क्लस्टरों को अलग-अलग आकार रखने की अनुमति देता है।
अनपर्यवेक्षित k-means एल्गोरिदम का k-निकटतम पड़ोसी क्लासिफायर के साथ एक ढीला संबंध है, जो वर्गीकरण के लिए एक लोकप्रिय पर्यवेक्षित मशीन लर्निंग तकनीक है, जिसे अक्सर नाम के कारण k-means के साथ भ्रमित किया जाता है। k-means द्वारा प्राप्त क्लस्टर केंद्रों पर 1-निकटतम पड़ोसी क्लासिफायर लागू करने से नए डेटा को मौजूदा क्लस्टरों में वर्गीकृत किया जाता है, जिसे निकटतम सेंट्रॉइड क्लासिफायर या रोक्कियो एल्गोरिदम के रूप में जाना जाता है।
औपचारिक परिभाषा
अवलोकनों का एक समुच्चय (x1, x2, ..., xn) दिया गया है, जहाँ प्रत्येक अवलोकन एक d-आयामी वास्तविक सदिश है, k-means क्लस्टरिंग का उद्देश्य n अवलोकनों को k (≤ n) समुच्चयों S = {S1, S2, ..., Sk} में विभाजित करना है ताकि क्लस्टर के भीतर वर्गों का योग (WCSS), यानी विचरण, न्यूनतम हो। औपचारिक रूप से, उद्देश्य निम्नलिखित खोजना है:
S पर argmin, i=1 से k तक के योग का, Si में x के लिए ||x - μi||^2 का योग,
जहाँ μi, Si में बिंदुओं का माध्य (जिसे सेंट्रॉइड भी कहा जाता है) है, और ||·|| सामान्य L2 मानदंड है। यह समान क्लस्टर में बिंदुओं के जोड़ीवार वर्गित विचलनों को न्यूनतम करने के बराबर है, जैसा कि पहचान द्वारा दिखाया गया है कि माध्य से वर्गित दूरियों का योग औसत जोड़ीवार वर्गित दूरी के बराबर है।
एल्गोरिदम
सबसे सामान्य एल्गोरिदम, जिसे अक्सर लॉयड का एल्गोरिदम कहा जाता है, एक पुनरावृत्त परिशोधन दृष्टिकोण का उपयोग करता है। यह k सेंट्रॉइड के प्रारंभिक समुच्चय से शुरू होता है, फिर दो चरणों के बीच वैकल्पिक होता है: असाइनमेंट और अपडेट। असाइनमेंट चरण में, प्रत्येक अवलोकन को उस क्लस्टर को सौंपा जाता है जिसका सेंट्रॉइड निकटतम होता है, आमतौर पर यूक्लिडियन दूरी का उपयोग करके। अपडेट चरण में, प्रत्येक क्लस्टर के सेंट्रॉइड को असाइन किए गए बिंदुओं के माध्य के रूप में पुनर्गणना किया जाता है। ये चरण तब तक दोहराए जाते हैं जब तक असाइनमेंट नहीं बदलते, जो स्थानीय इष्टतम पर अभिसरण का संकेत देता है।
आरंभीकरण महत्वपूर्ण है; k-means++ विधि, जो प्रारंभिक सेंट्रॉइड को फैलाती है, अंतिम क्लस्टरिंग की गुणवत्ता में सुधार के लिए एक लोकप्रिय अनुमानी है। एल्गोरिदम k की पसंद के प्रति संवेदनशील है, और एल्बो विधि या सिल्हूट विश्लेषण जैसी विधियों का उपयोग क्लस्टरों की उपयुक्त संख्या का अनुमान लगाने के लिए किया जाता है।
गुण और सीमाएँ
K-means मानता है कि क्लस्टर गोलाकार और समान आकार के हैं, जो जटिल क्लस्टर आकार वाले डेटा के लिए इसकी प्रयोज्यता को सीमित करता है। यह आउटलायर्स के प्रति भी संवेदनशील है, क्योंकि माध्य चरम मूल्यों से प्रभावित होता है। एल्गोरिदम एक स्थानीय इष्टतम पर अभिसरण करता है, जरूरी नहीं कि वैश्विक एक पर, और विभिन्न आरंभीकरण अलग-अलग परिणाम दे सकते हैं। इन सीमाओं के बावजूद, इसकी सरलता और मापनीयता इसे बड़े डेटासेट के लिए एक लोकप्रिय विकल्प बनाती है, विशेष रूप से डेटा संवर्धन और प्रीप्रोसेसिंग पाइपलाइनों में।
अनुप्रयोग
K-means विभिन्न डोमेन में उपयोग किया जाता है। कृत्रिम बुद्धिमत्ता में, यह क्लस्टरिंग कार्यों के लिए एक आधार रेखा के रूप में कार्य करता है। कंप्यूटर विज़न में, इसका उपयोग छवि विभाजन और रंग क्वांटीकरण के लिए किया जाता है। विपणन में, यह खरीद व्यवहार के आधार पर ग्राहकों को विभाजित करने में मदद करता है। प्राकृतिक भाषा प्रसंस्करण में, यह दस्तावेज़ों या शब्द एम्बेडिंग को क्लस्टर कर सकता है। एल्गोरिदम अधिक उन्नत तकनीकों के लिए एक निर्माण खंड भी है, जैसे गहन शिक्षण फीचर लर्निंग और Generative AI मॉडल।
अन्य विधियों से संबंध
K-means गाऊसी मिश्रण मॉडल (GMM) से संबंधित है, क्योंकि दोनों पुनरावृत्त परिशोधन और क्लस्टर केंद्रों का उपयोग करते हैं। हालाँकि, GMM क्लस्टरों को अलग-अलग आकार और सहप्रसरण रखने की अनुमति देता है, जबकि k-means आइसोट्रोपिक क्लस्टर मानता है। k-means से व्युत्पन्न निकटतम सेंट्रॉइड क्लासिफायर, एक सरल पर्यवेक्षित वर्गीकरण विधि है। K-means अक्सर k-निकटतम पड़ोसियों (k-NN) के साथ भ्रमित होता है, लेकिन वे अलग हैं: k-means अनपर्यवेक्षित है, जबकि k-NN पर्यवेक्षित है।
इतिहास और विकास
K-means की अवधारणा पहली बार 1956 में ह्यूगो स्टीनहॉस द्वारा प्रस्तावित की गई थी, और "k-means" शब्द 1967 में जेम्स मैकक्वीन द्वारा गढ़ा गया था। लॉयड का एल्गोरिदम, 1957 में प्रकाशित लेकिन 1982 तक व्यापक रूप से ज्ञात नहीं था, मानक कार्यान्वयन है। वर्षों से, कई प्रकार विकसित किए गए हैं, जैसे बड़े पैमाने पर डेटा के लिए मिनी-बैच k-means और सॉफ्ट क्लस्टरिंग के लिए फज़ी c-means।