K-Means Clustering

K-Means-Clustering ist ein Algorithmus für unüberwachtes Lernen, der Daten in k Gruppen aufteilt. Jede Gruppe wird durch ihren Zentroiden repräsentiert, also den Mittelwert der ihr zugeordneten Punkte. Gesucht wird die Aufteilung mit der kleinsten Summe der quadrierten Abstände innerhalb der Cluster, dem sogenannten Trägheitsmaß. Die Punkte eines Clusters liegen dadurch nahe an seinem Zentroiden. Das Standardverfahren ist der Algorithmus von Lloyd, den Stuart Lloyd 1957 bei Bell Labs zur Quantisierung von Signalen entwickelte. Der Name „k-means“ stammt aus einem Aufsatz von James MacQueen aus dem Jahr 1967. Da k-means einfach, schnell und auf Millionen von Punkten skalierbar ist, wird es standardmäßig für Data Mining, Komprimierung und die Untersuchung der Struktur unbeschrifteter Daten eingesetzt.

Funktionsweise des Algorithmus#

Nach der Wahl der Startzentroiden wechselt Lloyds Algorithmus zwischen einem Zuordnungsschritt und einem Aktualisierungsschritt, bis sich die Cluster nicht mehr ändern:

1. Initialisierung: Wähle k Startzentroiden. Die Standardeinstellung von Scikit-learn, k-means++, wählt den ersten Zentroiden zufällig aus. Jeder weitere wird mit einer Wahrscheinlichkeit ausgewählt, die proportional zum quadrierten Abstand vom nächstgelegenen bereits gewählten Zentroiden ist. Dadurch werden die Startpunkte weiter auseinander verteilt.
2. Zuordnung: Weise jeden Punkt seinem nächstgelegenen Zentroiden zu, üblicherweise anhand der euklidischen Distanz.
3. Aktualisierung: Verschiebe jeden Zentroiden zum Mittelwert der ihm nun zugeordneten Punkte.
4. Wiederholen: Kehre zum Zuordnungsschritt zurück, bis kein Punkt mehr das Cluster wechselt oder sich die Zentroiden um weniger als einen Toleranzwert verschieben.

Keiner der beiden Schritte kann die Trägheit erhöhen, daher konvergiert die Schleife immer. Sie endet jedoch nur in einem lokalen Minimum, das von den Startzentroiden abhängt. Das globale Optimum zu finden ist NP-schwer. Deshalb führen Implementierungen mehrere Initialisierungen aus und behalten diejenige mit der geringsten Trägheit bei. In scikit-learn's KMeans wird n_init="auto" standardmäßig einmal ausgeführt, wenn k-Means++ zur Initialisierung verwendet wird, und zehnmal bei zufälliger Initialisierung.

Die Anzahl der Cluster wählen#

Bei k-means muss k im Voraus festgelegt werden. Das Trägheitsmaß sinkt immer, wenn k steigt, da mehr Zentroiden näher an den Punkten liegen. Bei der Ellbogenmethode wird daher das Trägheitsmaß gegen k aufgetragen und nach dem Punkt gesucht, an dem der Rückgang abflacht. Der Silhouettenwert vergleicht für jeden Punkt den mittleren Abstand zum eigenen Cluster mit dem mittleren Abstand zum nächstgelegenen anderen Cluster. Er reicht von -1 bis 1; höhere Werte stehen für kompakte, klar getrennte Cluster. In diesem Beispiel werden für Daten, die um vier Zentren herum generiert wurden, die Werte für k von 2 bis 6 berechnet:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

Das Trägheitsmaß sinkt von 18.363 bei k=2 auf 5.241 bei k=3 und 1.127 bei k=4, danach nur noch auf 1.039 bei k=5 und 922 bei k=6. Der Ellbogen liegt somit bei k=4. Der Silhouettenwert bestätigt das: Er erreicht bei k=4 mit 0,811 seinen Höchstwert und sinkt bei k=5 auf 0,687. Damit werden die vier Zentren wiedergefunden, um die herum die Daten generiert wurden.

Annahmen und Varianten#

