क्लस्टर एक-आयामी डेटा बेहतर रूप से?

Question

क्या किसी के पास कोई पेपर है जो बताता है कि Ckmeans.1d.dp एल्गोरिदम कैसे काम करता है?

या: एक-आयाम में के-साधन क्लस्टरिंग करने का सबसे इष्टतम तरीका क्या है?

Answer 1

मुझे लगता है कि इस पत्र के लिए आप देख रहे हैं:

Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming by Haizhou Wang and Mingzhou Song।

Answer 2

यह बेल्लमान से बहुत पुरानी तकनीक है: क्लस्टर विश्लेषण और गतिशील प्रोग्रामिंग http://www.sciencedirect.com/science/article/pii/0025556473900072

www.informationgeometry.org

Answer 3

Univariate k-मतलब है क्लस्टरिंग हे में हल किया जा सकता (केएन) समय पर एक नोट (पहले से क्रमबद्ध इनपुट पर) मोंज मैट्रिस पर सैद्धांतिक परिणामों के आधार पर, लेकिन संख्यात्मक अस्थिरता और शायद चुनौतियों को हल करने के कारण दृष्टिकोण लोकप्रिय नहीं था।

एक बेहतर विकल्प एक ओ (knlgn) विधि है जिसे अब Ckmeans.1d.dp संस्करण 3.4.6 में लागू किया गया है। यह कार्यान्वयन ह्यूरिस्टिक के-साधन के रूप में तेज़ है लेकिन गारंटीकृत इष्टतमता प्रदान करता है, विशेष रूप से बड़े के के लिए हेरिस्टिक के-साधनों से बेहतर परिमाण के आदेश प्रदान करता है।

रिचर्ड बेलमैन (1 9 73) द्वारा सामान्य गतिशील प्रोग्रामिंग समाधान के-साधन समस्या के विनिर्देशों पर स्पर्श नहीं करता है और अंतर्निहित रनटाइम ओ (एन^3) है।