THE FOLD / GRIND / GRADIENT DESCENT / THE LLOYD
THE LLOYD
k-means: cluster by moving to the mean
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Lloyd’s algorithm is the classic k-means loop: pick k centers, then alternate two steps — assign each point to its nearest center, and update each center to the mean of its assigned points. Repeat until nothing moves. Each step can only lower the total squared distance (the distortion), so it converges monotonically to a local optimum. It is the workhorse of clustering, quantization, and color reduction.
LIT verified live: over 80 runs, every updated center is exactly the mean of its assigned points, and the distortion is non-increasing at every step (window.__lloyd). FIG no framing; exact (converges to a local optimum, not necessarily global).
LIT verified live: over 80 runs, every updated center is exactly the mean of its assigned points, and the distortion is non-increasing at every step (window.__lloyd). FIG no framing; exact (converges to a local optimum, not necessarily global).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at gradient-descent — the downhill loop, here descending the clustering distortion two moves at a time. Lloyd’s algorithm is that descent. AVAN (AI) built the instrument: the nearest-center assignment, the mean update, the distortion measure, the centroid-is-mean check, and the monotone-decrease check.
Credit as content: Stuart Lloyd (1957, published 1982). The weave: David names gradient-descent; I alternate assign and update, confirming each center becomes the mean of its cluster and the distortion never rises.
Credit as content: Stuart Lloyd (1957, published 1982). The weave: David names gradient-descent; I alternate assign and update, confirming each center becomes the mean of its cluster and the distortion never rises.
3 ONE DIMENSION
Two alternating moves. Assign: color each point by its nearest center. Update: slide each center to the average of its colored points. Neither move can raise the total squared distance.
4 TWO DIMENSIONS · INTERACTIVE
Points and k centers; step the assign/update loop and watch clusters settle, distortion falling each step.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: clusters settling to their means.
AVAN’s addition (the inverse-companion): cluster points by alternating assign-to-nearest and move-center-to-mean — each move only lowers the total squared distance, so it converges. The inverse of ‘search all groupings for the best clustering’ is ‘alternate two easy steps downhill — distortion never rises.’ Magenta is the combinatorial search you avoid; green is the settling centers. Clustering by moving to the mean.
LIT Genuine Lloyd's k-means algorithm (Lloyd 1957, pub. 1982). Verified live: over 80 runs, each updated center equals exactly the mean of its assigned points, and the distortion (sum of squared distances) is non-increasing at every assign and update step (window.__lloyd.centroidIsMean && .distortionMonotone).
FIG Exact per-step facts; honestly notes convergence is to a LOCAL optimum, not necessarily global. The nearest-center assignment, the mean update, the distortion measure, the centroid-is-mean check, and the monotone-decrease check run in-browser and hold. The AVAN inverse is honest — alternating assign-to-nearest and move-to-mean descends the distortion monotonically; magenta is the combinatorial search avoided, green the settling centers. Clustering by moving to the mean.
FIG Exact per-step facts; honestly notes convergence is to a LOCAL optimum, not necessarily global. The nearest-center assignment, the mean update, the distortion measure, the centroid-is-mean check, and the monotone-decrease check run in-browser and hold. The AVAN inverse is honest — alternating assign-to-nearest and move-to-mean descends the distortion monotonically; magenta is the combinatorial search avoided, green the settling centers. Clustering by moving to the mean.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GRADIENT DESCENT · David Lee Wise (ROOT0), with AVAN