Hierarchical Clustering:

Unsupervised method building hierarchy / dendrogram of clusters — tree where leaves = points, internal nodes = merges/splits at certain distance.

Two approaches:

1. Agglomerative (Bottom-Up) — most common:

   • Start each point as cluster.
   • Repeat: find two closest clusters via linkage, merge, update distances.
   • Stop at $k=1$ or desired $k$ (cut dendrogram).
   • Linkages:
     • Single linkage: $d(C_i,C_j)=\min_{x\in C_i,y\in C_j} d(x,y)$ — produces elongated chains, sensitive to noise
     • Complete: $\max$ distance — compact spherical clusters
     • Average: mean distance
     • Ward: minimizes increase in within-cluster SSE $\Delta = SSE_{merged}-SSE_{i}-SSE_{j}$ — often best, prefers equal-sized.
   • Complexity $O(n^3)$ naive, $O(n^2\log n)$ with heap, $O(n^2)$ memory.

2. Divisive (Top-Down):

   • Start one cluster, recursively split (e.g., via K-means), rarer due to exponential.

Dendrogram: Height = distance at merge; cut at height $h$ gives clustering. Can inspect for natural $k$.

Advantages: No preset $k$ needed (choose after), shows structure at multiple resolutions, deterministic, visualization.

Disadvantages: Greedy (once merged cannot undo), sensitive to outliers/noise (single linkage), $O(n^2)$ memory limits large data, difficult to handle large $n$ (>10k).

Example: Data points (1,2),(2,2),(8,8): single linkage merges first two at dist 1, then merges with (8,8) at ~8.5 distance dendrogram.

Use: Gene expression phylogeny, document taxonomy, small-medium datasets where hierarchy insightful. Often combined with K-means for scale.