Online k-means Clustering

Question

Gibt es eine Online-Version des k-Means clustering Algorithmus?

Mit online meine ich, dass jeder Datenpunkt seriell verarbeitet wird, eins nach dem anderen, wenn sie das System betreten, und spart dadurch Rechenzeit, wenn es in Echtzeit verwendet wird.

Ich habe mich selbst mit guten Ergebnissen geschrieben, aber ich würde wirklich etwas "Standardisiertes" bevorzugen, da es in meiner Masterarbeit verwendet werden soll.

Hat auch jemand Tipps für andere Online-Clustering-Algorithmen? (lmgtfy fehlgeschlagen;))

Answer 1

Ja, es gibt. Google konnte es nicht finden, weil es häufiger als "sequentielle k-means" bekannt ist.

Sie können zwei Pseudo-Code-Implementierungen von sequentiellen K-Mitteln in this section of some Princeton CS class notes von Richard Duda finden. Ich habe eine der beiden Implementierungen im Folgenden wiedergegeben:

Make initial guesses for the means m1, m2, ..., mk 
Set the counts n1, n2, ..., nk to zero 
Until interrupted 
    Acquire the next example, x 
    If mi is closest to x 
     Increment ni 
     Replace mi by mi + (1/ni)*(x - mi) 
    end_if 
end_until 

Das schöne daran ist, dass Sie nur den Mittelwert der einzelnen Cluster und die Zählung der Anzahl von Datenpunkten dem Cluster zugewiesen merken müssen. Sobald Sie diese beiden Variablen aktualisiert haben, können Sie den Datenpunkt wegwerfen.

Ich bin mir nicht sicher, wo Sie ein Zitat dafür finden könnten. Ich würde anfangen, in Dudas klassischem Text Pattern Classification and Scene Analysis oder der neueren Ausgabe Pattern Classification zu suchen. Wenn es nicht da ist, könntest du Chris Bishops neuestes Buch oder Daphne Kollers und Nir Friedmans letzten Text ausprobieren.

Answer 2

Sie können mehr über Online-k-Mittel in "Introduction to Machine Learning" von Ethem Alpaydin in 12 Kapitel finden Lokale Modelle