K-माध्यम क्लस्टरिंग

Not to be confused with k-निकटतम परस्पर एल्गोरिदम.

K-अर्थात समूह संचालन परिमाणीकरण की विधि है, जो मूल रूप से संकेत आगे बढ़ाना से है, जिसका उद्देश्य उपसमुच्चय N अवलोकनों को K समूहों में विभाजित करना है जिसमें प्रत्येक अवलोकन समूह (सांख्यिकी) से संबंधित हैI निकटतम माध्य (समूह केंद्र या समूह केन्द्रक) के साथ, समूह के प्रोटोटाइप के रूप में कार्य करता है। इसका परिणाम वोरोनोई कोशिकाओं में डेटा स्थान के विभाजन में होता है। k-अर्थात समूहिंग अंदर-समूह भिन्नता (यूक्लिडियन दूरियों को चुकता) को अल्प करता है, किन्तु नियमित यूक्लिडियन दूरियों को नहीं, जो कि अधिक कठिन वेबर समस्या होगी I माध्य चुकता त्रुटियों का अनुकूलन करता है, जबकि केवल ज्यामितीय माध्य यूक्लिडियन दूरी को अल्प करता है। उदाहरण के लिए, K-मीडियन समूहिंग k-मेडियंस एवं k-मेडोइड्स k-मेडॉयड्स का उपयोग करके उत्तम यूक्लिडियन समाधान संशोधित किये जा सकते हैं।

समस्या कम्प्यूटेशनल रूप से कठिन है (एनपी-कठोरता) चूंकि, कुशल अनुमानी एल्गोरिदम स्थानीय इष्टतम में परिवर्तित हो जाते हैं। ये सामान्यतः 'K-साधन' एवं 'गाऊसी मिश्रण प्रारूपो' दोनों द्वारा नियोजित पुनरावृत्त शोधन दृष्टिकोण के माध्यम से गॉसियन वितरण के मिश्रण प्रारूप के लिए अपेक्षा-अधिकतमकरण एल्गोरिथ्म के समान हैं। वे दोनों डेटा को प्रारूप करने के लिए समूह केंद्रों का उपयोग करते हैं; चूंकि, k - का अर्थ है समूहिंग तुलनीय स्थानिक सीमा के समूहों का शोध करने के लिए किया जाता है, जबकि गॉसियन मिश्रण प्रारूप समूह्स को अलग-अलग आकार देने की अनुमति देता है।

अनियंत्रित k-अर्थात एल्गोरिदम का k-निकटतम परस्पर से ढीला संबंध है, k-निकटतम परस्पर वर्गीकारक, के लिए लोकप्रिय पर्यवेक्षित यंत्र अधिगम प्रविधि है जिसे अक्सर के के साथ भ्रमित किया जाता है- अर्थात नाम के कारण। K द्वारा प्राप्त समूह केंद्रों में 1-निकटतम परस्पर वर्गीकारक को प्रारम्भ करने का अर्थात उपस्थित समूह में नए डेटा को वर्गीकृत करना है। इसे निकटतम केन्द्रक वर्गीकारक या रोक्चियो एल्गोरिथम के रूप में जाना जाता है।

विवरण

टिप्पणियों के उपसमुच्चय को देखते हुए (x₁, x₂, ..., x_n), जहां प्रत्येक अवलोकन डी-आयामी वास्तविक सदिश है, k-अर्थात समूहिंग का उद्देश्य nअवलोकनों को k (≤ n) समुच्चय 's' = {s में विभाजित करना है₁, s₂, ..., s_k} जिससे वर्गों के अंदर-समूह योग (WCSS) (अर्थात विचरण) को अल्प किया जा सके। औपचारिक रूप से इस उद्देश्य का शोध करना हैI

${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}$

