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

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

इतिहास

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 दोहराए जाते हैं।

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

कठिनाई

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

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

अनुप्रयोग

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

सदिश परिमाणीकरण

Main article: Vector quantization

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

k-माध्यिका का उपयोग करके वोरोनोई कोशिकाओं में ऊपर की छवि में उपस्थित रंगों का सदिश परिमाणीकरण

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

समूह विश्लेषण

Main article: Cluster analysis

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

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

विशेष अधिगम

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

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

गॉसियन मिश्रण प्रारूप

Main article: Gaussian mixture model

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

के-एसवीडी

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

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

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

Main article: Principal component analysis

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

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

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-समतल भूमि
• लिंडे-बुजो-ग्रे एल्गोरिदम
• स्व-आयोजन मानचित्र

संदर्भ