Clustering

Look back at Parts 2 and 4. Train/test splitting, cross-validation, precision and recall — all of it assumed somebody had already written down the right answer for every example, so the model’s answer could be compared against it. That comparison is the entire honesty toolbox. Take away the right answers and every tool in it stops working, not because the problem got harder, but because the ingredient they all need is gone.

Nobody labelled which customers belong together, which genes switch on as a set, which documents are about the same thing. There is no drawer of correct groupings to hold back and grade against later, because no correct grouping was ever written down. This is unsupervised learning: structure found in the points themselves, with no answer key anywhere in the building.

The algorithm in this chapter, k-means, is the simplest and most common way to do it. You tell it how many groups to look for. It looks. It always reports back a grouping — never a shrug, never an “I don’t see anything here.” Whether that grouping means anything is a question the algorithm has no way to answer, and neither will you until you build the habit of asking it separately, every time.

Start by dropping k points onto the plot — the centres. Everything else follows from two moves, repeated:

1. 1

   Assign

   Every point joins whichever centre is currently closest to it, measured in plain straight-line distance.

2. 2

   Move

   Each centre slides to the mean position of the points that just joined it — its own little average.

   A centre nobody joined does not move. There was nothing to average.

Repeat both steps until an assign round changes nobody’s group. That has to happen eventually: each move can only shrink or hold the total squared distance from every point to its centre — never grow it — and there are only finitely many ways to split a fixed set of points into k groups. A quantity that keeps shrinking and can only take finitely many values has to stop shrinking. That is the whole termination argument, and it says nothing about where it stops.

That squared-distance total has a name: inertia. It is the only thing k-means is minimising. Not how sensible the groups look to you, not whether they match anything you care about — just that one number, and it will happily settle for a bad answer as long as moving further would not lower it.

Run k = 3 on the data above with a centre dropped near each group you can actually see, and it converges in two rounds to an inertia of about 88,639. Drop all three centres together in one corner instead, and it takes three rounds to land at roughly 255,560 — nearly three times worse — with one centre never claiming a single point. Both runs finish. Both print a number with the same confidence. Nothing about the output tells you which one to trust; you have to already know, or go find out.

Run k-means for k = 1 to 8 on 300 generated points that really do come from three groups.

from sklearn.cluster import KMeansfrom sklearn.datasets import make_blobs # 300 unlabelled points that really do come from 3 groups.X, _ = make_blobs(n_samples=300, centers=3, cluster_std=1.2, random_state=4) for k in range(1, 9):    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)    print(f"k={k}: inertia {km.inertia_:8.0f}")# Inertia always falls as k grows. Look for where the drops become small.

Inertia drops from 8,029 to 1,477 to 760, and after that each extra centre buys only around a hundred: 648, 554, 467. The elbow is at 3. Change centers or cluster_std and see how quickly it stops being obvious.

There is a second assumption buried in the method itself, and it is easy to miss because nothing in the algorithm checks it. Distance to a single centre is only a sensible way to describe a group if the group is roughly round and roughly the same size as the others.

Here is the part that should worry you more than a bad elbow chart. Feed k-means pure noise — points scattered with no structure in them at all — and ask for three groups. It will not tell you there is nothing to find. It will draw three regions, hand you three centres, and report an inertia number exactly as confidently as it would on real structure. Clusters always come back. The algorithm has no mechanism for reporting “this is meaningless,” because meaning was never part of what it computes.

That confidence is manufactured, not earned, which is the dangerous part of this chapter’s algorithm. A classifier that is wrong will eventually meet a test set that says so. A clustering that is wrong meets nothing — there is no label to contradict it, so a meaningless grouping and a real one look identical in the output. The only thing that tells them apart is a check you choose to run.

None of that turns a hypothesis into proof. It turns a number the algorithm was obligated to produce into a claim you are willing to stand behind, which is a different and much smaller thing.