k-Means Clustering

Look at what is missing from the box above. Every scatter on this site so far coloured its dots before any model arrived, fails and passes, children and adults. Here every person starts uncoloured, and the colours you see were put there by the method, which was told only how many groups to look for.

The eight people it opens on are two tight clumps, four short and light around 121 centimetres and 26 kilograms, four tall and heavy around 181 and 80, and with k set to 2 the method finds exactly those two clumps.

Press the crowd button for the less tidy version, the classification pages’ eleven people with their labels stripped away, and notice the method still carves confident groups. It always will. Ask for k groups and k groups come back, whether or not the data has any, which is worth keeping in mind through everything that follows, and Part 4 returns to it.

Drag a dot from one clump toward the other and watch the colours and the X marks renegotiate; the groups are not stored anywhere, they are re-derived from the geometry every time anything moves.

The method never defines a group directly. It defines a centre, one point per group, and a group is then whoever is nearer to that centre than to any other. The shading in the playground is that rule painted over the whole plane, and with two centres the boundary between the two shaded regions is a straight line, the set of points exactly as far from one centre as from the other.

person belongs to group j   if   ‖person − centre_j‖ ≤ ‖person − centre_i‖ for every other i

‖x − a‖² = ‖x − b‖²   ⇔   2 x · (b − a) = ‖b‖² − ‖a‖²

A person sitting exactly on the boundary has to go somewhere, and either answer is equally correct. The fit here sends them to the lower-numbered group, and I checked that with a person placed at (151, 53), who lands in group 0. The rule matters only in that it must be a rule, so that two fits of identical data cannot disagree for no reason.

The other half of the definition is where a centre sits. When the loop has come to rest, every centre is the plain mean of the people assigned to it, the statistics primer’s balance point, and on the eight people that is arithmetic you can check against the X marks.

heights  118 + 120 + 122 + 124 = 484,   484 / 4 = 121
weights   24 +  25 +  28 +  27 = 104,   104 / 4 =  26

Before the loop, the number it is trying to make small. Take every person, measure the distance to their own group’s centre, square it, and add up over everyone. The total is called the inertia, and the name is Steinhaus’s, since for equal masses it is the sum of the parts’ moments of inertia about their own centres.

inertia = Σᵢ ‖personᵢ − centre of their group‖²

inertia = 20 + 10 + 20 + 14 = 64

The loop is two steps, and this is the first. Hold the centres where they are and give every person to whichever centre is nearest. Each person’s term in the inertia is their squared distance to their own centre, so moving a person to a nearer centre shrinks their term and touches nobody else’s, and a person already nearest their own centre stays put. The total cannot rise.

The second step holds the assignment fixed and moves each centre to the mean of its current members. This is the step that needs an argument, since it is not obvious that the mean is the best place to put a centre rather than merely a reasonable one. It is the best place, exactly. Work one coordinate at a time and ask which value c makes the total squared distance to the group smallest.

So the update does not nudge a centre somewhere better, it jumps to the exact minimiser for the current assignment, and the total cannot rise. The widget scores two candidates for the centre of the tall clump, the mean and the coordinate median, under two distances, and the stray person is there to pull them apart.

Put the two facts together. Each assignment lowers the inertia or holds it, each update lowers it or holds it, and there are only finitely many ways to assign eleven people to two groups. A total that never rises, stepping through finitely many states, cannot go on forever and cannot come back to a state it has left with a lower total, so the loop stops. The staircase watches it happen on the crowd, with the inertia read after each half of every pass.

…

Both kinds of step take a share of the fall. From the seeded start at 8197.0, the first update takes the total to 4127.7 and the first assignment to 4086.8, the second pair to 3802.0 and 3724.6, the third to 3483.3 and 3425.6, and the fourth update lands on 3185.9, where the assignment changes nobody. The fifth pass moves no centre at all, and the fit reports itself settled after five passes, which is the number the playground calls passes to rest.

The stepper below is the same walk as the staircase, drawn on the plane, with the two halves of each pass taken one at a time. On seed 3 the two starting centres are two of the people, (180, 80) and (159, 57), and the first assignment hands eight people to the second of them and three to the first.

Each update drags a centre toward the mean of a group that is still changing, each assignment then moves one more person across, and the two alternate until an update moves no centre and an assignment moves no person.

Switch to the two small clumps and the walk is over almost before it starts. Seed 3 places the centres on (182, 83) and (118, 24), one in each clump, the first assignment is already the right one, and a single update puts the centres on the two means with the inertia at 64.0. The second pass moves nothing, so the fit reports two passes, one of them spent confirming that the first was enough.

The staircase stopped at 3185.9 and the dashed line sat at 2952.6, so the loop rested somewhere that was not the lowest place available. This is the calculus primer’s two-valley curve with a different ball. Each step lowers the total, so the walk only ever goes downhill, and downhill from where it started is not the same as the deepest valley there is.

