K-Means Clustering Tool

Pseudocode

Zwei Schritte im Wechsel, bis sich nichts mehr ändert: jeden Punkt dem nächstgelegenen Zentroid zuordnen und danach jeden Zentroid auf den Mittelwert der ihm zugeordneten Punkte verschieben.

KMeans(punkte, k):
    k Zentroide initialisieren (zufällig oder k-means++)

    wiederhole, bis sich die Zuordnungen nicht mehr ändern:
        // Zuordnungsschritt
        für jeden Punkt p:
            cluster[p] = argmin über c von distanz(p, c)

        // Aktualisierungsschritt
        für jeden Zentroid c:
            c = Mittelwert aller Punkte mit cluster[p] == c

    gib Cluster und Zentroide zurück

Jeder Schritt senkt die Summe der quadrierten Abstände innerhalb der Cluster oder lässt sie gleich, und es gibt nur endlich viele mögliche Zuordnungen, der Algorithmus terminiert also stets. Nicht garantiert ist, dass er im globalen Optimum endet: er konvergiert gegen ein lokales Minimum, das vollständig von der Initialisierung abhängt, und genau das ist die praktische Einschränkung, die man handhaben muss.

Durchgerechnetes Beispiel, Schritt für Schritt

Gruppiere vier Punkte in zwei Cluster, ausgehend von einer bewusst schlechten Initialisierung, bei der beide Zentroide im selben echten Cluster liegen.

Beispielgraph: Punkte bei (1,1), (2,1), (8,8) und (9,8). Anfangszentroide auf (1,1) und (2,1) gesetzt, also beide im linken unteren Cluster.

1. Iteration 1, Zuordnung. Der Punkt (1,1) geht zum ersten Zentroid. Die übrigen drei, (2,1), (8,8) und (9,8), liegen näher am zweiten. Die Aufteilung ist deutlich schlecht: ein Cluster mit einem Punkt und einer mit dreien.
2. Iteration 1, Aktualisierung. Der erste Zentroid bleibt bei (1,1). Der zweite wandert auf den Mittelwert von (2,1), (8,8) und (9,8), also (6,33, 5,67). Die Summe der quadrierten Abstände innerhalb der Cluster beträgt 61,333.
3. Iteration 2, Zuordnung. Da der zweite Zentroid nach rechts oben gewandert ist, liegt der Punkt (2,1) nun näher am ersten. Die Aufteilung wird zu (1,1) und (2,1) gegen (8,8) und (9,8), also der richtigen.
4. Iteration 2, Aktualisierung. Die Zentroide wandern auf (1,5, 1) und (8,5, 8). Die Summe der quadrierten Abstände fällt von 61,333 auf 1,0.
5. Iteration 3, Konvergenz. Die Zuordnungen ändern sich nicht mehr, die Zentroide ebenso wenig. Der Algorithmus hält an.

Die Konvergenz tritt nach zwei Iterationen ein, und die Summe der quadrierten Abstände fällt von 61,333 auf 1,0. Beachte, dass sich der Algorithmus von einer bewusst schlechten Initialisierung erholt hat, bei der beide Zentroide im selben echten Cluster lagen. Das ist nicht garantiert: bei anderen Daten kann eine solche Initialisierung dich in einem lokalen Minimum festhalten. Genau deshalb wählt k-means++ die Anfangszentren weit auseinander, und deshalb lohnt es sich, den Algorithmus mehrfach mit verschiedenen Initialisierungen laufen zu lassen.

Komplexität und woher sie kommt

Zeit: O(n · k · i · d) · Speicher: O(n + k·d)

Jede Iteration ordnet n Punkte zu, indem sie mit k Zentroiden in d Dimensionen verglichen werden, was O(n mal k mal d) ergibt, und der Aktualisierungsschritt durchläuft die Punkte noch einmal mit denselben Kosten. Bei i Iterationen ergibt das insgesamt O(n mal k mal i mal d). In der Praxis ist i meist klein, in der Größenordnung von Dutzenden, im schlechtesten Fall kann es jedoch superpolynomiell wachsen. Der Speicher besteht aus der Clusterzuordnung je Punkt plus den k Zentroiden. Das optimale Clustering nach quadrierter Abstandssumme zu finden ist selbst für k gleich 2 NP-schwer, der überall verwendete Lloyd-Algorithmus ist also eine Heuristik: schnell und praktisch gut, ohne Optimalitätsgarantie.