जहां μ_iमें बिंदुओं का माध्य $S_{i}$ (जिसे केन्द्रक भी कहा जाता है) है , अर्थात <डिव वर्ग = केंद्र>${\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,$

$|S_{i}|$ का आकार $S_{i}$ है , एवं $\|\cdot \|$ सामान्य L² मानदंड (गणित) है|

यह समूह में बिंदुओं के जोड़ीदार वर्ग विचलन को अल्प करने के बराबर है

:

${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\,{\frac {1}{|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}$

समरूपता को सर्वसमिका से निकाला जा सकता है $|S_{i}|\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\frac {1}{2}}\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}$. चूंकि कुल भिन्नता स्थिर है, यह विभिन्न समूहों (वर्गों के मध्य-समूह योग, BCSS) में बिंदुओं के मध्य वर्ग विचलन के योग को अधिकतम करने के बराबर है। यह नियतात्मक संबंध प्रायिकता सिद्धांत में कुल विचरण के नियम से भी संबंधित है।

इतिहास

k-माध्यिका शब्द का प्रथम बार उपयोग जेम्स मैकक्वीन ने 1967 में किया था। चूँकि यह विचार 1956 में ह्यूगो स्टीनहॉस के पास वापस चला गया। मानक एल्गोरिथम प्रथम बार 1957 में बेल लैब्स के स्टुअर्ट लॉयड द्वारा पल्स कोड मॉडुलेशन के लिए प्रविधियों के रूप में प्रस्तावित किया गया था, चूँकि इसे 1982 तक जर्नल लेख के रूप में प्रकाशित नहीं किया गया था। 1965 में, एडवर्ड डब्ल्यू फोर्गी ने अनिवार्य रूप से विधि प्रकाशित की, यही कारण है कि इसे कभी-कभी लॉयड-फोर्गी एल्गोरिथम कहा जाता है।

एल्गोरिदम

मानक एल्गोरिदम (बेवकूफ के-साधन)

k-साधनों का अभिसरण

सबसे सरल एल्गोरिथ्म पुनरावृत्त शोधन प्रविधि का उपयोग करता है। इसकी सर्वव्यापकता के कारण, इसे प्रायः k-अर्थात एल्गोरिथम कहा जाता हैI इसे विशेष रूप से कंप्यूटर विज्ञान समुदाय में लॉयड्स एल्गोरिथम के रूप में भी जाना जाता है। इसे कभी-कभी भोली के-साधन के रूप में भी जाना जाता है I

कार्यभार चरण: प्रत्येक अवलोकन के समूह को निकटतम माध्य के साथ प्रस्तुत करता है। अल्प से अल्प वर्ग यूक्लिडियन दूरी के साथ। (गणितीय रूप से, इसका अर्थ है साधनों द्वारा उत्पन्न वोरोनोई आरेख के अनुसार अवलोकनों को विभाजित करना।)

$S_{i}^{(t)}=\left\{x_{p}:\left\|x_{p}-m_{i}^{(t)}\right\|^{2}\leq \left\|x_{p}-m_{j}^{(t)}\right\|^{2}\ \forall j,1\leq j\leq k\right\},$

जहां प्रत्येक $x_{p}$ ठीक को प्रदान किया गया है $S^{(t)}$, भले ही यह उनमें से दो या अधिक को सौंपा जा सकता है।

अद्यतन चरण: प्रत्येक समूह को अभिहस्तांकित किए गए अवलोकनों के लिए पुनर्गणना का अर्थ (केन्द्रक) होता है।

$m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}$

एल्गोरिथम अभिसरण तब होता है जब कार्यभार अब परिवर्तित नहीं होते हैं। इष्टतम का शोध करने के लिए एल्गोरिदम उत्तरदायी नहीं है। एल्गोरिथम को प्रायः दूरी के आधार पर निकटतम समूह में वस्तु अभिहस्तांकित करने के रूप में प्रस्तुत किया जाता है। (स्क्वायर) यूक्लिडियन दूरी के अतिरिक्त किसी भिन्न दूरी फ़ंक्शन का उपयोग करने से एल्गोरिथम को अभिसरण से बाधित किया जा सकता है। K-माध्यिका के विभिन्न संशोधन जैसे गोलाकार K-माध्यिका और K-मेडोइड्स को अन्य दूरी उपायों का उपयोग करने की अनुमति देने के लिए प्रस्तावित किया गया है।

आरंभीकरण की विधि

सामान्यतः उपयोग की जाने वाली आरंभीकरण विधियाँ और अनियमित विभाजन हैं। Forgy विधि यादृच्छिक रूप से डेटा समुच्चय से k अवलोकन का चयन करती है और प्रारंभिक साधनों के रूप में इनका उपयोग करती है। यादृच्छिक विभाजन विधि के पूर्व उचित रूप से प्रत्येक अवलोकन के लिए समूह प्रदान करती है और फिर अद्यतन चरण पर आगे बढ़ती है, इस प्रकार प्रारंभिक माध्य की गणना समूह के यादृच्छिक रूप से अभिहस्तांकित किए गए बिंदुओं के केन्द्रक के रूप में की जाती है। फोर्जी विधि प्रारंभिक साधनों को फैलाने की प्रवृत्ति रखती है, जबकि यादृच्छिक विभाजन उन सभी को डेटा समुच्चय के केंद्र के निकट रखता है। हैमरली एट अल के अनुसार, यादृच्छिक विभाजन विधि सामान्यतः एल्गोरिदम जैसे k-हार्मोनिक साधनों और k-साधनों के लिए उत्तम होती है। अपेक्षा अधिकतमकरण और मानक के-साधन एल्गोरिदम के लिए, प्रारंभिकरण की फोर्जी विधि उत्तम है। सेलेबी एट अल द्वारा व्यापक अध्ययन होता है। चूँकि, पाया गया कि फोर्जी, अनियमित विभाजन और मैक्सिमिन जैसे लोकप्रिय आरंभीकरण विधि प्रायः निकृष्ट प्रदर्शन करते हैं, जबकि ब्रैडली और फ़य्यद का दृष्टिकोण सर्वश्रेष्ठ समूह में निरंतर प्रदर्शन करता है और K-means++|k-means++ सामान्यतः उचित प्रदर्शन करता है।

