MATLAB kMeans हमेशा वैश्विक minima

Question

पर अभिसरण नहीं करता है मैंने मैटलैब में k-Means clustering एल्गोरिदम लिखा था, और मैंने सोचा कि मैं इसे kmeans(X,k) में निर्मित MATLABs के विरुद्ध कोशिश करूंगा।

हालांकि, बहुत आसान चार क्लस्टर सेटअप (चित्र देखें) के लिए, MATLAB kMeans हमेशा इष्टतम समाधान (बाएं) लेकिन (दाएं) तक अभिसरण नहीं होता है।

मैंने जो लिखा है वह हमेशा ऐसा नहीं करता है, लेकिन क्या अंतर्निहित फ़ंक्शन ऐसी आसान समस्या को हल करने में सक्षम नहीं होना चाहिए, हमेशा इष्टतम समाधान ढूंढना चाहिए?

Answer 1

@Alexandre C. समझाया गया है, के-मतलब एल्गोरिदम प्रारंभिक क्लस्टर केंद्र की स्थिति पर निर्भर करता है, और इस बात की कोई गारंटी नहीं है कि यह इष्टतम समाधान में परिवर्तित हो जाएगी।

सबसे अच्छा आप कर सकते हैं प्रयोग यादृच्छिक प्रारंभिक बिंदुओं के साथ कई बार प्रयोग दोहराना है।

MATLAB का कार्यान्वयन ऐसा विकल्प प्रदान करता है: replicates जो क्लस्टरिंग एन बार दोहराता है और सबसे कम कुल क्लस्टर पॉइंट-टू-सेंट्रॉइड दूरी के साथ एक को चुनता है। आपको यह नियंत्रित करने के लिए भी मिलता है कि start विकल्प के साथ प्रारंभिक सेंट्रॉइड कैसे चुने जाते हैं।

इसके अतिरिक्त, MATLAB कई दूरी उपायों (यूक्लिडियन, मैनहट्टन, कोसाइन, ...) के बीच विकल्प प्रदान करता है। एक साफ विकल्प emptyaction आपको यह नियंत्रित करने की अनुमति देता है कि क्या होता है जब क्लस्टर पुनरावृत्तियों के दौरान अपने सभी निर्दिष्ट सदस्य को खो देता है।

लेकिन वास्तविक लाभ यह है कि यह दो चरणों के एल्गोरिदम को नियोजित करता है: सामान्य असाइन-रीकंप्यूट पुनरावृत्ति, उसके बाद ऑनलाइन अपडेट चरण। अधिक जानकारी के लिए documentation page के एल्गोरिदम अनुभाग को पढ़ना सुनिश्चित करें।

Answer 2

k-इसका मतलब एल्गोरिथ्म काफी क्लस्टर केन्द्रों के लिए प्रारंभिक अनुमान के प्रति संवेदनशील है। क्या आपने समान प्रारंभिक जन केंद्रों के साथ दोनों कोडों को आजमाया है?

एल्गोरिदम सरल है, और मुझे संदेह है कि आपके कार्यान्वयन और मैटलैब के बीच बहुत भिन्नता है।

Answer 3

आप शायद इस समाधान से निराश होंगे कि "के-साधन एल्गोरिदम" (यानी लॉयड का एल्गोरिदम) का कोई भी विशेष भाग आता है। ऐसा इसलिए है क्योंकि लॉयड का एल्गोरिदम अक्सर खराब स्थानीय मिनीमा में फंस जाता है।

सौभाग्य से, लॉयड्स के-साधनों को हल करने का एक ही तरीका है। और एक दृष्टिकोण है जो लगभग हमेशा एक बेहतर स्थानीय मिनीमा पाता है।

चाल एक समय में डेटा बिंदुओं के क्लस्टर असाइनमेंट को अपडेट करना है। आप n अंकों की संख्या की गणना को प्रत्येक अर्थ के लिए आवंटित करके कुशलता से ऐसा कर सकते हैं। ताकि आप कर सकते हैं फिर से गणना क्लस्टर मतलब m बिंदु x हटाने के बाद इस प्रकार है:

m_new = (n * m - x)/(n - 1) 

और x जोड़ने का उपयोग कर मतलब m क्लस्टर के लिए:

m_new = (n * m + x)/(n + 1) 

बेशक

क्योंकि यह नहीं हो सकता vectorized, यह MATLAB में चलाने के लिए थोड़ा दर्दनाक है लेकिन अन्य भाषाओं में बहुत बुरा नहीं है।

यदि आप वास्तव में सर्वोत्तम संभव न्यूनतम मिनीमा प्राप्त करने के लिए उत्सुक हैं, और आपको उदाहरण-आधारित क्लस्टरिंग का उपयोग करने में कोई फर्क नहीं पड़ता है, तो आपको affinity propagation पर ध्यान देना चाहिए। MATLAB कार्यान्वयन Frey lab affinity propagation page पर उपलब्ध हैं।

Answer 4

हालांकि K-Means++ एक ही रन में समस्या का समाधान नहीं करेगा, यह एन बार चलाए जाने पर बेहतर परिणाम देता है (मूल के-मीन्स एल्गोरिदम एन बार चलाने की तुलना में)।

Answer 5

मैं इसे एक आसान समस्या नहीं कहूंगा। :) वास्तव में, "के-मतलब क्लस्टरिंग" पर विकिपीडिया लेख कम्प्यूटेशनल जटिलता की एक सुंदर उदास तस्वीर देता है।

यदि आप यादृच्छिक पुनरारंभ (प्रारंभिक अनुमान पर निर्भरता) से मुक्त होना चाहते हैं, तो समझौता "वैश्विक के-साधन" एल्गोरिदम है; पेपर और मैटलैब कोड यहां पाया जा सकता है: http://lear.inrialpes.fr/~verbeek/software.php