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

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.