K-Means Clustering

k-means splits unlabelled data into k groups, each pinned to a centre. You give it k; it finds k blobs and summarises each one by its centroid — the mean of its members. The toy above lets you drag the seeds and watch the groups snap into place.

Where you meet it

Customer or user segmentation — splitting a population into a few archetypes.
Image colour quantisation and compression — replacing pixels with k representative colours.
Vector quantisation, document grouping, and a fast first pass before heavier models.
Anomaly hunting — points that sit far from every centroid look suspicious.

What it does

It is unsupervised: no labels, just points. k-means partitions the data so that points within a cluster are close together and far from the others. Formally it minimises the within-cluster sum of squares — scikit-learn calls this the inertia_ — the total squared distance from each point to its assigned centre.

k-means always converges — just not necessarily to the right answer. You pick the k, and it only ever sees round blobs.

How it works

The standard recipe is Lloyd's algorithm, which alternates two steps until things stop moving:

1. assign  — each point joins its nearest centroid (squared distance)
2. update  — each centroid moves to the mean of its assigned points
3. repeat  — until centroids stop moving (or max_iter is reached)

The assign step carves the plane into Voronoi cells — borders sit halfway between centres. The update step then pulls each centre to the middle of its cell. Every full round can only lower the inertia, so the algorithm is guaranteed to converge — but only to a local optimum, not necessarily the best one. In scikit-learn:

from sklearn.cluster import KMeans
km = KMeans(n_clusters=3, init="k-means++", n_init="auto").fit(X)
km.labels_      # cluster of each point
km.inertia_     # final within-cluster sum of squares

Watch out

You must pick k. It won't tell you the right number — use the elbow (inertia vs. k) or silhouette analysis to choose.
Init matters. A bad start traps it in a poor local optimum. k-means++ seeds centres far apart, and n_init runs it several times and keeps the lowest-inertia result.
It assumes round, similar-sized clusters. Inertia favours convex, isotropic blobs; elongated, nested, or very unequal groups break it.
Scale your features first. Distances are dominated by large-range columns — standardise before clustering.

Go deeper

k-Means teilt ungelabelte Daten in k Gruppen, jede an ein Zentrum geheftet. Du gibst k vor; es findet k Häufungen und fasst jede durch ihren Centroid zusammen — den Mittelwert ihrer Mitglieder. Im Tool oben kannst du die Seeds ziehen und zusehen, wie die Gruppen einrasten.

Wo es vorkommt

Kunden- oder Nutzer-Segmentierung — eine Population in wenige Archetypen aufteilen.
Farbquantisierung und Bildkompression — Pixel durch k repräsentative Farben ersetzen.
Vektorquantisierung, Dokument-Gruppierung und schneller erster Durchlauf vor schwereren Modellen.
Anomalie-Suche — Punkte weit von jedem Centroid wirken verdächtig.

Was es tut

Es ist unüberwacht: keine Labels, nur Punkte. k-Means partitioniert die Daten so, dass Punkte innerhalb eines Clusters nah beieinander und weit von den anderen liegen. Formal minimiert es die Within-Cluster-Quadratsumme — in scikit-learn die inertia_ — die Summe der quadrierten Distanzen jedes Punkts zu seinem zugewiesenen Zentrum.

k-Means konvergiert immer — nur nicht zwingend zur richtigen Antwort. Du gibst k vor, und es sieht ausschließlich runde Häufungen.

Wie es funktioniert

Das Standardrezept ist der Lloyd-Algorithmus, der zwei Schritte abwechselt, bis sich nichts mehr bewegt:

1. zuweisen — jeder Punkt geht zum nächsten Centroid (quadrat. Distanz)
2. updaten  — jeder Centroid wandert zum Mittel seiner Punkte
3. wiederh. — bis die Centroide stehen (oder max_iter erreicht ist)

Der Zuweisen-Schritt zerlegt die Ebene in Voronoi-Zellen — die Grenzen liegen mittig zwischen den Zentren. Der Update-Schritt zieht dann jedes Zentrum in die Mitte seiner Zelle. Jede volle Runde kann die Inertia nur senken, daher konvergiert das Verfahren garantiert — aber nur zu einem lokalen Optimum, nicht zwingend zum besten. In scikit-learn:

from sklearn.cluster import KMeans
km = KMeans(n_clusters=3, init="k-means++", n_init="auto").fit(X)
km.labels_      # Cluster jedes Punkts
km.inertia_     # finale Within-Cluster-Quadratsumme

Worauf achten

k musst du vorgeben. Das richtige k verrät es nicht — nutze die Elbow-Methode (Inertia über k) oder die Silhouetten-Analyse zur Wahl.
Die Initialisierung zählt. Ein schlechter Start landet in einem mäßigen lokalen Optimum. k-means++ setzt die Zentren weit auseinander, und n_init läuft es mehrfach und behält das Ergebnis mit der kleinsten Inertia.
Es nimmt runde, gleich große Cluster an. Die Inertia bevorzugt konvexe, isotrope Häufungen; langgezogene, verschachtelte oder sehr ungleiche Gruppen brechen es.
Erst die Features skalieren. Distanzen werden von großskaligen Spalten dominiert — vor dem Clustern standardisieren.