12.2 Hierarchical Methods
Agglomerative clustering begins with \(n\) clusters of one observation each and repeatedly merges the two closest, until one cluster remains. The record of merges is drawn as a dendrogram, and cutting it at a chosen height gives a clustering.
What distinguishes the methods is how the distance between two clusters is defined:
- (i)
- Single linkage: the distance between the nearest pair, one from each. Detects elongated clusters, and suffers from chaining, in which a bridge of intermediate points joins two otherwise separate groups.
- (ii)
- Complete linkage: the distance between the furthest pair. Produces compact clusters of similar diameter, and will split an elongated group in two.
- (iii)
- Average linkage: the mean over all pairs. A compromise between the two.
- (iv)
- Ward’s method: merge the pair that increases the total within-cluster sum of squares least. Tends to produce clusters of similar size, and is the closest of the four to the criterion that \(k\)-means optimises.
Note 12.3. The choice of linkage changes the answer, often substantially, and no linkage is correct in general. This is not a defect to be apologised for but the nature of the problem: “cluster” has no definition independent of the criterion used to find one. What the honest analyst does is state the distance and the linkage, and check whether the structure survives changing them.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.