Hierarchical Clustering

Building nested clusters into a tree structure without specifying cluster count k upfront.

🟡 intermediate4 min readunsupervised

Hierarchical Clustering constructs a nested tree of clusters called a Dendrogram. Agglomerative (bottom-up) starts with N individual clusters and iteratively merges the closest pair of clusters until 1 root remains. Divisive (top-down) starts with 1 root cluster and recursively splits. Distance between clusters depends on Linkage criteria: Single (minimum distance), Complete (maximum distance), Average, or Ward's (minimum variance increase).

Agglomerative vs Divisive

                          DIVISIVE (Top-Down)
                     ┌──────────────────────────┐
                     │     All Data (Root)      │
                     └─────────────┬────────────┘
                            ┌──────┴──────┐
                            ▼             ▼
                         Cluster A     Cluster B
                       ┌────┴────┐     ┌────┴────┐
                       ▼         ▼     ▼         ▼
                      {1}       {2}   {3}       {4}  (Singletons)
                     └──────────────────────────┘
                        AGGLOMERATIVE (Bottom-Up)

Agglomerative (Bottom-Up - Standard): Every data point starts as its own cluster. At each step, merge the two closest clusters.
Divisive (Top-Down): All data starts in 1 big cluster. Recursively bisect clusters using k-Means or spectral cuts.

Linkage Criteria: Measuring Inter-Cluster Distance

Given two clusters $A$ and $B$:

Single Linkage (Min)         Complete Linkage (Max)         Average Linkage
  A o--------o B               A o════════════o B             A o - - - o B
  (Nearest pair)               (Farthest pair)                (Average all pairs)

Linkage Criterion	Formula $d(A, B)$	Cluster Shapes Produced	Pros & Cons
Single	$\min_{a \in A, b \in B} d(a, b)$	Arbitrary shapes (Chaining effect)	Sensitive to noise & bridging points
Complete	$\max_{a \in A, b \in B} d(a, b)$	Compact, equal-diameter clusters	Sensitive to outliers
Average	$\frac{1}{\|A\|\|B\|} \sum_{a,b} d(a, b)$	Balanced, robust clusters	Moderate computational cost
Ward's	$\Delta \text{Var}(A \cup B)$	Dense, spherical clusters	Default in scikit-learn (Requires Euclidean)

Reading a Dendrogram

To obtain a specific number of clusters $k$ (or a distance threshold $\tau$), draw a horizontal cutting line across the Dendrogram:

  Distance
    5.0 ┼─────────────────── Root ───────────────────
        │                     │
    3.5 ┼──────────────┐      │
        │              │      │
    1.5 ┼───────┐      │      │          ◄─── Cut at Height = 2.0 yields 3 Clusters!
        │       │      │      │
    0.0 ┴──{1}─{2}────{3}────{4}───

Say this out loud

"Agglomerative Hierarchical Clustering builds a nested tree (Dendrogram) bottom-up by iteratively merging the two closest clusters according to a linkage criterion. Single linkage uses minimum distance but suffers from chaining; Complete linkage uses maximum distance for compact clusters; Ward's linkage minimizes variance increase. You select k after fitting by cutting the Dendrogram at a chosen distance height."

Follow-ups to expect

When to use Hierarchical Clustering over k-Means? When you need a full hierarchical taxonomy (e.g. biological species trees, document topic trees), when $k$ is unknown upfront, or when non-Euclidean custom distance metrics are required.
How do you handle $O(N^3)$ computational scaling for large datasets? Use Connectivity Graphs (k-nearest neighbor graphs) to restrict candidate merge pairs to adjacent neighbors, reducing time complexity to $O(N^2 \log N)$.

Check yourself

Question 1 of 3

What visualization tool displays the full nested tree hierarchy of merges and distances in Hierarchical Clustering?

More in Classical ML

See all →

Bias–Variance Tradeoff4 min Overfitting vs Underfitting3 min Linear Regression4 min