MATLAB kMeans konvergiert nicht immer zu globalen Minima

Question

Ich schrieb einen k-Means clustering Algorithmus in MATLAB, und ich dachte, ich würde es gegen MATLABs versuchen, die in kmeans(X,k) gebaut werden.

Für das sehr einfache Vier-Cluster-Setup (siehe Bild) konvergiert MATLAB kMeans jedoch nicht immer zur optimalen Lösung (links), sondern zu (rechts).

Die eine, die ich geschrieben habe, tut das auch nicht immer, aber sollte die eingebaute Funktion nicht in der Lage sein, solch ein einfaches Problem zu lösen, immer die optimale Lösung zu finden?

Answer 1

Wie @Alexandre C. erklärt, hängt der K-Means-Algorithmus von den anfänglichen Clusterschwerpunktpositionen ab, und es gibt keine Garantie, dass er zur optimalen Lösung konvergiert.

Das Beste, was Sie tun können, ist, das Experiment mehrmals mit zufälligen Startpunkten zu wiederholen.

Die Implementierung von MATLAB bietet eine solche Option: replicates, die das Clustering N-mal wiederholt und diejenige mit der niedrigsten Gesamtpunkt-zu-Schwerpunkt-Entfernung innerhalb des Clusters auswählt. Sie können auch steuern, wie die anfänglichen Schwerpunkte mit der Option start gewählt werden.

Darüber hinaus bietet MATLAB die Wahl zwischen einer Reihe von Entfernungsmessungen (euklidisch, Manhattan, Kosinus, ...). Mit einer einfachen Option emptyaction können Sie steuern, was passiert, wenn ein Cluster während der Iterationen alle zugeordneten Elemente verliert.

Aber der wirkliche Vorteil ist, dass es einen zweiphasigen Algorithmus verwendet: die üblichen Zuweisungs-Neuberechnung-Iterationen, gefolgt von einer Online-Aktualisierungsphase. Lesen Sie unbedingt den Algorithmus-Abschnitt der für weitere Informationen.

Answer 2

Die K-Means-Algorithmus auf anfängliche Schätzung für die Clusterzentren recht empfindlich ist. Haben Sie beide Codes mit den gleichen ersten Massenzentren getestet?

Der Algorithmus ist einfach, und ich bezweifle, dass es zwischen Ihrer Implementierung und Matlabs viel Unterschied gibt.

Answer 3

Sie werden wahrscheinlich oft enttäuscht sein von der Lösung, die ein bestimmter Durchlauf des "k-Means-Algorithmus" (d. H. Des Lloyd-Algorithmus) bietet. Das liegt daran, dass Lloyds Algorithmus oft in schlechten lokalen Minima stecken bleibt.

Glücklicherweise ist Lloyd's nur eine Möglichkeit, k-means zu lösen. Und es gibt einen Ansatz, der fast immer bessere lokale Minima findet.

Der Trick besteht darin, die Clusterzuweisungen der Datenpunkte einzeln zu aktualisieren. Sie können dies effizient durchführen, indem Sie die Anzahl der jedem Mittelwert zugewiesenen Punkte n beibehalten. Damit können Sie neu berechnen, die Cluster m bedeuten nach dem Punkt zu entfernen x wie folgt:

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

Und fügen x mittlere m Cluster mit:

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

Natürlich, weil es nicht sein kann, vektorisiert, ist es ein bisschen schmerzhaft, in MATLAB zu laufen, aber nicht so schlecht in anderen Sprachen.

Wenn Sie wirklich daran interessiert sind, die bestmöglichen lokalen Minima zu erhalten, und es Ihnen nichts ausmacht, ein exemplarbasiertes Clustering zu verwenden, sollten Sie sich affinity propagation ansehen. MATLAB-Implementierungen sind unter Frey lab affinity propagation page verfügbar.

Answer 4

Obwohl K-Means++ das Problem nicht in einem einzigen Durchlauf lösen kann, tendiert es zu besseren Ergebnissen, wenn es N-mal ausgeführt wird (im Vergleich zum n-maligen Ausführen des ursprünglichen K-Means-Algorithmus).

Answer 5

Ich würde es kein einfaches Problem nennen :) Tatsächlich gibt der Wikipedia-Artikel über "k-means clustering" ein ziemlich düsteres Bild der Rechenkomplexität.

Wenn Sie frei von zufälligen Neustarts sein wollen (Abhängigkeit von der anfänglichen Schätzung), ist ein Kompromiss der Algorithmus "global k-means"; Den Papier- und Matlab-Code finden Sie hier: http://lear.inrialpes.fr/~verbeek/software.php