4 · K-Means: intuition + Lloyd's algorithm
The canonical clustering algorithm — alternate between assigning points to centroids and moving centroids to cluster means until convergence.
K-Means partitions points into K clusters by alternating: assign each point to nearest centroid, then move each centroid to the mean of its assigned points.
Without this:
Without K-Means you'd lack the canonical clustering algorithm — the unsupervised equivalent of linear regression.
Clustering is the task of grouping similar points together — without any labels. Where supervised learning says "predict the class of this point given labelled examples," clustering says "discover natural groupings in the data by structure alone."
K-Means is the most widely used clustering algorithm, with three clean ideas at its core:
-
Objective — minimise within-cluster sum of squares (WCSS), also called inertia:
WCSS = Σₖ Σ_{x ∈ Cₖ} ||x − μₖ||²
where Cₖ is the set of points in cluster k and μₖ is their mean (the centroid). Smaller WCSS = tighter, more compact clusters.
-
Lloyd's algorithm — a simple alternating minimisation that provably decreases WCSS at every step:
- (1) Initialise K centroids (randomly or via k-means++).
- (2) Assign each point to the nearest centroid (Voronoi partition).
- (3) Update each centroid to the mean of all its assigned points.
- (4) Repeat steps 2–3 until assignments stop changing.
-
Convergence guarantee — because there are finitely many possible assignments and WCSS decreases at every step, Lloyd's algorithm is guaranteed to converge. However, it converges to a local minimum of WCSS, not necessarily the global minimum. The solution depends on the initial centroids.
Why K-Means is so fundamental: it is arguably the unsupervised counterpart of linear regression — easy to interpret, fast to run, and the benchmark every other clustering method compares itself against.
Python (in browser)
K-Means on 4-blob data — points colored by cluster, black X marks are the final centroids.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Lloyd's algorithm by hand — centroid positions at iterations 0, 1, 2, 3, 5. The centroids stop moving between iteration 3 and 5: convergence.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Verifying that sklearn's model.inertia_ equals the manual WCSS formula — they match exactly.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Initialization sensitivity — each random seed gives a different inertia, showing that K-Means finds local minima whose quality depends on starting conditions.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
K-Means as a restricted EM algorithm — understanding this reveals exactly when and why it fails.
K-Means is guaranteed to converge, but only to...
- K-Means minimises WCSS (inertia) = Σₖ Σ_{x∈Cₖ} ||x−μₖ||² — the sum of squared distances from each point to its cluster centroid.
- Lloyd's algorithm alternates: assign points to nearest centroid (E-step) → recompute centroids as cluster means (M-step) → repeat until convergence.
- Convergence is guaranteed to a LOCAL minimum — different random initialisations can yield different inertias; sklearn's n_init=10 mitigates this.
- K-Means is EM restricted to isotropic equal-variance Gaussians — it assumes spherical, similarly-sized clusters.
- For elongated or irregularly shaped clusters, prefer DBSCAN or Gaussian Mixture Models over K-Means.
Customer segmentation (group similar customers), document clustering (group similar texts), image quantisation (reduce colour palette), warm-starting more complex algorithms like Gaussian mixture models.
If you remove it: You'd lack the canonical clustering tool — and most other clustering algorithms either build on K-Means' intuition or compare themselves to it.