 Finite termination of K-means clustering

For a finite dataset, alternate nearest-centre assignment and replacement of each centre by the centroid of its assigned observations. Keep the current assignment whenever an observation is tied between nearest centres. A changed assignment then strictly decreases the within-cluster sum of squared Euclidean distances; updating centres cannot increase it by the centroid sum-of-squares identity.

After each centre update, the centres are determined by the current partition of a set of observation indices. There are only finitely many such partitions, so a strictly improving sequence cannot revisit one and must stop. A convenient exact stopping test is to check after each update whether every observation is still assigned to a nearest centre. This proof is for algorithm termination; it does not guarantee a global minimum.

Empty clusters need an explicit convention. To retain exactly $K\le n$ nonempty clusters, transfer an observation from a cluster with at least two members to each empty cluster, making it a singleton centred at that observation. This cannot increase the objective: the transferred observation now has squared distance zero, and no other contribution changes before centre updating. A deterministic choice is an eligible observation farthest from its currently assigned centre, with ties resolved by index. After the first round, an empty cluster can arise only during a strictly improving reassignment, so these repairs preserve the finite-termination argument.