Start learning

Hierarchical Clustering

Lesson 43. About 6 minutes.

Hierarchical clustering builds a family tree of groups. It starts with every point as its own cluster and repeatedly merges the two closest clusters, until everything is one big cluster. You then cut the tree at the level you want.

Your Path Through This Lesson

0 of 5 done

By the End of This Lesson You Can
  • Follow the merge steps of agglomerative clustering by hand.
  • Compare the common linkage methods.
  • Read a dendrogram and cut it into clusters.

Bottom-Up Merging

The usual form is agglomerative (bottom-up) clustering:

  1. Start with each point as its own cluster.
  2. Find the two closest clusters and merge them.
  3. Repeat until only one cluster remains.

The full history of merges forms a tree called a dendrogram. Unlike K-means, you don't need to choose the number of clusters in advance: you choose it afterwards, by deciding where to cut the tree.

How Close Are Two Clusters? Linkage

Distance between two points is clear. Distance between two groups needs a rule, called the linkage:

Linkage Distance between clusters A and B Tends to give
Single Closest pair of points (one in A, one in B) Long, chain-like clusters
Complete Furthest pair of points Compact clusters of similar size
Average Average distance over all pairs A middle ground
Ward Merge that increases total within-cluster variance the least Compact, round clusters (the default in scikit-learn)

By Hand

Five students' weekly study hours: Noman 1, Lamia 2, Rafi 6, Tanvir 7, Arif 15. Single linkage.

Step Closest pair Distance Clusters after merging
1 Noman–Lamia 1 {1, 2}, {6}, {7}, {15}
2 Rafi–Tanvir 1 {1, 2}, {6, 7}, {15}
3 {1, 2}–{6, 7} 4 (from 2 to 6) {1, 2, 6, 7}, {15}
4 {1, 2, 6, 7}–{15} 8 (from 7 to 15) {1, 2, 6, 7, 15}

(Step 1 and step 2 tie at distance 1; either can go first.)

Cutting the tree:

  • Cut between heights 4 and 8 → 2 clusters: {Noman, Lamia, Rafi, Tanvir} and {Arif}.
  • Cut between heights 1 and 4 → 3 clusters: {Noman, Lamia}, {Rafi, Tanvir}, {Arif}.

A big jump in merge height suggests a natural place to cut: here, from 4 up to 8, Arif is clearly different.

python
import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage

hours = np.array([[1], [2], [6], [7], [15]])
Z = linkage(hours, method="single")
print("merge heights:", Z[:, 2])
print("2 clusters:", fcluster(Z, t=2, criterion="maxclust"))
print("3 clusters:", fcluster(Z, t=3, criterion="maxclust"))
Output
merge heights: [1. 1. 4. 8.]
2 clusters: [1 1 1 1 2]
3 clusters: [1 1 2 2 3]

Each row of Z records one merge; its third column is the merge distance, matching the table. To draw the tree, pass Z to scipy.cluster.hierarchy.dendrogram with Matplotlib.

In scikit-learn

python
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=200, centers=3, cluster_std=1.0, random_state=4)

for link in ["ward", "complete", "average", "single"]:
    labels = AgglomerativeClustering(n_clusters=3, linkage=link).fit_predict(X)
    print(f"{link:>8}: cluster sizes {sorted(np.bincount(labels).tolist(), reverse=True)}")
Output
    ward: cluster sizes [70, 66, 64]
complete: cluster sizes [74, 66, 60]
 average: cluster sizes [68, 66, 66]
  single: cluster sizes [134, 65, 1]

On these round, well-separated groups, most linkages agree. Single linkage is the one to watch: it can chain clusters together through a few in-between points, or leave tiny clusters of outliers.

Strengths and Weaknesses

✅ No need to fix K in advance Cut the dendrogram where it makes sense
✅ The dendrogram explains the structure Useful for reports and exploration
✅ Works with any distance measure
❌ Slow on big data Roughly memory and more in time: fine for thousands of rows, not millions
❌ Merges are final An early bad merge can't be undone
Tip

As with any distance-based method, scale your features first.

Try It Yourself
  1. Redo the hand example with complete linkage. What are the merge heights now? (Hint: step 3 becomes 7 − 1 = 6.)
  2. Run linkage(hours, method="complete") and check your answer.
The Key Idea

Agglomerative clustering repeatedly merges the closest clusters. The linkage defines "closest", and you choose the number of clusters by cutting the dendrogram.

Summary

  • Agglomerative clustering merges the closest clusters step by step.
  • Linkage (single, complete, average, Ward) defines cluster distance.
  • The dendrogram shows every merge; cut it to choose the number of clusters.
  • Great for small and medium data; slow for very large data.
  • Next: measuring how good a clustering is, with the silhouette score.