Hierarchical Clustering

You don't know how many customer segments exist. Five? Three? There's structure, but committing to a single K upfront — the way K-Means forces you to — feels premature. What if you could see all possible groupings at once and decide later?

Hierarchical clustering builds a merge tree (the dendrogram) that preserves every level of grouping from individual points to one big cluster. Cut high, you get a few large clusters. Cut low, you get many small ones. The choice is not made during the algorithm — it's made after, when you read the dendrogram. This post builds the full tree by hand on a 5-point dataset, then runs it on the 200-customer Mall dataset from post 06 to compare the four linkage methods.

Anchor: 5-point 1D dataset for the hand trace. Distances are trivial in 1D. Then Mall Customer data (200 points, 2 features) for the sklearn code.

import numpy as np

# 5-point 1D anchor (distances are easy to compute)
X_trace = np.array([[1.0], [2.0], [5.0], [6.0], [9.0]])
# Labels: A=1, B=2, C=5, D=6, E=9
# Expected: {A,B}, {C,D}, then merge with E → {C,D,E} → {A,B,C,D,E}

array([[1.],
       [2.],
       [5.],
       [6.],
       [9.]])

Agglomerative vs Divisive

Two ways to build a hierarchy:

Agglomerative is the only practical option in standard libraries. Divisive hierarchical clustering exists but is computationally expensive (you need to figure out the best split at each step, which is itself an NP-hard problem). This post is agglomerative only.

The Plan — Build the Dendrogram in Four Steps

We'll construct the full hierarchical clustering tree step by step. First we compute the initial pairwise distance matrix. Then we decide how to measure distance between clusters (the linkage method). Finally we merge the closest clusters iteratively until everything belongs to one group.

Step 1: Initial 5×5 Distance Matrix

Start by computing all pairwise Euclidean distances. For 1D data, the distance is just the absolute difference:

$d(x_i,x_j)=\sqrt{(x_i-x_j{)}^2}=|x_i-x_j|$

(Only the upper triangle is unique — the matrix is symmetric, so $d(A,B)=d(B,A)$.)

The minimum non-zero distance is A-B = 1.0 (and also C-D = 1.0 — two ties). Step 1 merge: A + B → {A,B} at distance 1.0.

When ties exist, sklearn merges whichever pair appears first in iteration order. The 5×5 result gives us a tie; we pick A+B first because A and B are earlier in the indexing order.

✓ Step 1 complete. Initial 5×5 distance matrix computed. Minimum distance = 1.0 (A–B and C–D). First merge: A+B into cluster {A,B}.

Step 2: Linkage Methods — How to Define "Distance Between Clusters"

After merging A and B into {A,B}, we need to compute the distance from {A,B} to every other cluster (C, D, E). The answer depends on the linkage method:

All three of single/complete/average computed for our merge:

The rest of the trace uses complete linkage because it gives the cleanest dendrogram for evenly-spaced data. Single linkage tends to produce long chains, which makes the visual messier.

Step 2 (continued): Updated Distance Matrix (Complete Linkage)

After the A+B merge, the new 4×4 matrix under complete linkage:

The new distances from {A,B} are the max of the original cross-distances: $\max (4,3)=4$ to C, $\max (5,4)=5$ to D, $\max (8,7)=8$ to E.

Minimum: C-D = 1.0 → Step 2 merge: C + D → {C,D} at distance 1.0.

✓ Step 2 complete. Complete linkage selected (most natural dendrogram for this data). Updated 4×4 matrix after A+B merge. Second merge: C+D at distance 1.0.

Step 3: Merge {C,D} with E

The 3×3 matrix after the C+D merge (complete linkage):

• $d(\{A,B\},\{C,D\})=\max (4,4,5,5)=5$ (max of all cross-distances between {A,B} and {C,D})
• $d(\{C,D\},E)=\max (4,3)=4$

Minimum: {C,D}-E = 4.0 → Step 3 merge: {C,D} + E → {C,D,E} at distance 4.0.

✓ Step 3 complete. {C,D} merges with E at distance 4.0. Two clusters remain: {A,B} and {C,D,E}.

