K-means clustering, and what it is really doing

You have a table of customers and no labels. Nobody has told you who is a “bargain hunter” or a “loyalist”. You suspect there are natural groups in the data and you want the data to tell you what they are.

K-means is the simplest thing that could possibly work for that, and it is worth understanding precisely, because “simplest thing that could work” is a double-edged description. It is genuinely simple. It also assumes a great deal about the shape of the answer, and it will hand you clusters whether or not those assumptions hold. It never refuses. That is the trap.

The loop is two steps repeated

Pick a number of clusters, k. The algorithm is:

1. Put k points somewhere in the feature space. Call them centroids.
2. Assign: give every data point to the nearest centroid.
3. Update: move each centroid to the mean of the points assigned to it.
4. Repeat 2 and 3 until nothing moves.

On thirty-five points and three centroids, the whole run looks like this:

Crosses are centroids; hollow dots are not assigned yet, filled dots take the colour of their centroid. Same points in all three panels — only the centroids and the labels change.

Nothing has been left out of that list. You could write it in twenty lines. It normally converges in a few dozen passes. The loop is Lloyd’s: he wrote it at Bell Labs in 1957 to quantise telephone signals, and it was finally published as Least Squares Quantization in PCM in 1982, long after MacQueen had attached the name k-means to the same idea in 1967.

The two steps each look obvious in isolation, and each is optimal given the other. If the centroids are fixed, assigning each point to its nearest centroid is clearly the best you can do. If the assignments are fixed, the mean is the point that minimises the sum of squared distances to that group. So each step can only leave the objective the same or improve it. It cannot cycle forever, and it stops.

Which raises the question of what the objective is.

What it is actually minimising

K-means minimises the within-cluster sum of squared distances: for every point, the squared distance to its own centroid, added up. Scikit-learn calls it inertia_.

Three things follow, and they explain almost every surprise the method produces.

Squared distance means outliers are loud. A point twice as far away contributes four times as much. One extreme value can drag a centroid a long way from the group it is supposed to represent, or claim a cluster of its own that describes nothing. K-means has no notion of “this point does not belong anywhere”. Everything gets a label. If your data has a heavy tail, deal with it before clustering — outliers and robust statistics is the relevant conversation.

The result depends on where you started. Each step improves the objective, which guarantees you reach a local minimum, not the best one. Different starting centroids give genuinely different answers on the same data. The standard fixes are k-means++, which spreads the initial centroids out instead of scattering them at random, and simply running the whole thing several times and keeping the lowest inertia. Scikit-learn does both by default (init="k-means++", n_init restarts). Do not turn them off to save time.

Inertia always falls when k rises. With k equal to the number of rows, every point is its own centroid and inertia is zero. So inertia can never be used to compare a model with 4 clusters against one with 8 and declare a winner. More on that below.

Why it only finds round clusters of similar size

This is the part that gets skipped, and it is the part that decides whether k-means is the right tool for your data at all.

Look at the assign step. A point goes to the nearest centroid. The set of points closer to centroid A than to centroid B is exactly the half-space on A’s side of the perpendicular line halfway between them. So every boundary k-means can draw is straight. The final partition is a mesh of straight cuts — a Voronoi diagram. Nothing else is expressible.

That single fact produces all the classic failures:

The last row deserves attention because it is quiet. Sum of squared distances is a total, not an average, so a large cluster contributes a large amount simply by having many members. The objective can usually be lowered more by splitting a big group in two than by giving a small group its own centroid. K-means therefore prefers clusters of roughly equal size and roughly equal spread. If your real segments are one enormous mass market and one tiny high-value niche, this is precisely the structure k-means is biased against finding.

To see the loop run, and to see it land badly, watch StatQuest: K-means clustering by StatQuest with Josh Starmer.

Scaling is not optional

K-means measures distance, and distance adds up the features. If one feature is annual income in euros and another is age in years, income ranges over tens of thousands and age over tens. Squared, income is millions of times larger.

The consequence is not that income is weighted more. The consequence is that age is not in the model at all. The clusters will be income bands with a decorative age column. Nobody chose that; the units chose it.

So standardise before clustering — subtract the mean, divide by the standard deviation, per feature. Then check that the result is what you meant, because standardising is itself a decision: it declares every feature equally important. Sometimes it is not. If you have thirty engagement metrics and one revenue column, scaling gives revenue a thirtieth of the vote.

Categorical columns are a related problem with no clean answer. One-hot encode a category and Euclidean distance treats “changed plan type” as a fixed distance in every direction, which is rarely what you mean. It works passably for a few low-cardinality columns and badly beyond that — see encoding categorical variables for what the alternatives cost.

Choosing k honestly

The elbow method plots inertia against k and tells you to find the bend. On textbook data there is a bend. On real data the curve is usually a smooth decline and three colleagues will point at three different values. If the elbow is ambiguous, that is information: it usually means the data does not contain k well-separated blobs, and no choice of k will fix that.

Better tools, none of them decisive:

• Silhouette score. For each point, compare its average distance to its own cluster against its distance to the nearest other cluster. It rewards separation, not just tightness, and unlike inertia it does not automatically improve with more clusters.
• Stability. Cluster several random 80% subsamples and see whether the same groups reappear. Clusters that dissolve when you drop a fifth of the rows are not findings.
• Do the profiles differ? Describe each cluster by its feature means. If two clusters differ only in ways nobody in the business can act on, they are one cluster with extra steps.

And the honest one: k is usually a business constraint, not a statistical discovery. If marketing can run four campaigns, the useful number of segments is four. Asking the data for the “true” k presumes the data has crisp groups. Most customer bases are a continuum.

The mistake worth avoiding is not picking the wrong k. It is presenting the output as discovery. K-means will partition uniform random noise into k neat regions and the plot will look convincing. A cluster is a claim, and before you name it “high-value loyalists” in a deck, it should survive a different seed, a different subsample, and a colleague asking what happens to it at k plus one.