Concept30 min

k-Means Clustering

How do you split customers into groups when nobody has labelled them?

The situation

Marketing wants three campaigns, one per kind of customer, but no column says which kind each customer is. The interviewer asks:

How does k-means work, and does it always find the best clustering?

Running example (shared by all six unsupervised lessons): a food-delivery app wants to group its customers without any labels. Each customer has two numbers, orders per month and average basket size, both standardised (mean 0, standard deviation 1). The simulated base has 180 customers drawn from three hidden segments: occasional small orders, frequent small orders, and occasional big orders. The algorithm never sees the segment; we use it only to score the result (adjusted Rand index, ARI: 1 = perfect agreement, 0 = chance).

Group customers when nobody has labelled them

Marketing wants three campaigns, one per kind of customer. There's no column saying which kind each customer is; that's the thing we want to discover. Clustering finds groups of points that are close to each other and far from other groups. k-means is the simplest and most used clustering method: fast, easy to explain, and the baseline every other method is compared with.

The idea

Think of opening three shops in a town. Each customer goes to their nearest shop. Then each shop moves to the middle of its customers. Customers re-choose, shops move again, and you repeat until nothing changes.

Illustrative. The assign and move steps repeat until the groups stop changing.

Play

Try to break it. Run start A until no points switch, and note the inertia. Then reset and run starts B and C.

Run it yourself

Step through Lloyd's algorithm on the customers

step

–

inertia

–

points that switched

–

k = 3, random starting centroids (three random customers). Grey points: not assigned yet. Watch the inertia fall at every step until nothing switches.

Now say why: why doesn't every start reach the same answer, and how would you protect against a bad one?

Maths

In one breath

k-means splits data into k groups by placing k centroids and repeating two steps: assign every point to its nearest centroid, then move each centroid to the mean of its points. Each step lowers the inertia (total squared distance to centroids), so it always converges, but only to a local minimum that depends on where you started, which is why k-means++ seeding and several restarts matter. You must choose k yourself (elbow, silhouette, or business sense), and because it measures squared Euclidean distance to a centre, it assumes round, similar-sized clusters: elongated, curved or uneven groups break it.What you'll be able to do after this: run Lloyd's algorithm by hand, explain why it converges and why it gets stuck, pick k with two methods, and name the shapes k-means can't handle.

cluster 1cluster 2cluster 3 (more clusters use more colours)centroids (◆)numbersfailure

Centroids and inertia

Describe each group by its centroid, the average customer in it. A good grouping keeps every customer close to their own group's centroid. k-means measures this with the inertia, the within-cluster sum of squares:

scikit-learn: k-means works by "minimizing a criterion known as the inertia or within-cluster sum-of-squares" clustering guide.

One principle

Alternate two easy problems

Minimising inertia over groupings and centroids together is hard. But each half is easy on its own:

Swipe sideways to see the whole diagram.

Nine customers and two starting centroids (◆), placed badly on purpose.
Assign: with centroids fixed, the best grouping is obvious: each point joins its nearest centroid. The middle customer joins the right one.
Update: with the grouping fixed, the best centroid is obvious too: the mean of its points (the mean minimises the sum of squared distances).
Assign again with the new centroids: the middle customer is now closer to the left centroid and switches. Update again.
Neither step can increase inertia, and there are finitely many groupings, so this always stops. That's Lloyd's algorithm.

scikit-learn: "Given enough time, K-means will always converge, however this may be to a local minimum. This is highly dependent on the initialization of the centroids" clustering guide. The algorithm is from Lloyd (1957 report, published 1982).

Better starts

Local minima, and k-means++

A bad start can trap Lloyd's algorithm: two centroids share one true group while another centroid sits between two groups, and no single assign/update step can fix it. k-means++ (Arthur & Vassilvitskii, 2007) picks the first centroid at random, then each next one with probability proportional to its squared distance from the nearest centroid chosen so far, so starts are spread out.

Seed

final inertia (best found: 53.4)

–

matches the true groups? (ARI)

–

bad runs out of 50 seeds

–

Five well-separated groups of 40 customers each, k = 5, a single run per seed. Try seeds until you find a stuck run: one big group split in two and two groups merged.

