20  Finding Kinds of Places: k-Means

Keywords

Quarto, reproducible publishing, coding agents, Markdown, Python, EPUB, data analysis, k-means clustering

The water data now have 11,235 prepared rows, each described by nine z-scores. Nobody can read that many rows. Clustering turns them into a few kinds that a person can name, compare and act on: these municipal zones are like each other, and unlike those. An official can ask which kinds need which help; a council can see which kind its own zones belong to. Clustering needs no labels, so it is a first look at data nobody has categorised, and an odd cluster can point to a data error or a special case. What it cannot do is explain: clusters describe, they do not show causes.

If the mathematics sounds daunting, it need not be. The algorithm is simple enough to watch step by step, and the judgement it needs, how many kinds to look for, is a decision you can write down and check before seeing the answer.

In this chapter
  • Describe the k-means loop, and why it needs many starts and a fixed seed.
  • Apply the written rule for k, and say how close the call was.
  • Interpret a low silhouette, a stability check and a PCA picture without over-reading them.
  • Run the clustering step and check the agent’s account of k.

Start fromThe project as Chapter 19 left it.

You buildThe clustering step, outputs/clusters.parquet and clusters.qmd.

Checkpointcheckpoints/07-water-cluster/.

20.1 k-means in four steps

k-means needs one number up front: \(k\), how many clusters to find. It makes one start, then repeats two moves until they change nothing:

  1. Drop \(k\) centres at \(k\) randomly chosen data points.
  2. Assign every point to its nearest centre.
  3. Move each centre to the mean of the points assigned to it.
  4. Repeat 2 and 3 until nothing changes.

Neither move ever raises the inertia, the sum of squared distances from each point to its centre,

\[\text{inertia} = \sum_{i} \lVert x_i - c_{\ell(i)} \rVert^2 ,\]

where \(x_i\) is point \(i\) (for the water data, a row’s nine z-scores), \(c_{\ell(i)}\) is the centre it is assigned to, and \(\lVert x_i - c_{\ell(i)} \rVert\) is the straight-line distance between them (Section 19.3). On z-scores, inertia is in squared standard deviations, a unit with no everyday meaning, so only its changes matter. There are only finitely many ways to group the points, so the algorithm always stops. It does not always stop at the best answer: a bad start can trap it in a worse grouping. Figure 20.1 shows the algorithm on 560 synthetic points in three groups, which are toy data made up for the illustration, not the water data.

1. drop 3 centres at random points

Figure 20.1: k-means on synthetic toy points. The numbered buttons step through the algorithm and “fix” stops the autoplay; “start 1” to “start 3” pick one of three random starts, of which two reach the best grouping and one gets stuck. Drag to turn.
Four small scatter plots of the toy points. In the first, all points are grey and three centres sit at random points. In the second, points are coloured by their nearest centre and the colours split the groups badly. In the third the centres have moved towards the three groups. In the fourth each group has its own colour with its centre in the middle.
Figure 20.2: The same algorithm on the toy points, flattened to two of their three dimensions: the random start, the first assignment, an assignment halfway, and the stable result.

Different starts can end in different groupings, so the real analysis runs k-means from 20 starts (scikit-learn’s n_init) and keeps the one with the lowest inertia. The starts are random, but repeatable: a fixed random seed, the number that starts the computer’s random-number generator, makes them the same on every run, so your project, the deck and this book all get the same clusters.

NoteWhy this works

The real starts are not dropped at random, as in the toy. scikit-learn’s default, k-means++ (Arthur and Vassilvitskii, 2007), picks the first centre at random from the data and each next one with probability proportional to its squared distance from the nearest centre already chosen. That spreads the centres out and makes a stuck start less likely; scikit-learn uses a greedy variant that draws several candidates at each step and keeps the best.

20.2 Choosing k

