Agglomerative clustering starts with every point alone and repeatedly merges the two closest groups (Algorithm 21.1). What "closest" means for groups defines the method: the smallest pair distance (single link, 21.10), the largest (complete link, 21.11) or the mean over all pairs (average link, 21.12). Single link follows chains of nearby points and so can trace the two moons or two rings, but also bridges blobs through a thin line of noise; complete and average link look for compact groups and fail on elongated shapes. Cut the tree at any number of clusters and compare with the true groups through the adjusted Rand index.
Data (simulated, Euclidean distance): three Gaussian blobs of 20 points; two noisy moons of 40 points each; two noisy rings (30 and 60 points); 300 yeast-like gene profiles over 7 time points, standardised, whose eight prototype shapes are the "true" groups (a stand-in for the book's yeast data). On the yeast set the right panel shows the time series of each cluster. The tree is built by the Lance-Williams update of the dissimilarity matrix. The adjusted Rand index is 1 for a perfect match and about 0 for a random partition.
code/ch21_clustering.py (hac, cut_tree, mst_prim).