Hierarchical Clustering and Dendrograms

Biologists organise living things into a hierarchy: species, genus, family, order. Libraries organise books into nested categories. Sometimes the natural structure of data is not a flat set of $k$ groups but a hierarchy of groups within groups. Hierarchical clustering discovers such structure and presents it as a tree called a dendrogram, letting you choose the level of granularity after seeing the data.

Two strategies#

• Agglomerative (bottom-up): start with every point as its own cluster; repeatedly merge the two closest clusters until one remains. This is by far the most common approach.
• Divisive (top-down): start with one cluster and recursively split it (e.g. with k-means for $k = 2$). Less common and more expensive.

The agglomerative algorithm#

1. Compute all pairwise distances between points.
2. Treat each point as a cluster.
3. Repeat $n - 1$ times: find the two closest clusters, merge them, and update the distances from the merged cluster to all others.

The result is a binary tree recording every merge and the distance at which it occurred.

Linkage: how far apart are two clusters?#

The crucial design choice is how to measure the distance between clusters $A$ and $B$:

Ward's method merges the pair whose union increases the within-cluster sum of squares least:

It is a good default for numeric data with Euclidean distance.

Reading a dendrogram#

The x-axis lists data points (leaves); the y-axis shows merge distance. Each horizontal join is a merge; its height is the distance at which the merge happened.

• Cutting the dendrogram horizontally at height $h$ yields a flat clustering: the number of vertical lines crossed equals the number of clusters.
• Long vertical gaps indicate natural, well-separated clusters — a good place to cut.
• The cophenetic correlation measures how faithfully the dendrogram preserves the original pairwise distances.

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster, cophenet
from scipy.spatial.distance import pdist
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=60, centers=[[0, 0], [5, 5], [0, 6]], cluster_std=0.9, random_state=3)

fig, axes = plt.subplots(1, 3, figsize=(15, 4))
for ax, method in zip(axes, ["single", "average", "ward"]):
    Z = linkage(X, method=method)
    c, _ = cophenet(Z, pdist(X))
    dendrogram(Z, ax=ax, no_labels=True, color_threshold=None)
    ax.set_title(f"{method} linkage (cophenetic r = {c:.2f})")
plt.tight_layout(); plt.show()

Z = linkage(X, method="ward")
labels = fcluster(Z, t=3, criterion="maxclust")      # cut to obtain 3 clusters
print(np.bincount(labels))

Complexity#

The naive algorithm needs $O(n^2)$ memory for the distance matrix and $O(n^3)$ time; optimised implementations reach $O(n^2)$ time for several linkages. In practice hierarchical clustering is comfortable for up to tens of thousands of points. For larger data, cluster a sample, use connectivity constraints, or use approaches like BIRCH that build a compact summary first.

Strengths and weaknesses#

Strengths

• No need to fix $k$ in advance — explore granularity visually.
• Works with any distance or similarity (e.g. edit distance between strings, correlation between gene expression profiles).
• The dendrogram is an interpretable summary of the data's structure.
• Deterministic (no random initialisation).

Weaknesses

• Merges are greedy and irreversible — an early mistake propagates.
• Quadratic memory limits scale.
• Results depend heavily on linkage and distance choices.

Connectivity-constrained clustering#

Sometimes clusters must be spatially contiguous — for example, grouping neighbouring districts into regions. Scikit-learn's AgglomerativeClustering accepts a connectivity graph so that only neighbouring clusters can merge.