Hierarchical Clustering

Hierarchical clustering builds a tree (hierarchy) of nested clusters rather than a single flat partition. Its great advantage over K-Means: you do not have to specify the number of clusters up front — you decide afterwards by cutting the tree wherever you like.

Two Approaches

The Agglomerative Algorithm

1. Treat each of the n data points as a separate cluster
2. Compute the distance (proximity) matrix between all clusters
3. REPEAT:
     a) Find the two CLOSEST clusters
     b) MERGE them into a single cluster
     c) UPDATE the proximity matrix (using the chosen LINKAGE method)
   UNTIL only one cluster remains
4. Record the merge order and heights as a DENDROGRAM
5. CUT the dendrogram at a chosen height to obtain the desired clusters

Linkage Criteria — How to Measure Distance Between Clusters

This choice determines the shape of the resulting clusters.

Worked Example — By Hand

Five points with this initial distance matrix:

Using single linkage (minimum distance):

Step 1 — Smallest distance is d(P3,P5) = 2 → merge into (P3,P5)

Recompute with single linkage — take the MIN of the two constituent distances:
   d((P3,P5), P1) = min(3, 11) = 3
   d((P3,P5), P2) = min(7, 10) = 7
   d((P3,P5), P4) = min(9, 8)  = 8

Step 2 — Smallest is d(P1,(P3,P5)) = 3 → merge into (P1,P3,P5)

   d((P1,P3,P5), P2) = min(9, 7) = 7
   d((P1,P3,P5), P4) = min(6, 8) = 6

Step 3 — Smallest is d(P2,P4) = 5 → merge into (P2,P4)

   d((P2,P4), (P1,P3,P5)) = min(7, 6) = 6

Step 4 — Merge the final two clusters at height 6.

Merge sequence and heights:
   Height 2:  P3 + P5
   Height 3:  P1 + (P3,P5)
   Height 5:  P2 + P4
   Height 6:  (P1,P3,P5) + (P2,P4)

Cutting the dendrogram between heights 5 and 6 gives TWO clusters:
   Cluster A = {P1, P3, P5}
   Cluster B = {P2, P4}

The Dendrogram

A dendrogram is the tree diagram recording the merge order, with the y-axis showing the distance at which each merge occurred.

  6 ┤        ┌──────────────┐
    │        │              │
  5 ┤        │           ┌──┴──┐
    │        │           │     │
  4 ┤        │           │     │
    │        │           │     │
  3 ┤     ┌──┴──┐        │     │
    │     │     │        │     │
  2 ┤  ┌──┴──┐  │        │     │
    │  │     │  │        │     │
  0 ┴─ P3   P5  P1      P2    P4

  Cutting at height 4 (a horizontal line) crosses 2 vertical lines
  ->  2 clusters: {P1,P3,P5} and {P2,P4}

How to choose where to cut: find the largest vertical gap that a horizontal line can cross without intersecting a merge. In the diagram above, the gap between height 3 and height 5 is the biggest — cutting there gives the most "natural" 2-cluster solution.

Python

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import squareform

# Reproducing the hand-worked example from the distance matrix
dist_matrix = np.array([
    [0,  9, 3, 6, 11],
    [9,  0, 7, 5, 10],
    [3,  7, 0, 9,  2],
    [6,  5, 9, 0,  8],
    [11,10, 2, 8,  0],
])
condensed = squareform(dist_matrix)          # scipy needs the condensed form

Z = linkage(condensed, method="single")
print("Linkage matrix [cluster1, cluster2, distance, size]:")
print(Z)
# [[2.  4.  2.  2.]      P3 + P5 at height 2
#  [0.  5.  3.  3.]      P1 + (P3,P5) at height 3
#  [1.  3.  5.  2.]      P2 + P4 at height 5
#  [6.  7.  6.  5.]      final merge at height 6     <- matches the hand calc

labels = fcluster(Z, t=2, criterion="maxclust")
print("\nCluster assignments:", dict(zip(["P1","P2","P3","P4","P5"], labels)))
# {'P1': 1, 'P2': 2, 'P3': 1, 'P4': 2, 'P5': 1}

plt.figure(figsize=(9, 5))
dendrogram(Z, labels=["P1", "P2", "P3", "P4", "P5"],
           color_threshold=4, above_threshold_color="gray")
plt.axhline(4, color="#ef4444", linestyle="--", label="cut at height 4 -> 2 clusters")
plt.title("Dendrogram — Single Linkage", fontweight="bold")
plt.xlabel("Data points"); plt.ylabel("Merge distance")
plt.legend(); plt.tight_layout(); plt.show()

# Comparing linkage methods on real data
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score, adjusted_rand_score

iris = load_iris()
X = StandardScaler().fit_transform(iris.data)

fig, axes = plt.subplots(1, 4, figsize=(20, 4.5))
for ax, method in zip(axes, ["single", "complete", "average", "ward"]):
    Z = linkage(X, method=method)
    dendrogram(Z, ax=ax, no_labels=True, color_threshold=0.7 * max(Z[:, 2]))
    ax.set_title(f"{method.capitalize()} linkage")
    ax.set_ylabel("Distance")
plt.tight_layout(); plt.show()

results = []
for method in ["single", "complete", "average", "ward"]:
    model = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = model.fit_predict(X)
    results.append({
        "Linkage": method,
        "Silhouette": round(silhouette_score(X, labels), 4),
        "ARI vs true species": round(adjusted_rand_score(iris.target, labels), 4),
    })
print(pd.DataFrame(results).to_string(index=False))
# Ward's method typically wins on this dataset — it produces the most compact clusters.

# Choosing the number of clusters from the dendrogram's largest gap
Z = linkage(X, method="ward")
distances = Z[:, 2]
gaps = np.diff(distances)
biggest_gap_idx = int(np.argmax(gaps[-10:])) + len(gaps) - 10
suggested_k = len(X) - biggest_gap_idx - 1
print(f"Largest merge-distance gap suggests k = {suggested_k}")

for k in [2, 3, 4, 5]:
    labels = fcluster(Z, t=k, criterion="maxclust")
    print(f"k = {k}: silhouette = {silhouette_score(X, labels):.4f}")

# Practical use: a clustered correlation heatmap
import seaborn as sns

df = pd.DataFrame(iris.data, columns=iris.feature_names)
sns.clustermap(df.corr(), annot=True, cmap="coolwarm", center=0,
               figsize=(7, 7), fmt=".2f")
plt.show()
# clustermap runs hierarchical clustering on both rows and columns, reordering
# them so related features sit together — a standard EDA technique.

K-Means vs Hierarchical Clustering — The Exam Table

Advantages and Disadvantages

Applications

Biological taxonomy and phylogenetic trees, gene-expression analysis, document/topic hierarchies, social network community detection, market segmentation with sub-segments, image segmentation, and clustered heatmaps in EDA.

The final two lessons of Unit 3 cover the other major descriptive technique: association rule mining.