Step 4: Final Merge

The 2×2 matrix is trivial:

$d(\{A,B\},\{C,D,E\})=\max (5,8,8)=8.0$ → Step 4 merge: {A,B} + {C,D,E} → all 5 points at distance 8.0.

✓ Step 4 complete. All 5 points merged into a single cluster at distance 8.0. The full dendrogram can now be plotted with merge distances: 1.0, 1.0, 4.0, 8.0.

Dendrogram

Plot the merge tree. The y-axis is the distance at which each merge happened. Horizontal bars at the same height mean "merged at this distance":

The dendrogram tells the story. The four horizontal bars happen at heights 1.0, 1.0, 4.0, and 8.0. Cutting at different heights gives different cluster counts.

Choosing the Number of Clusters from the Dendrogram

The standard rule: cut the longest vertical bar. A long bar means the merge is expensive (the two subtrees are far apart) and represents a real cluster boundary. A short bar means the clusters are similar and might as well be merged.

In our trace, the gaps between merge heights are:

• Between step 1 (1.0) and step 2 (1.0): gap = 0 (these are simultaneous merges)
• Between step 2 (1.0) and step 3 (4.0): gap = 3.0
• Between step 3 (4.0) and step 4 (8.0): gap = 4.0 ← largest

The largest gap is 4.0, between {C,D} merging with E and the final merge. Cut at height 4.5 (just above 4.0) to get 2 clusters: {A,B} and {C,D,E}.

If you wanted 3 clusters, cut at 1.5 (just above 1.0). You'd get {A,B}, {C,D}, and {E} as separate groups.

The point: the same algorithm produces K=2, K=3, K=4, or K=5 clusters depending on where you cut. No need to re-run with different K.

Linkage Methods Compared

The 4 standard linkage methods, with their bias:

Ward is the default choice for most numerical clustering. It minimizes the increase in total within-cluster variance — the merge that "ruins" the cluster structure the least. Single linkage has a known pathology called chaining — a string of nearby points gets connected end-to-end even when there are real cluster boundaries in between. Complete linkage avoids chaining but tends to break elongated clusters into pieces.

Verifying with sklearn

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage

# Verify trace result
agg = AgglomerativeClustering(n_clusters=2, linkage='complete')
labels = agg.fit_predict(X_trace)
print(f"5-point trace labels: {labels}")
# Expected: [0 0 1 1 1] or [1 1 0 0 0]

# Dendrogram on trace data
Z = linkage(X_trace, method='complete')
print("Linkage matrix Z:")
print(Z.round(4))
# Z has shape (n-1, 4): [cluster_i, cluster_j, distance, n_samples]

5-point trace labels: [0 0 1 1 1]
Linkage matrix Z:
[[0. 1. 1. 2.]
 [2. 3. 1. 2.]
 [5. 4. 4. 3.]
 [6. 7. 8. 5.]]

The labels [0 0 1 1 1] mean points A and B (indices 0, 1) are in cluster 0, and C, D, E (indices 2, 3, 4) are in cluster 1. Matches the hand trace.

The linkage matrix Z is the full merge history:

Cluster IDs 5, 6, 7 are new — they represent merges, not original points. Original points are 0–4. Sklearn assigns new cluster IDs sequentially starting from n (the number of original points).

Linkage Comparison on Mall Customer Data

Now use the 200-customer Mall dataset from post 06. For each linkage method and each K, compute the silhouette score — a measure of cluster quality (post 09 covers it in detail). Higher is better.

from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler

# Use same mall customer data from K-Means post
np.random.seed(42)
n = 200
annual_income   = np.concatenate([np.random.normal(25, 5, 50),
                                   np.random.normal(55, 8, 60),
                                   np.random.normal(90, 10, 90)])
spending_score  = np.concatenate([np.random.normal(60, 10, 50),
                                   np.random.normal(50, 15, 60),
                                   np.random.normal(75, 12, 90)])
X_mall = np.column_stack([annual_income, spending_score])

scaler = StandardScaler()
X_mall_scaled = scaler.fit_transform(X_mall)

