K-Means-Clustering — Algorithmus & Funktionsweise

K-Means-Clustering ist eine Methode, um numerische Daten in $k$ Cluster zu gruppieren. Wenn du $k$ festlegst und die übliche euklidische Variante verwendest, wiederholt der Algorithmus eine Schleife: Ordne jeden Punkt dem nächstgelegenen Zentrum zu und verschiebe dann jedes Zentrum zum Mittelwert der ihm zugeordneten Punkte.

Einfach gesagt versucht das Verfahren, Punkte innerhalb derselben Gruppe möglichst nah beieinander zu halten und Punkte aus verschiedenen Gruppen weiter voneinander zu trennen. Es ist schnell und nützlich, funktioniert aber nur dann gut, wenn diese „Gruppen“ einigermaßen kompakt sind und Distanz als Maß sinnvoll ist.

Was K-Means-Clustering optimiert

In der standardmäßigen euklidischen Form versucht K-Means, die Punkte innerhalb jedes Clusters möglichst nah an den Zentroiden dieses Clusters zu bringen. Eine häufige Zielfunktion ist

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Hier ist $C_j$ das $j$-te Cluster und $\mu_j$ sein Zentroid.

Das ist die Summe der quadrierten Abstände innerhalb der Cluster. Kleinere Werte bedeuten, dass die zugeordneten Punkte enger um ihre Zentroide liegen.

Diese Zielfunktion erklärt die zwei Teile des Algorithmus:

• Wenn die Zentroide fest sind, ist es am besten, jeden Punkt seinem nächstgelegenen Zentroiden zuzuordnen.
• Wenn die Zuordnungen fest sind, ist der beste Zentroid der Mittelwert der zugeordneten Punkte.

Deshalb ist die Aktualisierungsregel nicht willkürlich. Die „means“ in K-Means sind ganz wörtlich arithmetische Mittelwerte.

So funktioniert der K-Means-Algorithmus

Die übliche Schleife ist kurz:

1. Wähle $k$ anfängliche Zentroide.
2. Ordne jeden Punkt dem nächstgelegenen Zentroiden zu.
3. Berechne jeden Zentroiden als Mittelwert seiner zugeordneten Punkte neu.
4. Wiederhole das, bis sich die Zuordnungen nicht mehr ändern oder die Verbesserung sehr klein ist.

Dieser Prozess konvergiert meist schnell, aber nicht unbedingt zur bestmöglichen Clusterung. Unterschiedliche Start-Zentroide können zu unterschiedlichen Endergebnissen führen, deshalb ist die Initialisierung wichtig.

K-Means-Clustering: Beispiel Schritt für Schritt

Nimm diese eindimensionalen Datenpunkte:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Angenommen, wir wollen $k = 2$ Cluster und starten mit Zentroiden bei $1$ und $10$. Das ist ein gutes Beispiel, weil sich die Zentroide nach dem ersten Update tatsächlich verschieben.

Schritt 1: Punkte dem nächstgelegenen Zentroiden zuordnen

Die Punkte $1, 2, 3$ liegen näher bei $1$.

Die Punkte $10, 11, 12$ liegen näher bei $10$.

Also sind die Cluster

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Schritt 2: Die Zentroide aktualisieren

Der neue Zentroid des ersten Clusters ist

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Der neue Zentroid des zweiten Clusters ist

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Beide Zentroide haben sich verschoben: von $1$ auf $2$ und von $10$ auf $11$.

Schritt 3: Erneut zuordnen

Prüfe jetzt mit $2$ und $11$ noch einmal den nächstgelegenen Zentroiden.

Die Punkte $1, 2, 3$ gehören weiterhin zum ersten Cluster, und die Punkte $10, 11, 12$ weiterhin zum zweiten Cluster. Weil sich die Zuordnungen nicht mehr ändern, ist der Algorithmus konvergiert.

Das ist ein sauberes Beispiel, weil sich die Daten natürlich in zwei kompakte Gruppen aufteilen. Echte Datensätze sind unordentlicher, und genau dort kann K-Means irreführend werden.

