Give a cloud of points and a number k, and the machine finds the k centers that carve it into tight groups — with no labels, no teacher. It only ever does two things, over and over: assign each point to its nearest center, then move each center to the mean of the points that chose it. Down the center, data flows: points and k go in, the loop descends, and the clusters + the shrinking error come out. The blue team builds and defends it; the red team tries to break it.
source S. P. Lloyd, Least Squares Quantization in PCM (Bell Labs 1957; IEEE Trans. Inf. Theory 28, 1982); J. MacQueen, Some Methods for Classification and Analysis of Multivariate Observations (5th Berkeley Symp., 1967) — projecteuclid · bsmsp/1200512992. AMBER: no archive.org/details scan of either paper was found on search (2026-08); accessible full text linked instead. Rendered, not quoted.
k-means minimizes one number: the within-cluster sum of squares (WCSS) — total squared distance from each point to its cluster's center. The loop is two half-steps, each of which can only lower WCSS:
assign — hold the centers fixed; send every point to its nearest center. No point can do better than nearest, so error drops or holds.
update — hold the assignment fixed; move each center to the mean of its points. The mean is exactly the point that minimizes squared distance to a set, so error drops or holds.
Two steps that never increase WCSS ⇒ the sequence descends and must stop. Live descent this run:
Lloyd wrote this to place quantizer levels in a telephone signal; the identical alternating descent is what the rest of THE FOLD keeps meeting under other names. Assign-then-average is the hard-membership special case of EM; it is coordinate descent on a squared-error objective; it is unsupervised learning as alternating minimization.
Each neighbouring sphere is the same idea softened or supervised — swap "nearest center" for "responsibility" and you have a mixture model; keep the descent, change the loss, and you have the batch. One current, many names.
The blue team's live check: re-run the whole algorithm on the seeded data and confirm four things — WCSS never rose, it reached a fixed point, every center equals the exact mean of its members, and the obvious clusters were recovered. If red tampers, this badge is where it shows.
A fixed, seeded cloud of 60 points in the plane — three well-separated blobs of 20, drawn from a fixed-seed PRNG so every run is identical and checkable. You also feed in one integer: k, how many centers to fit (the count is your choice, not the data's — see the adversary).
The objective the engine is handed: place k centers to minimize total squared distance from each point to its nearest center (WCSS). Nothing about the true grouping is given — only the raw coordinates go into the panel below.
✕ = a moving center · dots = points colored by current assignment (grey = not yet assigned). One step = one assign + one move. Every number below is computed on the spot.
Step and watch WCSS fall each iteration until the assignment stops changing — that fixed point is the answer. Nothing is looked up.
What the machine produces, proven, for the seeded 3-blob data at k=3: convergence in · iterations to a fixed point with final WCSS · (down from · at the start), and every one of the 60 points sorted into its correct blob — the obvious clusters, recovered from coordinates alone.
The blue team's witness (left) confirms these numbers live; the red team (right) tries to make them wrong.
A single outlier drags its center; the "fixed point" it finds is optimal only for the seed it started from, not globally. Robust practice re-seeds many times (k-means++), or picks k by an external criterion. "Converged" here means stopped, not best — an honest distinction the panel keeps.
"k-means finds the optimal clustering." Cut. It finds a local optimum of WCSS; the global problem is NP-hard. It finds the best clustering only for its starting centers.
"More iterations keep lowering the error." Cut. WCSS is non-increasing but hits a fixed point and then holds exactly — the flat tail in the log is convergence, not a stall.
"Moving a center to any member point is fine." Kept, corrected. Only the mean minimizes squared distance to a set — the tamper below moves to the first member instead, and WCSS climbs.
The red team's move: change the update step to place each center on its first assigned point instead of the mean. The mean is what makes WCSS fall; break it and the descent guarantee is gone.
Swap the mean for the first member and WCSS can rise between iterations — the witness (window 7) recomputes, sees error go up and the clusters miss, and turns red. Nothing is faked; the attack is real and it is caught.