Hierarchical Methods

1. Idea

Hierarchical clustering creates a nested sequence of clusters (a tree-like decomposition of the data) instead of a single flat partition. Two directions:

Approach	Starts from	Proceeds to	Name
Agglomerative (bottom-up)	Each object = one cluster	One cluster containing all objects	AGNES
Divisive (top-down)	All objects in one cluster	Each object its own cluster	DIANA

Because they produce a full hierarchy, the user can obtain any number of clusters by cutting the dendrogram at a chosen level.

2. Agglomerative Algorithm (AGNES)

1. Place each of the n objects in its own cluster  ->  n clusters
2. Compute the distance matrix between clusters
3. repeat
      merge the two clusters with the smallest distance (or highest similarity)
      update the distance matrix for the new cluster
   until all objects are in one cluster (or the stopping condition is met)
4. Output the dendrogram; cut it to obtain k clusters

Complexity is the main drawback: at least $O(n^2)$ time (distance matrix) and $O(n^2)$ space; naive implementations are $O(n^3)$ .

3. Inter-Cluster Distance (Linkage) Measures

Linkage	Distance definition	Shape bias	Handles non-globular?	Cost update
MIN / single link	Distance between the closest pair of points in the two clusters	Can follow elongated, chained clusters	Good for non-elliptical shapes, but sensitive to noise/bridges	Simple: $\min(d_{ik}, d_{jk})$
MAX / complete link	Distance between the farthest pair	Tends to produce compact equal-diameter clusters	Biased toward globular shapes, breaks large clusters	$\max(d_{ik}, d_{jk})$
Average link (UPGMA)	Average of distances between all pairs (one from each cluster)	Compromise	Reasonable general purpose	$O(n^2)$ weighted update
Centroid / Ward	Distance between centroids; Ward's method merges the pair that minimises the increase in total within-cluster variance	Globular; Ward is the most accurate on numeric, similarly sized clusters	Not for non-globular	Needs recomputation of centroids

Formally for clusters $C_i, C_j$ :

d_{\min}=\min_{p\in C_i,\ q\in C_j}|p-q|,\qquad d_{\max}=\max_{p\in C_i,\ q\in C_j}|p-q|,\qquad d_{avg}=\frac{1}{|C_i||C_j|}\sum_{p\in C_i}\sum_{q\in C_j}|p-q|

Ward's merging cost:

\Delta(C_i,C_j)=\frac{|C_i||C_j|}{|C_i|+|C_j|}\,\|\bar{C_i}-\bar{C_j}\|^{2}

4. Numeric Example — Points on a line

Points at 1-D positions 1, 2, 5, 9, 10 (distance = absolute difference).

Distance matrix:

	1	2	5	9	10
1	-	1	4	8	9
2		-	3	7	8
5			-	4	5
9				-	1
10					-

AGNES with MIN link:

 Step 1: merge {1,2}   (d = 1)   -> clusters: {1,2}, {5}, {9}, {10}
 Step 2: merge {9,10}  (d = 1)   -> clusters: {1,2}, {5}, {9,10}
 Step 3: merge {1,2}-{5}  d = 3  ; {9,10}-{5} d = 4   -> merge {1,2,5}
 Step 4: merge {1,2,5}-{9,10}  d = min|5-9| = 4  -> one cluster
 Dendrogram (heights):  (1,2) at 1 ; (9,10) at 1 ; (5) attaches at 3 ; final merge at 4

Obtained partition: cut at height 3.5 → two clusters {1, 2, 5} and {9, 10}.

AGNES with MAX link gives a different merge order at step 3 — merging {1,2} with {5} has distance 4, while {5} with {9,10} has distance max|10-5| = 5, so the final merge of {1,2,5} and {9,10} happens at $d=\max|2-9|=7$ ; the two-cluster solution is the same here, but complete link avoids long chains in general.

5. BIRCH — Scalable Hierarchical Clustering

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) handles large datasets in one scan using a CF (Clustering Feature) tree.

A CF-triple summarises a cluster of $N$ points:

CF=(N,\ \vec{LS},\ SS),\qquad \vec{LS}=\sum_{i=1}^{N}\vec{x_i},\qquad SS=\sum_{i=1}^{N}\|\vec{x_i}\|^{2}

Additivity theorem — CFs can be merged: $CF_1+CF_2=(N_1+N_2,\ \vec{LS_1}+\vec{LS_2},\ SS_1+SS_2)$ , giving compact, incremental summaries.

Derived statistics:

