Concept · Chapter 3: Machine Learning
k-Means Clustering
k-means groups unlabelled points into k clusters by alternating two steps: assign each point to its nearest centre, then move each centre to the mean of its points.
The problem
With no labels, we still want to discover natural groups — customer segments, topics, colour palettes.
The solution
Choose k centres, then repeat: assign every point to the nearest centre; recompute each centre as the average of its assigned points; stop when nothing changes.
The consequence
It's simple, fast and everywhere — and its core move, 'find the nearest centroid', reappears in vector quantization, approximate nearest-neighbour indexes and tokenizing images and audio.
You should understand first
The loop
Initialize
Pick k starting centres (e.g. k random points).Assign
Each point joins the cluster of its nearest centre.Update
Each centre moves to the mean of its cluster's points.Repeat
Until assignments stop changing. Each round never increases the total squared distance, so it always converges — to a local optimum, which is why it's often run several times from different starts.
Where it shows up later
The inverted-file (IVF) indexes used by vector databases (Chapter 12) cluster embeddings with k-means so a search only has to scan the few clusters nearest the query.
What to remember
- Unsupervised: no labels.
- Repeat: assign to nearest centre → move centre to mean.
- Minimizes within-cluster squared distance; finds a local optimum.
- You must choose k; results depend on initialization.
Key papers
Least squares quantization in PCM
S. Lloyd · 1982 · IEEE Transactions on Information Theory
The paper behind 'Lloyd's algorithm', the standard iterative procedure for k-means clustering (circulated at Bell Labs in 1957, published 1982).