k-means clustering & Lloyd's algorithm

Hook

No labels this time — just a scatter of points. Can an algorithm find the groups on its own?

Intuition

Step 0 — drag a centroid, or take a step

Drag the two diamond centroids anywhere, then take a step. Every point turns the color of whichever centroid it's closest to; then each centroid jumps to the middle of the points that just turned its color. Do that a few times and the centroids stop moving — they've found the two blobs, starting from nothing but a guess.

Formalize

This is k-means, and one iteration is just two moves repeated:

\text{assign: } c_i = \arg\min_k \lVert x_i - \mu_k \rVert^2 \qquad\qquad \text{update: } \mu_k = \frac{1}{|S_k|}\sum_{i \in S_k} x_i

$c_i$ — the cluster that point $i$ gets assigned to.
$x_i$ — the coordinates of point $i$ .
$\mu_k$ — the centroid (mean position) of cluster $k$ .
$S_k$ — the set of points currently assigned to cluster $k$ .

Assign, then update
Assign every point to its nearest centroid, then move each centroid to the mean of the points now assigned to it.
Assignment alone stalls
Assignment without updating just repeats the same bad guess forever.
Updating alone misses reassignments
And updating without reassigning never notices when a point should switch sides.

Play

Step 0 — centroid 1: (9.00, 1.00), centroid 2: (1.00, 8.00)

Try a few very different starting positions for the centroids — both inside one blob, both in empty space, swapped to the wrong side entirely. The path each takes to get there differs, but for two well-separated blobs like these, they all end up in the same place.

Worked example

Starting both centroids in empty space — one at $(9,1)$ , the other at $(1,8)$ :

First assignment step is messy
Point $(2,1)$ ends up nearer to $(9,1)$ (distance $7$ ) than to $(1,8)$ (distance $\approx 7.07$ ) — a near-tie that could easily have gone the other way.
First update already helps a lot
That first assignment sorts 6 points to each centroid: $(9,1)$ 's group ends up $\{(2,1),(8,7),(9,7),(9,8),(8.5,7.5),(9.5,8)\}$ , and $(1,8)$ 's group gets the other six. Averaging each group's coordinates:
- $(9,1)$ 's new centroid: $x=(2+8+9+9+8.5+9.5)/6=46/6\approx7.67$ , $y=(1+7+7+8+7.5+8)/6=38.5/6\approx6.42$
- $(1,8)$ 's new centroid: $x=(1+1+2+1.5+2.5+8)/6=16/6\approx2.67$ , $y=(1+2+2+1.5+2+8)/6=16.5/6=2.75$
— close enough to the real blobs that the next assignment step cleanly sorts every point correctly.
Converges to the true means
With the centroids that close, every point sorts to its own blob this time — no more near-ties. Averaging each true blob's 6 points:
- Blob near $(9,1)$ : $x=(8+9+8+9+8.5+9.5)/6=52/6\approx8.67$ , $y=(7+7+8+8+7.5+8)/6=45.5/6\approx7.58$
- Blob near $(1,8)$ : $x=(1+2+1+2+1.5+2.5)/6=10/6\approx1.67$ , $y=(1+1+2+2+1.5+2)/6=9.5/6\approx1.58$
— landing exactly on both blobs' true means, and a further step changes nothing at all.

Checkpoint

Starting from this deliberately bad position, take steps until both centroids converge.

Step 0 — centroid 1: (9.00, 1.00), centroid 2: (1.00, 8.00)

Take a step to try it

Summary

\text{assign: } c_i = \arg\min_k \lVert x_i - \mu_k \rVert^2 \qquad\qquad \text{update: } \mu_k = \frac{1}{|S_k|}\sum_{i \in S_k} x_i

K-means needs no labels at all — it only ever looks at distances between points and centroids. That's also its limit: it can only find clusters shaped like blobs around a center. The next chapter's technique looks at the data differently, by asking which directions it actually varies in.