Gleiches Ergebnis von K-Means und sequentiellen K-Means?

Question

Erhalten wir das gleiche Ergebnis, wenn wir K-Means- und sequentielle K-Means-Methoden mit denselben Anfangseinstellungen auf denselben Datensatz anwenden? Erklären Sie Ihre Gründe.

Persönlich denke ich, dass die Antwort Nein ist, das Ergebnis, das von sequentiellen k-Means erhalten wurde, hängt von der Präsentationsreihenfolge der Datenpunkte ab. Und die Endbedingung ist nicht gleich.

Hier findet der Pseudocode der beiden Clustering -Algorithmen an.

K-means

Make initial guesses for the means m1, m2, ..., mk
Until there is no change in any mean
    Assign each data point to the cluster whose mean is the nearest.
    Calculate the mean of each cluster.
    For i from 1 to k
        Replace mi with the mean of all examples for cluster i.
    end_for
end_until

Sequentielle k-means

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

Answer 1

Richtig, die Ergebnisse können unterschiedlich sein.

Punkte: x1 = (0,0), x2 = (1,1), x3 = (0,75,0), x4 = (0,25,1); M1 = (0,0,5), M2 = (1,0,5). K-Means weist dem M1-Cluster X2 und X3 dem M2-Cluster zu. Die neuen Mittelwerte sind M1 '= (0,125,0,5) und M2' = (0,875,0,5), und es findet keine Neuzuweisung statt. Bei sequentiellen k-means bewegt sich X2 nach dem Zuordnen von X1 M1 zu (0,0), M2 auf (1,1). Dann steht M1 auf X3 am nächsten, so dass M1 zu (0,375,0) wechselt. Schließlich ist M2 X4 am nächsten, so dass M2 zu (0,625,1) bewegt. Dies ist wieder eine stabile Konfiguration.