K-Means Clustering

Unsupervised learning without labels

When you have points in space without any ground truth labels, you can still find structure by alternating between two straightforward steps.

First, you pick $k$ random starting locations, called centroids.

Then, you repeat these two steps:

1. Assign each point to the centroid nearest to it.
2. Recentre each centroid to the mean of all points assigned to it.

This process is called k-means clustering.

Why it always stops

Every time you assign points, the total distance from points to their centroids (the inertia) must go down or stay the same. Every time you recentre a centroid to the mean of its points, the inertia also goes down or stays the same, because the mean is exactly the spot that minimises squared distance.

Since inertia can never drop below zero and both steps only ever reduce it, the algorithm is mathematically guaranteed to stop moving. It converges.

More precisely, it reaches a fixed point: a state where no point would switch cluster and no centre would move. The lab tests for exactly that, which is why the Step button disappears at the same moment the readout says Converged.

The trap of local minima

Convergence just means it stopped. It does not mean it found the "true" clusters.

Because k-means is deterministic once the initial seeds are placed, everything depends on where those first centroids land. If you seed two centroids inside what looks like one natural cluster, they will carve it in half and merge two others into one. The algorithm will happily report that it converged cleanly.

On the lab's dataset this happens at exactly four of the forty starting positions. Those four runs settle at an inertia between 185.5 and 223.4, against 42.3 for the other thirty-six — four to five times worse, reached in the same two to four iterations, with nothing in the run itself to flag it.

How you find out, without labels

You cannot inspect the answer, because there is no answer to inspect. What you can do is run the algorithm again from a different start and compare.

That is the whole content of the n_init parameter in a real implementation: fit the model several times, keep the one with the lowest inertia, discard the rest. Ten restarts is a common default, and on a dataset where one start in ten goes wrong it is enough to make a bad result unlikely rather than merely unlucky.

The lab shows the best inertia reachable from any of its forty starting positions next to the current run's. That single comparison is the only evidence available that a converged run is a poor one.

Why inertia cannot choose k

It is tempting to pick $k$ by minimising inertia. It does not work, because inertia falls at every increase in $k$ — more centres means every point is nearer to one — and its minimum is the useless case where every point is its own cluster and inertia is zero.

Measured on this dataset, the best inertia at $k = 1$ through $6$ runs 392, 193, 42.3, 34.8, 29.4, 24.4. It never rises. What it does do is stop falling usefully: the drop into $k = 3$ is 150, and the drop out of it is 7. That change in slope is the elbow, and reading it is a judgement, not a computation.

This exposes the fundamental limit of unsupervised learning: it finds a mathematically stable answer, but you are the one who has to decide if it means anything.