Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics III / 9 / b / Solution

Write $x_i\in {\mathbb{R}}^p$ for row $i$ of the data matrix. The k-means clustering objective is the within-cluster sum of squared Euclidean distances:The nonempty $C_k$ form a partition of a set of observation indices. For fixed clusters, part (a) shows that the best $m_k$ is their centroid.

Initialize distinct centres, for example by choosing $K\le n$ distinct observations. Then repeat the following steps:

The empty-cluster repair is possible for $K\le n$ and cannot increase $J$: the transferred observation now has squared distance zero, while all other squared distances stay unchanged before the centre update.

Assignment cannot increase $J$, and any changed assignment strictly decreases it under the tie rule. Updating centres cannot increase $J$ by the centroid sum-of-squares identity. After an update, the centres are determined by the partition of a set. There are only finitely many possible assignments. Unless this is the initial round, any nonterminal round starts with an assignment that strictly reduces $J$; repairing empty clusters and updating cannot undo that decrease. Thus a partition cannot recur, proving finite termination of K-means clustering. The final result need not be a global minimum; different initial centres can lead to different final clusterings.