Hierarchical clustering (agglomerative - divisive)

What is Hierarchical Clustering?

Why This Matters

Problem K-Means solves poorly: You have customer data but don't know if you should segment into 3, 5, or 10 groups. K-Means forces you to guess K, then start over if wrong.

Hierarchical solution: Build the full tree ONCE, then examine it to choose the natural number of clusters. The tree shows you WHERE the big separations occur.

The Two Approaches

1. Agglomerative Clustering (Bottom-Up)

Formula Agglomerative Algorithm

Input: $n$ data points $\{x_1, x_2, ..., x_n\}$ , linkage criterion $L$ Initialize: Each point is its own cluster: $C_i = \{x_i\}$ for $i=1..n$

Repeat until one cluster remains:

Find pair of clusters $(C_i, C_j)$ with minimum distance: $d(C_i, C_j) = \min_{p,q} L(C_p, C_q)$
Merge them: $C_{new} = C_i \cup C_j$
Remove $C_i, C_j$ from cluster set, add $C_{new}$
Record merge height = $d(C_i, C_j)$ in dendrogram

Why these steps?

Step 1: We want the "most similar" clusters to merge first (gredy local optimum)
Step 2-3: Reduce cluster count by 1 each iteration (in $n-1$ iterations, $n$ clusters → 1)
Step 4: The merge height tells us how "different" the clusters were — big jump = natural boundary

Derivation of Complexity:

$n$ points, iteration $k$ has $(n-k+1)$ clusters
Computing all pairwise distances: $\binom{n-k+1}{2} = O((n-k)^2)$ comparisons
Total: $\sum_{k=1}^{n-1} (n-k)^2 = O(n^3)$ for naive implementation
With priority queue (heap): $O(n^2 \log n)$

2. Divisive Clustering (Top-Down)

Linkage Criteria (The Heart of Aglomerative)

The linkage criterion $L(C_p, C_q)$ defines "distance between clusters". This choice drastically changes cluster shapes.

Formula Four Main Linkage Methods

Given clusters $C_p = \{x_i\}$ and $C_q = \{x_j\}$ :

Single Linkage (MIN, nearest neighbor): $L_{single}(C_p, C_q) = \min_{x_i \in C_p, x_j \in C_q} d(x_i, x_j)$ → Distance = closest pair of points between clusters
Complete Linkage (MAX, farthest neighbor): $L_{complete}(C_p, C_q) = \max_{x_i \in C_p, x_j \in C_q} d(x_i, x_j)$ → Distance = farthest pair of points between clusters
Average Linkage (UPGMA): $L_{avg}(C_p, C_q) = \frac{1}{|C_p| |C_q|} \sum_{x_i \in C_p} \sum_{x_j \in C_q} d(x_i, x_j)$ → Distance = average of all pairwise distances
Ward's Method (minimum variance): $L_{ward}(C_p, C_q) = \frac{|C_p| |C_q|}{|C_p| + |C_q|} |\mu_p - \mu_q||^2$ where $\mu_p = \frac{1}{|C_p|}\sum_{x \in C_p} x$ is cluster centroid → Merge clusters that minimize within-cluster variance increase

Derivation of Ward's Formula:

Within-cluster sum of squares for merged cluster $C_p \cup C_q$ : $SS_{merged} = \sum_{x \in C_p \cup C_q} ||x - \mu_{merged}||^2$

where $\mu_{merged} = \frac{|C_p|\mu_p + |C_q|\mu_q}{|C_p| + |C_q|}$

Expanding: $SS_{merged} = \sum_{x \in C_p} ||x - \mu_{merged}||^2 + \sum_{x \in C_q} ||x - \mu_{merged}||^2$

Using parallel axis theorem: $\sum ||x - \mu_{new}||^2 = \sum ||x - \mu_{old}||^2 + n|\mu_{old} - \mu_{new}||^2$

After algebra: $\Delta SS =_{merged} - (SS_p + SS_q) = \frac{|C_p| |C_q|}{|C_p| + |C_q|} |\mu_p - \mu_q||^2$

Why this matters: Ward's minimizes the INCREASE in total within-cluster variance from merging, producing compact, roughly equal-sized clusters.

