बराबर आकार के समूह n k में अंक समूहों

Question

संभव डुप्लिकेट:
K-means algorithm variation with equal cluster size

संपादित करें: इस सवाल casperOne यह मेरे लिए बिंदु बाहर की तरह डुप्लिकेट है। https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points

मेरे आवश्यकताओं

एक परियोजना मैं समूह n अंक (एक्स, वाई) बराबर आकार के कश्मीर समूहों में की जरूरत में (एन/ट): वैसे भी यहाँ एक अधिक सामान्य सवाल है कि कवर यह एक है । जहां एक्स और वाई डबल फ्लोटिंग नंबर हैं, एन 100 से 10000 तक हो सकते हैं और के 2 से 100 तक हो सकते हैं। इसके अलावा ए को एल्गोरिदम रन से पहले जाना जाता है।

मेरे प्रयोगों

मैं http://en.wikipedia.org/wiki/K-means_clustering एल्गोरिथ्म, जो काम महान और तेजी से मोटे तौर पर एक ही आकार के बिल्कुल कश्मीर समूहों का निर्माण करने के का उपयोग करके समस्या को हल करने शुरू कर दिया।

लेकिन मेरी समस्या यह है, के-मतलब का मतलब लगभग उसी आकार के क्लस्टर का उत्पादन होता है, जहां मुझे क्लस्टर को एक ही आकार के होने की आवश्यकता होती है (या अधिक सटीक होने के लिए: मुझे उन्हें फर्श के बीच आकार (एन/के) और छत (एन/के))।

इससे पहले कि आप इसे इंगित करें, हाँ मैंने पहले उत्तर K-means algorithm variation with equal cluster size पर आजमाया, जो एक अच्छा विचार की तरह लगता है।

मुख्य विचार क्लस्टर उत्पादन की सरणी को के-माध्यमों द्वारा प्रोसेस करना है। सबसे छोटे क्लस्टर से सबसे छोटे तक। हम उन समूहों के आकार को कम करते हैं जिनके पास अन्य बिंदुओं को अतिरिक्त बिंदुओं को स्थानांतरित करके एन/के सदस्यों से अधिक होता है। केवल क्लस्टर को छोड़कर जो पहले ही कम हो चुके हैं।

यहाँ छद्म कोड मैं लागू किया है:

n is the number of point 
k is the number of cluster 
m = n/k (the ideal cluster size) 
c is the array of cluster after K-means 
c' = c sorted by size in descending order 
for each cluster i in c' where i = 1 to k - 1 
    n = size of cluster i - m (the number of point to move) 
    loop n times 
     find a point p in cluster i with minimal distance to a cluster j in c' where j > i 
     move point p from cluster i to cluster j 
    end loop 
    recalculate centroids 
end for each 

इस एल्गोरिथ्म के साथ समस्या यह है कि इस प्रक्रिया के अंत (जब मैं करीब आ k करने के लिए), हम ग में एक क्लस्टर जे चुनना है पास '(जहां जे> मैं क्योंकि हमें पहले ही संसाधित क्लस्टर को छोड़ने की ज़रूरत है), लेकिन यह क्लस्टर जे जो हमने पाया है क्लस्टर I से दूर हो सकता है, इस प्रकार क्लस्टर की अवधारणा को तोड़ सकता है।

मेरा प्रश्न

वहाँ है एक पोस्ट कश्मीर का मतलब एल्गोरिथ्म या एक K-मतलब है संस्करण है कि मेरे आवश्यकताओं को पूरा कर सकते हैं, या मैं शुरू से ही गलत हूँ और मैं एक दूसरे एल्गोरिथ्म क्लस्टरिंग खोजने की जरूरत है?

पीएस: मुझे अपने आप को समाधान लागू करने की कोई बात नहीं है, लेकिन अगर मैं लाइब्रेरी का उपयोग कर सकता हूं, और आदर्श रूप से जावा में यह अच्छा होगा।

Answer 1

विषय पर एक विशेषज्ञ नहीं होने के नाते, मुझे एक बार मानचित्र पर क्लस्टर स्थानों पर एक साधारण एल्गोरिदम के साथ आने की आवश्यकता होती है, जहां प्रत्येक बिंदु को क्लस्टर का हिस्सा बनने की आवश्यकता होती है, और क्लस्टर कई तरीकों से बंधे होते हैं (न केवल आकार में (यानी बिंदु गिनती), लेकिन कुछ अन्य उपायों में भी जो विभिन्न कारकों पर निर्भर करता है)।