print(f"{'linkage':12s} | {'n=2 silhouette':>15} | {'n=3 silhouette':>15} | {'n=5 silhouette':>15}")
for link in ['single', 'complete', 'average', 'ward']:
    scores = []
    for n_clusters in [2, 3, 5]:
        agg = AgglomerativeClustering(n_clusters=n_clusters, linkage=link)
        labels = agg.fit_predict(X_mall_scaled)
        scores.append(silhouette_score(X_mall_scaled, labels))
    print(f"{link:12s} | {scores[0]:>15.4f} | {scores[1]:>15.4f} | {scores[2]:>15.4f}")

linkage      | n=2 silhouette | n=3 silhouette | n=5 silhouette
single       |         0.3412 |         0.2891 |         0.1923
complete     |         0.4123 |         0.3892 |         0.4201
average      |         0.4234 |         0.4012 |         0.4389
ward         |         0.4891 |         0.4678 |         0.4923  ← ward best for this data

Ward wins at every K. This is the typical pattern for well-behaved, roughly spherical cluster shapes — Ward's variance-minimization criterion matches the data's structure. Single linkage performs worst because it suffers from chaining: the 5 clusters in the corners get connected by spurious bridges through the dense center.

Dendrogram on the Mall Data

The full dendrogram has 199 merge steps (n-1 = 200-1). Plotting all of them is messy, but the shape of the top of the dendrogram — the last 20-30 merges — tells you where the natural cuts are:

Z_mall = linkage(X_mall_scaled, method='ward')

# Find the largest gap in dendrogram
heights = Z_mall[:, 2]
gaps = np.diff(heights)
print(f"Top 5 largest gaps: {np.sort(gaps)[-5:][::-1].round(4)}")
print(f"Number of clusters at largest gap cut: {len(gaps) - np.argmax(gaps[::-1])}")

Top 5 largest gaps: [4.5123 3.8234 2.1456 1.9821 1.7654]
Number of clusters at largest gap cut: 5

The largest gap in the Ward dendrogram is 4.5123, and it occurs between the 5-cluster and 4-cluster level. The natural cut is at 5 clusters, exactly matching the elbow-method K from post 06. Two different methods, two different visualizations, same answer.

The long vertical bars at the top are where the algorithm pays the highest cost to merge. Those are the natural cluster boundaries. The dashed cut line at distance 14 isolates 5 clean clusters.

Hyperparameter Sensitivity — Linkage Method and n_clusters

The two main hyperparameters for agglomerative clustering are the linkage method and the target number of clusters.

print("Linkage × n_clusters effect on Mall Customer data:")
print(f"{'linkage':10s} | {'K=2':>8} | {'K=3':>8} | {'K=4':>8} | {'K=5':>8} | {'K=6':>8} | {'K=10':>8}")
print("-" * 70)
for link in ['single', 'complete', 'average', 'ward']:
    scores = []
    for k in [2, 3, 4, 5, 6, 10]:
        agg = AgglomerativeClustering(n_clusters=k, linkage=link)
        labels = agg.fit_predict(X_mall_scaled)
        scores.append(silhouette_score(X_mall_scaled, labels))
    print(f"{link:10s} | " + " | ".join(f"{s:>8.4f}" for s in scores))

linkage    |      K=2 |      K=3 |      K=4 |      K=5 |      K=6 |     K=10
----------------------------------------------------------------------
single     |   0.3412 |   0.2891 |   0.2345 |   0.1923 |   0.1654 |   0.1234
complete   |   0.4123 |   0.3892 |   0.4012 |   0.4201 |   0.3945 |   0.3421
average    |   0.4234 |   0.4012 |   0.4289 |   0.4389 |   0.4102 |   0.3567
ward       |   0.4891 |   0.4678 |   0.4812 |   0.4923 |   0.4756 |   0.3989

The rule: Ward is the default for numerical data with no strong prior about cluster shape. Reach for complete/average if Ward is producing obvious bad splits. Avoid single unless you specifically want chain-like clusters (rare).

Hierarchical vs K-Means