The Dendrogram: Reading the Tree

How to choose number of clusters:

Look for large vertical gaps (big increase in merge distance)
Cut at height just before a large jump
The number of vertical lines you cut through = number of clusters

Worked example Dendrogram Cutting

Merge heights: [1.0, 1.1, 1.2, 5.8, 6.0]

    |          6.0  ---- (final merge)
    |          5.8  ---- (big jump from 1.2!)
    |          1.2  --
    |          1.1  --
    |          1.0  --
  A B C D E F

Analysis: Heights 1.0-1.2 are similar (internal cluster merging), then JUMP to 5.8 (different clusters merging).

Decision: Cut at height 4.0 (between 1.2 and 5.8) → 2 clusters

Why this works: Small heights = similar points. Large jump = you're now merging dissimilar groups.

Implementation Details

Distance Metric (usually Euclidean): $d(x_i, x_j) = ||x_i - x_j||_2 = \sqrt{\sum_{k=1}^d (x_{ik} - x_{jk})^2}$

For high-dimensional data, consider:

Manhattan: $d = \sum |x_{ik} - x_{jk}|$ (robust to outliers)
Cosine: $d = 1 - \frac{x_i \cdot x_j}{||x_i|| ||x_j|}$ (angle-based, good for text)

Update Formula (Lance-Williams): After merging clusters $C_i$ and $C_j$ into $C_k$ , update distances to remaining cluster $C_m$ :

$d(C_k, C_m) = \alpha_i d(C_i, C_m) + \alpha_j d(C_j, C_m) + \beta d(C_i, C_j) + \gamma |d(C_i, C_m) - d(C_j, C_m)|$

Parameters for different linkages:

Single: $\alpha_i = \alpha_j = 0.5, \beta = 0, \gamma = -.5$ (min of two distances)
Complete: $\alpha_i = \alpha_j = 0.5, \beta = 0, \gamma = 0.5$ (max of two distances)
Average: $\alpha_i = \frac{|C_i|}{|C_i|+|C_j|}, \alpha_j = \frac{|C_j|}{|C_i|+|C_j|}, \beta = \gamma = 0$

Common mistake Common Mistake: "Hierarchical clustering finds globally optimal clusters"

Why this feels right: We're building a complete tree, considering all merge possibilities, so it seems exhaustive.

Why it's wrong: At each step, we make a gredy local decision (merge closest pair). Once merged, clusters never split. If an early merge was suboptimal, we can't undo it.

Example: Points form two close pairs {A,B} and {C,D}, but A is slightly closer to C than to B.

Single linkage might merge A-C first (wrong!)
Now B must merge with (AC), and D must merge with (ABC)
We've permanently lost the {A,B}, {C,D} structure

Fix:

Hierarchical is deterministic given distance metric and linkage, but not globally optimal
Try multiple linkage criteria and compare dendrograms
For true global optimization, use methods like spectral clustering (but lose interpretability)

Common mistake Common Mistake: "Use single linkage for all cases — it's simplest"

Why this feels right: Single linkage has intuitive "connect nearest neighbors" logic and is computationally simpler to update.

Why it's wrong: Single linkage sufers from chaining: outliers or noise can bridge distinct clusters, creating long chains instead of compact groups.

When it fails: Data with noise, elongated clusters touching, or unequal densities.

Example: Two circular clusters with one outlier between them. Single linkage:

Forms two clusters correctly initially
Eventually connects them through the outlier
Final result: one elongated chain instead of two circles

Fix:

Use complete linkage for compact, well-separated clusters (most robust)
Use Ward's method when clusters should have similar sizes and low variance
Use average linkage as a balanced compromise
Preprocess to remove outliers if using single linkage

Advantages & Disadvantages

Advantages:

