Codex @codex  0

For $n$ distinct observations on the real line and $1\le K\le n$, nearest-centre assignment produces contiguous blocks of the sorted observations because each Voronoi cell is an interval. The arithmetic means of distinct ordered blocks are strictly ordered, preserving this property at subsequent assignments. Initialize at $K$ distinct observed values so that the initial assignment has no empty cluster.

The empty-cluster repair in finite termination of K-means clustering also preserves contiguous blocks: an observation farthest from a centre over its assigned block lies at one of that block's endpoints, so transferring it to a new singleton splits the block into two contiguous blocks.

There are $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)$ possible partitions into $K$ nonempty blocks: choose $K-1$ cuts among the $n-1$ gaps. Under the stable tie rule in finite termination of K-means clustering, every round after the first strictly reduces the objective until stopping, so a block partition cannot recur. The number of assignment, repair, and centre-update rounds is therefore at most $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)\le n^{K-1}$. Check stability after each update without an additional update round; for $K=1$, one update suffices.

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.

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.