"Find the natural groups in this data" is a lovely goal, but it's a vague one — how would a computer even start? k-means turns that vague wish into a concrete recipe: guess some starting points, nudge them toward the data, and repeat. Guess k "centres" at random, hand every data point to its nearest centre, slide each centre to the middle of the points it was just handed, and do it all again. Nothing about a single step looks clever — it's just measuring distances and averaging — yet after a handful of rounds this simple back-and-forth almost always settles into sensible, tight clusters.

The algorithm, spelled out step by step:

1. Choose k. Decide how many clusters you want, and drop k random starting centres anywhere among the data.
2. Assign. Give each data point to its nearest centre (measuring straight-line distance).
3. Update. Move each centre to the mean — the average position — of the points now assigned to it. (That's where the name "k-means" comes from.)
4. Repeat steps 2 and 3 until the assignments stop changing at all. When not a single point switches teams, the algorithm has converged.

Notice what's clever here: nobody ever told the algorithm what a "cluster" looks like, or gave it a single labelled example of "this point belongs to group 1". It only ever does two dumb, mechanical things — measure a distance, and take an average — over and over. Yet those two dumb steps, repeated, are enough to discover groupings a person would draw by eye. That's the quiet magic behind a lot of machine learning: simple rules, applied patiently, uncovering structure nobody explicitly programmed in.

Assign, update, assign, update — each pass tightens the clusters, and within a handful of rounds the centres settle right into the heart of each clump. This same simple loop is what a store uses to split its customers into a handful of shopping "personalities" for targeted offers, what a biologist uses to group similar gene-activity patterns, and — as you'll see in a moment — what an old-fashioned image format uses to squeeze a photo's millions of colours down to a tidy palette. One tiny recipe, an enormous number of uses.

Watch the centres settle

The two centres below start in poor positions, nowhere near the middle of either cluster. Step the algorithm forward: points recolour to their nearest centre, then each centre slides to the middle of its colour. Repeat, and the centres glide into the two clusters and lock in place — the moment nothing changes, k-means has converged.

Worked example: two rounds by hand

Reading the recipe is one thing; running it with a pencil is another, and it's the fastest way to see why such a simple loop actually works. The whole algorithm is just distances and averages, so it's worth tracing by hand once. Take six points and ask for k=2 clusters, starting from two of the points themselves as the initial centres: C_1 = (1, 1) and C_2 = (5, 7).

Round 1 — assign. Compare each point's distance to C_1 and C_2. Point E = (3.5, 5), for instance, is \sqrt{(3.5-1)^2 + (5-1)^2} \approx 4.72 from C_1 but only \sqrt{(3.5-5)^2 + (5-7)^2} \approx 2.5 from C_2 — nearer to C_2. Run the same check on every point and A, B, C land with C_1 while D, E, F land with C_2.

Round 1 — update. Average the points in each group: C_1 = \left(\tfrac{1 + 1.5 + 3}{3}, \tfrac{1 + 2 + 3.5}{3}\right) \approx (1.83, 2.17) C_2 = \left(\tfrac{5 + 3.5 + 4.5}{3}, \tfrac{7 + 5 + 5}{3}\right) \approx (4.33, 5.67) Both centres have shifted noticeably closer to the middle of their own cluster.

Round 2 — assign again. Recheck every point against the new centres. A, B and C are still closer to the (moved) C_1; D, E and F are still closer to the (moved) C_2. Nobody switched sides — so re-averaging would give the exact same centres back. The algorithm has converged after just two rounds, and the two clusters it found are exactly the two visual clumps a person would draw by eye.

How many clusters? The elbow method

k-means never tells you what k should be — you supply it. Pick k too small and distinct groups get squashed together; too large and a single natural group gets needlessly sliced up. One common trick is the elbow method: run k-means for k = 1, 2, 3, \dots and plot how much total error (distance from points to their own centre) each run leaves behind. Error always drops as k grows — more centres can only fit the data better — but the drop is dramatic at first and then flattens out. The "elbow", where the curve bends from steep to shallow, is usually a good, defensible choice of k. It's not an exact formula, just a rule of thumb — choosing the "right" number of groups is one of the open questions of clustering in general.

Picture running the elbow method on a customer dataset that secretly has three real groups (bargain-hunters, regulars, big spenders). The total error might fall like this as k increases: 120 at k=1, 40 at k=2, 12 at k=3, then only 10 at k=4 and 9 at k=5. The big drops happen on the way to k=3 — after that, extra centres barely help, because there's no fourth real group left to find. That sharp bend at three is the signal to stop adding centres. Choose k=1 instead and every customer gets lumped into one indistinguishable blob; choose k=10 and k-means will obediently slice the three real groups into ten arbitrary fragments, finding "structure" that isn't really there.

Simple, fast, imperfect

Because every round is just "measure distances, then average", k-means is quick even on huge datasets — which is exactly why it's the go-to clusterer to try first. It has real quirks (you must choose k yourself, and it likes round, evenly-sized blobs), but those quirks are well understood and usually manageable, mostly by re-running it a few times and keeping the tidiest result. More than anything, k-means is a perfect example of how a trivially simple loop, repeated patiently a handful of times, can uncover real structure hiding inside a pile of numbers that looked completely shapeless to begin with.

See it explained