पहली बार "कठिन" अंक ढूंढने और फिर वहां से क्लस्टर बढ़ने से, मुझे सर्वोत्तम परिणाम मिल गए। "कठिन" अंक ऐसे अंक होंगे जो पहुंचने में कठोर हैं, उदा।क्योंकि वे कुल क्षेत्र के बाहरी इलाके में अकेले झूठ बोलेंगे, या क्योंकि वे अन्य बिंदुओं की तुलना में एक और क्लस्टर सीमा की स्थिति को हिट करने में मदद करेंगे। इससे क्लस्टर को अच्छी तरह से संरेखित करने में मदद मिली, जिससे उन्हें बहुत कम अकेला और उन्हें रखने के लिए संबंधित हैंडवर्क छोड़ दिया गया।

यह आपकी मदद कर सकता है यदि आपका वर्तमान एल्गोरिदम सामान्य रूप से इन कठिन बिंदुओं को अंतिम रूप से ढूंढता है।

प्रारंभ:

Answer 2

इस बदलाव kmeans प्रयास करें प्रत्येक बिंदु के लिए

• kmeans का उपयोग कर यादृच्छिक पर डाटासेट से k केन्द्रों चुनते हैं, या और भी बेहतर ++ रणनीति
• , दूरी की गणना अपने निकटतम क्लस्टर सेंटर में, और इस
• ढेर से अंक खींचें, और उन्हें निकटतम क्लस्टर तक असाइन करें, जब तक क्लस्टर पहले से ही न हो भरा हुआ। यदि हां, तो अगले निकटतम क्लस्टर केंद्र की गणना और ढेर

अंत में में डालें, तो आप एक paritioning कि क्लस्टर प्रति वस्तुओं की + -1 एक ही नंबर की अपनी आवश्यकताओं को संतुष्ट करना चाहिए था (यकीन है कि पिछले कुछ बनाना क्लस्टर के पास सही संख्या भी होती है। पहले m क्लस्टर में ceil ऑब्जेक्ट्स, शेष floor ऑब्जेक्ट्स होना चाहिए।) ध्यान दें कि एक ढेर का उपयोग करके क्लस्टर का उत्तल होना सुनिश्चित होता है: यदि वे अब उत्तल नहीं होते हैं, तो बेहतर स्वैप उम्मीदवार होता ।

पुनरावृत्ति कदम:

आवश्यक वस्तुएँ: "स्वैप प्रस्तावों" (वस्तुओं है कि एक अलग समूह में होने के लिए पसंद करेंगे) के साथ प्रत्येक समूह के लिए एक सूची है।

ई कदम: गणना नियमित में के रूप में अद्यतन क्लस्टर केन्द्रों k-इसका मतलब

एम कदम: सभी बिंदुओं के माध्यम से (एक बैच में या तो सिर्फ एक, या सभी) पुनरावृत्ति

कंप्यूट निकटतम क्लस्टर सेंटर ऑब्जेक्ट/ऑब्जेक्ट क्लस्टर सेंटर जो मौजूदा क्लस्टर से करीब हैं। यदि यह एक अलग समूह है:

• तो अन्य क्लस्टर वर्तमान क्लस्टर से छोटी है, बस अगर कोई अन्य समूह से एक स्वैप प्रस्ताव (या एक के साथ किसी भी समूह है नई क्लस्टर
• पर ले जाते हैं कम दूरी), दो तत्व क्लस्टर कार्य स्वैप (वहाँ है अगर एक से अधिक प्रस्ताव, सबसे बड़ा सुधार के साथ एक)
• अन्यथा चुनते हैं, तो अन्य क्लस्टर

क्लस्टर आकार रहने के लिए एक स्वैप प्रस्ताव से संकेत मिलता है invariant (+ - छत/मंजिल अंतर), एक वस्तुएं हैं केवल एक क्लस्टर से दूसरे तक ले जाया जाता है जब तक कि यह अनुमान के सुधार में न हो। इसलिए इसे किसी बिंदु पर के-साधनों से अभिसरण करना चाहिए। यह थोड़ा धीमा हो सकता है (यानी अधिक पुनरावृत्तियों) हालांकि।

मुझे नहीं पता कि यह पहले प्रकाशित या लागू किया गया है या नहीं। यह वही है जो मैं कोशिश करूंगा (अगर मैं के-साधनों का प्रयास करूंगा। वहां बेहतर क्लस्टरिंग एल्गोरिदम हैं।)