K-Means

Point every observation at its nearest centre, move each centre to the mean of its points, and repeat. The total error always falls, but where it lands depends on where it started.

Points 1, 2, 9 and 10 settle at centres 1.5 and 9.5 with error 1.0 down from 113, yet the same rule cuts two long bands across instead of along them

Why Does This Exist?

A garden centre holds 30,000 loyalty cards and six end-of-aisle display slots. Nobody wrote down which kind of shopper each card belongs to. Each card gives two columns: last year spend and visit count.

The wanted groups already sit in the receipts, not in a label column. K-means is the oldest tool that still finds them well enough to be everywhere: no labels in, group assignments out.

Two words first. A distance is one number saying how far apart two shoppers are once written as coordinates. A centroid is a group average, column by column, a made-up shopper at the middle of a real crowd. This page covers the assign-and-move loop. The density method that needs no count upfront lives in DBSCAN. How to score a result once it settles lives in clustering evaluation. The tree that returns every count at once lives in hierarchical clustering.

Think of It Like This

Six ice-cream vans on a long beach

Six vans park on the sand wherever they arrived. Every sunbather walks to the nearest van. Each driver then moves to the middle of the queue they got.

That move changes everything. Some sunbathers now stand nearer a different van, so they switch, and drivers reposition again. Rounds later it stops: nobody switches, nobody moves. The beach sits carved into six territories.

Park the vans differently tomorrow and they settle somewhere else entirely, also stable, sometimes visibly worse. Stable never meant best. And nearest carves round patches, so no van in this picture can serve a long thin strip along the water edge, however real that strip is.

Where it stops: sunbathers choose the nearest van honestly. Shoppers do not walk. You compute nearest, and any column you forgot to scale counts more than the rest.

How It Actually Works

Pick $k$ centroids somehow. Then repeat two steps until nothing changes: assign every point to its nearest centroid, then move every centroid to the mean of its points. That loop is Lloyd algorithm, and it is the whole method.

What it drives down is the within-cluster sum of squares. For clusters $C_j$ with centroids $\mu_j$ :

\mathrm{WCSS} = \sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2

Here $x$ is one shopper written as numbers, $\mu_j$ is the centroid of cluster $j$ , and the double bars mean straight-line distance. Both steps lower that total or leave it alone: moving a point to a nearer centroid cannot raise it, and the mean is the point that minimizes summed squared distance. A total that only falls, over finitely many assignments, must stop falling. So k-means always converges, to a local minimum set by its start.

Worked example: four numbers on a line

Points sit at $1$ , $2$ , $9$ , and $10$ . Guess centres at $1$ and $2$ . Assign by nearest: $1$ joins the first, $2$ , $9$ , and $10$ join the second. Squared error is $0 + 0 + 49 + 64 = 113$ .

Move each centre to its group mean. The first stays at $1.0$ . The second jumps to $(2 + 9 + 10) / 3 = 7.0$ . Reassign: $1$ and $2$ join the first, $9$ and $10$ join the second. New means are $1.5$ and $9.5$ . Nobody switches after that. Final error is $0.25 + 0.25 + 0.25 + 0.25 = 1.0$ , down from $113$ . Same points, same ruler, nearly one hundred times tighter. That stillness means done.

Start positions decide the landing

Random starts fail in one specific way: two centroids land inside the same real group and split it down the middle, while a genuinely separate group gets absorbed. Restarts help, but they charge for luck.

K-means++ buys the luck instead. Take the first centroid at random. For each later one, measure every point squared distance to the nearest centroid chosen so far, and draw the next with probability proportional to that. Far points become likely, covered points become nearly impossible. It is the library default: faster convergence and a lower landing almost every time.

Choosing k, and the shape it assumes

The elbow method plots error against $k$ and asks for the bend. On our four points one cluster centred at $5.5$ costs $(4.5^2 + 3.5^2 + 3.5^2 + 4.5^2) = 65.0$ . Two clusters cost $1.0$ . Three clusters with groups $\{1, 2\}$ , $\{9\}$ , $\{10\}$ cost $0.5 + 0 + 0 = 0.5$ . The first extra centre buys $64.0$ , the next buys $0.5$ . That bend at 2 is unusually clean. Often the curve is a smooth arc and three people read three values, because there is no elbow. Clustering evaluation gives better instruments and still only heuristics.

In practice the answer comes from outside the data. Six display slots mean $k$ is six. Six segments you can act on beat five because a curve looked bent.

Then the assumption that decides the failure. Squared distance to a mean expects clusters roughly round, similar in size, and similar in density. Feed it two long parallel bands and it slices both bands across the middle, because that split has lower squared error than the correct along-the-bands split. The diagram is that failure.

Code

The point is the collapse and the continued fall: error drops fast, then keeps dropping past the true count.

1pts: list[float] = [1.0, 2.0, 9.0, 10.0]2
3def wcss(centres: list[float]) -> float:4    total: float = 0.05    for p in pts:6        total += min((p - c) ** 2 for c in centres)7    return total8
9print(round(wcss([1.0, 2.0]), 1))  # -> 113.010print(round(wcss([1.5, 9.5]), 1))  # -> 1.011print(round(wcss([5.5]), 1))  # -> 65.012print(round(wcss([1.5, 9.0, 10.0]), 1))  # -> 0.5

The printout matches the hand computation: first guesses cost $113.0$ , settled centres cost $1.0$ , one cluster costs $65.0$ , three cost $0.5$ . Move the first guess from $1.0$ to $9.0$ and the first assignment changes completely, which shows how much the start matters.

Watch Out For

Clustering columns that were never on the same scale

Annual spend runs 20 to 4,000 while visit count runs 1 to 40. Squared, spend contributes roughly ten thousand times more to every distance, so nearest centroid means nearest in spend and nothing else.

Symptom: clusters form clean spend bands with boundaries near quartiles, and visit count holds almost the same mean in every group. Fix: standardize first by subtracting the mean and dividing by the standard deviation per column, then refit. Feature scaling covers when to use something else. This decides who lands where, not a tuning detail.

Treating a lower total as proof the clusters are real

Someone reports $0.5$ at $k = 3$ against $1.0$ at $k = 2$ and concludes three segments fit better. The code shows why that is empty: the total falls every time a centroid is added, and hits exactly zero when $k$ equals the point count.

Symptom: the chosen $k$ is always the largest tried. Fix: never read the total alone. Check silhouette, stability across resamples, or separation on a column kept out of the clustering, as clustering evaluation lays out.

The Quick Version

Assign each point to its nearest centre, move each centre to its group mean, and repeat. That loop is Lloyd algorithm.
Points 1, 2, 9 and 10 settle at 1.5 and 9.5 with error 1.0, down from 113 under the first guesses.
The total only falls, so the loop always converges to a local minimum set by the starting centres. Restart it or seed with k-means++.
One cluster costs 65.0 and three cost 0.5 on the same four points, so the total alone never justifies $k$ .
Scale columns first. Unscaled, the widest column decides every assignment.
Squared distance assumes round similar-sized clusters. Long bands get cut across, not separated.