K-Means ist ein Algorithmus des unüberwachten Lernens, der Datenpunkte in k Gruppen (Cluster) einteilt. Er gehört zur Familie des Clustering und arbeitet ohne vorgegebene Labels — die Gruppen ähneln sich innerhalb und unterscheiden sich zwischen den Clustern.
So funktioniert der Algorithmus
- Initialisierung: k zufällige Schwerpunkte (Centroids) werden gesetzt.
- Zuordnung: Jeder Datenpunkt wird dem nächstgelegenen Centroid zugeordnet (üblicherweise euklidischer Abstand).
- Neuberechnung: Jeder Centroid wandert in den Mittelpunkt (Mean) seiner zugeordneten Punkte.
- Wiederholung: Schritte 2 und 3 laufen, bis sich die Zuordnung nicht mehr ändert.
Das Ergebnis minimiert die Summe der quadrierten Abstände innerhalb der Cluster (Within-Cluster Sum of Squares). Weil die Start-Centroids zufällig liegen, kann der Algorithmus in lokale Optima laufen — die Variante k-means++ wählt die Startpunkte bewusst verteilt und ist heute Standard.
Wie viele Cluster (k)?
- Elbow-Methode: Die Fehlersumme wird für verschiedene k berechnet; der Knick in der Kurve zeigt ein sinnvolles k.
- Silhouette-Koeffizient: Misst, wie gut sich die Cluster trennen; Werte nahe 1 sind ideal.
- Fachwissen: Ist die erwartete Anzahl Gruppen bekannt (z. B. drei Kundentypen), wird sie direkt als k gesetzt.
Stärken und Grenzen
- Stärken: einfach, schnell, auch für große Datensätze geeignet.
- Grenzen: k muss vorgegeben werden; empfindlich gegenüber Ausreißern und unterschiedlich dichten Clustern; findet vor allem kugelförmige Gruppen.
Typische Anwendungen
Kundensegmentierung im Marketing, Farbquantisierung bei der Bildkompression, Dokument-Clustering in der Textsuche und Anomalie-Erkennung: Punkte weit entfernt von jedem Centroid fallen als Ausreißer auf.
K-Means arbeitet auf Datensätzen ohne Labels — das unterscheidet es vom Entscheidungsbaum, der gelabelte Beispiele aus dem überwachten Lernen benötigt. K-Means ist ein Vertreter des unüberwachten Lernens.