K-means in plain words: guess, move, repeat

K-means sorts unlabeled points, data with no answers attached, into k groups called clusters, where k is a number chosen in advance. It starts from a guess and repeats two simple moves until nothing changes.

1. 1
   The clip shows 60 points in three loose groups, with k = 3. Each circled cross is a centroid, the current guess for a cluster's center. At iteration 0 the three centroids start at random spots, all near the lower group. Every point takes the color of its nearest centroid, so the colors cut across the real groups. Inertia, the sum of each point's squared distance to its centroid, reads 929.0.
2. 2
   Each iteration makes two moves. First, every centroid moves to the mean of its points, the average of their positions, and a dashed arrow traces the move. Then every point picks its nearest centroid again, which can change its color. At iteration 1 the longest move, shown as Max disp, is 3.11 units, and inertia falls to 287.7. At iteration 2 the centroids move up to 2.15 units more, each one lands inside its own group, and inertia drops to 85.7.
3. 3
   At iteration 3 no point changes color, and the centroids shift by at most 0.19 to take in the one point that switched at iteration 2. At iteration 4 nothing moves: Max disp reads 0.00 and inertia stays at 84.8. That is convergence. Neither move can raise inertia, and there are only finitely many ways to split 60 points into 3 clusters, so k-means always stops. Where it stops depends on the starting guess, and a poor start can end in a worse split, called a local optimum.