Wann K-Means gut funktioniert

K-Means funktioniert am besten, wenn diese Bedingungen ungefähr erfüllt sind:

• Die Merkmale sind numerisch.
• Die euklidische Distanz ist ein sinnvolles Maß für Ähnlichkeit.
• Die Cluster sind relativ kompakt, nicht langgezogen oder gekrümmt.
• Die Merkmale wurden skaliert, sodass nicht eine Variable alle anderen dominiert.

Wenn diese Bedingungen nicht erfüllt sind, kann das Ergebnis trotzdem ordentlich aussehen und dabei die eigentliche Struktur der Daten verfehlen.

Häufige Fehler bei K-Means

K-Means als universelle Clustering-Methode behandeln

K-Means funktioniert am besten, wenn Cluster einigermaßen kompakt sind und der Mittelwert eine sinnvolle Zusammenfassung ist. Es ist keine gute Standardwahl für jeden Datensatz.

Merkmals-Skalierung ignorieren

Wenn ein Merkmal auf einer viel größeren Skala gemessen wird als ein anderes, kann dieses Merkmal die Distanzberechnung dominieren. Das Standardisieren oder Normalisieren von Merkmalen ist vor dem Ausführen von K-Means oft wichtig.

Annehmen, dass die Antwort eindeutig ist

K-Means kann von unterschiedlichen Startpunkten aus zu verschiedenen lokalen Minima konvergieren. Deshalb werden häufig mehrere Durchläufe oder Verfahren wie die Initialisierung mit k-means++ verwendet.

Nichtnumerische oder schlecht kodierte Merkmale verwenden

Weil Zentroide Mittelwerte sind, ist das Standard-K-Means für numerische Variablen gedacht. Wenn ein Merkmal kategorial ist, ergibt ein arithmetischer Mittelwert möglicherweise keinen Sinn.

Einsatz bei stark nicht kugelförmigen Clustern

Wenn die echten Gruppen langgezogen, gekrümmt oder in ihrer Dichte sehr ungleich sind, kann K-Means eine natürliche Gruppe aufspalten oder zwei verschiedene zusammenfassen. Das Verfahren bevorzugt kompakte, zentroidbasierte Cluster.

Vergessen, dass Ausreißer Zentroide verschieben können

Weil Zentroide Mittelwerte sind, können extreme Werte sie deutlich verschieben. Wenn Ausreißer in deinen Daten wichtig sind, solltest du das prüfen, bevor du dem Ergebnis vertraust.

Wo K-Means-Clustering eingesetzt wird

K-Means wird oft für explorative Gruppierung, Kunden- oder Verhaltenssegmentierung, Farbquantisierung in Bildern und als schnelle Baseline im unüberwachten Lernen verwendet.

Am nützlichsten ist es, wenn du numerische Merkmale hast, ein schnelles einfaches Modell möchtest und Cluster erwartest, die im euklidischen Raum ungefähr kompakt sind.

Ein einfaches mentales Modell

Stell dir vor, du setzt $k$ verschiebbare Stecknadeln auf ein Streudiagramm. Jeder Punkt hängt sich an die nächstgelegene Stecknadel. Dann gleitet jede Stecknadel zur durchschnittlichen Position der Punkte, die an ihr hängen. Wiederhole das, bis sich die Stecknadeln kaum noch bewegen.

Dieses Bild ist nicht nur eine Intuition. Es ist fast schon der ganze Algorithmus.

Probiere ein ähnliches Clustering-Problem aus

Nimm eine kleine Menge von Punkten auf einer Zahlengeraden, wähle $k = 2$ und führe einen vollständigen Zuordnungs- und Aktualisierungszyklus von Hand aus. Ändere dann die Start-Zentroide oder füge einen Ausreißer hinzu und beobachte, wie sich das Ergebnis verändert. Wenn du noch einen Schritt weitergehen willst, probiere deine eigene Variante mit einem kleinen Datensatz aus und vergleiche, was vor und nach der Merkmals-Skalierung passiert.