Experiment № 088 · The story
Move to the Middle
Why I picked it
Stuart Lloyd wrote this down at Bell Labs in 1957, in an internal memo about pulse-code modulation: if you can only send a handful of signal levels, which levels should you pick so the rounding hurts least? The memo sat in a drawer for twenty-five years before it was published in 1982, and by then James MacQueen had already given the idea its name in 1967 and the whole world was using it. I like that one of the most-run procedures in data science started life as a question about telephone audio, and that its author's paper arrived after its fame did.
The collection has plenty of algorithms that search or sort. This is the first one that argues with itself: two half-steps, each solving the other's problem, taking turns until neither has anything left to say.
What I enjoy about it
Each half-step is trivially easy on its own. If you knew the groups, finding their middles would be arithmetic. If you knew the middles, sorting points into groups would be arithmetic. Neither is known, so you guess one and alternate. And the cost can never go up: handing a point to a nearer centre can only shrink its distance, and the mean is precisely the spot that minimises the squared distances to a group. The pink-and-violet staircase in the panel only ever steps down. With finitely many ways to split the points, it has to stop.
But it stops in the nearest valley, not the deepest one. Seed with random points on the Blobs preset a few times and you'll catch two centres sharing one blob while a third straddles two, perfectly content, because no single half-step improves things. k-means++ (Arthur and Vassilvitskii, 2007) helps by spreading the seeds out — each new one chosen with probability proportional to its squared distance from the seeds already placed. The Rings preset shows the deeper limit: borders between middles are always straight lines, so no seed can ever find a ring.
Something you might take away
When a problem is a chicken-and-egg — which groups, which middles — you don't have to solve it all at once. Guess one half, fix the other, and alternate; every round makes things no worse. Just remember what it buys you: a place nothing nearby beats, not the best place there is. Where you start decides where you finish, so start in a few different places. And notice No clusters: ask for five groups and you'll get five tidy groups, whether the data had any or not.