Past exam of the mathematics course of the University of Oxford / Undated / Prelims / Mathematics III resit / 8 / a

For observations ${\mathbf{x}}_i\in {\mathbb{R}}^p$, K-means clustering seeks nonempty clusters in cluster analysis $C_1,\dots ,C_K$ and centroids ${\mathbf{m}}_k$ minimizingAt fixed centroids, assigning each point to a nearest centroid minimizes its squared Euclidean distance. At fixed assignments, the centroid sum-of-squares identity shows that the sample mean uniquely minimizes each group's contribution. These alternating steps cannot increase $W$.

For finite termination of K-means clustering, more than a lower bound on $W$ is needed. Keep an assignment unchanged when nearest centroids tie, and stop when assignments no longer change. Every change then strictly decreases $W$. After updating the centroids, $W$ is determined by the partition of a set of $n$ indices; there are only finitely many choices for that partition of a set, so no strictly improving partition of a set can recur. Empty clusters in cluster analysis require a convention, such as moving a point from a nonsingleton cluster in cluster analysis to become its own centroid, which cannot increase $W$. With such a consistent convention the algorithm terminates, although it may reach only a local minimum.