k-Means-Algorithmus: Ablauf, Beispiel und Grenzen

k-Means gehört zum unüberwachten Lernen. Das ist maschinelles Lernen ohne im Voraus bekannte Zielwerte. Es gibt also keine Musterlösung, an der sich der Algorithmus orientiert. Er sucht in den Daten selbst nach Gruppen von ähnlichen Objekten. Solche Gruppen heißen Cluster.

Eines musst du vorher festlegen: die Zahl k der Gruppen. Der Algorithmus bildet dann aus den Objekten genau k Cluster. Jedes Objekt gehört dabei zu genau einem Cluster. Das Ziel ist, dass die Summe der quadrierten Abweichungen von den Cluster-Mittelpunkten möglichst klein wird.

Die Objekte werden als Punkte dargestellt. Ihre Eigenschaften sind die Koordinaten der Punkte. k-Means rechnet mit Mittelwerten und braucht deshalb Zahlen. Kategorien wie „Auto“, „LKW“ und „Fahrrad“ gehen nicht, weil man daraus keinen Mittelwert bilden kann. Was die gefundenen Gruppen bedeuten, sagt der Algorithmus nicht. Das muss man danach separat untersuchen.

k-Means arbeitet in Runden. Vorher gibt es einen Start: Im häufigsten Verfahren wählst du k zufällige Punkte aus den Daten als erste Mittelpunkte. Je nach Programm kann der Start auch anders ablaufen.

Dann wiederholst du zwei Schritte. Beim Zuordnen kommt jeder Punkt in den Cluster, dessen Mittelpunkt ihm am nächsten liegt. Gemessen wird mit dem euklidischen Abstand. Auf einer Zahlengeraden ist das einfach der Abstand zwischen den Zahlen, also der Betrag der Differenz. Zwischen 3 und 8 sind es 5.

Beim Aktualisieren berechnest du für jeden Cluster den Mittelpunkt neu. Er ist der Mittelwert aller Punkte im Cluster: Summe der Punkte geteilt durch ihre Anzahl. Liegen die Punkte 2 und 4 im Cluster, ist der neue Mittelpunkt (2 + 4) : 2 = 3.

Das Ganze wiederholst du, bis sich die Zuordnungen nicht mehr ändern. Weil sich die Mittelpunkte verschieben, können Punkte dabei ihren Cluster wechseln. Die Musteraufgabe weiter unten rechnet das mit sechs ausgedachten Punkten durch.

Startpunkte: Die Startpunkte werden zufällig gewählt. Die gefundene Lösung hängt stark von ihnen ab, und k-Means muss nicht die beste mögliche Lösung finden. Der einfachste Ansatz ist, den Algorithmus mehrmals mit verschiedenen Startwerten zu starten und die beste Lösung zu nehmen. Das Verfahren k-Means++ versucht, bessere Startpunkte zu finden.

Wahl von k: Bei einem ungeeigneten k können sich komplett andere, unter Umständen unintuitive Lösungen ergeben. Bei einem „falschen“ k kann kein gutes Clustering erfolgen. Deshalb probierst du verschiedene Werte für k aus und wählst dann ein geeignetes. Das geht zum Beispiel mit dem Silhouettenkoeffizienten, einer Maßzahl für die Qualität eines Clusterings, oder durch Vergleich der Clusteringkosten. Beachte: Die Kosten sinken mit steigendem k monoton. Der Silhouettenkoeffizient ist dagegen von k unabhängig. Damit kann man auch Ergebnisse vergleichen, die mit verschiedenen k entstanden sind.

Ausreißer: k-Means ordnet jeden Punkt einem Cluster zu und kann Ausreißer nicht erkennen. Sie können das Ergebnis stark verfälschen. Fehlerhafte Datenobjekte verschieben die Mittelpunkte oft erheblich. Ausgedachtes Beispiel: Ein Cluster hat die Punkte 1, 2 und 3 mit dem Mittelwert 2. Kommt der Punkt 50 dazu und liegt im selben Cluster, ist der Mittelwert (1 + 2 + 3 + 50) : 4 = 14. Der Mittelpunkt liegt dann weit weg von den drei anderen Punkten.

Bevor du einen Ausreißer aussortierst, prüfst du, ob er ein verlässliches, echtes Ergebnis ist oder ein Messfehler. Abhilfe kann eine vorherige Noisereduktion (Rauschen verringern) schaffen oder ein anderer Algorithmus wie DBSCAN, der Noise automatisch erkennt.