Linkage Criteria
The linkage decides what “distance between two clusters” means and changes the shape of the resulting clusters far more than the choice of distance metric does.
- Single linkage (nearest neighbor): distance is the minimum pairwise distance between any two points across the clusters. Produces long, chain-like clusters; sensitive to noise.
- Complete linkage (farthest neighbor): distance is the maximum pairwise distance. Produces compact, roughly spherical clusters; can break up large natural clusters.
- Average linkage: mean of all cross-cluster pairwise distances. A middle ground between single and complete.
- Ward linkage: merges the pair of clusters that causes the smallest increase in total within-cluster variance. Tends to produce balanced, compact clusters and is the most common default for Euclidean data.
The metric and the linkage need to be compatible — Ward, in particular, assumes squared Euclidean distance.