k-bedeutet vs k-bedeutet ++

Soweit ich weiß, wählt k-means die Anfangszentren zufällig aus. Da sie auf purem Glück basieren, können sie wirklich schlecht ausgewählt werden. Der K-means ++ Algorithmus versucht, dieses Problem zu lösen, indem er die Anfangszentren gleichmäßig verteilt.

• Garantieren die beiden Algorithmen die gleichen Ergebnisse? Oder es ist möglich, dass die schlecht ausgewählten Anfangsschwerpunkte zu einem schlechten Ergebnis führen, egal wie viele Iterationen.

• Nehmen wir an, es gibt einen bestimmten Datensatz und eine bestimmte Anzahl gewünschter Cluster. Wir führen einen k-means-Algorithmus aus, solange er konvergiert (keine Mittenbewegung mehr). Gibt es eine genaue Lösung für dieses Clusterproblem (bei gegebener SSE), oder führt k-means bei erneuter Ausführung zu manchmal unterschiedlichen Ergebnissen?

• Wenn es mehr als eine Lösung für ein Clustering-Problem gibt (gegebener Datensatz, gegebene Anzahl von Clustern), garantiert K-means ++ ein besseres Ergebnis oder nur ein schnelleres? Mit besser meine ich niedrigere SSE.

Der Grund, warum ich diese Fragen stelle, ist, dass ich auf der Suche nach einem k-means-Algorithmus zum Clustering eines riesigen Datensatzes bin. Ich habe einige k-means ++ gefunden, aber es gibt auch einige CUDA-Implementierungen. Wie Sie bereits wissen, verwendet CUDA die GPU und kann mehr als Hunderte von Threads parallel ausführen. (So ​​kann es den gesamten Prozess wirklich beschleunigen). Aber keine der CUDA-Implementierungen - die ich bisher gefunden habe - hat eine k-means ++ - Initialisierung.

K-means beginnt mit der zufälligen Zuweisung von Cluster-Zentren und sucht dann nach "besseren" Lösungen. K-means ++ beginnt mit der zufälligen Zuordnung eines Clusterzentrums und sucht dann nach anderen Zentren, wenn das erste gegeben ist. So beide Algorithmen zufällige Initialisierung als Ausgangspunkt zu verwenden, so können unterschiedliche Ergebnisse auf verschiedenen Läufen geben. Als Beispiel können Sie diese Vorlesung überprüfen: Clustering als Beispiel für ein Inferenzproblem. In der 40. Minute gibt es Beispiele für k-means-Läufe, aber die gesamte Vorlesung ist interessant.

Beantworten Sie also Ihre Fragen:

• Nein, da es eine zufällige Initialisierung gibt, können verschiedene Läufe unterschiedliche Ergebnisse liefern (siehe Beispiele in der Vorlesung). Sie sollten vergleichbare Ergebnisse liefern, dies ist jedoch nicht garantiert. Da alle Zentren zufällig in k-Mitteln initialisiert werden, kann dies zu anderen Ergebnissen führen als k-Mittel ++.
• K-Mittel können bei verschiedenen Läufen unterschiedliche Ergebnisse liefern.
• Das k-means ++ - Papier liefert Monte-Carlo-Simulationsergebnisse, die zeigen, dass k-means ++ sowohl schneller als auch leistungsfähiger ist, daher gibt es keine Garantie, aber es kann besser sein.

Was Ihr Problem betrifft: Was k-means ++ tut, wählt die Zentren aus und startet dann ein "klassisches" k-means. Sie können also (1) den Teil des Algorithmus verwenden, der Zentren auswählt, und dann (2) diese Zentren in den GPU-Implementierungen von k-means verwenden. Auf diese Weise wird zumindest ein Teil eines Problems mit GPU-basierter Software gelöst und sollte daher schneller sein.

Anzeigen der Startschwerpunkte von K-means und K-means ++

Um eine intuitive Ansicht des Unterschieds zwischen den Startschwerpunkten der beiden Algorithmen hinzuzufügen, betrachten Sie den folgenden Spielzeugdatensatz, der aus drei einheitlich erzeugten Quadraten besteht

Hier sind 2D-Histogramme, die zeigen, wo die Algorithmen k-means und k-means ++ ihre Startschwerpunkte initialisieren (2000 Simulationen).

Es ist klar, dass das Standard-k-Mittel die Punkte gleichmäßig initialisiert, während k-Mittel ++ dazu neigt, nahe der Mitte der Quadrate zu initialisieren

Viele Male KMeans Die zufällige Initialisierung benötigt weniger Zeit als KMeans ++, führt jedoch zu einem schlechten Ergebnis. Aufgrund der zufälligen Initialisierung erhalten wir oft ein lokales Optimum, da unser anfänglicher Satz von Zentren nicht über den Datensatz verteilt ist.

Beantworten Sie also Ihre Frage:

1. Nein, da KMeans ++ - Zentren über die Daten verteilt sind, sind die Kosten (innerhalb der Clustersumme des Quadrats) mit größerer Wahrscheinlichkeit geringer als die zufällige Initialisierung.
2. Da es sich um eine zufällige Initialisierung in KMeans handelt, ergibt sich je nach Ihrer anfänglichen Gruppe von Zentren ein unterschiedliches Ergebnis
3. Erstens gibt es keine endgültige Lösung für KMeans, da es sich um unbeaufsichtigtes Lernen handelt. Wir können die KMeans-Kosten (SSE) senken. KMeans wählen das Anfangszentrum intelligent aus. Die Konvergenz erfordert weniger Llyods-Iteration und liefert ein besseres Ergebnis als Random