• Demonstration of the standard algorithm
• 

  1. k प्रारंभिक साधन (इस स्थिति में k = 3) डेटा डोमेन (रंग में दिखाया गया) के अंदर यादृच्छिक रूप से उत्पन्न होते हैं।

• 

  2. k समूह प्रत्येक अवलोकन को निकटतम माध्य से जोड़कर बनाया जाता है। यहां के विभाजन माध्यम से उत्पन्न वोरोनोई आरेख का प्रतिनिधित्व करते हैं।

• 

  3. प्रत्येक k समूह का केन्द्रक नया माध्य बन जाता है।

• 

  4. अभिसरण होने तक चरण 2 और 3 दोहराए जाते हैं।

एल्गोरिथ्म वैश्विक इष्टतम के अभिसरण का आश्वासन नहीं देता है। परिणाम प्रारंभिक समूहों पर निर्भर हो सकता है। जैसा कि एल्गोरिथ्म सामान्यतः तीव्र होता है, इसे भिन्न-भिन्न प्रारंभिक स्थितियों के साथ कई बार चलाना साधारण विषय है। चूँकि, सबसे खराब स्थिति का प्रदर्शन मंद हो सकता है: विशेष रूप से निश्चित बिंदु समुच्चय, दो आयामों में भी, घातीय समय में अभिसरण करते हैं, अर्थात 2^Ω(n). ये बिंदु समुच्चय व्यवहार में उत्पन्न नहीं होते हैं: यह इस तथ्य से पुष्ट होता है कि k-माध्यिका का स्निग्ध विश्लेषण चलने का समय बहुपद है। <रेफरी नाम = आर्थर, डेविड; मंथे, बी.; रोगलिन, एच. 20092 >Arthur, David; Manthey, B.; Roeglin, H. (2009). "के-साधन में बहुपद स्निग्ध जटिलता है". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). arXiv:0904.1113.</ref>

कार्यभार चरण को स्वीकृ‍त अर्थ चरण कहा जाता है, जबकि अद्यतन चरण अधिकतमकरण चरण है, जो इस एल्गोरिथम को सामान्यीकृत स्वीकृ‍त अर्थ-अधिकतमकरण एल्गोरिथम का रूपांतर बनाता है।

कठिनाई

डी आयामों में अवलोकन के लिए k-साधन समूह समस्या का इष्टतम समाधान का शोध करना है।

• दो समूहों के लिए भी सामान्य यूक्लिडियन अंतरिक्ष (डी आयामों में) में NP कठिन होते है।
• NP-कठिन सामान्य संख्या में समूह के लिए विमान में भी,
• यदि k और d (आयाम) निश्चित हैं, तो समस्या का समय से निवारण किया जा सकता है। $O(n^{dk+1})$, जहां n समूह होने वाली संस्थाओं की संख्या है।

इस प्रकार, ऊपर दिए गए लॉयड के एल्गोरिथम जैसे विभिन्न अनुमानी एल्गोरिदम को सामान्यतः उपयोग किया जाता है।

लॉयड्स एल्गोरिथम (और अधिकांश रूपांतर) का बढनेवाला समय है। $O(nkdi)$, जहाँ:

• n डी-रंगात्मक सदिश की संख्या है (क्लस्टर किया जाना है)।
• कश्मीर समूहों की संख्या होती है।
• I अभिसरण तक आवश्यक पुनरावृत्तियों की संख्या होती है।

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