Change the seed on the stepper to 1 and the start is (120, 25) and (178, 78), one centre in each clump; the first assignment is already the winning grouping, and one update reaches 2952.6.

The cheapest insurance against a poor start is more starts. Run the whole loop from several seedings, read each one’s resting inertia, and keep the lowest. The gallery does that for ten seeds and lines the results up.

On the crowd at two groups the ten starts find three different valleys. Five of them rest at 2952.6, which pairs the three short people with the person at (147, 41) against the other seven; three rest at 3185.9, with one more of the middle people, at (145, 57), pulled into the short group; and two rest at 3141.7, the three short people alone against everyone else.

The fit the playground shows is the usual ten starts from one seed, and it keeps the lowest by a strict comparison, so a later start that only ties an earlier one does not replace it. At three groups the same ten starts all rest at 501.6 with sizes 3, 5 and 3, which is the three clumps the eye sees, and the only thing that differs between the panels is which clump got which number.

Choosing the starting centres by picking k people at random is the obvious thing, and it has a real weakness. A dense clump holding most of the people is likely to be handed several centres while a sparse one gets none, and the loop cannot recover from that, since it only ever moves a centre to the middle of the people who already chose it.

The seeding the fits here use spreads the start out instead. Pick the first centre uniformly from the people. Then for each remaining centre, find every person’s squared distance to the nearest centre already chosen, and pick the next centre from the people with probability in proportion to that squared distance.

P(next centre is person i) = Dᵢ² / Σⱼ Dⱼ²,   where Dᵢ is the distance from i to the nearest centre so far

The rule is not to take the furthest person, which would be deterministic and would chase exactly the stray people Part 5 worries about. Sampling in proportion makes a far person likely rather than certain, so the start is spread out without being at the mercy of one strange point. It is also why the starts on the stepper are always two of the people, and why seed 3 on the crowd, having picked (180, 80) first, went on to pick (159, 57) rather than another tall person.

Restarts repair a bad start. They cannot repair a bad objective, and the two bands on the gallery are the case that separates those. Twenty-two people lie on two parallel bands fourteen kilograms apart, each band far longer than the gap between them, and at two groups every one of the ten starts rests at exactly the same inertia, 4504.4, with eleven people in each group.

The grouping they agree on cuts both bands in half by height. It is the deepest valley this objective has on these people, and the eye can see that each band was meant to be one group.

One number in this method is never learned, and that is k itself. Slide it upward on the two small clumps and watch the inertia. At one group it is 13096.0, at two it is 64.0, the natural grouping found, and it keeps falling from there, because more centres can only sit closer to people, all the way to zero when every person has a private centre. The falling number cannot choose k for us, since a larger k never costs it anything.

What practitioners do is look for the elbow, the k past which the fall flattens, and treat the further gains as bookkeeping rather than structure. On the eight it is unmistakable, since the drop from one group to two is 13032 and the next drop is 25. On the crowd it is less so. The fall from one group to two is 7529.6, from two to three another 2451.0, and from three to four only 279.6, and at three groups 4.8 percent of the total scatter is left.

Three is the reading I would take, and it is a reading, not a calculation.

A classifier’s label 1 means the same thing in every fit, because the data said what 1 was. A clusterer’s group 1 means whichever group the seeding happened to number first. In the seed gallery at three groups, seed 0 and seed 6 find the identical grouping of the crowd and give the short clump the numbers 2 and 1 respectively, and the gallery has to compare which people share a group rather than compare the numbers to see that they agree.

The method has no way to answer that there are fewer groups than it was asked for. Press the ideal case, sixteen people in two clear clumps, and set k to 3. The fit obliges, with an inertia of 202.9 against 282.4 at two groups, by cutting one clump into pieces of 5 and 3, and the elbow chart is the only thing that says the third group bought little. On the crowd at six groups the inertia is 54.5 and three of the six groups hold a single person.

Section 2 showed that a group here is a region of nearest centre, bounded by straight lines and without dents. Two long thin groups lying side by side are not shaped like that, and no pair of centres can describe them. On the two bands the fit cuts each band in half by height, because halving the length of a band saves far more squared distance than separating the bands would, and section 12 showed every start agrees. The gallery puts three other definitions of a group beside it on the same people.

Density asks whether a person sits within ten units of another and follows the chain, and it recovers both bands with nobody left out. Single linkage merges the two groups with the closest pair of members until two remain, and it recovers them too, since each band is a chain of short steps. The mixture of two bell-shaped components can describe an elongated group and still does not find one here, because it starts from the nearest-centre grouping and only ever climbs; its answer is the same cut, person for person.

That is recorded elsewhere as measured, and I found the same.

Two arcs curving around each other are the classic case, because no straight line separates them and their centres sit nearly on top of each other. Switch the gallery to the crescents. The nearest-centre fit rests at 7949.1 with ten in each group and gets both arcs nearly right, then swaps the ends, handing the upper arc’s person at (173, 58) to the lower group and the lower arc’s person at (148, 46) to the upper.

