Hierarchical (Agglomerative) Clustering

Source: Unit 4 §2

Hierarchical clustering produces a set of nested clusters organized as a hierarchical tree, visualized as a dendrogram - a tree diagram that records the sequence of merges (or splits).

Dendrograms

The dendrogram records every merge and the height it happened at. Cutting it at a height is the only thing you do to choose K.

✓Best practiceDo not pick K in advance here

The strength of hierarchical clustering is that no number of clusters has to be assumed. Run it once, then get any number of clusters you like by cutting the dendrogram at the right level.

Type	Direction
Agglomerative	Bottom-up: start with each point as its own cluster, repeatedly merge
Divisive	Top-down: start with one big cluster, repeatedly split

The agglomerative algorithm

→StepsAgglomerative clustering

1. Compute the proximity (distance) matrix.
2. Let each data point be its own cluster.
3. Repeat:
4.     Merge the two closest clusters.
5.     Update the proximity matrix.
6. Until only a single cluster remains.

◎Exam cueWhere the variants live

The key operation is defining the proximity between two clusters. Steps 1, 2, 3 and 6 never change; different definitions of "closest" in step 4 are what give you different algorithms.

Inter-cluster similarity methods (linkage)

Method	Cluster distance =
MIN (Single link)	minimum distance between any two points (one from each cluster)
MAX (Complete link)	maximum distance between any two points
Group Average	average of all pairwise distances
Distance between Centroids	distance between the cluster centroids
Ward's Method	uses squared error (objective-function driven)

The group-average formula:

$$\text{proximity}(C_i, C_j) = \frac{\displaystyle\sum_{p_i \in C_i,\; p_j \in C_j} \text{proximity}(p_i, p_j)} {|C_i| \cdot |C_j|}$$

Worked example

Two clusters C1 = {a, b} and C2 = {c, d, e}, with 1-D features a=1, b=2, c=4, d=5, e=6.

Distance matrix (absolute differences):

	a	b	c	d	e
a	0	1	3	4	5
b	1	0	2	3	4
c	3	2	0	1	2
d	4	3	1	0	1
e	5	4	2	1	0

The cross-cluster distances are the only ones linkage cares about: d(a,c)=3, d(a,d)=4, d(a,e)=5, d(b,c)=2, d(b,d)=3, d(b,e)=4.

Single, complete and average linkage read the same six cross-cluster distances and disagree only on which number to keep.

→StepsThree linkages, same six numbers

1. Single (MIN): min{3, 4, 5, 2, 3, 4} = 2.
2. Complete (MAX): max{3, 4, 5, 2, 3, 4} = 5.
3. Average: (3+4+5+2+3+4) / 6 = 21/6 = 3.5.

Time and space complexity

Resource	Cost	Why
Space	O(N²)	stores the proximity matrix (N = number of points)
Time	O(N³)	N steps × (update + search the N² matrix); reducible to O(N² log N) for some approaches

Limitations

⚠GotchaA merge can never be undone

Agglomerative clustering is irreversible: once two clusters are merged, there is no step that separates them again. A bad early merge is carried all the way to the root.

Different schemes also struggle with noise and outliers, clusters of different sizes, non-convex shapes, and breaking large clusters.