k is a hyperparameter: a setting the algorithm cannot learn from its own objective, because inertia always falls as k grows, down to zero when every point is its own cluster. So the analysis fits k-means for k from 2 to 8 and reads two measures (Figure 20.3). The first is where inertia stops falling much, the elbow. The second, the silhouette, scores from −1 to 1 how much closer each point is to its own cluster than to the next one, averaged over the points. It needs every distance between points, so it is computed on a fixed sample of 5,000 rows, which keeps it fast.

Two line charts over k from 2 to 8. Inertia falls steadily, steeply at first and more gently after k equals 4. The silhouette is highest at k equals 2, then flat near 0.19 to 0.20 from k equals 3 to 7, and lower at 8. The chosen k, 4, is marked on both.
Figure 20.3: Choosing k: inertia and silhouette for k = 2 to 8, fitted on all kept rows. The chosen k is marked.

The rule, written into choose_k() in the analysis script, has three parts, and Table 20.1 applies it row by row:

  • k = 2 is excluded. Two clusters mostly split urban from rural rows, which we knew already: they match the zone for 86% of rows. The script measures this with the adjusted Rand index (ARI), which scores how far two groupings agree beyond what chance would give: 1 means identical, 0 no better than chance. Here it is 0.50.
  • The elbow: take the smallest k from 3 up after which one more cluster cuts inertia by less than 10%. Here that is k = 4: a fifth cluster cuts inertia by only 7%.
  • The silhouette check: k’s silhouette must be within 0.01 of the best for k ≥ 3. At k = 4 it is 0.195. The check rules out only k = 8 here.
Table 20.1: choose_k()’s rule, row by row, on the kept rows: how much one more cluster would cut inertia, the silhouette (on the fixed sample) and the verdict. Computed by the finished project’s analysis.py.
k One more cluster cuts Silhouette Verdict
2 14.9% 0.237 excluded: the urban–rural split
3 10.8% 0.194 one more still cuts 10% or more
4 6.7% 0.195 chosen: the smallest that passes
5 6.3% 0.189 passes, but larger
6 5.4% 0.196 passes, but larger
7 4.7% 0.191 passes, but larger
8 – 0.166 silhouette too far below the best

The elbow is marginal. The fourth cluster itself cuts inertia by 10.8% (the row for k = 3), only just above the 10% threshold, so a threshold of 11% would pick k = 3 instead. And the four clusters account for 41% of the spread in the data, one minus the ratio of their inertia to that of a single cluster; the rest is difference within the kinds.

Two more checks follow the fit. Stability: refits from 5 other seeds agree, with an adjusted Rand index of at least 0.998, so the result does not depend on the start. That says nothing about other data, features or k; refitting on rows drawn again at random (a bootstrap), or leaving out one year at a time, would test that. Ordering: clusters are numbered by their centre’s IRCA, from lowest to highest, so a re-run keeps the same numbers and colours.

WarningCommon pitfall

A silhouette near 0.2 is low. In the subjective reading Rousseeuw and colleagues propose, a best average silhouette of 0.25 or less means that “no substantial structure has been found” (Struyf, Hubert and Rousseeuw, 1997, Table 2), and the best here, at any k, is 0.24. The kinds overlap: they summarise a continuum rather than separate islands of data. So treat k as a judgement call, and do not force a number of clusters to make a nicer story. Writing the rule down before seeing the result is what keeps such a choice honest; choose_k() at least makes the rule explicit, so anyone can check it and see how close the call was.

Pause and think

An official reads the report and asks: “So Colombia has four kinds of municipal zone?” What do you answer?

Answer

That four is a useful summary, not a discovery. A written rule chose it by a narrow margin, and a threshold one percentage point higher picks three; the low silhouette says the kinds overlap. The clusters describe typical combinations of water, services and context, and a zone near the edge of one could as well sit in the next.

20.3 A picture of the clusters

Nine dimensions cannot be drawn. Principal component analysis (PCA) finds the directions in which the data vary most and projects the rows onto them. Each direction, a principal component, is a weighted sum of the nine z-scores, and its weights, called loadings, say what it measures. Figure 20.4 uses the first two components, which keep 30% and 21% of the variance.

