समान तत्वों के साथ क्लस्टरिंग
मान लें कि हमारे पास टिप्पणियों का एक सेट है: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, युक्त $n$ एक निश्चित आयाम के लिए टिप्पणियों $d$। मान लें, हमारे पास कुछ निश्चित पूर्णांक हैं$k$। के-साधन क्लस्टरिंग (एल 2 दूरी के साथ) समूहों को खोजने में समस्या है$S_{1}, \dots, S_{k}$ कम से कम $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ कहाँ पे $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ केन्द्रक हैं, अर्थात $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$।
वहाँ मान लें $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ समान तत्व हैं $\{x\} \subset \mathbf{X}$।
क्या यह संभव है कि एक वैश्विक (सैद्धांतिक) समाधान में ये एक दूसरे तत्वों के बराबर हों $\{x\}$ विभिन्न समूहों से संबंधित हैं?
जवाब
पहले हमें विश्व स्तर पर इष्टतम k- साधन समाधान और एक k- साधन एल्गोरिथ्म से प्राप्त परिणाम के बीच अंतर करने की आवश्यकता है। इनमें से काफी संख्या में हैं, और जब तक कि डेटासेट बहुत छोटा नहीं है, वे एक स्थानीय इष्टतम वितरित करेंगे जो जरूरी नहीं कि वैश्विक हो। (आप अपने प्रश्न में "वैश्विक" कहते हैं, इसलिए मुझे लगता है कि आप वैश्विक रूप से इष्टतम समाधान का मतलब है; बस सुनिश्चित करने के लिए।)
आपके प्रश्न का उत्तर "सामान्य रूप से नहीं" से शुरू होता है; जो अपने$\|x-q_j\|$-वस्तु स्पष्ट रूप से सभी के लिए समान हैं $q_j$, इसलिए एक बार एल्गोरिथ्म में परिवर्तित हो जाता है (या विश्व स्तर पर इष्टतम $q_j$ ज्ञात हैं), वे सभी अपने निकटतम को सौंपे जाएंगे $q_j$, जो उन सभी के लिए समान है।
एक असाधारण स्थिति जो उपरोक्त तर्क से कवर नहीं होती है, यदि केवल कई ही नहीं होती है $x$ बराबर हैं, लेकिन वे दो या अधिक के बराबर दूरी पर भी हैं $q_j$। मुझे वास्तव में किसी भी एल्गोरिथ्म का पता नहीं है कि इस मामले में उन्हें अलग-अलग समूहों को सौंपा जा सकता है, लेकिन मैं इस तरह के कार्यान्वयन को बाहर नहीं कर सकता।
वास्तव में मैंने इसे साबित करने की कोशिश नहीं की है, लेकिन मुझे संदेह है कि वैश्विक इष्टतम कभी भी समान अवलोकनों को अलग नहीं करेगा, क्योंकि संभावना है कि यदि समान अवलोकनों को अलग किया जाता है, तो कोई भी उन सभी को क्लस्टर में डालकर एक बेहतर समाधान प्राप्त कर सकता है जिसमें बहुमत है। उनमें से (या बस किसी भी क्लस्टर अगर वे समान रूप से वितरित किए जाते हैं)। यह समझ में नहीं आता है कि इन टिप्पणियों का एक से अधिक क्लस्टर माध्य पर प्रभाव पड़ता है (यह उस क्लस्टर में अन्य टिप्पणियों के बहुमत के लिए संभावित रूप से बदतर बना देता है)। एक शायद गणित बिताते हुए इस दोपहर को साबित कर सकता है, लेकिन यहां कोई गारंटी नहीं है, बस एक अनुमान।
मैंने जो देखा है वह डेटा के दो हिस्सों जैसे 1,2,3,3,4,5 के बीच बैठकर 1-d उदाहरणों की संख्या है। वास्तव में आपको एक बेहतर समाधान मिलता है ($k=2$) लागत की दृष्टि से, यदि आप दो तीनों को या तो १,२ या ४,५ के साथ एक क्लस्टर में रखते हैं, बजाए एक और एक से दाएं (आप लागत कार्यों की स्पष्ट रूप से गणना करके इसे जांच सकते हैं) ।