k-means is the classic clustering algorithm: given a set of unlabeled points and a number k, it splits them into k groups, each represented by its center. It is the first species in this Pokédex that learns without a teacher (unsupervised learning): there is no class to predict, only "natural" groups that presumably reflect some mechanism in the domain (Witten et al., 2017, p. 141).
How it works
Each point is a vector. The procedure described by Witten et al. (2017) has five steps (2017, pp. 142–143):
- Fix k in advance.
- Pick k points at random as initial centers.
- Assign each point to the nearest center (Euclidean distance).
- Replace each center with the mean, or centroid, of its points: hence "means."
- Repeat steps 3 and 4 until no assignment changes.
In the book's example, fifteen points with k = 3 settle down in a few rounds (Witten et al., 2017, p. 143). Convergence is guaranteed because no step makes things worse: the centroid is the point that minimizes the sum of squared distances within a group, and assigning each point to the nearest center reduces it too; the overall effect is to minimize the total squared distance (Witten et al., 2017, p. 144). In today's terms, it is a loss function optimized in turns.
The name comes from MacQueen (1967). The alternating procedure had already been formulated by Stuart Lloyd at Bell Labs in 1957, for quantizing signals in pulse-code modulation (PCM), although it was published only in 1982 (Lloyd, 1982); hence the name "Lloyd's algorithm."
What changed
Compared with k-nearest neighbors, which keeps every example, k-means summarizes: each group is condensed into a single vector, and its parameters are just k × d numbers (k centers in d dimensions). The assignment step carves space into convex cells, one per center: the same geometry kNN uses with all its examples, but with only k representatives.
Limits
The minimum it finds is local: the result depends on the initial seeds, and small changes can produce very different clusterings. Witten et al. (2017) give a minimal example: four points at the corners of a rectangle; if the seeds fall at the midpoints of the long sides, the solution is stable and wrong (2017, p. 144). The usual remedy is to run it several times and keep the best result, or to seed with k-means++, which picks each seed with probability proportional to its squared distance from those already chosen (Witten et al., 2017, p. 144).
The deeper problem is k, a hyperparameter. On the training data, the "best" clustering by total distance is always one cluster per point; one must penalize extra clusters (for instance with minimum description length) or test successive splits (Witten et al., 2017, p. 146). Add to this its inductive bias: it assumes compact, convex groups.
With text, the typical pipeline is to turn documents into embeddings, reduce their dimension, and only then cluster (Alammar & Grootendorst, 2024, p. 139). k-means is a common choice, but it requires knowing k; density-based methods such as HDBSCAN decide the number of clusters themselves and leave outliers unassigned (Alammar & Grootendorst, 2024, p. 143).