Scatter plot of about eleven thousand dots in four coloured groups that overlap at their edges. Cluster 4 spreads to one side, clusters 1 and 2 to others, and cluster 3 sits in the middle, drawn on top.
Figure 20.4: Each dot is a zone-year on the first two principal components of the nine z-scored features, coloured and shaped by cluster. PCA is only for the picture: k-means used all nine features.

Overlaps in the picture can be separations in the dimensions it leaves out. Adding a third component, which keeps another 16% of the variance, shows how much (Figure 20.5). On two components, on average 78% of a zone-year’s 15 nearest neighbours are in its own cluster; on three, 94%. The third component rises with altitude and falls with rainfall, its two largest loadings. Cluster 3, the most mixed in two dimensions, sits below the others along it: it is the lowest and wettest of the kinds.

Figure 20.5: The zone-years on the first three principal components, coloured and shaped by cluster. Face on, the cloud is the 2-D picture. Drag to turn and scroll to zoom.

20.4 Where the clusters stand

Altitude carries the third component’s largest loading. A map shows altitude directly (Figure 20.6): one column for each of the 966 clustered urban zones in 2023, at its municipality’s centroid, as tall as its head town’s altitude (one derived SRTM point, exaggerated 50 times) and coloured by cluster.

Figure 20.6: Clustered urban zones as columns at their head towns’ altitude, coloured by cluster. Labels name the ten most populous department capitals and Tunja. Drag to turn and scroll to zoom.

Cluster 2’s urban zones stand highest, with a median altitude of 1,766 m, and 56% of them are in the region Centro Oriente (DANE’s regional grouping). Cluster 3’s stand lowest, at 130 m, and 53% of them are in Caribe. This shows where the kinds are, not why they differ. Tunja’s head town stands at 2,695 m, and all 16 of its zone-years, urban and rural, fall in cluster 1.

The map draws urban zones only, one column per municipality, because the altitude is the head town’s. So it shows little of cluster 4, whose zone-years are 91% rural. Its few urban columns stand low, at a median of 159 m, but the median head-town altitude of its rural zone-years is 1,475 m, so the map says little about where that kind is found.

20.5 Use the model, or build it

There are two routes through the modelling, and both end with the same outputs/ and the same pages:

  • Use it (the normal route): copy the finished analysis.py from this step’s checkpoint, run it, and spend your effort on checking what it chose and on the publications.
  • Build it (a challenge): give the agent the prompt below and have it write the clustering step itself.

This is a book about publishing, so using the finished model is the normal route, not a fallback. But a copied script is only as trustworthy as your reading of it, so the route has two prompts: one runs the script, the other makes the agent explain what it printed.

Ask your coding agent
Copy ../quarto-workshop/checkpoints/07-water-cluster/scripts/analysis.py over scripts/analysis.py (keep mine as scripts/analysis-before-07.py), run it with `uv run python scripts/analysis.py`, and tell me k.
Expect it to run

copies the script, keeping yours · uv run python scripts/analysis.py · reports k = 4

Among its output, the script prints the table behind Figure 20.3 and then its verdict in one line, which on this book’s data reads:

k = 4: the next cluster cuts inertia by only 7% (< 10%), and its silhouette 0.195 is within 0.01 of the best k >= 3 (0.196).

Ask the agent to take that line apart:

Ask your coding agent
Explain what scripts/analysis.py printed about k: what `inertia`, `silhouette`, ari_vs_zone and inertia_drop mean for each k, and which test in choose_k() chose k. Quote the lines of choose_k() that decide it.
Expect it to run

reads the printed table and choose_k() · explains each column and the rule, quoting the code

Pause and think

While it explains: which test in choose_k() chose k, and which could only have ruled one out?

Answer

