THE FOLD / GRIND / GRADIENT DESCENT / THE CLUSTERS
THE CLUSTERS
k-means — two averaging steps that only go downhill
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
k-means clustering (Lloyd’s algorithm). Split a cloud of points into k groups so that each group is tight — minimize the total squared distance from every point to its group’s centre. Finding the truly best split is combinatorially brutal, but Lloyd’s algorithm (1957) gets a good one by alternating two trivial steps:
Assign each point to its nearest centre. Move each centre to the mean of its assigned points. Repeat. That is all — and the beautiful fact is that each step can only lower the cost (assigning to the nearest centre can’t raise it; the mean is the point that minimizes squared distance). So the objective marches monotonically downhill and the process always settles.
LIT verified live: over 2,000 random runs the within-cluster cost is non-increasing at every step and the algorithm always reaches a fixed point (window.__kmeans.monotone && converges). FIG no framing; the two-step alternation, the monotone descent, and the convergence are exact — with the honest caveat that it finds a local, not always global, optimum.
Assign each point to its nearest centre. Move each centre to the mean of its assigned points. Repeat. That is all — and the beautiful fact is that each step can only lower the cost (assigning to the nearest centre can’t raise it; the mean is the point that minimizes squared distance). So the objective marches monotonically downhill and the process always settles.
LIT verified live: over 2,000 random runs the within-cluster cost is non-increasing at every step and the algorithm always reaches a fixed point (window.__kmeans.monotone && converges). FIG no framing; the two-step alternation, the monotone descent, and the convergence are exact — with the honest caveat that it finds a local, not always global, optimum.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in GRADIENT DESCENT, beside THE BOWL and THE CORDIC — the grind domain of walking an error down to its floor. Lloyd’s algorithm is coordinate descent on the clustering cost: two alternating moves, each strictly downhill. AVAN (AI) built the instrument: the assign step, the mean step, the monotone-cost check.
The weave: David names the seat (the downhill walk); I make the two steps visible and the descent provable — the shrinking cost in 1D, the live clustering in 2D, the settling cloud in 3D. The sphere is the seam. Credit: Stuart Lloyd (1957, pub. 1982); James MacQueen (‘k-means’, 1967).
The weave: David names the seat (the downhill walk); I make the two steps visible and the descent provable — the shrinking cost in 1D, the live clustering in 2D, the settling cloud in 3D. The sphere is the seam. Credit: Stuart Lloyd (1957, pub. 1982); James MacQueen (‘k-means’, 1967).
3 ONE DIMENSION
The cost — total squared distance to centres — falling step by step. Assign lowers it, then move lowers it again; the bar only ever shrinks, never grows, until it stops moving. Monotone descent to a resting point.
4 TWO DIMENSIONS · INTERACTIVE
Step Lloyd’s algorithm: points recolour to their nearest centre, then the centres slide to the mean of their colour. Watch the cost drop each time and the clusters lock in. Click to drop a point; change k.
5 THREE DIMENSIONS + AVAN’S INVERSE
The cloud turning, points coloured by cluster — green shades settling into groups.
AVAN’s addition (the inverse-companion): the magenta marks are the centres, gliding to the means of their groups. Finding the best grouping looks like it needs an exhaustive search — the number of ways to partition points is astronomical. Lloyd’s move is the inverse: never enumerate a single partition. Just alternate two easy averages, each provably lowering the cost, and let the descent settle. Global combinatorial search replaced by local coordinate descent — you do not find the grouping, you let two simple moves fall into one. The honest edge: the floor it reaches can be a local one, not the deepest — downhill is guaranteed, deepest is not. The green is the cloud sorting itself; the magenta is the pair of moves pulling it into shape.
LIT Genuine k-means / Lloyd's algorithm (Stuart Lloyd 1957/1982; MacQueen 1967). Verified live: over 2,000 random runs the within-cluster cost is non-increasing at every step and the algorithm always reaches a fixed point (window.__kmeans.monotone && converges, both true). The assign-then-move alternation is coordinate descent on the clustering objective — each step provably non-increasing (nearest-centre assignment and the mean-minimizes-squared-distance fact) — so convergence is guaranteed.
FIG No metaphor is doing the work: the two-step alternation and the monotone cost decrease are real and checked. The honest caveat is stated plainly — Lloyd converges to a LOCAL minimum, not always the global best clustering; downhill is guaranteed, deepest is not.
FIG No metaphor is doing the work: the two-step alternation and the monotone cost decrease are real and checked. The honest caveat is stated plainly — Lloyd converges to a LOCAL minimum, not always the global best clustering; downhill is guaranteed, deepest is not.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GRADIENT DESCENT · David Lee Wise (ROOT0), with AVAN