K-Means and Its Assumptions

Two elongated, parallel groups of points, clearly separated by eye. K-means with \(k=2\) cuts across both of them, splitting each group in half and reporting a lower objective value than the answer you wanted. The algorithm did not fail; it optimised what it was asked to optimise. Everything surprising about k-means is downstream of what its objective actually says.

That objective is within-cluster sum of squares:

Minimising it exactly is NP-hard for \(k \geq 2\) in general dimension. Lloyd's algorithm is the standard heuristic: assign each point to its nearest centroid, recompute each centroid as the mean of its members, repeat.

Why it always converges, and to what

Each of the two steps is exact coordinate descent on \(J\). The assignment step minimises \(J\) over assignments with centroids fixed, because assigning a point to any other centroid increases its squared distance term. The update step minimises \(J\) over centroids with assignments fixed, because the mean is the unique minimiser of summed squared distance. So \(J\) decreases monotonically, and since there are finitely many assignments, the algorithm terminates in finite time.

It terminates at a local minimum, and the local minima can be arbitrarily worse than the global one. This is why initialisation carries most of the quality risk. K-means++ seeds centroids sequentially, sampling each new centroid with probability proportional to its squared distance to the nearest existing centroid, which gives a solution that is \(\Theta(\log k)\)-competitive with the optimum in expectation (Arthur and Vassilvitskii, 2007, SODA). It costs one extra pass per centroid and is the default in every serious implementation for good reason.

The assumptions hiding in the objective

Squared Euclidean distance to a mean encodes three assumptions, none of which is stated anywhere in the algorithm.

Clusters are spherical. The level sets of \(\|x-\mu\|^2\) are spheres, so any elongated or correlated group must be carved into pieces to be represented. A Gaussian mixture with full covariance matrices is the direct generalisation that removes this.

Clusters have similar spread. A tight cluster and a diffuse one of the same size contribute unequally to \(J\), so the algorithm steals points from the diffuse one to reduce the total.

Clusters have comparable sizes. Because every point contributes equally, a large cluster can be split in two more profitably than a small distinct cluster can be separated.

Scaling matters for the same reason. Distance sums over dimensions, so a feature measured in dollars dominates one measured in fractions; standardisation is not optional preprocessing, it is a statement about which dimensions should count equally.

Choosing k, honestly

\(J\) decreases monotonically in \(k\) and reaches zero at \(k=n\), so it cannot be used to select \(k\) directly. The elbow method looks for the point of diminishing return and is genuinely subjective; on real data the curve is frequently smooth with no elbow at all.

The silhouette score compares each point's mean distance to its own cluster against its mean distance to the nearest other cluster, giving a value in \([-1,1]\) that does not decrease automatically with \(k\). The gap statistic compares \(\log J\) against its expectation under a null reference distribution of uniformly scattered points, which is the most principled of the common options and the most expensive.

The uncomfortable truth is that all of these assume the k-means model is right. If clusters are elongated, every one of them will report a \(k\) that is a fact about the algorithm rather than about the data.

When it breaks

Non-convex shapes are unrepresentable. Two concentric rings, two crescents, any manifold structure: k-means partitions space into a Voronoi tessellation, and no Voronoi cell is a ring. Spectral clustering or DBSCAN, which work from a neighbourhood graph rather than from centroids, handle these directly.

High dimensions flatten the distances. As dimension grows, the ratio between nearest and farthest distances converges toward 1, so "nearest centroid" becomes a decision between near-identical numbers driven by noise. Reducing dimension first, with PCA or a learned embedding, is standard practice and it changes what "cluster" means.

Every point gets assigned. There is no notion of an outlier or a point that belongs to nothing. A single extreme point drags its centroid measurably, because the mean is not robust. K-medoids, which uses actual data points as centres and supports arbitrary distances, trades a large cost increase for that robustness.

Cluster labels are not stable identities. Refit on new data and the label indices permute, and the partition itself can change substantially even when the data barely did. Any pipeline treating cluster ID as a persistent key needs an explicit matching step between runs.