Merge Nearby Groups
Start with every record as a separate group, then repeatedly merge the closest pair of groups. Small groups become nested inside larger ones. This is agglomerative hierarchical clustering.
Follow four points
Take positions 1, 2, 8, and 10 on a line, using absolute difference as distance.
- Merge 1 and 2, whose distance is 1.
- Merge 8 and 10, whose distance is 2.
- Merge the two groups to include every point.
A dendrogram records the merge order and distances. Cutting it at a chosen height selects a grouping.
What is the distance between groups?
Point distance alone is insufficient; define linkage too.
- Single linkage: The closest cross-group pair. Here the two groups are distance 6 apart.
- Complete linkage: The farthest cross-group pair, here 9.
- Average linkage: Average every cross-group pair, here
(7+9+6+8)/4 = 7.5.
Single linkage can join large groups through thin chains. Complete linkage is more sensitive to maximum spread. Different linkage rules may produce different clusters.
Check your understanding
Does the basic agglomerative method later split a merged group? Is a table of every pairwise distance expensive for large data?
Show explanation
It does not undo merges. A full pairwise-distance table uses O(n²) space, which can be costly. Running time depends on linkage and implementation.