The elbow chose it: k = 4 is the smallest k from 3 up after which one more cluster cuts inertia by less than 10%. k = 2 is excluded before any test, and the silhouette check only vetoes: it rules out only k = 8 here. Check the agent’s explanation against this and Table 20.1: one that says the silhouette chose k has misread the rule.

To build it instead (optional):

Ask your coding agent
In scripts/analysis.py, run k-means on the z_ features for k=2–8 (random_state=42, n_init=20); save inertia and silhouette to outputs/k_selection.csv; pick k by the elbow, check silhouette and 5-seed ARI; number clusters by centroid IRCA; save outputs/clusters.parquet (prepared columns + `cluster`, pc1, pc2). Run it; explain k.
TipIn practice

If you build it, your k may differ from 4 when your preparation differs, and that is fine if the reason is sound. What matters is that the rule for choosing k is written down before you see the answer, and that the clusters are numbered by a fixed rule (here, centre IRCA, which the prompt calls centroid IRCA), so a re-run keeps the same numbers and colours.

20.6 The clusters page

Both routes then build the project’s second page, which only reads outputs/ and never refits:

Ask your coding agent
Create clusters.qmd that reads outputs/k_selection.csv and outputs/clusters.parquet and shows an elbow plot, silhouette by k and a PCA scatter (pc1, pc2) coloured by cluster, each with a caption and alt text. Render it and tell me about errors.
Expect it to run

writes clusters.qmd · uv run quarto render clusters.qmd

You do

open clusters.html in your browser

ImportantTry it

Take one route through the model, then build the clusters page.

You’re done when outputs/clusters.parquet exists, you can say what k is and why, and clusters.html shows the elbow, the silhouette and the PCA picture.

Stuck for two minutes? Paste this into your agent. It backs up your work and brings the project to this point; then carry on from here.

Catch me up: follow ../quarto-workshop/checkpoints/07-water-cluster/README.md

Summary

  • k-means assigns points to the nearest centre and moves centres to their points’ mean; it can stall, so it keeps the best of many seeded starts.
  • k is chosen by a rule written beforehand: exclude k = 2, take the elbow, let the silhouette veto.
  • The elbow is marginal and the silhouette low: the kinds summarise a continuum.
  • Agreement across seeds shows independence from the start, not from the data or features.
  • PCA and the map show where the kinds stand, not why, and the map leaves rural zone-years out.
  • Using the finished model is legitimate if you can explain what it chose.

The kinds so far are only numbers, from cluster 1, lowest centre IRCA, to cluster 4: the next chapter works out what sets each one apart, names it by a rule, and compares the outcomes the clustering never saw.

Further reading

  • scikit-learn, Clustering: k-means and silhouette analysis (checked 2026-11-12).
  • scikit-learn, Principal component analysis (checked 2026-11-12).
  • Stuart P. Lloyd, “Least squares quantization in PCM”, IEEE Transactions on Information Theory 28(2), 129–137, 1982, https://doi.org/10.1109/TIT.1982.1056489: the algorithm behind k-means (checked 2026-11-12).
  • Peter J. Rousseeuw, “Silhouettes: a graphical aid to the interpretation and validation of cluster analysis”, Journal of Computational and Applied Mathematics 20, 53–65, 1987, https://doi.org/10.1016/0377-0427(87)90125-7: the silhouette (checked 2026-11-12).
  • Anja Struyf, Mia Hubert and Peter Rousseeuw, “Clustering in an object-oriented environment”, Journal of Statistical Software 1(4), 1997, https://doi.org/10.18637/jss.v001.i04: Table 2 reads the silhouette coefficient (checked 2026-11-12).
  • David Arthur and Sergei Vassilvitskii, “k-means++: the advantages of careful seeding”, SODA 2007 (ACM-SIAM Symposium on Discrete Algorithms), https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf (checked 2026-11-12).
  • examples/water/references.bib in the workshop repository: the k-means, silhouette and adjusted Rand index papers the finished white paper cites, checked against their publishers’ pages.