\bar x=\frac{\vec{LS}}{N},\qquad R=\sqrt{\frac{SS}{N}-\left(\frac{\vec{LS}}{N}\right)^{2}}\ \text{(radius)},\qquad D=\sqrt{\frac{\sum_i\sum_j\|\vec{x_i}-\vec{x_j}\|^{2}}{N(N-1)}}\ \text{(diameter)}

CF-tree structure:

Parameter	Meaning
Branching factor $B$	Maximum number of children per non-leaf node
Threshold $T$	Maximum radius (diameter) of a sub-cluster stored at a leaf
Leaf node	Holds up to $L$ micro-clusters (CF entries)

Phases: (1) build CF-tree from data in one scan, inserting each point into the closest leaf entry and splitting nodes only when the tree grows (incremental, similar to a B+-tree); (2) optionally condense the tree by increasing $T$ ; (3) cluster the leaf CF entries with an in-memory algorithm (agglomerative or k-means); (4) optionally refine with more passes.

Complexity $\approx O(n)$ (linear) — the strength of BIRCH. Limitation: order-sensitive and only good for spherical (radius-based) clusters; it cannot recover non-globular shapes.

Worked CF example — points (3,4) and (4,5):

N=2,\ \vec{LS}=(7,9),\ SS=3^2+4^2+4^2+5^2=9+16+16+25=66

\bar x=(3.5,4.5),\qquad R=\sqrt{66/2-(3.5^2+4.5^2)}=\sqrt{33-32.5}=\sqrt{0.5}\approx0.71

6. ROCK — Categorical / Categorical-Attribute Hierarchical Clustering

For boolean and categorical attributes, distance is replaced by links: two points are neighbours if their similarity exceeds a threshold $\theta$ ; link(p_i, p_j) = number of common neighbours.

\text{Goodness}(C_i,C_j)=\frac{\text{link}(C_i,C_j)}{\left(|C_i|+|C_j|\right)^{1+2f(\theta)}},\qquad f(\theta)=\frac{1-\theta}{1+\theta}

ROCK merges the pair with the highest goodness; $f(\theta)$ keeps clusters about equal in size. It is the hierarchical analogue of a Jaccard-based similarity method.

CHAMELEON (a third approach) first builds a $k$ -nearest-neighbour graph and then merges clusters using relative interconnectivity and relative closeness, which lets it find clusters of arbitrary shape, density and size:

RI(C_i,C_j)=\frac{|EC(C_i,C_j)|}{\frac{1}{2}\big(|EC(C_i)|+|EC(C_j)|\big)},\qquad RC(C_i,C_j)=\frac{\bar{S}_{EC(C_i,C_j)}}{\frac{|C_i|}{|C_i|+|C_j|}\bar S_{EC(C_i)}+\frac{|C_j|}{|C_i|+|C_j|}\bar S_{EC(C_j)}}

7. Divisive Hierarchical Clustering (DIANA)

Put all objects in one cluster.
Find the object with the largest average dissimilarity to all others; move it to a new cluster; then repeatedly move objects that are closer (on average) to the new cluster than to the old one, until the split is stable.
Recurse on each resulting cluster.

Divisive methods are needed when the interesting structure is at the top of the hierarchy (a few big clusters), but they are far more expensive than agglomerative ones: evaluating all $2^{n-1}$ possible first splits is prohibitive, so heuristics are used.

8. Advantages and Limitations

Advantages

No need to pre-specify $k$ ; the dendrogram gives the whole nested solution.
Deterministic (no random initialisation), easy visualisation and interpretability.
Any distance/linkage can be plugged in; handles mixed data with suitable measures.
Good exploratory tool; the tree itself is a compact summary of similarity structure.

Limitations

Poor scalability: $O(n^2)$ or worse in time and memory — too slow for millions of objects (hence BIRCH/CF-tree, ROCK, CHAMELEON).
Merges are irreversible — an early wrong decision can never be undone.
Local greedy decisions; sensitive to the linkage criterion and to noise/outliers (single-link especially).
Different linkages give different clusters → choice is subjective.

9. Exam Points

Explain AGNES and DIANA with algorithms; draw the dendrogram — 10 marks (frequent).
Solve a given distance matrix by agglomerative clustering with single link — 10 marks (very frequent numerical).
Explain MIN/MAX/average link and their bias; state why single link suffers the chaining effect — 5-7 marks.
Explain BIRCH with CF-triple, CF-tree parameters $B$ , $L$ , $T$ and phases, plus a small numerical for $R$ — 10 marks.
Short note on ROCK vs CHAMELEON — 5 marks.

Hierarchical Methods