Past exam of the mathematics course of the University of Oxford / Undated / Prelims / Mathematics III resit / 8

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.

Every Euclidean distance obeys the triangle inequality. The three recorded entries $d_{14}=0.67$, $d_{16}=2.88$ and $d_{46}=4.37$ violate it:At least one of $0.67,2.88,4.37$ must be incorrect. Two are in the final row as required. The gap is far larger than any possible rounding of entries to two decimal places.

Complete-linkage clustering defines the dissimilarity between clusters in cluster analysis $A,B$ as $d_{\mathrm{CL}}(A,B)={\max }_{i\in A,j\in B}{d}_{ij}$. Remove point 6 and first merge 1 with 4 at height $0.67$. The distances from $\{1,4\}$ to 2, 3, 5 are respectivelyThe next merge therefore attaches 2 at $1.41$. Now the distances from $\{1,2,4\}$ to 3 and 5 are $2.95$ and $3.32$, whereas $d_{35}=2.82$. Merge 3 and 5 at $2.82$. The final distance between the two remaining clusters in cluster analysis is the largest cross-entry, $3.32$. Thus the dendrogram has merges

Cutting strictly between heights $2.82$ and $3.32$ gives the two clusters in cluster analysisThe figure is an original drawing of these computed merges.

With two distinct centroids, K-means clustering assigns points on opposite sides of their nearest-centroid decision hyperplane, which in two dimensions is a straight line. This constraint explains the typical outcomes in the three source plots; exact assignments depend on initialization and the realized points.

Dataset A: one cluster in cluster analysis contains most of the horizontal cloud and the bottom of the vertical cloud; the other contains the upper part of the vertical cloud. The two visually elongated groups are poorly matched to squared Euclidean distance from their centroids. Points at the lower end of the vertical group can be closer to the horizontal group's centroid, so the two original shapes need not be recovered intact.

Dataset B: a roughly straight cut divides the ring and generally the central cloud between the two clusters in cluster analysis. A Voronoi cell for either centroid is a half-plane; it cannot select a surrounding ring while excluding its center. The cut's direction can vary because the geometry is approximately rotationally symmetric.

Dataset C: the two dense lower clouds typically receive different centroids. The much smaller upper cloud is absorbed into one or divided between both clusters in cluster analysis, according to the nearly vertical separating line. With $K=2$, the objective usually benefits more from separating the two large clouds than from spending one centroid on the sparse third group. These are typical qualitative outcomes, rather than guarantees about every initialization.

It is single-linkage clustering. Its intercluster distance is the smallest cross-pair Euclidean distance. Successive nearby points can join around the ring and within the dense central cloud before any edge crosses the gap between them. Equivalently, at a threshold below the between-group gap but above the lengths needed to connect each group, the single-linkage clustering components are precisely the central group and the ring.

Complete-linkage clustering uses the largest cross-pair Euclidean distance. Opposite points on the ring are far apart, so an intact ring has a large diameter. That rule favors compact pieces and can attach a ring segment to the center before all ring segments join. The visible gap and short links within each group explain why single-linkage clustering recovers the two intended clusters in cluster analysis in this example; it is not a universal guarantee for arbitrary noisy rings.