Clustering - Mining of Massive Datasets - page 235

Figure 7.2 Twelve points to be clustered hierarchically
Figure 7.3 Combining the first two points into a cluster
You might think that (10,5) gets combined with the new cluster next, since it is so close
to (11,4). But our distance rule requires us to compare only cluster centroids, and the dis-
tance from (10,5) to the centroid of the new cluster is which is slightly greater than 2.
Thus, now the two closest clusters are those of the points (4,8) and (4,10). We combine
them into one cluster with centroid (4,9).
At this point, the two closest centroids are (10,5) and (11.5, 3.5), so we combine these
two clusters. The result is a cluster of three points (10,5), (11,4), and (12,3). The centroid of
this cluster is (11,4), which happens to be one of the points of the cluster, but that situation
is coincidental. The state of the clusters is shown in Fig. 7.4 .
Figure 7.4 Clustering after two additional steps
Now, there are several pairs of centroids that are at distance and these are the closest
centroids. We show in Fig. 7.5 the result of picking three of these:
(1) (6,8) is combined with the cluster of two elements having centroid (4,9).
(2) (2,2) is combined with (3,4).
(3) (9,3) is combined with the cluster of three elements having centroid (11,4).