K-Means im großen Maßstab: Wo er scheitert und was kommt

K-Means ist der Algorithmus, den jeder im Einführungskurs zu Machine Learning lernt und danach für den Rest seiner Karriere falsch einsetzt. Er wirkt trügerisch einfach: K Cluster-Zentren wählen, jeden Punkt dem nächsten Zentrum zuordnen, die Zentren auf den Mittelwert ihrer Punkte verschieben und das wiederholen. Drei Zeilen Pseudocode. Das Problem ist, dass diese Einfachheit eine Reihe von Fallstricken verbirgt, die hochgehen, sobald man den Algorithmus auf echte Daten im großen Maßstab anwendet.

Bei 10.000 Punkten ist K-Means in Millisekunden fertig, und niemand macht sich Gedanken über Implementierungsdetails. Bei 10 Millionen Punkten ändert die Wahl der Initialisierungsmethode die Laufzeit um den Faktor 100. Bei 1 Milliarde Punkten passt der Standardalgorithmus nicht mehr in den Speicher, und man braucht grundlegend andere Ansätze. Ein aktuelles Paper zu Flash-KMeans nimmt genau das in Angriff: Es erreicht exakte K-Means-Ergebnisse mit deutlich weniger Speicher und schnellerer Konvergenz. Schauen wir uns an, was K-Means im großen Maßstab so schwierig macht und wie moderne Varianten das lösen.

Was der Standard-K-Means tatsächlich tut

Lloyds Algorithmus, also das, was die meisten meinen, wenn sie „K-Means“ sagen, besteht pro Iteration aus zwei Schritten. Im Zuordnungsschritt berechnet man für jeden Datenpunkt die Distanz zu allen K Zentroiden und ordnet ihn dem nächstgelegenen zu. Im Aktualisierungsschritt wird jedes Zentroid als Mittelwert aller ihm zugeordneten Punkte neu berechnet.

import numpy as np
def kmeans_lloyd(X, K, max_iter=100):
n, d = X.shape
# Random initialization (bad, but we'll fix this later)
centroids = X[np.random.choice(n, K, replace=False)]
for _ in range(max_iter):
# Assignment: O(n * K * d) — this is the bottleneck
distances = np.linalg.norm(X[:, None] - centroids[None, :], axis=2)
labels = np.argmin(distances, axis=1)
# Update: O(n * d)
new_centroids = np.array([
X[labels == k].mean(axis=0) for k in range(K)
])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids

Der Zuordnungsschritt kostet O(n × K × d) pro Iteration, wobei n die Anzahl der Punkte, K die Anzahl der Cluster und d die Dimensionalität ist. Bei n = 1 Milliarde, K = 1000 und d = 128 (ein realistisches Szenario beim Clustering von Embeddings) sind das 128 Billionen Gleitkommaoperationen pro Iteration. Selbst bei einem Teraflop Rechenleistung dauert das 128 Sekunden pro Iteration, und K-Means braucht typischerweise 10 bis 50 Iterationen bis zur Konvergenz.

Das Initialisierungsproblem

Bevor K-Means auch nur eine Iteration ausführt, muss er die Startpositionen der Zentroide wählen. Diese Wahl ist weitaus wichtiger, als die meisten glauben. Eine schlechte Initialisierung kann zu einer Lösung führen, die beliebig viel schlechter ist als das Optimum.

Zufällige Initialisierung (K zufällige Datenpunkte als Start-Zentroide wählen) ist simpel, aber unzuverlässig. Landen zwei Start-Zentroide zufällig im selben Cluster, bleibt ein anderer Cluster unrepräsentiert. Der Algorithmus konvergiert trotzdem, aber zu einer suboptimalen Lösung. Bei K = 100 ist die Wahrscheinlichkeit für mindestens eine solche Kollision hoch.

K-Means++ (Arthur und Vassilvitskii, 2007) ist die Standardlösung dafür. Das erste Zentroid wird zufällig gewählt, jedes weitere mit einer Wahrscheinlichkeit, die proportional zur quadrierten Distanz zum nächsten bereits vorhandenen Zentroid ist. Punkte, die weit von allen bestehenden Zentroiden entfernt liegen, werden also eher gewählt, wodurch sich die Startzentroide über die Daten verteilen. Das liefert eine Approximationsgarantie von O(log K): Die Lösung liegt nachweislich innerhalb des Faktors O(log K) vom Optimum.

def kmeans_plus_plus_init(X, K):
n, d = X.shape
centroids = [X[np.random.randint(n)]]
for _ in range(1, K):
# Distance from each point to nearest existing centroid
dists = np.min([
np.sum((X - c) ** 2, axis=1) for c in centroids
], axis=0)
# Sample proportional to distance squared
probs = dists / dists.sum()
next_idx = np.random.choice(n, p=probs)
centroids.append(X[next_idx])
return np.array(centroids)

