= Solution
{c}
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>:
$$
\boxed{J(C_1,\ldots,C_K;m_1,\ldots,m_K)=\sum_{k=1}^K\sum_{i\in C_k}\|x_i-m_k\|^2.}
$$
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:
* Assign each observation to a nearest centre in <Euclidean distance>. Keep its current assignment on an exact tie; for a previously unassigned observation use a fixed ordering to resolve ties.
* If a cluster is empty, choose an observation from a cluster with at least two members and make it the empty cluster's sole member, placing its centre at that observation. A definite rule is to choose an eligible observation farthest from its currently assigned centre, breaking ties by observation index. Repeat until all clusters are nonempty.
* Replace each centre by the <arithmetic mean> of its assigned observations.
* After updating, check whether every observation is still assigned to a nearest updated centre, retaining its assignment on ties. If so, stop; otherwise repeat.
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.
Back to article page