• सबसे निकृष्ट स्थिति में, लॉयड के एल्गोरिथ्म की आवश्यकता होती है। $i=2^{\Omega ({\sqrt {n}})}$ पुनरावृत्तियों, जिससे लॉयड के एल्गोरिथम की सबसे निकृष्ट स्थिति समय कठिन अधिबहुपद समय होता है।* लॉयड के K-माध्यिका एल्गोरिदम में बहुपद स्निग्ध बढनेवाला समय है। यह दिखाया गया है कि <रेफरी नाम = आर्थर, डेविड; मंथे, बी.; Roeglin, H. 20092 /> n बिंदुओं के इच्छानुकूल समुच्चय के लिए होता है। $[0,1]^{d}$, यदि प्रत्येक बिंदु माध्य के साथ सामान्य वितरण द्वारा स्वतंत्र रूप से चिंतित है 0 और विचरण $\sigma ^{2}$, अपेक्षित चलने का समय k-अर्थात एल्गोरिद्म परिबद्ध है $O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})$, जो बहुपद है। n, k, d और $1/\sigma$.
• साधारण स्थितियों के लिए उत्तम सीमाएँ सिद्ध होती हैं। उदाहरण के लिए, यह दिखाया गया है कि k- साधन एल्गोरिथम का चलने का समय सीमाबद्ध है। $O(dn^{4}M^{2})$ के लिए n पूर्णांक जाली में अंक $\{1,\dots ,M\}^{d}$.

रूपांतर

• Jenks प्राकृतिक टूटता अनुकूलन: K-माध्यिका यूनीवेट डेटा पर प्रारम्भ होता है
• K-माध्यिका समूह औसत के अतिरिक्त प्रत्येक आयाम में औसत का उपयोग करता है, और इस प्रकार अर्घ्य करता है $L_{1}$ मानदंड (टैक्सीकैब ज्यामिति)।
• K-माध्यिका (यह भी: माध्यिका के निकट विभाजन, पीएएम) माध्य के अतिरिक्त मेडॉइड का उपयोग करता है, और इस प्रकार इच्छानुकूल दूरी कार्यों के लिए दूरी का योग अल्प करता है।
• फ़ज़ी समूह फ़ज़ी C-माध्यिका समूह K-माध्यिका का नरम वर्जन है, जहाँ प्रत्येक डेटा पॉइंट में प्रत्येक समूह से संबंधित फ़ज़ी श्रेणी होती है।
• मिश्रण प्रारूप गॉसियन मिश्रण प्रारूप आश्वास-अधिकतमकरण एल्गोरिदम (ईएम एल्गोरिदम) के साथ प्रशिक्षित नियतात्मक कार्यभार के अतिरिक्त समूहों के लिए संभाव्य कार्यभार बनाए रखता है, और साधनों के अतिरिक्त बहुभिन्नरूपी गॉसियन वितरण करता है।
• K-means++|k-means++ प्रारंभिक केंद्रों का इस प्रकार चयन करता है जो WCSS उद्देश्य पर सिद्ध ऊपरी सीमा देता है।
• निस्पंदन एल्गोरिथ्म प्रत्येक k- साधन चरण को गति देने के लिए kd- ट्री का उपयोग करता है।
• कुछ विधियाँ त्रिभुज असमानता का उपयोग करके प्रत्येक k- साधन चरण को गति देने का प्रयास करती हैं।* समूहों के मध्य बिंदुओं का आदान-प्रदान करके स्थानीय से संरक्षण करते है।* गोलाकार k- साधन क्लस्टरिंग एल्गोरिथ्म शाब्दिक डेटा के लिए उपयुक्त है।
• पदानुक्रमित संस्करण जैसे द्विभाजित k- साधन, X-अर्थात समूह और G-अर्थात समूह पदानुक्रमित समूह, विभाजक समूह, और डेटा उपसमुच्चय में समूह की इष्टतम संख्या को स्वचालित रूप से निर्धारित करने का प्रयास भी कर सकता है।
• समूह विश्लेषण आंतरिक मूल्यांकन उपाय जैसे सिल्हूट (समूह) डेटा उपसमुच्चय में समूह की संख्या निर्धारित करने में सहायक हो सकते हैं।
• Minkowski भारित k-माध्यिका स्वचालित रूप से समूह विशिष्ट वैशिष्टय वेट की गणना करता है, सहज विचार का समर्थन करता है कि विशेषता में भिन्न-भिन्न सुविधाओं पर प्रासंगिकता की भिन्न-भिन्न उपाधि हो सकती है। इन भारों का उपयोग किसी दिए गए डेटा समुच्चय को स्तर करने के लिए भी किया जा सकता है, जिससे समूह की अपेक्षित संख्या में समूह वैधता सूचकांक को अनुकूलित करने की संभावना बढ़ जाती है।
• अल्प-दल k- साधन डेटा उपसमुच्चय के लिए अल्प दल प्रतिमान का उपयोग करके भिन्नता जो मेमोरी में योग्य नहीं होती है।
• ओत्सु की विधि

