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

Use the corrected decompositionThe hint's minus sign before $({\mu }_j-w_j)$ is a typographical error. Squaring, summing, and using ${\sum }_i(y_{ij}-{\mu }_j)=0$ for each coordinate gives the centroid sum-of-squares identitySince $m>0$ and $w\ne \mu$, the final term is strictly positive. HenceThus the centroid uniquely minimizes the sum of squared Euclidean distances to the observations.

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.

Sort the distinct observations as $x_{(1)}<\cdots <x_{(n)}$. For ordered centres $m_1<\cdots <m_r$, a point is closer to $m_j$ than to $m_{j+1}$ precisely when it lies to the left of their midpoint. Thus each Voronoi cell is an interval, with either choice allowed for an endpoint tie. Consequently, after assignment, each nonempty cluster is a contiguous block of the sorted observations.

The arithmetic means of disjoint ordered blocks are strictly ordered, so updating centres preserves this order. The empty-cluster repair in part (b) preserves contiguous blocks too: an observation farthest from its assigned centre lies at an endpoint of its block, and removing that endpoint makes a new singleton block. In one dimension with distinct observations, choosing $K$ distinct observations as initial centres makes the first assignment nonempty.

The one-dimensional K-means iteration bound now follows by counting block partitions. Choosing the $K-1$ gaps between consecutive nonempty blocks givespossibilities. By the strict-decrease argument in part (b), no such partition can recur before algorithm termination. Counting a step as an assignment, any empty-cluster repairs, and a centre update, with the stability check performed after that update, givesFor $K=1$, one update to the overall arithmetic mean suffices. Arbitrary changes between tied centres would invalidate the strict-decrease argument, which is why the stable tie convention in part (b) matters.