= 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.
Back to article page
