k-means clustering

No labels this time, only dots. Can the groups be found? Below, three centres go looking. Before it plays: can the number under the picture ever go up?

The two steps

There are $m$ points $\mathbf{x}_1,\dots,\mathbf{x}_m$ and no labels: nobody has said which point belongs where. Choose a number of groups, or clusters, $k$, and a starting place for each centre, $\mathbf{c}_1,\dots,\mathbf{c}_k$, numbered by $r$. Then repeat two steps.

Assign. Give each point to its nearest centre:

so $r(i)$ is the cluster of point $i$. If two centres are equally near, the point goes to the lower $r$. This is Nearest neighbours with $k=1$, asked of the centres instead of the training examples.

Update. Move each centre to the mean of its points: the average of their first coordinates and the average of their second. A centre with no points keeps its place.

Stop when an assignment changes nothing. That is k-means.

Why it settles

Measure how well the centres fit by the total squared distance from each point to its own centre,

Now the answer to the question. The cost can never go up, and each step is the reason.

• The assign step gives each point the nearest centre. Its squared distance can only shrink or stay.
• The update step moves each centre to the mean of its points. The mean is the one point with the smallest total squared distance to a set of points, the best constant of Models and loss worked in each coordinate. So no centre position does better for those points.

A cost that never rises, with only finitely many ways to split $m$ points into $k$ groups, has to stop changing. In the clip it falls from 1216.7 to 59.1 in six steps.

Starts and the choice of k

The cost settles, but not always at the lowest cost there is. It stops at the first split that no single step can improve, and where that is depends on the start.

So different starts can end on different groups: here at nearly four times the cost. Practical programs run k-means from several starts and keep the run with the lowest cost. A good way to start, called k-means++, picks the first centre at a random data point and each next one at a data point chosen at random, with points far from every centre so far more likely to be picked.

The number $k$ is a choice too, and the cost cannot make it:

More centres never cost more: give one more centre a place on any point and the cost can only fall. With one centre per point, every point is its own centre and the cost is 0. So the lowest cost always picks the largest $k$, and it means nothing. Here the bend at $k=3$ stands out, because the data were made from three clouds. Real data rarely bend so clearly, and choosing $k$ often needs knowledge of what the groups are for.

What it cannot find

Every point goes to its nearest centre, so the boundary between two clusters is the line of points equally far from both centres: a straight line at right angles to the segment between them, through its middle. k-means can only cut the plane with such straight lines, and it favours round groups of similar size.

The same goes for long groups, which k-means cuts across rather than along, and for a small, tight group next to a large, spread-out one: the boundary runs midway between the two centres, so the small group’s centre takes the large group’s edge points. Gaussian mixtures allow stretched groups and groups of different sizes.

Worked example

Six points, $(1,1)$, $(1,2)$, $(2,1)$, $(6,5)$, $(7,5)$ and $(6,6)$, and $k=2$, starting from a poor place: $\mathbf{c}_1=(1,1)$ and $\mathbf{c}_2=(2,1)$, both in the lower group.

Assign. $(1,1)$ and $(1,2)$ are nearest $\mathbf{c}_1$; $(2,1)$ sits on $\mathbf{c}_2$, and the three upper points are nearer $\mathbf{c}_2$ too. The squared distances to the chosen centres are $0$, $1$, $0$, $4^2+4^2=32$, $5^2+4^2=41$ and $4^2+5^2=41$: cost 115.

Update. $\mathbf{c}_1$ moves to the mean of $(1,1)$ and $(1,2)$, which is $(1,1.5)$. $\mathbf{c}_2$ moves to the mean of the other four, $(21/4,17/4)=(5.25,4.25)$. Cost 30.

Assign. $(2,1)$ is now nearer $\mathbf{c}_1$: squared distance $1+0.25=1.25$, against $3.25^2+3.25^2=21.125$ to $\mathbf{c}_2$. It changes group. Cost 10.125.

Update. $\mathbf{c}_1=(4/3,4/3)$, the mean of the lower three, and $\mathbf{c}_2=(19/3,16/3)$, the mean of the upper three. Cost $24/9=2.667$.

Assign. No point changes group, so the run stops. The costs were $115\to30\to10.125\to2.667$.

Both centres in one place. Start both centres at the same point. Every point is then equally near both, so the tie rule gives all of them to $\mathbf{c}_1$, and $\mathbf{c}_2$ gets none. The update moves $\mathbf{c}_1$ to the mean of all the data while $\mathbf{c}_2$ keeps its place. Now the two differ, and the next assignment splits the data. On the clip’s 90 dots, with both centres starting at $(0,0)$, that second split is 59 and 31 dots.

Where you’ll meet this

Customers. Shops group customers by what they buy and how often, to see which kinds of customer they have.

Colour palettes. A photo’s pixels are points in a space of red, green and blue; k-means with $k=16$ finds 16 colours, and each pixel is drawn in its centre’s colour.

Codebooks. Speech and image coders send the number of the nearest centre instead of the whole vector; the centres, the codebook, are often found by k-means.

Operating modes. A machine’s sensor logs fall into groups such as idle, running and starting up, found without anyone labelling the readings.

Reference card