हार्टिगन-वोंग विधि

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

होने देना $\varphi (S_{j})$ की व्यक्तिगत वित्त हो $S_{j}$ द्वारा परिभाषित $\sum _{x\in S_{j}}(x-\mu _{j})^{2}$, साथ $\mu _{j}$ समूह का केंद्र होता है।

कार्यभार विधि: हार्टिगन और वोंग की विधि बिंदुओं को यादृच्छिक समूहों में विभाजित करके प्रारम्भ होती है $\{S_{j}\}_{j\in \{1,\cdots k\}}$।

अद्यतन चरण: आगामी यह निर्धारित करता है $n,m\in \{1,\ldots ,k\}$ और $x\in S_{n}$ जिसके लिए निम्नलिखित कार्य अधिकतम तक पहुँचता है।

$\Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\smallsetminus \{x\})-\varphi (S_{m}\cup \{x\})$

के लिए $x,n,m$ जो इस अधिकतम तक पहुँचे, $x$ समूहों से चलता है $S_{n}$ समूह को $S_{m}$निर्धारित करता है।

समाप्ति: एल्गोरिथम टर्मिनेट होता है $\Delta (m,n,x)$ सभी के लिए शून्य से अर्घ्य है $x,n,m$.

विभिन्न चाल स्वीकृति रणनीतियों का उपयोग किया जा सकता है। पूर्व-सुधार की रणनीति में, किसी भी सुधार के स्थानांतरण को प्रारम्भ किया जा सकता है, जबकि सर्वोत्तम-सुधार की रणनीति में, सभी संभव स्थानांतरणों का पुनरावृत्त रूप से परीक्षण किया जाता है और प्रत्येक पुनरावृत्ति पर केवल सर्वश्रेष्ठ को प्रारम्भ किया जाता है। पूर्व दृष्टिकोण गति का समर्थन करता है, दृष्टिकोण सामान्यतः अतिरिक्त कम्प्यूटेशनल समय के मूल्य पर समाधान की गुणवत्ता का पक्ष लेता है। कार्यक्रम $\Delta$ स्थानांतरण के परिणाम की गणना करने के लिए उपयोग किया जाता है, समानता का उपयोग करके भी कुशलतापूर्वक मूल्यांकन किया जा सकता है।

$\Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.$

वैश्विक अनुकूलन और मेटाह्यूरिस्टिक्स

शास्त्रीय k- साधन एल्गोरिथ्म एवं इसकी विविधताओं को