K-means eignet sich am besten für Cluster, die ungefähr kugelförmig, ähnlich groß und im euklidischen Raum voneinander getrennt sind. Merkmale mit größeren Skalen beeinflussen die Distanz stärker, daher werden die Daten üblicherweise zuerst standardisiert. Jeder Punkt wird einem Cluster zugeordnet, und einige extreme Ausreißer können einen Zentroiden von seiner Gruppe wegziehen. Mehrere Varianten lockern diese Einschränkungen:

• Mini-Batch-k-means: Aktualisiert Zentroiden anhand kleiner, zufälliger Batches. Bei großen Datensätzen wird dadurch etwas Genauigkeit gegen eine deutlich schnellere Trainingszeit eingetauscht.
• K-Medoids: Verwendet tatsächliche Datenpunkte als Clusterzentren. Dadurch ist das Verfahren robuster gegenüber Ausreißern und funktioniert mit jedem Distanzmaß.
• Fuzzy-c-means: Weist jedem Punkt für jedes Cluster einen Zugehörigkeitsgrad zu, ähnlich wie bei der Fuzzy-Logik, statt ihn nur einem Cluster zuzuordnen.
• Gaußsche Mischmodelle: Passen für jedes Cluster eine Wahrscheinlichkeitsverteilung an. Dadurch sind elliptische Cluster unterschiedlicher Größe möglich, und die Zuordnungen werden als Wahrscheinlichkeitsverteilungen ausgegeben.

Anwendungen in KI und maschineller Bildverarbeitung#

• Farbquantisierung: Beim Clustern der Pixel einer Bildes nach ihren Farben und Ersetzen jedes Pixels durch den Schwerpunkt seines Clusters wird ein Foto mit Tausenden von Farben auf eine Palette mit k Farben reduziert. Dadurch wird das Bild komprimiert und zugleich eine schnelle, grobe Form der Bildsegmentierung ermöglicht.
• Codebücher und Vektorquantisierung: Die Schwerpunkte bilden ein Codebuch, und jeder Vektor wird als Index seines nächstgelegenen Schwerpunkts gespeichert. Bei der klassischen Bildsuche mit dem Bag-of-Visual-Words-Verfahren wurden die Vokabulare auf diese Weise aus lokalen Bildmerkmalen erstellt.
• Entwurf von Ankerboxen: YOLOv2 führte k-means auf den Breiten und Höhen der Trainingsboxen aus und verwendete 1 minus IoU als Abstand, um die Ankerboxen auszuwählen.
• Gewichtspalettierung: Beim Exportieren von YOLO26 nach Core ML mit quantize=8 werden die Werte jedes großen Gewichtstensors mithilfe von k-means zu 256 Schwerpunkten gruppiert. Dadurch speichert das exportierte Modell pro Gewicht einen 8-Bit-Index sowie eine kleine Nachschlagetabelle.
• Kundensegmentierung: Einzelhändler gruppieren Kundinnen und Kunden anhand von Kaufhäufigkeit, Warenkorbgröße und Aktualität der letzten Bestellung, um Angebote auf die einzelnen Segmente zuzuschneiden.

K-Means und verwandte Algorithmen#

• K-nächste Nachbarn (KNN): Das gemeinsame „k“ sorgt für Verwirrung. KNN ist ein überwachter Algorithmus, der einen neuen Punkt anhand seiner k nächsten beschrifteten Beispiele klassifiziert. k-means ist dagegen unüberwacht, und k bezeichnet die Anzahl der erzeugten Cluster.
• DBSCAN: Gruppiert Punkte nach ihrer Dichte, ermittelt die Anzahl der Cluster selbst, erkennt Cluster beliebiger Form und kennzeichnet dünn besetzte Punkte als Rauschen, statt sie einem Cluster zuzuordnen.
• Hierarchisches Clustering: Erstellt einen Baum verschachtelter Cluster, indem wiederholt die jeweils nächstgelegenen Gruppen zusammengeführt werden. So lässt sich k nachträglich durch einen Schnitt auf beliebiger Ebene des Baums auswählen. Dafür steigen die Kosten mindestens quadratisch mit der Anzahl der Punkte.