Der Haken: Die K-Means++-Initialisierung selbst kostet O(n × K × d), sie braucht also K Durchgänge durch den gesamten Datensatz. Bei großem K und großem n dauert die Initialisierung länger als mehrere Iterationen von Lloyds Algorithmus. Skalierbare Varianten wie k-Means|| (Bahmani et al., 2012) reduzieren die Zahl der Durchgänge, indem sie parallel mehr Kandidaten überabtasten und diese anschließend zu K Zentroiden zusammenfassen.

Die Speicherwand

Standard-K-Means benötigt den gesamten Datensatz gleichzeitig im Speicher. Für den Zuordnungsschritt muss man auf jeden Datenpunkt zugreifen und ihn mit jedem Zentroid vergleichen. Bei 1 Milliarde 128-dimensionalen float32-Vektoren belegen allein die Daten 512 GB, mehr, als die meisten Einzelrechner haben.

Die naheliegende Lösung ist Mini-Batch-K-Means: Bei jeder Iteration zieht man eine zufällige Teilmenge der Punkte und aktualisiert die Zentroide anhand dieser Stichprobe. Das funktioniert, konvergiert aber langsamer und zu einer etwas anderen, meist leicht schlechteren Lösung als exaktes K-Means. Für viele Anwendungen ist der Qualitätsverlust akzeptabel. Für andere, etwa Quantisierungs-Codebücher bei der Vektorsuche, fällt der Qualitätsunterschied dagegen ins Gewicht.

Flash-KMeans geht einen anderen Weg. Statt den gesamten Datensatz im Speicher zu verarbeiten, nutzt er einen Streaming-Durchlauf mit intelligentem Caching. Die zentrale Erkenntnis: Die meisten Punkte wechseln zwischen den Iterationen nicht ihren Cluster. Liegt ein Punkt eindeutig in Cluster 7 (deutlich näher an Zentroid 7 als an jedem anderen), ist es verschwendete Arbeit, alle K Distanzen zu prüfen. Indem Flash-KMeans Distanzgrenzen speichert, kann er bei den meisten Punkten in den meisten Iterationen die vollständige Distanzberechnung überspringen.

Optimierungen mit der Dreiecksungleichung

Elkans Algorithmus (2003) nutzt die Dreiecksungleichung, um unnötige Distanzberechnungen zu vermeiden. Sie besagt: Der Abstand von Punkt P zu Zentroid A ist höchstens so groß wie der Abstand von P zu Zentroid B plus der Abstand von B zu A. Wenn man weiß, dass P aktuell Zentroid B zugeordnet ist, und den Abstand zwischen A und B kennt, lässt sich manchmal beweisen, dass A zu weit von P entfernt ist, ganz ohne die tatsächliche Distanz zu berechnen.

In der Praxis entfallen so nach den ersten Iterationen 80 bis 95 Prozent der Distanzberechnungen, denn dann liegen die meisten Punkte bereits nahe an ihrem richtigen Zentroid. Die verbleibenden Berechnungen betreffen nur Punkte nahe den Cluster-Grenzen, also die einzigen, die tatsächlich ihre Zuordnung ändern könnten.

Der Haken: Elkans Algorithmus benötigt zusätzlich O(n × K) Speicher für die Distanzgrenzen (untere Schranken von jedem Punkt zu jedem Zentroid sowie obere Schranken zum zugeordneten Zentroid). Bei großem K kann dieser Speicherbedarf erheblich werden. Hamerlys Algorithmus reduziert ihn auf O(n), indem er pro Punkt nur eine einzige untere Schranke speichert. Dafür werden allerdings weniger Berechnungen eingespart.

GPU-Beschleunigung

K-Means ist im Zuordnungsschritt geradezu ideal parallelisierbar, denn die Distanzberechnung jedes Punktes ist unabhängig von den anderen. Damit eignet er sich hervorragend für GPU-Beschleunigung. NVIDIAs cuML-Bibliothek und Facebooks FAISS enthalten beide GPU-Implementierungen von K-Means, die bei großen Datensätzen eine 10- bis 50-fache Beschleunigung gegenüber CPU-Implementierungen erreichen.

Der Haken ist der begrenzte GPU-Speicher. Eine A100 hat 80 GB, das reicht für etwa 150 Millionen 128-dimensionale Vektoren. Größere Datensätze erfordern entweder eine Aufteilung auf mehrere GPUs oder einen Streaming-Ansatz, bei dem die Daten in Blöcken geladen, auf der GPU verarbeitet und auf der CPU zusammengeführt werden.

