Why K-Means Converges, and the Shape of Its Clusters

Every reassignment strictly lowers the k-means objective, and there are finitely many partitions, so Lloyd's algorithm must stop, though possibly at a local optimum. At convergence each cluster is the set of points nearer its mean than any other mean: a Voronoi region bounded by perpendicular bisectors, which is why k-means cannot find ring-shaped clusters.

Lloyd's algorithm repeats two simple moves. Could it go on forever, with points hopping between clusters in a cycle? And when it does stop, what do its clusters look like? Both questions have clean answers, and both rest on the same small fact.

One fact about means

Given any points $x_1, \dots, x_m$ , which single point $v$ minimises the total squared distance to all of them?

\min_{v} \sum_{i=1}^{m} \lVert x_i - v \rVert^2 .

The gradient with respect to $v$ is $-2\sum_i (x_i - v)$ . Setting it to zero gives $v = \tfrac{1}{m}\sum_i x_i$ , the mean. The function is a convex bowl in $v$ , so this is the global minimum: no point is closer, in total squared distance, to a set of points than their own mean.

The objective can only go down

Let the current partition be $z^{(t)}$ , with cluster means $\mu^{(t)}_k$ , and suppose the algorithm has not converged, so at least one point moves. Compare three quantities.

Before: the objective of the current partition, $F_t = \sum_i \lVert x_i - \mu^{(t)}_{z^{(t)}_i} \rVert^2 .$
Intermediate: each point measured against the old mean of the cluster it is moving to, $G = \sum_i \lVert x_i - \mu^{(t)}_{z^{(t+1)}_i} \rVert^2 .$
After: the objective of the new partition, with the new means, $F_{t+1} = \sum_i \lVert x_i - \mu^{(t+1)}_{z^{(t+1)}_i} \rVert^2 .$

$G < F_t$ . A point moves only when some other old mean is strictly closer than its own; points that stay contribute the same amount to both sums. At least one point moves, so the inequality is strict.

$F_{t+1} \le G$ . Group both sums by cluster in the new partition. In $G$ , the points now in cluster $k$ are measured against the old mean $\mu^{(t)}_k$ ; in $F_{t+1}$ , against their own new mean $\mu^{(t+1)}_k$ . By the fact above, a set of points is closest to its own mean, so each cluster's contribution can only fall.

Putting them together,

F_{t+1} \;\le\; G \;<\; F_t .

Every round that changes anything strictly lowers the objective. Therefore no partition can ever be visited twice (it would have to have a lower objective than itself). Since there are only finitely many partitions, the algorithm must stop.

Two caveats keep this honest.

The argument bounds the number of rounds by the number of partitions, which is astronomically large. In practice Lloyd's algorithm usually converges in a handful of rounds; the proof only rules out cycling.
Converging is not the same as finding the best partition. The algorithm stops at a partition where no single reassignment helps: a local optimum. A different start can stop somewhere better.

Try it yourself

Machine Learning Lab: k-means →

Step the algorithm and watch the SSE curve: it never rises. Then press "New start" a few times with random initialisation and compare where it stops.

What converged clusters look like

At convergence, every point is at least as close to its own cluster's mean as to any other mean. Start with $K = 2$ and means $\mu_1, \mu_2$ . A point $x$ in cluster 1 satisfies

\lVert x - \mu_1 \rVert^2 \le \lVert x - \mu_2 \rVert^2 .

Expand both sides; the $\lVert x \rVert^2$ terms cancel, leaving

x^\top(\mu_2 - \mu_1) \;\le\; \frac{\lVert \mu_2 \rVert^2 - \lVert \mu_1 \rVert^2}{2} .

This is a linear inequality in $x$ : the boundary is a straight line (a hyperplane in higher dimensions), perpendicular to $\mu_2 - \mu_1$ . The midpoint $\tfrac{\mu_1 + \mu_2}{2}$ satisfies it with equality, so the boundary is the perpendicular bisector of the segment joining the two means. Cluster 1 is everything on $\mu_1$ 's side of it.

With $K$ clusters, a point in cluster 1 must beat every other mean, so cluster 1 is the intersection of $K - 1$ half-spaces, one for each bisector between $\mu_1$ and another mean. An intersection of half-spaces is a convex polygon (a convex polytope in higher dimensions). The space is carved into $K$ such cells, one per mean: a Voronoi diagram.

Three cluster means in the plane, the perpendicular bisectors between each pair, and the three convex Voronoi cells they form, with points coloured by cell — At convergence, each k-means cluster is a Voronoi cell: the convex region of points nearer its mean than any other. The cell edges lie on perpendicular bisectors between pairs of means.

What k-means cannot find

Because every cluster is a convex cell with straight edges, k-means can only produce convex, roughly round clusters separated by flat boundaries. Two consequences follow.

Rings. Take points on two concentric circles. The natural clusters are the inner ring and the outer ring, but no straight boundary separates a disc from the ring around it. With $K = 2$ , k-means will draw a straight line through both rings and cut each in half.
Size and spread. The bisector sits halfway between the means regardless of how spread out each cluster is, so a large diffuse cluster next to a small tight one gets its edge points stolen.

The first problem has the same cure as PCA's: map the data to a feature space where the clusters are separated by flat boundaries, and run k-means there using only dot products. That is kernel k-means, closely related to spectral clustering, which clusters points using the leading eigenvectors of a similarity matrix. The second problem is addressed by the probabilistic view of clustering in the next module, where each cluster gets its own shape and spread.

EasyK-meansGeometry

Show that the k-means boundary between means μ₁ = (0, 0) and μ₂ = (4, 2) is the perpendicular bisector, and write its equation.

MediumK-meansConvergence

The convergence proof says the objective strictly decreases. Why does that guarantee the algorithm stops, and why doesn't it guarantee the best answer?

MediumK-meansGeometry