🎯 K-Means-Clustering — Lloyds Algorithmus

Initialisieren Sie k Zentroiden (zufällig oder per k-means++). Weisen Sie jeden Datenpunkt anhand der euklidischen Distanz dem nächsten Zentroiden zu. Berechnen Sie jeden Zentroiden neu als mittlere Position aller zugewiesenen Punkte. Wiederholen Sie Zuweisung und Aktualisierung, bis kein Punkt mehr zwischen Iterationen den Cluster wechselt (Konvergenz). Führen Sie den Vorgang mehrfach mit unterschiedlichen Initialisierungen durch und behalten Sie das Ergebnis mit dem niedrigsten WCSS.

Die Ellbogenmethode stellt WCSS gegen Werte von k dar; das optimale k liegt am Knick (Ellbogen), an dem zusätzliche Cluster nur noch geringe Verbesserungen bringen. Der Silhouettenkoeffizient misst, wie gut jeder Punkt zu seinem Cluster passt im Vergleich zu benachbarten Clustern (Bereich -1 bis +1; höher ist besser). Fachwissen liefert oft die beste Orientierung — ein Einzelhändler, der Kunden segmentiert, weiß zum Beispiel vielleicht, dass er 5 Kundenpersonas möchte.

K-means geht von kugelförmigen Clustern ähnlicher Größe und Dichte aus und hat Schwierigkeiten mit länglichen, unregelmäßigen oder verschachtelten Clustern. Es reagiert empfindlich auf Ausreißer (die Zentroiden vom Großteil der Daten wegziehen können) und auf die Wahl von k. Es verwendet die euklidische Distanz und eignet sich daher ohne Vorverarbeitung nicht für kategoriale Daten. Algorithmen wie DBSCAN, Gaußsche Mischmodelle oder hierarchisches Clustering beheben einige dieser Einschränkungen.

K-means++ verbessert die Wahl der Anfangszentroiden, um schlechte Startkonfigurationen zu vermeiden. Der erste Zentroid wird zufällig gewählt. Jeder weitere Zentroid wird mit einer Wahrscheinlichkeit proportional zum quadrierten Abstand zum nächsten bereits gewählten Zentroiden ausgewählt, sodass die Zentroiden von Anfang an gut getrennt und über die Daten verteilt sind. Das führt in der Regel zu einer besseren endgültigen Clusterqualität und schnellerer Konvergenz als eine rein zufällige Initialisierung.

Bei der Bildkompression behandelt k-means die RGB-Farbe jedes Pixels als 3D-Datenpunkt und gruppiert alle Pixel in k Farbgruppen. Jedes Pixel wird dann durch die Zentroidfarbe seines Clusters ersetzt, wodurch das Bild auf eine Palette von k Farben reduziert wird. Bei k=16 wird ein 24-Bit-Farbbild mit nur 4 Bit pro Pixel plus einer 16-Farben-Nachschlagetabelle angenähert — eine erhebliche Kompression bei mäßigem Qualitätsverlust.