# Using FAISS for GPU-accelerated k-means
import faiss
import numpy as np
# 10 million 128-dimensional vectors
n, d, K = 10_000_000, 128, 1000
X = np.random.randn(n, d).astype('float32')
# CPU k-means (for comparison)
kmeans_cpu = faiss.Kmeans(d, K, niter=20, verbose=True)
kmeans_cpu.train(X)  # ~120 seconds
# GPU k-means (single GPU)
kmeans_gpu = faiss.Kmeans(d, K, niter=20, verbose=True, gpu=True)
kmeans_gpu.train(X)  # ~8 seconds — 15x faster

Wann K-Means die falsche Wahl ist

Bevor du deine K-Means-Implementierung optimierst, prüfe, ob K-Means überhaupt der richtige Algorithmus ist. Er trifft starke Annahmen, die auf viele reale Datensätze nicht zutreffen.

• Kugelförmige Cluster. K-Means setzt voraus, dass Cluster ungefähr kugelförmig und gleich groß sind. Sind deine Cluster länglich, unregelmäßig geformt oder sehr unterschiedlich groß, zerteilt K-Means große Cluster und fasst kleine zusammen. Gaussian Mixture Models (GMMs) kommen mit elliptischen Clustern zurecht, DBSCAN mit beliebigen Formen.
• Bekanntes K. Die Anzahl der Cluster muss im Voraus festgelegt werden. Kennst du K nicht, musst du K-Means mit verschiedenen Werten mehrfach ausführen und mit einer Metrik (Silhouetten-Score, Ellbogenmethode) den besten auswählen. Dadurch vervielfacht sich der Rechenaufwand um die Anzahl der getesteten K-Werte.
• Euklidische Distanz. K-Means verwendet standardmäßig die euklidische Distanz. Bei Text-Embeddings ist meist die Kosinus-Ähnlichkeit passender. Man kann das umgehen, indem man die Vektoren L2-normalisiert (dann entspricht die euklidische Distanz der Kosinus-Distanz), aber das vergisst man leicht.
• Ausreißer-Empfindlichkeit. Ein einzelner Ausreißer weit entfernt von allen Clustern zieht das zugeordnete Zentroid in seine Richtung. Robuste Varianten wie k-Medoids (das statt des Mittelwerts den Median verwendet) gehen besser mit Ausreißern um, sind aber teurer.

Praktische Tipps

Nachdem ich K-Means auf Datensätzen mit Tausenden bis Milliarden Punkten eingesetzt habe, sind dies die Punkte, die meiner Erfahrung nach am meisten zählen:

1. Immer K-Means++ zur Initialisierung verwenden. Zufällige Initialisierung ist das Risiko nie wert. Der Unterschied in der finalen Cluster-Qualität beträgt oft 10 bis 30 Prozent, und K-Means++ verursacht bei kleinem bis mittlerem K kaum Mehraufwand.
2. Mehrfach ausführen. K-Means findet ein lokales Optimum, kein globales. Führe ihn 5- bis 10-mal mit unterschiedlichen Zufallsstartwerten aus und nimm das beste Ergebnis (die geringste Gesamtdistanz innerhalb der Cluster). Das ist eine günstige Versicherung gegen schlechte Läufe.
3. Features normalisieren. Hat ein Feature den Wertebereich [0, 1000000] und ein anderes [0, 1], dominiert das Feature mit dem großen Wertebereich die Distanzberechnung. Standardisiere (Mittelwert abziehen, durch die Standardabweichung teilen) oder skaliere die Werte per Min-Max-Normalisierung, bevor du clusterst.
4. Für großskaliges Clustering FAISS verwenden. Bei mehr als einer Million Punkten ist die K-Means-Implementierung von scikit-learn langsam. FAISS ist stark optimiert und unterstützt GPU-Beschleunigung direkt ohne Zusatzaufwand.
5. Für explorative Arbeit Näherungsverfahren erwägen. Mini-Batch-K-Means ist etwa zehnmal schneller als exaktes K-Means und liefert meist gut genug Ergebnisse zum Erkunden. Für Produktiv-Clustering, bei dem es auf die Qualität ankommt, nimm exaktes K-Means.

K-Means ist einer dieser Algorithmen, die leicht zu benutzen, schwer richtig einzusetzen und es wert sind, gründlich verstanden zu werden. Der Unterschied zwischen einer naiven und einer optimierten Implementierung, sowohl bei der Geschwindigkeit als auch bei der Ergebnisqualität, ist enorm. Im kleinen Maßstab spielt das alles keine Rolle. Dort, wo es darauf ankommt, entscheidet das Verständnis von Initialisierung, Speicherverwaltung, Distanz-Pruning und GPU-Beschleunigung darüber, ob das Clustering Stunden oder Minuten dauert.