k-means: find groups nobody labelled

A shop has thousands of customers and no idea how they split into types. A photo has a million colours and you want a palette of eight. There are no labels to learn from, only points: you want the algorithm to find the groups itself.

k-means is the classic answer, and it fits in two lines: give every point to its nearest centre, then move every centre to the middle of its points. Repeat.

centroid

The centre of a cluster. k-means keeps $k$ of them, named C1, C2, …

assign step

Every point joins its nearest centroid. The shading shows each centroid's territory.

update step

Every centroid moves to the mean of the points that joined it.

inertia

The sum of squared distances from each point to its centroid: how tight the clusters are. Lower is better.

Both steps can only lower the inertia. Joining the nearest centroid can only shorten a point's distance, and the mean is exactly the spot with the smallest total squared distance to a group of points. A quantity that keeps falling and can't go below zero must settle, so k-means always stops, here after a few rounds.

But stopping isn't the same as finding the best answer:

Drag the centroids before the first step (or move them with the arrow keys) and watch the whole run change. Then try the other examples:

• Bad start: compare its final inertia with Three blobs: same points, much worse answer.
• k too big: four centroids for three blobs, so one blob is split in two.
• Pure noise: no real clusters, yet k-means still returns neat territories.
• Uneven sizes: the boundary sits halfway between the centroids, so a big, spread-out cluster loses points to a small one.

• k-means alternates two steps: assign each point to its nearest centroid, move each centroid to its mean.
• Inertia never rises, so it always stops, but possibly at a local optimum: use several starts or k-means++.
• It always finds $k$ clusters and prefers round, similar-sized ones; choosing $k$ is up to you.