K-Means Clustering

A marketing team has 50,000 customers and budget for four campaigns. They need four groups, each coherent enough that one message works for everyone in it.

Try doing this by hand. The obvious move is to split on spend: under £100, £100–£500, £500–£2,000, over £2,000. Where did those boundaries come from? Somebody's intuition. Change them slightly and thousands of customers move groups.

Worse, spend alone is the wrong basis. Two customers both spending £600 a year could be completely different people — one places a single large order at Christmas, the other buys something small every fortnight. Those two need different messages. So add purchase frequency. Now you need boundaries on two dimensions and the number of boxes multiplies. Add recency and average basket size and you have a four-dimensional grid with dozens of cells, most of them empty and a few containing 40,000 customers.

The manual approach fails because you are imposing boundaries rather than discovering them. The data may well contain four natural clumps — but they will not be aligned to round numbers on individual axes, and you cannot see them because you cannot look at four dimensions at once.

What you want is a procedure that finds where the clumps actually are.

The idea in one sentence

Pick $k$ points to act as cluster centres. Assign every customer to the nearest one. Move each centre to the middle of the customers assigned to it. Repeat until nothing moves.

That is the whole algorithm. It is short enough to be suspicious, so let us run it by hand.

Two iterations, worked

Six customers, two features (annual spend in hundreds of pounds, orders per year), $k = 2$.

Start with two deliberately poor centres: $c_1 = (1, 2)$ and $c_2 = (2, 1)$.

Iteration 1, assignment. Compute the distance from each point to each centre and take the nearer.

Iteration 1, update. Move each centre to the mean of its members.

• Cluster 1 = {A, C, D}: mean = ((1+2+8)/3, (2+3+8)/3) = (3.67, 4.33)
• Cluster 2 = {B, E, F}: mean = ((2+9+10)/3, (1+7+9)/3) = (7.00, 5.67)

Iteration 2, assignment. With the centres in better places, the assignments change.

Iteration 2, update. Cluster 1 = {A,B,C}, centre (1.67, 2.00). Cluster 2 = {D,E,F}, centre (9.00, 8.00).

Run it again and no point changes cluster. The algorithm has converged, and it has found exactly the split any human would draw — despite starting from two centres sitting almost on top of each other in the corner. Two passes.

What it is actually minimising

The algorithm optimises a specific quantity, inertia (also called within-cluster sum of squares):

In words: for every point, the squared distance to its own cluster's centre, summed over everything. Lower means tighter clusters.

Both steps provably reduce $J$, which is why convergence is guaranteed:

• Assignment step: moving a point to a nearer centre reduces its own squared distance and leaves every other term untouched. $J$ cannot increase.
• Update step: for a fixed set of members, the point minimising the sum of squared distances to them is their mean. This is a calculus fact, not a heuristic. So relocating the centre to the mean cannot increase $J$ either.

Since $J$ never increases and there are finitely many possible assignments, the algorithm must stop.

Convergence is guaranteed. Convergence to the best answer is not. K-means finds a local minimum, and which one it finds depends entirely on where the centres started.

The initialisation problem

Bad starting positions produce bad final clusters that are nonetheless stable — the algorithm sits happily in a local minimum. Two defences, and scikit-learn applies both by default:

Multiple restarts. Run the whole thing several times from different random starts and keep whichever run achieved the lowest inertia. That is the n_init parameter.

k-means++ initialisation. Rather than choosing all centres at random, choose the first at random and then choose each subsequent one with probability proportional to the squared distance from the nearest existing centre. Points far from every current centre are very likely to be picked, so the initial centres are spread out rather than clumped. This typically converges faster and to better solutions, and it is the default (init="k-means++").

The step that decides whether any of this works

K-means minimises squared Euclidean distance. Distance is computed in whatever units your features happen to be in. So the feature with the largest numeric range dominates the entire clustering.

Two customers:

Spend contributes 99.6% of the squared distance. A customer placing 48 orders a year is treated as nearly identical to one placing 2, because their spend is similar. Every cluster you get back will be a spend band, and you will have spent a week rediscovering the arbitrary boundaries you were trying to avoid.

After standardising each feature to mean 0 and standard deviation 1, the differences become comparable — perhaps 0.3 standard deviations of spend against 2.1 of order frequency — and the clustering reflects behaviour rather than units.

1from sklearn.pipeline import make_pipeline2from sklearn.preprocessing import StandardScaler3from sklearn.cluster import KMeans45model = make_pipeline(6    StandardScaler(),7    KMeans(n_clusters=4, n_init=10, random_state=42),8).fit(X)

One nuance: standardising gives every feature equal influence, which is a choice, not a neutral act. If you have twelve features about spending and one about location, standardising means the clustering is twelve-thirteenths about spending. Weighting features deliberately — or dropping redundant ones — is part of the job.

Choosing k

The algorithm requires $k$ up front and will cheerfully produce whatever number you ask for, including nonsense. Three approaches, used together.

The elbow method

Plot inertia against $k$. Inertia always falls as $k$ rises — at $k = n$ every point is its own cluster and inertia is zero — so you are looking for the point where the improvement stops being worth it.