के रूप में परिभाषित न्यूनतम-योग-वर्ग समूह समस्या के केवल स्थानीय न्यूनतम में परिवर्तित करने के लिए जाना जाता है। ${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.$

कई अध्ययनों ने एल्गोरिथम के अभिसरण व्यवहार में सुधार करने एवं वैश्विक इष्टतम (या अल्प से अल्प, उत्तम गुणवत्ता के स्थानीय न्यूनतम) प्राप्त करने की संभावना को अधिकतम करने का प्रयत्न किया है। पूर्व अनुभागों में वर्णन किया गया था। आरंभीकरण एवं पुनः आरंभ करने की प्रविधि उत्तम समाधान का शोध करने के लिए विकल्प हैं। शाखा एवं बंधन एवं अर्ध निश्चित प्रोग्रामिंग पर आधारित वैश्विक अनुकूलन एल्गोरिदम ने 4,177 संस्थाओं एवं 20,531 सुविधाओं के साथ डेटासमुच्चय के लिए सिद्ध रूप से इष्टतम समाधान प्रस्तुत किए हैं। जैसा कि अपेक्षित था, उपजात अनुकूलन समस्या की NP-कठोरता के कारण, K-साधनों के लिए इष्टतम एल्गोरिदम का कम्प्यूटेशनल समय इस आकार से तीव्र गति से बढ़ता है। अन्य अनुमानों की गुणवत्ता का मूल्यांकन करने के लिए, अल्प एवं मध्यम स्तर के लिए इष्टतम समाधान अभी भी बेंचमार्क उपकरण के रूप में मूल्यवान हैं। नियंत्रित कम्प्यूटेशनल समय के अंदर उच्च-गुणवत्ता वाले स्थानीय मिनिमा का शोध करने के लिए, किन्तु इष्टतमता का कथन के बिना, अन्य कार्यों ने मेटाह्यूरिस्टिक्स एवं अन्य वैश्विक अनुकूलन प्रविधियों की जानकारी ज्ञात की है। उदाहरण के लिए, वृद्धिशील दृष्टिकोण एवं उत्तल अनुकूलन के आधार पर, यादृच्छिक आदान-प्रदान (अर्थात, पुनरावृत्त स्थानीय शोध), परिवर्तनशील परस्पर शोध एवं आनुवंशिक एल्गोरिदम। यह वास्तव में ज्ञात है कि न्यूनतम सम-वर्ग समूहिंक समस्या का उत्तम स्थानीय न्यूनतम का शोध करने से उच्च आयाम वाले वैशिष्टय अंतर में समूह संरचनाओं को पुनर्प्राप्त करने में विफलता एवं सफलता के मध्य अंतर हो सकता है।

उल्लेख

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

होते है।

K-माध्यिका आइरिस पूर्ण डेटा उपसमुच्चय के लिए समूह परिणाम और सूचकांक-संरचनाओं द्वारा समर्थित केडीडी-अनुप्रयोगों के विकास के लिए पर्यावरण का उपयोग करके वास्तविक प्रजातियों की कल्पना की गई। समूह साधनों को बड़े, अर्ध-पारदर्शी प्रतीकों का उपयोग करके चिह्नित किया जाता है।

k-अर्थ समूह के प्रति कृत्रिम डेटाउ उपसमुच्चय (माउस) पर ईएम समूह समान आकार के समूहों का उत्पादन करने के लिए K-साधन की प्रवृत्ति यहां निकृष्ट परिणामों की ओर ले जाती है, जबकि ईएम डेटा उपसमुच्चय में उपस्थित विभिन्न त्रिज्या वाले गॉसियन वितरण से लाभान्वित होता है।

K-माध्यिका की तीन प्रमुख विशेषताएं जो इसे कुशल बनाती हैं, प्रायः इसकी सबसे बड़ी अल्पियां मानी जाती हैं।

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

K- साधन की प्रमुख सीमा इसका समूह प्रारूप है। अवधारणा गोलाकार समूहों पर आधारित है जो वियोज्य हैं जिससे माध्य समूह केंद्र की ओर अभिसरण होता है। समूह समान आकार के होने की अपेक्षा है, जिससे निकटतम समूह केंद्र को कार्यभार सही कार्यभार हो। उदाहरण के लिए जब k- साधन को मान के साथ प्रारम्भ किया जाता है। $k=3$ प्रसिद्ध आइरिस फूल डेटा उपसमुच्चय पर, परिणाम प्रायः डेटा उपसमुच्चय में निहित तीन आइरिस (पौधे) प्रजातियों को भिन्न करने में विफल रहता है। साथ $k=2$, दो दृश्य समूहों (दो प्रजातियों वाला ) का शोध किया जायेगा, जबकि साथ में $k=3$ दो समूहों को दो समान भागों में विभाजित किया जाएगा। वास्तव में, $k=2$ डेटा उपसमुच्चय में 3 वर्ग होने के पश्चात, इस डेटा उपसमुच्चय के लिए अधिक उपयुक्त है। किसी भी अन्य समूह एल्गोरिदम के साथ, K-साधन परिणाम यह मानते हैं कि डेटा कुछ मानदंडों को पूर्ण करता है। यह कुछ डेटा उपसमुच्चय पर उचित कार्य करता है और दूसरों पर विफल रहता है।

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

अनुप्रयोग

k-means क्लस्टरिंग अपेक्षाकृत बड़े डेटा सेट पर लागू करना आसान है, खासकर जब ह्यूरिस्टिक्स जैसे कि लॉयड्स एल्गोरिथम का उपयोग करते हैं। इसे कई अन्य डोमेन के बीच बाजार विभाजन, कंप्यूटर दृष्टि और खगोल विज्ञान में सफलतापूर्वक उपयोग किया गया है। यह अक्सर अन्य एल्गोरिदम के लिए प्रीप्रोसेसिंग चरण के रूप में उपयोग किया जाता है, उदाहरण के लिए प्रारंभिक कॉन्फ़िगरेशन खोजने के लिए।

वेक्टर परिमाणीकरण

Main article: Vector quantization

दो-चैनल (चित्रण उद्देश्यों के लिए - केवल लाल और हरे रंग के चैनल) रंगीन छवि

के-मीन्स का उपयोग करके वोरोनोई कोशिकाओं में ऊपर की छवि में मौजूद रंगों का वेक्टर परिमाणीकरण

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

क्लस्टर विश्लेषण

Main article: Cluster analysis

समूह विश्लेषण में, k- साधन एल्गोरिथ्म का उपयोग इनपुट डेटा समुच्चय को k विभाजन (समूह) में विभाजित करने के लिए किया जा सकता है।

हालांकि, शुद्ध के-साधन एल्गोरिदम बहुत लचीला नहीं है, और जैसा कि सीमित उपयोग का है (सिवाय इसके कि जब ऊपर के रूप में वेक्टर क्वांटिज़ेशन वास्तव में वांछित उपयोग मामला है)। विशेष रूप से, पैरामीटर k को चुनना कठिन माना जाता है (जैसा कि ऊपर चर्चा की गई है) जब बाहरी बाधाओं द्वारा नहीं दिया जाता है। एक और सीमा यह है कि इसका उपयोग मनमाने दूरी के कार्यों या गैर-संख्यात्मक डेटा के साथ नहीं किया जा सकता है। इन उपयोग मामलों के लिए, कई अन्य एल्गोरिदम श्रेष्ठ हैं।

फीचर लर्निंग

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

अन्य एल्गोरिदम से संबंध

गॉसियन मिश्रण मॉडल

Main article: Gaussian mixture model

के-मीन्स क्लस्टरिंग के लिए धीमी मानक एल्गोरिथ्म, और इसके संबद्ध अपेक्षा-अधिकतमकरण एल्गोरिथ्म | अपेक्षा-अधिकतमकरण एल्गोरिथ्म, गॉसियन मिश्रण मॉडल का एक विशेष मामला है, विशेष रूप से, सीमित मामला जब सभी सहप्रसरणों को विकर्ण, समान और अपरिमेय होने के लिए तय किया जाता है छोटा अंतर। छोटे प्रसरणों के बजाय, कठिन गॉसियन मिश्रण मॉडलिंग के एक विशेष मामले में k-साधन क्लस्टरिंग की एक और तुल्यता दिखाने के लिए एक कठिन क्लस्टर असाइनमेंट का भी उपयोग किया जा सकता है। इसका मतलब यह नहीं है कि के-साधनों की गणना करने के लिए गॉसियन मिश्रण मॉडलिंग का उपयोग करना कुशल है, लेकिन सिर्फ एक सैद्धांतिक संबंध है, और गॉसियन मिश्रण मॉडलिंग को के-साधनों के सामान्यीकरण के रूप में व्याख्या किया जा सकता है; इसके विपरीत, कठिन डेटा पर गॉसियन मिश्रण मॉडलिंग के लिए शुरुआती बिंदुओं को खोजने के लिए k- साधन क्लस्टरिंग का उपयोग करने का सुझाव दिया गया है।

के-एसवीडी

Main article: के-एसवीडी

K- साधन एल्गोरिथ्म का एक अन्य सामान्यीकरण k-SVD एल्गोरिथ्म है, जो कोडबुक वैक्टर के विरल रैखिक संयोजन के रूप में डेटा बिंदुओं का अनुमान लगाता है। के-साधन 1 के वजन के साथ एकल कोडबुक वेक्टर का उपयोग करने के विशेष मामले से मेल खाता है।

प्रधान घटक विश्लेषण

Main article: Principal component analysis

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

माध्य पारी समूह

Main article: Mean shift

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

स्वतंत्र घटक विश्लेषण

Main article: Independent component analysis

विरलता मान्यताओं के अनुसार और जब इनपुट डेटा सफेदी परिवर्तन के साथ प्री-प्रोसेस किया जाता है, तो k-माध्यिका रैखिक स्वतंत्र घटक विश्लेषण (ICA) कार्य का समाधान प्रस्तुत करता है। यह विशेषता अधिगम के लिए K-माध्यिका के सफल अनुप्रयोग की व्याख्या करने में सहायता करता है।

द्विपक्षीय निस्पंदन

Main article: Bilateral filter

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

समान समस्याएं

समूह फ़ंक्शंस को अल्प करने वाली चुकता त्रुटि के उपसमुच्च में K- medoids | k-मेडोइड्स एल्गोरिथ्म भी सम्मिलित है, दृष्टिकोण जो प्रत्येक समूह के केंद्र बिंदु को वास्तविक बिंदुओं में होने के लिए विवश करता है, अर्थात, यह केन्द्रक के स्थान पर मेडोइड्स का उपयोग करता है।

सॉफ्टवेयर कार्यान्वयन

एल्गोरिथम के विभिन्न कार्यान्वयन प्रदर्शन अंतर प्रदर्शित करते हैं, परीक्षण डेटा उपसमुच्चय पर सबसे तीव्र 10 सेकंड में समाप्त होता है, सबसे मंद 25,988 सेकंड (~ 7 घंटे) लेता है।अंतर को कार्यान्वयन गुणवत्ता, भाषा और संकलक अंतर, विभिन्न समाप्ति मानदंड और स्थिर स्तर, और त्वरण के लिए अनुक्रमणिका के उपयोग के लिए उत्तरदायी ठहराया जा सकता है।

मुफ़्त सॉफ़्टवेयर/ओपन सोर्स

नि:शुल्क और ओपन-सोर्स सॉफ़्टवेयर के अनुसार निम्नलिखित कार्यान्वयन उपलब्ध हैं। सार्वजनिक रूप से उपलब्ध स्रोत कोड के साथ मुफ़्त सोर्स सॉफ़्टवेयर अनुज्ञाप‍त्र होते है।

• Accord.NET में k-माध्यिका, k-माध्यिका++ और k-modes के लिए C# कार्यान्वयन सम्मिलित हैं।
• ALGLIB में k-माध्यिका और k-माध्यिका ++ के लिए समानांतर C++ और C# कार्यान्वयन सम्मिलित हैं।
• एंड्रॉइड (ऑपरेटिंग प्रणाली)ओपन-सोर्स समुदाय में K-साधनों के लिए जावा कार्यान्वयन सम्मिलित है।
• क्राइमस्टैट दो स्थानिक के-माध्यिका एल्गोरिदम को प्रारम्भ करता है, जिनमें से उपयोगकर्ता को प्रारंभिक स्थानों को परिभाषित करने की अनुमति देता है।
• ईएलकेआई में के-माध्यिका (लॉयड और मैकक्वीन पुनरावृत्ति के साथ-साथ विभिन्न आरंभीकरण जैसे कि K-माध्यिका ++ आरंभीकरण) और विभिन्न अधिक उन्नत समूह एल्गोरिदम सम्मिलित हैं।
• मुस्कान में के-माध्यिका और कई अन्य एल्गोरिदम और परिणाम प्रत्योक्षकरण (जावा, कोटलिन और स्कैला के लिए) सम्मिलित हैं।
• जूलिया भाषा में जूलियास्टैट्स समूह में K-साधन कार्यान्वयन सम्मिलित है।
• KNIME में k-माध्यिका और k-medoids के लिए नोड होते हैं।
• Apache Mahout में MapReduce आधारित k-माध्यिका सम्मिलित है।
• mypack में K-साधनों का C ++ कार्यान्वयन सम्मिलित है।
• जीएनयू ऑक्टेव में के-माध्यिका सम्मिलित हैं।
• OpenCV में k- साधन कार्यान्वयन सम्मिलित है।
• ऑरेंज (सॉफ्टवेयर) में K-माध्यिका समूह के लिए घटक सम्मिलित है जिसमें K और समूह सिल्हूट स्कोरिंग का स्वत: चयन होता है।
• PSPP में k- साधन सम्मिलित हैं, QUICK CLUSTER कमांड डेटासेट पर k- साधन क्लस्टरिंग करता है।
• R (प्रोग्रामिंग भाषा) में तीन k-माध्यिका रूपांतर होते हैं।
• SciPy और scikit-learn में कई k- साधन कार्यान्वयन सम्मिलित हैं।
• Apache Spark MLlib वितरित k- साधन एल्गोरिथम प्रारम्भ करता है।
• टॉर्च (मशीन अधिगम) में अन-अप संकुल होता है जो k- साधन समूह प्रदान करता है।
• वीका (मशीन लर्निंग) में K-माध्यिका और X-माध्यिका सम्मिलित हैं।

प्रभुत्व

निम्नलिखित कार्यान्वयन प्रभुत्व सॉफ्टवेयर अनुज्ञाप‍त्र अनुबंध के अनुसार उपलब्ध हैं, और सार्वजनिक रूप से उपलब्ध स्रोत कोड नहीं हो सकते हैं।

• अयस्दि
• मेथेमेटिका
• अर्थात
• ओरिजिन (डाटा एनालिसिस सॉफ्टवेयर)
• रपीडमीनेर
• सैप हाना
• एसएएस प्रणाली
• सपसस
• सताता

यह भी देखें

• बीएफआर एल्गोरिदम
• केन्द्रक वोरोनोई चौकोर
• सिर/पूंछ टूट जाती है
• K Q-समतल भूमि
• लिंडे-बुजो-ग्रे एल्गोरिदम
• स्व-आयोजन मानचित्र

संदर्भ