K-Means vs. Online K-Means

K-means ist ein bekannter Algorithmus zum Clustering, aber es gibt auch eine Online-Variante eines solchen Algorithmus (online K-means). Was sind die Vor- und Nachteile dieser Ansätze und wann sollte jeder bevorzugt werden?

Online-k-Mittel (allgemeiner als sequentielle k-Mittel bekannt ) und traditionelle k-Mittel sind sehr ähnlich. Der Unterschied besteht darin, dass Sie mit k-means das Modell online aktualisieren können, sobald neue Daten eingehen.

Online k-means sollte verwendet werden, wenn Sie damit rechnen, dass die Daten einzeln (oder in Stücken) empfangen werden. Auf diese Weise können Sie Ihr Modell aktualisieren, sobald Sie weitere Informationen dazu erhalten. Der Nachteil dieser Methode ist, dass sie von der Reihenfolge abhängt, in der die Daten empfangen werden ( ref ).

Die ursprüngliche MacQueen k-means-Veröffentlichung (die erste, die den Namen "kmeans" verwendet) ist ein Online-Algorithmus.

MacQueen, JB (1967). "Einige Methoden zur Klassifikation und Analyse multivariater Beobachtungen". Tagungsband des 5. Berkeley-Symposiums für mathematische Statistik und Wahrscheinlichkeitsrechnung 1. University of California Press. S. 281–297

Nach dem Zuweisen jedes Punktes wird der Mittelwert unter Verwendung einer einfachen gewichteten Durchschnittsformel inkrementell aktualisiert (der alte Mittelwert wird mit n gewichtet, die neue Beobachtung wird mit 1 gewichtet, wenn der Mittelwert zuvor n Beobachtungen hatte).

Soweit ich das beurteilen kann, sollte es auch nur ein einziger Durchgang über die Daten sein, obwohl er bis zur Konvergenz mehrmals wiederholt werden kann, um Punkte neu zuzuweisen.

MacQueen benötigt normalerweise weniger Iterationen als Lloyds, um zu konvergieren, wenn Ihre Daten gemischt werden (da der Mittelwert schneller aktualisiert wird!). Bei bestellten Daten kann es zu Problemen kommen. Auf der anderen Seite erfordert es mehr Berechnung für jedes Objekt, so dass jede Iteration etwas länger dauert (zusätzliche mathematische Operationen, offensichtlich).