ML Explorer · Level 3 · Classic ML
k-means clustering
With no labels at all, find groups by moving a few centres until they settle.
Overview
Every lesson so far had answers to learn from: a number to predict, or a label. This one has none. We have points, and we want to know whether they fall into groups.
k-means does it with two simple moves, repeated: give each point to its nearest centre, then move each centre to the middle of its points. We step through it, watch its score fall, see two starts end in different places, and ask how many groups to look for.
The points are made up. See "About the data" at the end.
You'll learn
- how k-means alternates an assign step and an update step, and what inertia measures
- why inertia never rises, and why the answer still depends on where you start
- why the best inertia keeps falling as you add clusters, so it cannot choose K by itself
-
No labels
These points have no labels. The task is to find groups in them.
There are points, each described by two made-up measurements, feature 1 and feature 2. They have no units. Unlike every point in the lessons before, they carry no class and no target number: they are all drawn the same, as grey circles.
Finding groups in data without labels is called clustering. It is a kind of unsupervised learning: unsupervised because there are no answers to check against.
Your eye probably sees three clumps. k-means is a way to make a computer find groups like these, and to say exactly what it means by a good grouping.
The maths
The data are feature vectors , with no . Clustering gives each point a cluster number . The numbers are names: nothing makes cluster 1 come before cluster 2.
-
Start: K centres
Decide how many clusters to look for, and place that many starting centres.
We write the number of clusters as K, a capital letter. It is a different thing from the k in k-nearest neighbours, which counted neighbours. Here K = 3. You choose K; k-means does not learn it.
k-means needs a starting spot for each centre. A simple rule is to pick K of the data points. Here we picked three points that all sit in the lower-left clump, a poor-looking start on purpose, so you can watch the centres travel.
The centres are the large outlined shapes. Each has its own shape: circle for cluster 1, triangle for cluster 2, square for cluster 3. The algorithm made these numbers up. They are not true classes, and swapping them round would change nothing.
The maths
The centres are , each a point in the same space as the data. Here is a centre, not a population mean of the whole data set.
-
Assign: nearest centre
Give every point to the centre nearest to it.
Each point now takes the shape of its nearest centre. The shading shows, for every spot on the plot, which centre is nearest, and a line marks each border.
The centres started close together, so the clusters are lopsided: points.
To score a grouping, k-means uses the inertia. For every point, take the squared distance to its own centre, then add them all up. It is a sum, not an average: each point adds its own term. Smaller is better: it means points sit close to their centres.
After this first assign step the inertia is .
The value depends on the units. These features have none, but if they were recorded in units ten times smaller, every number would be ten times larger and the inertia a hundred times larger. Compare inertias only on the same data.
The maths
The assign step sets
Here just numbers the clusters; it is not the of k-nearest neighbours. A tie goes to the lower-numbered centre. The inertia is
Dividing by would give the mean squared distance; k-means software usually reports the sum. The shaded patches are called Voronoi cells: each holds the spots nearer to one centre than to any other. The shading is a simplification, worked out on a grid of 60 × 56 small squares, each coloured by the centre nearest to its middle, so the drawn borders follow the grid.
-
Update: move to the mean
Move each centre to the mean of its points. Then assign again, and repeat.
Each centre moves to the mean of the points in its cluster: the average of their feature 1 values and the average of their feature 2 values. That is where the name comes from: K clusters, each summed up by its mean. The dashed lines trace where each centre has been.
Press "Next: assign" and every point goes to whichever centre is now nearest. Right after an update, some points sit in another centre's patch; the next assign step moves them. Keep pressing. The chart shows the inertia after every step.
The inertia never goes up. It falls from to . In round , an assign step changes no label, so the centres cannot move again and k-means stops.
The three clusters it ends with are exactly the three clumps the points were made from (see "About the data"). k-means did not know that. It never saw a label.
The maths
Neither step can raise the inertia. The assign step changes only , and picking the nearest centre can only shrink each point's term. The update step changes only the centres. For one cluster with points and mean , any centre gives
so the mean is the centre with the smallest sum of squared distances.
Why it stops, in outline: there are only finitely many ways to split points into groups. Each round either lowers the inertia, so that split cannot come back, or leaves it unchanged, and then the centres stay put and the next assign step changes no label. So k-means always stops, at a fixed point: assigning changes no label and updating moves no centre.
If a cluster ever lost all its points, it would have no mean to move to. Our version then keeps its centre where it is. That does not happen in this demo.
-
Starting points matter
A different start can stop at a worse answer. So run several starts and keep the best.
Start A is the run you just watched. Start B swaps just one of its three starting points for another point in the same clump. The dotted rings mark the starting points. Press "Start B".
Start B stops with an inertia of , times start A's . Two centres share the lower-left clump between them, and the third sits between the other two clumps and takes both.
Start B did nothing wrong. It reached a fixed point, where neither step changes anything. A fixed point need not have the lowest inertia possible, and k-means cannot tell which kind it has reached.
The usual cure is to run k-means from several starts and keep the run with the lowest inertia. The chart shows 10 random starts with K = 3, each made of three data points picked at random. of them reach ; the other stops at .
There are also more careful ways to choose the starts. The best known is called k-means++. This page does not use it.
The maths
A fixed point of k-means is often loosely called a local minimum: no single assign or update step can lower the inertia from there. Finding the split with the lowest inertia of all is a hard problem in general: trying every split is hopeless, because their number grows enormously with , and no known shortcut works on every data set. That is why several starts are the standard practice.
Keeping the lowest of several runs is safe because the inertia measures the same thing in every run: same data, same .
-
Choosing K
With more clusters the best inertia you can reach is always lower, so inertia alone cannot choose K. Look for the bend.
Move the K slider. For each K from 1 to 8 we ran 10 random starts and kept the lowest inertia. The plot shows that run's centres as plus signs, with lines between their cells; the chart shows its inertia.
The inertia falls at every step: at K = 1, at K = 3 and at K = 8. More centres means every point can sit nearer to one. With K = 60, each point could be its own centre and the inertia would be 0.
So look for where adding a cluster stops helping much. From K = 2 to 3 the inertia drops by ; from 3 to 4, by only . That bend, often called the elbow, points to K = 3.
The elbow is a hint, not a rule. On real data the bend is often soft or missing, and the right K also depends on what the groups are for.
The maths
The lowest possible inertia can never rise as grows: with centres you can keep the best centres and add one more anywhere, and the points that move to it only get nearer. Our numbers are the best of 10 starts, not the lowest possible, so that argument does not cover them; on this data they fall at every step all the same.
With the single centre is the mean of all the points, and the inertia is the total sum of squares, . That is times the sum of the two features' sample variances (dividing by ).
In this step the plot draws only the cells' borders and the centres, because for more than three clusters there are not enough shapes.
Quick check
Lesson complete
- Clustering finds groups in data without labels. The cluster numbers are names the algorithm makes up.
- k-means repeats two steps: assign each point to its nearest centre, then move each centre to the mean of its points.
- Inertia, the sum of squared distances to the assigned centres, never rises. k-means stops at a fixed point, which need not be the lowest inertia possible.
- Run several starts and keep the lowest inertia. Choose K with care: the best inertia keeps falling as K grows, and the elbow is only a hint.
Common misconceptions
- "k-means always finds the best grouping." It finds a fixed point, which depends on the start.
- "Cluster 1 means the same thing every time." The numbering is arbitrary; another run can give the same groups different numbers.
- "The K with the lowest inertia is best." The largest K always wins on best inertia.
Further reading
- James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 12.4.1, "K-Means Clustering". The book starts from random cluster numbers rather than random centres, shows why each step cannot make the objective worse, and runs the algorithm from several starts, keeping the best.
About the data. The points are made up, in three round clumps of 20, made one clump after another: feature 1 = m₁ + 0.8 z₁ and feature 2 = m₂ + 0.8 z₂, where z₁ and z₂ are independent draws from a normal distribution with mean 0 and SD 1, made with mulberry32 and seed 101 (z₁ before z₂ for each point). The clump centres (m₁, m₂) are (2, 2), (6, 2.5) and (4, 6). Start A uses the 1st, 2nd and 3rd points made as its centres; start B uses the 1st, 2nd and 4th. Start B was found by trying every set of three points as a start, in order, and taking the first whose final inertia is more than 20% above the lowest any of them reached. The random starts in steps 5 and 6: for each K, 10 starts, each K different data points picked by index with mulberry32(200 + K) (index = whole part of 60 × draw; a repeat is drawn again). When a point is equally near two centres, it goes to the lower-numbered one. Displayed values are rounded; the calculations are not.
If this helped, you can .