Linkage by hand

Topic: Hierarchical clustering and kernel density estimation · more questions on this topic
Number of merges ›

Cluster the points 1,2,6,8,15 on a line by single, complete, and average linkage. List the merge heights for each. Do the three dendrograms have the same topology?

Worked answer (click to show)

After every merge, recompute the distance between clusters using the chosen linkage. The same observations can produce different merge heights even when the merge order agrees.

Single linkage merges \{1,2\} at 1 and \{6,8\} at 2, then merges \{1,2\} with \{6,8\} at 4 (the closest pair is 2 and 6), then attaches 15 at 7 (the closest pair is 8 and 15). The heights are 1,2,4,7.

Complete linkage makes the same first two merges, at heights 1 and 2. The union \{1,2\}\cup\{6,8\} then has maximum cross distance 8-1=7, and 15 joins at 15-1=14. The heights are 1,2,7,14.

Average linkage again merges \{1,2\} at 1 and \{6,8\} at 2. The mean of the cross distances (5,7,4,6) between \{1,2\} and \{6,8\} is 5.5. The mean of the distances (14,13,9,7) from 15 to \{1,2,6,8\} is 10.75. The heights are 1,2,5.5,10.75.

The merge order and the groupings are the same for all three: \{1,2\}, \{6,8\}, then their union, then 15. Only the heights differ, with single linkage at most average linkage, and average linkage at most complete linkage, at every merge.