Problem. Given points X (n × d) and k, find k centroids that minimise the inertia: the sum of squared distances from each
point to its nearest centroid. Use Lloyd's algorithm:
- Assign: each point goes to its nearest centroid.
- Update: each centroid moves to the mean of its assigned points.
- Repeat until the assignments stop changing (or a maximum number of iterations).
Both steps can only lower (or keep) the inertia: assigning to the nearest centroid can't increase any point's distance, and the mean is the point that minimises the sum of squared distances to a set. So the loop always converges, though possibly to a local minimum that depends on the starting centroids.
ML context. k-means is the default clustering baseline, and much more: it builds the coarse quantiser of IVF vector indexes (lesson 15.2's Change C), the codebooks of product quantisation and vector-quantised models, colour palettes, and data-deduplication clusters. In an ML round you're expected to vectorise both steps, handle empty clusters, and know why initialisation matters.