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

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.