On this data, a single run with random starts got stuck in 15 of 50 seeds; with k-means++, in 6 of 50. The worst random run had inertia 697, against 53.4 for the right answer. The fix that always works is cheap: run several starts and keep the lowest inertia (scikit-learn's n_init). Arthur & Vassilvitskii proved k-means++ seeding alone is expected to be within a factor of 8(ln k + 2), i.e. O(log k), of the optimal inertia SODA 2007.

Choosing k

Elbow and silhouette

Inertia always falls as k grows (k = n gives inertia 0), so you can't pick k by minimising it. Two common aids:

Elbow: plot inertia against k and look for the bend where adding a cluster stops helping much.
Silhouette: for each point, a = mean distance to its own cluster, b = mean distance to the nearest other cluster; s = (b − a) / max(a, b), between −1 and 1. Average over points; higher means tighter, better-separated clusters.

inertia

–

silhouette

–

agreement with hidden segments (ARI)

–

On the customers, inertia drops from 583 (k = 1) to 314 (k = 2) to 97 (k = 3), then only to 83 at k = 4: a clear elbow at 3. The silhouette peaks at k = 3 too (0.64). Real data is rarely this clean; often there's no sharp elbow, and the right k is the one the business can act on (three campaigns, not seven). my take scikit-learn's caution about the silhouette: it is generally higher for convex clusters than for density-based ones, so don't use it to compare k-means with DBSCAN.

In practice

The clustering toolbox

Method	Finds	You choose	Lesson
k-means	Round, similar-sized groups	k	this one
Hierarchical	A tree of nested groups	linkage, where to cut	next
DBSCAN / HDBSCAN	Any shape; marks noise	density (eps, min_samples)	lesson 3
Gaussian mixtures	Elliptical groups, soft membership	k, covariance type	lesson 4

scikit-learn ships all of these with the same fit/predict interface clustering guide.

The whole recipe

Scale features (StandardScaler); consider PCA first if there are many.
Fit with k-means++ and several starts (n_init), for a range of k.
Choose k with the elbow and silhouette, then sanity-check that the clusters mean something to the business.
Describe each cluster by its centroid (in original units) and size.
Check stability: refit on a resample; clusters that change a lot aren't real.

Cost: each Lloyd iteration is O(n·k·d). For millions of rows, MiniBatchKMeans updates centroids from small random batches, trading a little inertia for big speed-ups clustering guide.

When to use it

Use k-means when

You want a quick segmentation with a fixed number of groups
Groups are roughly blob-shaped after scaling
Data is large and you need speed

Reach for something else when

Shapes are curved or density varies: DBSCAN/HDBSCAN
You need probabilities of membership: GMM
You want a hierarchy or don't know k: hierarchical clustering

The answer that sounds right

The trap

"Just try every possible grouping and keep the best"

The number of ways to split 180 customers into 3 non-empty groups is about 3¹⁸⁰ / 6, roughly 10⁸⁵, more than the number of atoms in the observable universe. Finding the grouping with the lowest inertia exactly is NP-hard in general. So every practical method is a heuristic that finds a good grouping, not a guaranteed best one. k-means is the heuristic that won because each step is cheap and provably helps.

The shape assumption

Round, similar-sized clusters only

Assigning each point to the nearest centre draws straight boundaries halfway between centroids (a Voronoi diagram). scikit-learn: "Inertia makes the assumption that clusters are convex and isotropic, which is not always the case. It responds poorly to elongated clusters, or manifolds with irregular shapes" clustering guide.

agreement with the true groups (ARI)

–

Same algorithm, best of 10 starts, true k given. Round groups: perfect. Moons: k-means cuts straight across both (ARI 0.21). Tilted groups: it slices them crosswise (ARI 0.62).

Also breaks on

Groups of very different sizes or spreads (the boundary sits halfway, cutting into the big group)
Unscaled features (one feature in rupees dominates the distance)
Outliers (squared distance lets one far point drag a centroid)
Very high dimensions: distances concentrate (see k-NN)

What to use instead

Curved or noisy shapes: DBSCAN / HDBSCAN
Elliptical or overlapping groups, soft membership: Gaussian mixtures
Outliers: k-medoids or trimming
High dimensions: reduce first with PCA

Caveats

Strengths

Fast, simple, scales to millions (mini-batch)
Centroids are easy to describe ("the average frequent small-basket customer")
Assigning new points is instant
A strong first baseline; also used for vector quantisation and as an initialiser (GMMs, IVF indexes in vector search)

Weaknesses

You must pick k
Local minima: needs k-means++ and restarts
Assumes round, similar-sized clusters; sensitive to scale and outliers
Every point is forced into a cluster; no notion of noise

Say it

How does k-means work, and does it always find the best clustering?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

k-means minimises the within-cluster sum of squared distances to the centroids.
It alternates two steps: assign to the nearest centroid, then move each centroid to the mean.
Each step can only lower the objective, so it converges, but to a local minimum.
So you use k-means++ seeding and multiple restarts.
You choose k with the elbow, silhouette or domain needs.
It assumes round, similar-sized clusters and needs scaled features.