module 09
k-Means Clustering
Least Squares Quantization in PCM
Stuart P. Lloyd
Written to choose the best levels for turning a sound signal into numbers. The method, put each value with its nearest level, then move each level to the average of its values, and repeat, is exactly the k-means algorithm.
k-means++: The Advantages of Careful Seeding
David Arthur & Sergei Vassilvitskii
k-means depends heavily on where the centres start. This paper picks starting centres that are spread out (far points are more likely to be chosen) and proves the result is never too far from the best clustering.
the goal
Split the points into k groups so that every point is close to the centre of its
group. "Close" is measured by squared distance, and the total over all points is
called the inertia (the spread):
Finding the very best split is too hard to do exactly. What everyone runs instead is a simple back-and-forth that's fast and usually good enough.
lloyd's algorithm
Repeat until nothing moves:
- Assign: give every point to its nearest centre.
- Update: move every centre to the middle (average) of its points.
Step through it below. Try both starts.
lloyd's algorithm, one step at a time
Both steps can only lower the spread, or leave it the same, so the algorithm always stops. But it stops at the best answer near where it started. With a bad start it gets stuck, as the first run shows.
Lloyd wasn't clustering data at all. He was choosing the best levels for turning a sound signal into numbers: put each value with its nearest level, move each level to the average of its values, repeat. In one dimension that's exactly this algorithm.
k-means++: start well
Picking random points as starting centres often puts two centres in one group and none in another. Lloyd's small moves can't fix that.
Arthur and Vassilvitskii's fix:
- Pick the first centre at random.
- Pick each next centre at random too, but make far-away points much more likely (the chance grows with the squared distance to the nearest centre already chosen).
The starting centres end up spread out, and the result is guaranteed to be within a reasonable factor of the best possible, before Lloyd even starts.
how the code works
| idea | in kmeans.py |
|---|---|
| assign step | sq_dists(X, centres).argmin(1) |
| update step | X[members].mean(0) |
| spread-out starting centres | kmeans_plus_plus |
| keep the best of several runs | n_init |
| a centre with no points | moved to the worst-served point |
| Lloyd's original 1-D problem | lloyd_max_1d |
| every step, for animation | history() |
what the demo checks
Run uv run python examples/09_kmeans.py.
- Lloyd's original problem, solved. The best 4 levels for a bell-curve signal come out at ±0.453 and ±1.510, matching the known answer to three decimals.
- The spread never goes up at any step.
- Over 200 runs on 15 groups: random starts end at 12× the best spread on average and never find the best answer. k-means++ ends at 1.7× and finds the best answer 16% of the time.
- A centre placed far away from everything owns no points, gets moved, and the run still finds the best answer.
when it goes wrong
- Bad start: compare the two runs above.
- Groups that aren't round (moons, rings): k-means only draws straight borders halfway between centres.
- Groups of different sizes: the halfway border cuts into the bigger group.
- Choosing k: the spread always falls as k grows. Look for the point where it stops falling quickly (the "elbow").