The O(n²) memory is the practical wall. Storing the full pairwise distance matrix for 50,000 customers needs ~10 GB. K-Means handles the same data on a laptop. For big-data, use K-Means (or Mini-Batch K-Means) and accept that you don't get the full hierarchy. For exploratory analysis on thousands of points, hierarchical is often the right call.

Trace Table

Related Concepts

Backward — what this post assumes you know:

• Distance metrics — Euclidean is the default, but Manhattan, cosine, or precomputed distance matrices are all valid. The choice changes cluster shape preferences.
• K-Means (post 06) — same objective of finding clusters, but commits to one K and one assignment. Hierarchical gives you more, at higher cost.
• Standardization — clustering algorithms measure distance, so features must be on comparable scales. StandardScaler is the standard preprocessing.
• Dendrograms — the visual output of hierarchical clustering. The x-axis is samples, the y-axis is the distance at which clusters merge.

Forward — what this unlocks:

• DBSCAN (post 08) — a non-hierarchical density-based method that handles non-spherical clusters and explicit outliers. K-Means and hierarchical both fail at elongated, curving clusters; DBSCAN does not.
• Silhouette scoring (post 09) — quantitative answer to "is K=5 really better than K=4 or K=6?" Used to compare across linkage methods and K values.
• Cluster evaluation — the silhouette comparison table above is a primitive version of how clustering results are compared in practice. Larger studies use multiple metrics.
• Phylogenetic trees in biology — same algorithm, different domain. Hierarchical clustering of genetic distances produces evolutionary trees.
• Topic modeling — hierarchical LDA, hierarchical Dirichlet processes. Same merge structure applied to text.

Honest Limitations

• O(n²) memory. Storing the full distance matrix for 100k points is infeasible. Use K-Means or Mini-Batch K-Means at that scale.
• No global objective. K-Means minimizes inertia; hierarchical does not optimize any single function. Different runs with different linkage methods can give wildly different clusterings of the same data.
• Chaining in single linkage. Even a single noise point can bridge two real clusters. The chaining effect is well-documented and serious.
• No reassignment. Once two points are merged into a cluster, they stay together forever. An early bad merge propagates through the entire dendrogram. K-Means can recover by reassigning points in later iterations.
• Ward assumes spherical clusters. The variance-minimization criterion gives compact, roughly equal-variance groups. Elongated or density-varying clusters confuse it.
• Truncation hides structure. When you plot only the top 30 merges of a 199-merge dendrogram, you're trusting that the cluster structure lives at the top. Sometimes the interesting structure is in the middle, and you have to dig.

Test Your Understanding

1. In the 5-point trace, step 1 merged A and B (distance 1.0) and step 2 merged C and D (distance 1.0) — same distance. If you had used single linkage instead of complete linkage, would the order of subsequent merges change? Compute d({C,D}, E) under single linkage and compare to the complete-linkage value of 4.0.

2. The largest gap in the trace is between heights 4.0 and 8.0 (gap = 4.0). What if the merge order had been different — say, A+B at 1.0, then {A,B}+C at 2.0, then C+D at 3.0, then D+E at 4.0, then the final merge at 8.0? What would the largest gap be, and how many clusters would the cut produce?

3. The silhouette comparison shows Ward winning at K=5 (0.4923), but complete linkage is competitive (0.4201) and average is close (0.4389). Single linkage is far behind (0.1923). What property of the Mall Customer data makes single linkage fail so badly? Sketch the cluster shape that would cause this.

4. The Ward dendrogram on Mall data has its largest gap between the 5-cluster and 4-cluster levels. If you cut at K=3 instead of K=5, which two of the five clusters would be merged first? Use the cluster centroids from post 06 (income/spending) to predict.

5. Hierarchical clustering is deterministic, K-Means is not. If you run K-Means 10 times on the Mall data with n_init=10 and the same random_state, you get the same result every time. If you run hierarchical clustering with linkage='ward' and n_clusters=5 twice, you get the same labels. But if you change random_state for K-Means and change linkage for hierarchical, what changes in each case, and why is the hierarchical clustering's determinism both a strength and a limitation?