Hierarchical Clustering Linkage Methods
Agglomerative hierarchical clustering starts with every point in its own cluster and repeatedly merges the two "closest" clusters. The linkage rule defines what "closest" means for two clusters, and that choice changes which clusters form and when.
The four standard linkage methods
| Method | Distance between clusters and | Shape tendency |
|---|---|---|
| Single | : nearest pair | Elongated chains |
| Complete | : farthest pair | Compact, equally-sized |
| Average (UPGMA) | : mean of all pairs | Balanced; most common |
| Ward | : variance increase | Compact, evenly-sized; best for spherical blobs |
Which linkage to use?
Ward linkage minimizes within-cluster variance at every merge, so it produces the most compact and evenly-sized clusters. It is the best default for spherical, roughly equal-sized blobs. Single linkage is the only method that can detect elongated "chain" shapes, but it suffers from chaining: one bridge point between two distant blobs can pull them together early. Complete linkage is robust to this but can split large, elongated natural clusters.
Watch it run
Merge by merge on the four points below, with the cross-pair distances that each linkage rule reduces to a single number drawn in:
Agglomerative clustering — and the linkage rule that changes the answer
Four points in two obvious blobs: A(1,1), B(2,2) and C(8,8), D(9,9). Agglomerative clustering starts with every point alone and repeatedly merges the closest pair of clusters. The only thing that varies between methods is how "closest" is defined once a cluster has more than one member.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0.00 | 1.41 | 9.90 | 11.31 |
| B | 1.41 | 0.00 | 8.49 | 9.90 |
| C | 9.90 | 8.49 | 0.00 | 1.41 |
| D | 11.31 | 9.90 | 1.41 | 0.00 |
Merge-by-merge agglomerative clustering on four points, where all three linkage rules agree on structure and differ only in merge height — which is the case the worked example above covers. The final step adds a single bridge point between the blobs, and single and complete linkage now return genuinely different clusters at k = 2. That is chaining: the reason single linkage can trace an elongated cluster and the reason it can also destroy a good one.
What to notice as you step:
- The first merges are linkage-independent. While both clusters are singletons there is only one cross-pair distance, so min, max and mean are the same number. Linkage cannot matter until a cluster has two members.
- The choice is a reduction, not a metric. Every rule sees the same set of cross-pair distances and differs only in how it collapses them to one.
- The last step adds one bridge point halfway between the blobs, and single and complete linkage now return different clusters at , not merely different heights. That is chaining, and it is the same property that lets single linkage follow an elongated cluster no other rule can.
Comparing the linkages on a 4-point worked example
Here we trace 4 points across 3 linkages.
Points: A(1,1), B(2,2), C(8,8), D(9,9).
Step 1: full pairwise distance matrix (Euclidean):
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1.41 | 9.90 | 11.31 |
| B | — | 0 | 8.49 | 9.90 |
| C | — | — | 0 | 1.41 |
| D | — | — | — | 0 |
Computations: ; ; ; .
Step 2: Merge 1 (all linkages agree). Two ties at 1.41: A–B and C–D. Merge A+B at height 1.41 and C+D at height 1.41.
Step 3: Merge 2: cluster vs cluster . This is where linkages diverge:
Single linkage — nearest pair:
Height = 8.49. The two blobs merge at the smallest inter-cluster gap.
Complete linkage — farthest pair:
Height = 11.31. The two blobs are judged by their most distant representatives.
Average linkage — mean of all 4 cross-pairs:
Height = 9.90.
Observation: all three methods produce exactly the same cluster structure ( and ), because the two blobs are extremely well-separated. The only difference is the height of the final merge in the dendrogram, which affects where you would "cut" to decide the number of clusters.
import numpy as np
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
import matplotlib.pyplot as plt
X = np.array([[1,1], [2,2], [8,8], [9,9]])
labels = ['A','B','C','D']
fig, axes = plt.subplots(1, 3, figsize=(13, 4))
for ax, method in zip(axes, ['single', 'complete', 'average']):
Z = linkage(X, method=method)
dendrogram(Z, ax=ax, labels=labels)
ax.set_title(f'{method.title()} linkage')
ax.set_ylabel('Distance (merge height)')
plt.tight_layout()
plt.show()
When linkages give different cluster structures
The 4-point example is too clean — the blobs are far apart. Linkages produce different cluster assignments when:
- Elongated clusters → Single linkage chains them together (good); complete/Ward splits them (bad)
- Noisy bridge points → Single linkage merges distant blobs through one noisy intermediate; complete/Ward resist this
- Unequal cluster sizes → Ward favors equally-sized clusters; single/average can find a large cluster + many singletons
from sklearn.datasets import make_blobs, make_moons
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt
# Compare linkages on two crescents (non-spherical)
X_moons, _ = make_moons(n_samples=100, noise=0.05, random_state=42)
fig, axes = plt.subplots(1, 4, figsize=(14, 3))
for ax, method in zip(axes, ['single', 'complete', 'average', 'ward']):
labels = AgglomerativeClustering(n_clusters=2, linkage=method).fit_predict(X_moons)
ax.scatter(X_moons[:, 0], X_moons[:, 1], c=labels, cmap='coolwarm', s=15)
ax.set_title(f'{method}')
ax.set_xticks([]); ax.set_yticks([])
plt.suptitle('Linkage methods on two crescents — single finds the right structure')
plt.tight_layout()
plt.show()
Deriving Ward linkage from variance
Ward linkage uses a different formula: instead of computing the distance between two clusters directly, it asks "how much does the within-cluster variance increase if we merge these two clusters?"
For clusters and with centroids and :
The prefactor is the harmonic mean of the cluster sizes — it penalizes merging two large clusters more than merging a small one into a large one. Ward always merges the pair that increases total within-cluster variance the least.
Related concepts
- Hierarchical Clustering & DBSCAN: the full lesson with DBSCAN, parameter selection, and comparison table
- K-Means Clustering: the centroid-based alternative
- K-Means: Full Algorithm: convergence proof and worked trace