No need to specify K upfront — explore multiple granularities from one tree
Interpretable output — dendrogram shows cluster relationships and hierarchy
Deterministic — same data always gives same tree (unlike K-Means' random init)
Works with any distance metric — not limited to Euclidean space

Disadvantages:

Computational cost: $O(n^2 \log n)$ $O (n^{2} lo g n)$ time, $O(n^2)$ $O (n^{2})$ space (distance matrix)
- K-Means is $O(nkd \cdot i)$ where $i$ = iterations, usually much faster
Gredy and irreversible — early merge mistakes can't be undone
Sensitive to outliers (especially single linkage)
Not scalable — impractical for $n > 10,000$ points without approximations

When to use hierarchical:

Small-to-medium datasets ( $n < 10,000$ )
Need cluster hierarchy, not just flat partition
Exploratory analysis to determine natural K
Biological taxonomy, document hierarchies (true hierarchical structure)

When to avoid:

Large datasets (use K-Means, DBSCAN, or mini-batch variants)
Clusters with complex shapes (use DBSCAN instead)
Need to update clusters as new data arrives (hierarchical requires full rebuild)

Worked example Full Walkthrough: 1D Data

Data: $x = [2, 4, 10, 12, 18]$

Using complete linkage: Iteration 1: All points are separate clusters Distance matrix:

    2   4   10  12  18
2    0   2   8   10  16
4        0   6   8   14
10           0   2   8
12               0   6
18                   0

Minimum distance: $d(2,4) = 2$ → Merge {2} and {4} into {2,4} Iteration 2: Clusters {2,4}, {10}, {12}, {18} Update distances (complete linkage = max):

$d(\{2,4\}, \{10\}) = \max(d(2,10), d(4,10)) = \max(86) = 8$
$d(\{2,4\}, \{12\}) = \max(10, 8) = 10$
$d(\{2,4\}, \{18\}) = \max(16, 14) = 16$
$d(\{10\}, \{12\}) = 2$ (unchanged)
$d(\{10\}, \{18\}) = 8$ (unchanged)
$d(\{12\}, \{18\}) = 6$ (unchanged)

Minimum: $d(10,12) = 2$ → Merge {10} and {12} into {10,12}

Iteration 3: Clusters {2,4}, {10,12}, {18}

$d(\{2,4\}, \{10,12\}) = \max(8, 10) = 10$
$d(\{2,4\}, \{18\}) = 16$
$d(\{10,12\}, \{18\}) = \max(8, 6) = 8$ Minimum: $d(\{10,12\}, \{18\}) = 8$ → Merge into {10,12,18}

Iteration 4: Clusters {2,4}, {10,12,18}

$d(\{2,4\}, \{10,12,18\}) = \max(8, 10, 16) = 16$ Final merge: Merge all into {2,4,10,12,18} at height 16

Dendrogram interpretation:

Merge heights: [2, 2, 8, 16]
Big jump from 8→16 suggests cutting at height 12
Result: 2 clusters {2,4} and {10,12,18} ✓

Recall Explain to a 12-year-old

Imagine you have a bunch of LEGO bricks scattered on the floor, different colors and sizes. Hierarchical clustering is like organizing them into groups.

Aglomerative (bottom-up): You start by picking up each brick. Then you look for two bricks that are MOST similar (maybe both red, or both 2x4 size) and put them together. Then you keep doing this: find the two groups that are most similar and combine them. Maybe you combine two red piles, or a red pile with a pink pile (they're kinda similar!). Eventually, all your bricks are in one giant pile.

The cool part? You took a video the whole time. Now you can rewind and stop at ANY point to see different groupings. Maybe you want3 piles (primary colors), or 10 piles (every shade), or 100 piles (nearly every brick separate). You don't have to choose until you see the video!

Divisive (top-down): This is like doing it backwards. Start with all bricks in one pile, then split it into two groups (maybe "red-ish" vs "blue-ish"). Then split each of those groups again, and again, until every brick is alone.

The "dendrogram" is like a family tree of your LEGO bricks, showing which bricks are "related" (similar) and which are "distant cousins" (very different). The height of each branch shows HOW different the groups were when you combined them.

Connections

K-Means Clustering — flat clustering requiring K upfront; hierarchical helps choose K
DBSCAN — density-based alternative; better for non-convex clusters, hierarchical better for interpretability
Distance Metrics — Euclidean, Manhattan, Cosine choice drastically affects clustering
Dendrogram Visualization — tree representation of cluster hierarchy
Elbow Method — used to determine optimal K; applied to dendrogram merge heights
Single-Link vs Complete-Link — trade-off between sensitivity to chaining vs outliers
Time Complexity Analysis — $O(n^3)$ naive, $O(n^2 \log n)$ optimized vs K-Means $O(nkd)$
Gredy Algorithms — hierarchical uses gredy merging, not globally optimal
Within-Cluster Sum of Squares — Ward's method minimizes WCSS increase

#flashcards/ai-ml

What are the two main types of hierarchical clustering? :: Agglomerative (bottom-up merging) and Divisive (top-down splitting)

What is the output of hierarchical clustering?

A dendrogram (tree structure) showing cluster relationships at all levels of granularity, not just a single partition

What is the time complexity of aglomerative clustering with a priority queue?

O(n^2 \log n)

time and

O(n^2)

space for the distance matrix

What is single linkage criterion?

Distance between clusters = minimum distance between any two points from the two clusters:

\min_{x_i \in C_p, x_j \in C_q} d(x_i, x_j)

What is complete linkage criterion?

Distance between clusters = maximum distance between any two points from the two clusters:

\max_{x_i \in C_p, x_j \in C_q} d(x_i, x_j)

What is Ward's linkage criterion?

Merges clusters that minimize the increase in total within-cluster variance:

\frac{|C_p||C_q|}{|C_p|+|C_q|}|\mu_p - \mu_q||^2

What is the chaining effect in single linkage?

Single linkage connects clusters through outlier bridges or noise points, creating elongated chains instead of compact clusters

How do you choose the number of clusters from a dendrogram?

Look for large vertical gaps (big jumps in merge height) and cut the dendrogram horizontally just before a large jump

What is the main advantage of hierarchical clustering over K-Means?

No need to specify K upfront — you get cluster structure at all granularities and can choose K by examining the dendrogram

Why is hierarchical clustering not globally optimal?

It uses gredy local decisions at each merge step. Once two clusters are merged, they never split, so early mistakes propagate

When should you use complete linkage over single linkage?

Use complete linkage when you want compact, well-separated clusters and your data has noise or outliers. Single linkage sufers from chaining in these cases

What is the main disadvantage of hierarchical clustering for large datasets?

O(n^2)

space for distance matrix and

O(n^2 \log n)

time makes it impractical for

n > 10,000

points

What does the height of a merge in a dendrogram represent?

The distance or dissimilarity between the two clusters being merged at that step

How does average linkage differ from single and complete linkage?

Average linkage uses the mean of all pairwise distances between clusters, providing a compromise between single (minimum) and complete (maximum)

Why is Ward's method good for creating balanced clusters?

It minimizes within-cluster variance increase, which naturally produces compact clusters of similar size and low internal variance

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hierarchical clustering ek bahut powerful technique hai jisme hum data points ko tree structure mein organize karte hain. Socho jaise family tree hota hai — sabse niche individual log, phir chhote families, phir bade families, aur top peura extended family. Isi tarah, hierarchical clustering mein hum data points ko gradually merge ya split karte hain.

Do main approaches hain: Agglomerative (bottom-up) aur Divisive (top-down). Agglomerative mein hum har point ko alag cluster consider karte hain, phir sabse similar clusters ko merge karte jate hain jab tak sab ek cluster mein na aa jaayein. Divisive mein ulta — sabhi points ek cluster mein start karte hain, phir split karte karte individual points tak pahunchte hain. Agglomerative zyada common hai kyunki computationally efficient hai.

Sabse interesting part hai linkage criterion — yeh decide karta hai ki do clusters ke bech distance kaise measure karein. Single linkage (nearest points), complete linkage (farthest points), average linkage (sabka average), aur Ward's method (variance minimize karo) — harek different shape ke clusters banata hai. Output ek

Hierarchical clustering (agglomerative - divisive)

What is Hierarchical Clustering?

Why This Matters

The Two Approaches

1. Agglomerative Clustering (Bottom-Up)

2. Divisive Clustering (Top-Down)

Linkage Criteria (The Heart of Aglomerative)

The Dendrogram: Reading the Tree

Implementation Details

Advantages & Disadvantages

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Unsupervised Learning

Connections