Konvergenznachweis von k-means

Für eine Aufgabe wurde ich gebeten, einen Beweis zu liefern, dass k-means in einer endlichen Anzahl von Schritten konvergiert.

Das habe ich geschrieben:

Im Folgenden ist eine Sammlung aller Cluster-Zentren. Definiere eine “Energie” -Funktion Die Energiefunktion ist nicht negativ. Wir sehen, dass die Schritte (2) und (3) des Algorithmus beide die Energie reduzieren. Da die Energie von unten begrenzt wird und ständig reduziert wird, muss sie auf ein lokales Minimum konvergieren. Die Iteration kann gestoppt werden, wenn sich E (C) mit einer Rate unter einem bestimmten Schwellenwert ändert.$C$

$$E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$$ $E(C)$

Schritt 2 bezieht sich auf den Schritt, bei dem jeder Datenpunkt durch sein nächstgelegenes Clusterzentrum gekennzeichnet wird, und Schritt 3 ist der Schritt, bei dem die Zentren durch einen Mittelwert aktualisiert werden.

Dies reicht nicht aus, um die Konvergenz in einer endlichen Anzahl von Schritten zu beweisen. Die Energie kann immer kleiner werden, aber es schließt nicht aus, dass die Mittelpunkte herumspringen können, ohne die Energie stark zu verändern. Mit anderen Worten, es kann mehrere Energieminima geben und der Algorithmus kann zwischen ihnen springen, nicht wahr?

Erstens gibt es höchstens Möglichkeiten, N Datenpunkte in k Cluster zu unterteilen; Jede solche Partition kann als "Clustering" bezeichnet werden. Dies ist eine große, aber endliche Zahl. Für jede Iteration des Algorithmus erstellen wir ein neues Clustering, das nur auf dem alten Clustering basiert . Beachte das$k^N$$N$$k$

1. Wenn das alte Clustering mit dem neuen identisch ist, ist das nächste Clustering wieder dasselbe.
2. Wenn sich das neue Clustering vom alten unterscheidet, sind die Kosten für das neue Clustering niedriger

Da der Algorithmus eine Funktion iteriert, deren Domäne eine endliche Menge ist, muss die Iteration schließlich in einen Zyklus eintreten. Der Zyklus kann nicht länger als da ansonsten nach (2) ein Clustering auftreten würde, das kostengünstiger ist als das, was unmöglich ist. Daher muss der Zyklus genau . Daher konvergiert k-means in einer endlichen Anzahl von Iterationen.$1$$1$

Um etwas hinzuzufügen: Ob der Algorithmus konvergiert oder nicht, hängt auch von Ihrem Stoppkriterium ab. Wenn Sie den Algorithmus stoppen, sobald sich die Clusterzuweisungen nicht mehr ändern, können Sie tatsächlich nachweisen, dass der Algorithmus nicht unbedingt konvergiert (vorausgesetzt, die Clusterzuweisung verfügt nicht über einen deterministischen Bindungsunterbrecher, wenn mehrere Zentroide den gleichen Abstand haben).

Hier haben Sie 8 Datenpunkte (Punkte) und zwei Zentroide (rote Kreuze). Jetzt haben die grünen Datenpunkte den gleichen Abstand zum linken und rechten Schwerpunkt. Gleiches gilt für die blauen Datenpunkte. Nehmen wir an, dass die Zuweisungsfunktion in diesem Fall nicht deterministisch ist. Weiterhin nehmen wir an, dass bei Iteration 1 die grünen Punkte dem linken Cluster und die blauen Punkte dem rechten Cluster zugewiesen werden. Dann aktualisieren wir die Zentroide. Es stellt sich heraus, dass sie tatsächlich an derselben Stelle bleiben. (Dies ist eine einfache Berechnung. Für den linken Schwerpunkt werden die Koordinaten der beiden linken schwarzen Punkte und der beiden grünen Punkte gemittelt -> (0, 0,5). Gleiches gilt für den rechten Schwerpunkt.)

Dann sieht die Situation bei Iteration 2 wieder gleich aus, aber jetzt nehmen wir an, dass unsere (bei Gleichheit) nicht deterministische Zuweisungsfunktion die grünen Punkte dem rechten Cluster und die blauen Punkte dem linken Cluster zuweist. Auch hier werden sich die Schwerpunkte nicht ändern.

Die Iteration 3 ist wieder die gleiche wie die Iteration 1. Wir haben also einen Fall, in dem sich die Clusterzuweisungen kontinuierlich ändern und der Algorithmus (mit diesem Stoppkriterium) nicht konvergiert.

$\leq$$\lt$