MATLAB kMeans konvergiert nicht immer zu globalen Minima
Ich habe einen k-Means-Clustering -Algorithmus in MATLAB geschrieben, und ich dachte, ich würde es gegen MATLABs versuchen eingebaut in kmeans(X,k) .
Aber für die sehr einfache Vier-Cluster-Konfiguration (siehe Bild) tut MATLAB kMeans konvergieren nicht immer zur optimalen Lösung (links) sondern (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?
5 Antworten
Wie @Alexandre C erklärt, der K-Means-Algorithmus hängt 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 MATLAB-Implementierung 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 Anfangsschwerpunkte mit der Option start ausgewählt werden.
Darüber hinaus bietet MATLAB die Wahl zwischen einer Reihe von Entfernungsmessungen (euklidisch, Manhattan, Cosinus, ...). 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 besteht darin, dass es einen zweiphasigen Algorithmus verwendet: die üblichen Assign-Recompute-Iterationen, gefolgt von einer Online-Update-Phase. Weitere Informationen finden Sie auf dem Algorithmabschnitt der Dokumentationsseite .
>Der k-Means-Algorithmus reagiert empfindlich auf die erste Schätzung für die Clusterzentren. Haben Sie beide Codes mit den gleichen anfänglichen Massenzentren getestet?
Der Algorithmus ist einfach, und ich bezweifle, dass es zwischen Ihrer Implementierung und Matlabs viel Unterschied gibt.
Ich würde es nicht als ein einfaches Problem bezeichnen. :) In der Tat gibt der Wikipedia-Artikel über "k-means clustering" ein ziemlich düsteres Bild von der rechnerischen Komplexitä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: Ссылка
Sie werden wahrscheinlich oft enttäuscht sein von der Lösung, die ein bestimmter Durchlauf des "k-Means-Algorithmus" (d. h. des Lloyd-Algorithmus) liefert. Das liegt daran, dass der Lloyd-Algorithmus oft in schlechten lokalen Minima stecken bleibt.
Glücklicherweise ist Lloyd's nur eine Möglichkeit, k-Mittel 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 Punkte n , die jedem Mittelwert zugewiesen sind, beibehalten. Damit können Sie den Cluster-Mittelwert m nach dem Entfernen des Punktes x wie folgt neu berechnen:
Und x zum Cluster hinzufügen m mit:
Natürlich, weil es nicht vektorisiert werden kann, ist es etwas 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 Affinitätsausbreitung . MATLAB-Implementierungen sind auf der Frey-lab-Affinitätsausbreitungsseite verfügbar.
Obwohl K-Means ++ das Problem nicht in einem einzigen Durchlauf lösen wird, neigt es dazu um bessere Ergebnisse zu erhalten, wenn es N-mal ausgeführt wird (verglichen mit dem N-maligen Ausführen des ursprünglichen K-Means-Algorithmus).
Tags und Links cluster-analysis matlab machine-learning k-means