Finding groups: k-means

Every lesson in this track so far has been Supervised learningLearning from examples that come with the right answer attached, such as photos labeled "cat" or houses with their sale prices.Open in glossary: examples come with the right answers, and the model learns to reproduce them. Often you have no answers at all. A shop has purchase histories but no labels saying which customers are alike. A biologist has measurements of thousands of cells but no list of cell types. The task is to find structure in the data itself. That is Unsupervised learningLearning from examples that have no answers attached, by finding structure such as groups or directions of variation in the data itself.Open in glossary, and the classic first method is k-meansA clustering method that places k centers, assigns every point to its nearest center, moves each center to the average of its points, and repeats until nothing changes.Open in glossary.

Two steps, repeated

You choose $k$ , the number of groups to look for. k-means places $k$ centers, then alternates two steps.

Assign. Every point joins the center nearest to it.
Update. Every center moves to the CentroidThe average position of a group of points. In k-means, each cluster is represented by its centroid.Open in glossary of its points, their average position.

Moving a center changes which points are nearest to it, so assign again, then update again, until an assignment step changes nothing. At that point the centers will never move again, and the algorithm has converged.

k-means, step by step

Nobody labeled these points. k-means looks for k groups by alternating two simple steps.

The centers start at randomly chosen data points. Next: assign every point to its nearest center.

Center moves0

Inertia (spread within clusters)n/a

Try this

Press Assign points, then Move centers, and keep alternating. Watch the dashed trails as the centers walk toward the middle of each blob.
Watch the inertia chart. It never goes up, not even for half a step.
Press New starting centers several times. Most starts find the three blobs, but with some, two centers end up sharing one blob while a single center covers two. Switch to k-means++ starts and compare.
Set k to 2 or 4 on the three blobs. k-means always returns exactly k groups, whether or not that many exist.
Try Stretched. The two horizontal stripes are obvious to you, but k-means cuts them into a left group and a right group.
Try No groups. k-means still confidently draws k regions in data with no clusters at all.

Why it always settles

k-means is quietly minimizing a loss, called inertia: the sum of squared distances from every point to its own center,

\text{inertia} = \sum_{i=1}^{n} \left\lVert x_i - c_{a(i)} \right\rVert^2

where $x_i$ is a point, $a(i)$ is the cluster it is assigned to, and $c_{a(i)}$ is that cluster’s center. The assign step can only lower this, because every point switches to a center at least as close. The update step can only lower it too, because the average is the single position that minimizes the sum of squared distances to a group of points. A quantity that never increases, with only finitely many ways to assign the points, must eventually stop changing.

Where it goes wrong

Settling is not the same as succeeding. The demo shows three different ways k-means can disappoint.

Bad starts. Like gradient descent, k-means only improves from where it starts, so it can settle in a Local minimumA point lower than everything around it but not necessarily the lowest point overall. Gradient descent can settle in one and stop improving.Open in glossary. The standard defenses are to run it several times from different starts and keep the lowest inertia, and to use k-means++, which spreads the starting centers apart. k-means++ makes bad starts much less likely, though not impossible.

Wrong shape. k-means judges a cluster by how tightly it gathers around a center, so it assumes groups are compact and roundish. On the stretched data, cutting each stripe in half actually gives a lower inertia than separating the two stripes, so k-means is doing exactly what it was asked. Its objective just does not match the structure. The Uneven data shows a related bias: it tends to carve up one large, spread-out group and merge small ones, because it prefers clusters of similar spread.

You pick k. k-means will find $k$ groups in anything, including data with no groups at all. Choosing $k$ is a judgment call, often guided by plotting inertia for several values of $k$ and looking for the point where adding clusters stops helping much.

Key ideas

Unsupervised learning finds structure in data without answers; clustering is one example.
k-means alternates assigning points to the nearest center and moving each center to the average of its points.
It minimizes inertia, the total squared distance to the centers, and is guaranteed to settle.
It can settle in a poor local minimum, so it is run from several starts; k-means++ starts help.
It assumes compact, similarly sized clusters and always returns exactly k of them, whether or not they are real.