Wann K-Means Logistik-Clustering passt und wann nicht

Wähle danach, welche Clusterform du erwartest und ob dir k vorab bekannt ist.

Häufige Fehler

• Zufällig initialisieren ohne k-means++. Eine schlechte Initialisierung kann gegen ein deutlich schlechteres lokales Minimum konvergieren. K-means++ wählt die Anfangszentren mit einer Wahrscheinlichkeit proportional zum quadrierten Abstand zu den bereits gewählten, was sie auseinanderzieht und das erwartete Ergebnis bei minimalem Mehraufwand deutlich verbessert.
• Die Merkmale nicht normalisieren. K-Means nutzt euklidische Distanz, ein in Tausendern gemessenes Merkmal dominiert also eines zwischen 0 und 1. Unterscheiden sich die Skalen, normalisiere vor dem Clustern, sonst spiegeln die Cluster nur das Merkmal mit der größten Spannweite.
• k allein anhand der Fehlerquadratsumme wählen. Die Summe der quadrierten Abstände innerhalb der Cluster sinkt mit wachsendem k immer weiter, bis sie null erreicht, wenn k der Punktzahl entspricht. Nutze die Ellbogenmethode, den Silhouettenkoeffizienten oder die Gap-Statistik, nicht das absolute Minimum.
• Es auf nicht kugelförmige Cluster anwenden. K-Means zerlegt den Raum in Voronoi-Zellen und kann daher nur konvexe Grenzen erzeugen. Bei sichelförmigen oder ineinander geschachtelten Clustern scheitert es konstruktionsbedingt, gleich wie oft du es laufen lässt. DBSCAN oder spektrales Clustering sind dann die Alternativen.
• Es nur einmal ausführen. Da das Ergebnis von der Initialisierung abhängt, sagt ein einzelner Lauf nichts darüber aus, ob du in einem lokalen Minimum gelandet bist. Führe es mehrfach mit verschiedenen Startwerten aus und behalte den Lauf mit der kleinsten Fehlerquadratsumme.

Häufig gestellte Fragen

Was ist K-Means-Clustering?

K-Means teilt eine Punktmenge in k Cluster, indem es zwei Schritte abwechselt: jeden Punkt dem nächstgelegenen Zentroid zuordnen und danach jeden Zentroid auf den Mittelwert seiner zugeordneten Punkte verschieben. Das wiederholt sich, bis sich die Zuordnungen nicht mehr ändern, und minimiert dabei die Summe der quadrierten Abstände innerhalb der Cluster.

Wie ist die Zeitkomplexität von K-Means?

O(n mal k mal i mal d), wobei n die Punkte, k die Cluster, i die Iterationen und d die Dimensionen sind. In der Praxis liegt i meist im Bereich von Dutzenden. Das optimale Clustering nach quadrierter Abstandssumme zu finden ist selbst für k gleich 2 NP-schwer, der Standardalgorithmus ist also eine Heuristik ohne Optimalitätsgarantie.

Konvergiert K-Means immer?

Ja, es terminiert stets, denn jeder Schritt senkt die Summe der quadrierten Abstände innerhalb der Cluster oder hält sie gleich, und es gibt nur endlich viele mögliche Zuordnungen. Es konvergiert jedoch gegen ein lokales Minimum, nicht zwangsläufig gegen das globale, und welches es erreicht, hängt vollständig von der Initialisierung ab.

Warum ist die Initialisierung bei K-Means wichtig?

Weil der Algorithmus nur lokal von seinem Startpunkt aus verbessern kann. Schlecht platzierte Anfangszentren können ihn in einer deutlich schlechteren Aufteilung als der optimalen festhalten. K-means++ mildert das, indem es weit auseinanderliegende Anfangszentren wählt, und mehrere Läufe mit verschiedenen Startwerten samt Auswahl des besten sind gängige Praxis.

Wie wählt man den Wert von k?

Es gibt keine eindeutige Antwort. Die Ellbogenmethode trägt die Fehlerquadratsumme gegen k auf und sucht die Stelle, an der die Verbesserung abflacht. Der Silhouettenkoeffizient misst, wie gut die Cluster getrennt sind. Die Gap-Statistik vergleicht mit zufälligen Referenzdaten. Häufig überwiegt Fachwissen über die Domäne alle drei.