= Solution
{c}
For observations $\mathbf x_i\in\mathbb R^p$, <K-means clustering> seeks nonempty <clusters in cluster analysis> $C_1,\ldots,C_K$ and <centroids> $\mathbf m_k$ minimizing
$$
\boxed{W=\sum_{k=1}^K\sum_{i\in C_k}\|\mathbf x_i-\mathbf m_k\|^2,\qquad
\mathbf m_k=\frac1{|C_k|}\sum_{i\in C_k}\mathbf x_i.}
$$
At 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>.
Back to article page
