के-मीन्स क्लस्टरिंग

के-मीन्स क्लस्टरिंग अवलोकनों को क्लस्टर सेंट्रोइड्स (cluster centroids) से दूरियों के कुल विदइन-क्लस्टर योग को न्यूनतम करके निश्चित संख्या में क्लस्टरों में विभाजित करता है।

Definition

के-मीन्स क्लस्टरिंग एक विभाजन विधि है जो निर्धारित संख्या में क्लस्टर केंद्र स्थापित करती है और प्रत्येक अवलोकन को उसके निकटतम केंद्र को असाइन करती है ताकि अवलोकनों से उनके असाइन किए गए केंद्रों तक कुल वर्ग यूक्लिडियन दूरी (Euclidean distance) को न्यूनतम किया जा सके।

Scope

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

Core questions

• विदइन-क्लस्टर फैलाव को न्यूनतम करने के लिए अवलोकनों को कैसे विभाजित किया जा सकता है?
• एल्गोरिथम केवल एक स्थानीय इष्टतम (local optimum) पर ही क्यों अभिसरित होता है और इसे कैसे कम किया जाता है?
• क्लस्टरों की संख्या का चुनाव कैसे किया जाता है?
• यह विधि अंतर्निहित रूप से किन क्लस्टर आकृतियों और पैमानों को मानती है?

Key theories

विदइन-क्लस्टर सम-ऑफ-स्क्वायर न्यूनीकरण

के-मीन्स बिंदुओं से उनके क्लस्टर केंद्रों तक कुल वर्ग दूरी को न्यूनतम करने वाले विभाजन और सेंट्रोइड्स के सेट की तलाश करता है, एक उद्देश्य जिसके लिए वैकल्पिक असाइनमेंट-अपडेट पुनरावृत्ति मानदंड को एकदिष्ट रूप से कम करती है।

स्थानीय-इष्टतम संवेदनशीलता

क्योंकि उद्देश्य गैर-उत्तल (non-convex) है, एल्गोरिथम एक स्थानीय न्यूनतम पर अभिसरित होता है जो प्रारंभिक केंद्रों पर निर्भर करता है, जो कई पुनरारंभों और सावधानीपूर्वक बीजारोपण (seeding) को प्रेरित करता है।

Clinical relevance

के-मीन्स बड़े डेटासेट को विभाजित करने के लिए एक तेज़, स्केलेबल डिफ़ॉल्ट है और इसका उपयोग वेक्टर क्वांटिज़ेशन (vector quantization), इमेज कलर रिडक्शन (image color reduction), ग्राहक विभाजन (customer segmentation) और अधिक जटिल मॉडलों के लिए एक आरंभीकरण के रूप में किया जाता है।

History

सेंट्रोइड-आधारित विभाजन के विचार को मैकक्वीन (MacQueen) ने औपचारिक रूप दिया, जिन्होंने 1967 में के-मीन्स का नामकरण किया, जो लॉयड (Lloyd) के पहले के क्वांटिज़ेशन एल्गोरिथम पर आधारित था। यह अपनी सरलता और गति के कारण सबसे व्यापक रूप से उपयोग की जाने वाली क्लस्टरिंग विधियों में से एक बन गया।

Debates

के-मीन्स की अंतर्निहित धारणाएँ

वर्ग यूक्लिडियन दूरी को न्यूनतम करना मोटे तौर पर गोलाकार, समान आकार के क्लस्टरों का पक्षधर है, इसलिए जब क्लस्टर लम्बे, असमान आकार के, या गैर-उत्तल होते हैं, तो के-मीन्स गुमराह कर सकता है, जो मॉडल-आधारित या घनत्व-आधारित विकल्पों को प्रेरित करता है।

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

के-मीन्स अलग-अलग रन पर अलग-अलग परिणाम क्यों देता है?

इसका उद्देश्य गैर-उत्तल है, इसलिए एल्गोरिथम एक स्थानीय इष्टतम पर अभिसरित होता है जो यादृच्छिक प्रारंभिक केंद्रों पर निर्भर करता है; इसे कई बार चलाना और सर्वोत्तम परिणाम रखना मानक अभ्यास है।

मैं क्लस्टरों की संख्या k कैसे चुनूँ?

सामान्य अनुमानी (heuristics) में विदइन-क्लस्टर सम-ऑफ-स्क्वायर में एल्बो (elbow), गैप स्टैटिस्टिक (gap statistic), और औसत सिल्हूट चौड़ाई (average silhouette width) शामिल हैं, हालांकि कोई भी निश्चित नहीं है और डोमेन ज्ञान अक्सर चुनाव का मार्गदर्शन करता है।