Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2025 / Paper 1 / 7

Write $n_k=|C_k|$ and suppose the cluster is nonempty. Expanding the Euclidean norm through its inner product givesSum over $x\in C_k$. The final term does not depend on $x$, so its sum is $n_k\Vert z-{\bar{x}}_k{\Vert }^2$, which proves the requested identity. This expansion is the starting point for the centroid sum-of-squares identity.

The centred observations sum to zero:By linearity of the inner product,This cancellation holds for every $z$.

Combining the first two parts gives the centroid sum-of-squares identityThe added term is nonnegative and, since $n_k>0$, vanishes exactly at $z={\bar{x}}_k$. Thus the unique minimizing centroid in this step of K-means clustering isAn empty cluster needs a separate algorithmic convention because its sample mean is undefined and its objective is identically zero.

Expanding the squared Euclidean distances givesFor distinct centroids, chooseA point assigned to $C_1$ has the displayed distance difference at most zero and therefore $w^{\mathsf{T}}x+b\ge 0$; assignment to $C_2$ gives the reverse inequality. The separating hyperplane is the perpendicular bisector of the line segment joining the two centroids. Points tied between them lie on that hyperplane. This is the nearest-centroid decision hyperplane.

The requested nonzero $w$ needs the additional assumption $z_1\ne z_2$. It does not follow from the stated algorithm alone. In one dimension, take $C_1=\{-1,1\}$ and $C_2=\{0\}$, whose centroids are both zero. A tie rule that retains previous assignments can leave this configuration after an iteration. The inequalities at $-1,1$ imply $b\ge |w|$, while the inequality at zero implies $b\le 0$, forcing $w=0$. Thus the unconditional nonzero-separator claim has this degenerate exception.