Reductions of 21,400 → 9,700 → 5,200 then suddenly 1,200. The bend is at $k = 4$. Be honest about this method's weakness: on real data the curve is frequently smooth with no visible elbow at all, and different people reading the same plot pick different values.

Silhouette score

More principled, because it measures both tightness and separation. For each point $i$:

where $a(i)$ is the mean distance to other points in its own cluster and $b(i)$ is the mean distance to points in the nearest other cluster.

A worked value: a point sits 0.8 units on average from its own cluster-mates and 3.2 from the nearest other cluster. $s = (3.2 - 0.8)/3.2 = 0.75$ — comfortably inside its own group. A point with $a = 2.9$ and $b = 3.1$ scores 0.06, meaning it sits almost exactly on the boundary. A negative score means the point is closer to another cluster than its own, which is a genuine misassignment.

The criterion that outranks both

The business constraint. If marketing can run four campaigns, $k = 4$ regardless of what the silhouette plot prefers, and the metrics are then used to check whether four is a defensible description rather than to choose the number.

1import numpy as np2from sklearn.metrics import silhouette_score, davies_bouldin_score34X_scaled = StandardScaler().fit_transform(X)56for k in range(2, 9):7    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X_scaled)8    print(f"k={k}  inertia={km.inertia_:10,.0f}  "9          f"silhouette={silhouette_score(X_scaled, km.labels_):.3f}  "10          f"davies-bouldin={davies_bouldin_score(X_scaled, km.labels_):.3f}")

Davies-Bouldin measures average similarity between each cluster and its most similar neighbour; unlike the other two, lower is better. When the three measures disagree, that itself is information — usually that the data has no strong cluster structure and any $k$ is a description you are imposing rather than discovering.

What k-means assumes, and how it fails

Because it assigns every point to the nearest mean, k-means implicitly assumes clusters are round, similar in size, and similar in density. Real data often disobeys.

That last row is the one that costs money. K-means never refuses. Ask for six segments in uniformly distributed data and you will get six segments, complete with cluster profiles and a slide deck. The silhouette score is your main protection: a mean silhouette of 0.11 means the partition is essentially arbitrary, whatever the cluster means look like.

   Works well                  Fails badly   ---------                   -----------    o o     x x                    o o o o   o o o   x x x               o x x x x x o    o o     x x                o x   o o  x o                                o x x x x x o   round, separated,               o o o o   similar sizes            k-means cuts the rings in half

A segmentation, end to end

1import pandas as pd2import numpy as np3from sklearn.preprocessing import StandardScaler4from sklearn.cluster import KMeans5from sklearn.metrics import silhouette_score67df = pd.read_csv("customers.csv")8features = ["annual_spend", "orders_per_year", "avg_basket",9            "days_since_last_order", "tenure_years"]1011# skewed monetary features benefit from a log transform before scaling12X = df[features].copy()13X["annual_spend"] = np.log1p(X["annual_spend"])14X["avg_basket"] = np.log1p(X["avg_basket"])1516scaler = StandardScaler()17X_scaled = scaler.fit_transform(X)1819km = KMeans(n_clusters=4, n_init=10, random_state=42).fit(X_scaled)20df["segment"] = km.labels_2122print("silhouette:", round(silhouette_score(X_scaled, km.labels_), 3))2324# profile each segment in ORIGINAL units, which is what stakeholders read25profile = df.groupby("segment")[features].mean().round(1)26profile["n"] = df["segment"].value_counts().sort_index()27profile["share"] = (profile["n"] / len(df) * 100).round(1)28print(profile)

Two details in that code carry real weight. The log transform tames monetary features, which are almost always right-skewed — without it, a handful of enormous spenders sit so far from everyone else that they pull a centre out to meet them and you get a cluster of eleven people. And profiling in original units matters because "mean spend £2,340" is actionable while "mean spend 1.8 standard deviations" is not.

The output might look like this:

Note that the algorithm produced the numbers and a person produced the names. K-means found that four coherent bundles exist; it has no concept of "loyal" or "lapsed". That interpretation step is where the value is created and where the errors get made.

When your data is large

Standard k-means recomputes distances from every point to every centre on every pass — $O(n k p)$ per iteration. Beyond a few hundred thousand rows, use MiniBatchKMeans, which updates centres from random subsamples. It is typically 10–50 times faster with inertia a few percent worse, which is almost always the right trade.

What this means when you build something

Treat the clustering itself as the cheap part. Getting KMeans to run takes three lines; the work is in the decisions around it.

Scale your features, and log-transform the skewed monetary ones before scaling, or the algorithm will cluster on whichever column has the largest raw numbers. Choose the feature set deliberately, remembering that adding five correlated spending columns quietly makes the segmentation five times more about spending. Run with several values of $k$ and check the silhouette before believing any of them — if it sits below 0.25, the honest report is "this data does not contain distinct segments", which is a genuine finding and better than four fabricated ones.

Then profile the clusters in original units and take them to someone who knows the business. If they cannot recognise the groups, the segmentation is not wrong exactly — it is just a partition of a space, and every partition is valid. It simply is not useful, and useful is the only standard that applies to a result nobody can score.