Density and single linkage recover the two arcs exactly, and here the mixture does too, which is worth saying since on the bands it did not; a nearest-centre start that is nearly right can be climbed from, and one that is wholly wrong cannot.

Why might k-means divide a large group instead of isolating a small nearby group? Its objective counts the squared distance of every observation. Reducing many distances in a broad group can improve that total more than giving a compact group its own centre.

The unequal-size example makes this visible. There are twenty loosely spread observations and five tightly packed ones. With two centres, the fitted groups have sizes 15 and 10 and inertia 2464.6. The compact five have been combined with part of the broader group.

With three centres, one solution gives the compact five their own group, leaving groups of sizes 11, 9, and 5. Only three of the ten displayed starts find that solution. The seed gallery lets us separate the effect of the objective from the effect of initialization.

The other methods in the comparison use different definitions of a group. Density uses a neighborhood radius, single linkage connects nearby observations, and the mixture model can assign a separate spread to each component. Their different partitions follow from those different assumptions.

The mean gives a far person a large say, and the objective is built on means. Add one stray person at 196 centimetres and 14 kilograms to the eight and ask for two groups again. The stray is nearest the tall centre, so they join it, and the update drags that centre from (181, 80) to (184, 66.8), thirteen kilograms off the clump it is supposed to mark, while the inertia goes from 64.0 to 3728.8.

At three groups the stray gets a private centre and the other two return to exactly where they were, inertia 64.0 again. Density, with a radius of six, calls the stray a person in no group and leaves the two clumps alone.

The neighbour pages let you choose what near means, and it is tempting to ask for the same here, Manhattan distance say, for people measured on scales that should not be squared. The method cannot offer it, and the reason is section 6. The update step is a mean, and the mean is the exact minimiser of squared Euclidean distance specifically.

Under Manhattan distance the minimiser is the coordinate median instead, and the widget in section 6 measured the gap, since on the tall four with the stray the Manhattan total is 129.6 at the mean and 93.0 at the median. Keep the mean as the update and swap the distance, and the update step stops lowering the objective, so the convergence argument of section 7 collapses and nothing promises the loop will stop.

Replacing the mean with the median gives a real method with its own name, k-medians, which is not offered here, so the fits on this page take no distance choice at all. On the tall four alone the two candidates nearly tie, 34.0 against 35.0 for squared distance and 14.0 against 14.0 for Manhattan, since with an even count of people any weight between the middle two is a median; the stray is what pulls them apart.

Since everything here is distance, the units the features are written in are part of the model. Rewrite the crowd’s heights in millimetres and every horizontal gap becomes ten times larger while the vertical gaps stay put, so height alone decides who is near whom. Write them in metres and weight alone does.

At two groups, centimetres and metres agree on the grouping and millimetres do not, splitting the crowd by height into 6 and 5. At three groups it is metres that disagree, moving the person at (147, 41) into the short clump for sizes 4, 3 and 4, while millimetres now agree with centimetres. The inertias are not comparable across the panels at all, 2952.6 against 155104.7 at two groups, because they are in different squared units.

Standardising each feature by its own spread gives a grouping that agrees with the centimetre one at both k on this crowd, which is a fact about this crowd and not a law; what standardising guarantees is only that neither feature outweighs the other by its unit.

A fitted grouping is k centres in named feature space, and a person the fit never saw is placed by the same rule that placed everyone else, nearest centre, with the centres exactly where the fit left them. That is what makes the playground’s shading possible, since every cell of it is a new person asked where they fall. Nothing is refitted, so a new person cannot move a centre, which is the one thing the stray of section 20 could do while the fit was still being made.

The features are matched by name rather than position. Hand the fit weight then height and the answer is the same as height then weight, and I checked that on two people, who came back in their own groups either way. A person missing the weight, or carrying an extra measurement, or with height renamed, is refused, since the distance to a centre cannot be evaluated with a coordinate absent and an extra one has nothing in any centre to be compared against.

Beside the labels and the centres, a fit here reports three things worth reading together. The inertia, for comparing groupings at one k. The passes to rest, which is the cheapest sign that the loop stopped by settling rather than by hitting its pass limit of three hundred. And the group sizes, where a zero means a centre that nobody chose.

A complete implementation states the number of groups, the seeding rule, how many starts it runs and how it chooses among them, the pass limit and the tolerance that ends a walk, that the distance is squared Euclidean, what it does with an empty group, how a tie in assignment breaks, and which of the labels, centres, inertia, pass count and sizes it returns. Here the defaults are ten starts from a seeding by spread, at most three hundred passes each, stopping when no centre’s squared movement exceeds one part in a hundred million, and the fit the playground shows is seeded so the page can quote it.

The last row is the one to remember. The refusals above are all about data the arithmetic cannot process. Data the arithmetic processes happily and describes wrongly is the ordinary case for this method, and the only guard against it is looking at the picture, which is why every section of Part 5 drew one.