# Hierarchical clustering

> Build a tree of nested clusters (a dendrogram); cutting it at any height gives a flat clustering.

Source: https://www.mlfoundry.in/learn/hierarchical-clustering  
Section: ML Algorithms › Unsupervised · Clustering  
Level: core · 17 min read · updated 2026-10-07

**Hierarchical clustering:** builds a **nested family of clusterings** of the same data — from $n$ singletons up to one cluster containing everything — and records it as a tree called a **dendrogram**. Each internal node is a merge (or split) drawn at the *height* where it happened; cutting the tree with a horizontal line at height $h$ gives an ordinary flat clustering, and every $k$ from 1 to $n$ is available from the one tree.

- **Task:** Unsupervised clustering — and a summary of the data's structure at every scale
- **Input → output:** $n$ points (or just an $n\times n$ dissimilarity matrix) → a binary tree with $n-1$ merge heights; a cut turns it into labels
- **Learns:** the order in which groups join and the height $h_1\le h_2\le\dots\le h_{n-1}$ of each join
- **Training:** agglomerative: $O(n^2)$ to $O(n^3)$ time and $O(n^2)$ memory for the distance matrix; divisive: exponential if exact, so heuristics such as DIANA are used
- **Prediction:** none built in — the tree describes the training points; a new point is assigned to the nearest cluster after cutting
- **Hyperparameters:** dissimilarity metric, linkage (single / complete / average / Ward), and where to cut (height or k)
- **Assumes:** that a meaningful nested structure exists, and that the chosen metric on your (scaled) features expresses similarity

## The problem

A flat method such as **k-means** answers one question — *split the data into exactly $k$ groups* — and asks you to pick $k$ before you have looked. Change your mind and you re-run it, and the 4-cluster answer need not refine the 3-cluster one: a point can jump between groups as $k$ changes. Many real structures are not flat at all. Species nest into genera and families, products into sub-categories, documents into topics and sub-topics, genes into co-expressed modules within pathways.

We want a method that (1) does not need $k$ in advance, (2) produces clusterings at all granularities that are **consistent with each other** — the 4-cluster answer is the 3-cluster answer with one group split — and (3) gives a picture of *how strongly* groups are separated, so that the choice of $k$ can be made by looking. Hierarchical clustering delivers all three, and it needs only pairwise dissimilarities, so it works for strings, graphs or any objects you can compare.

## The idea

Start with every point as its own cluster. Repeatedly **merge the two closest clusters**, writing down how far apart they were. After $n-1$ merges everything is one cluster, and the log of merges *is* the tree. This bottom-up version is **agglomerative** clustering and is what almost everyone uses; the merge loop and the choice of linkage are covered in depth in the **agglomerative clustering** article. The top-down alternative, **divisive** clustering, starts with one cluster and repeatedly splits the least coherent one.

Either way, draw each merge as a ⊓-shaped link whose horizontal bar sits at the merge height. Tight groups join near the bottom; well-separated groups join only near the top, leaving a long vertical stretch with no merges. A horizontal line through that stretch cuts the tree into a stable flat clustering.

**Vocabulary**

- **Dendrogram:** the tree of merges; leaves are data points along the bottom, the vertical axis is merge height
- **Merge height:** the linkage distance $h$ between the two clusters at the moment they were joined
- **Linkage:** the rule for the distance between two *sets* of points: single (closest pair), complete (farthest pair), average (mean pair), Ward (increase in within-cluster squared error)
- **Cut:** a horizontal line at height $h$: every subtree hanging below it becomes one cluster. Cutting so that exactly $k$ subtrees remain gives a $k$-clustering
- **Cophenetic distance:** $c(x,y)$: the height of the lowest node that contains both $x$ and $y$ — the tree's own notion of how far apart they are
- **Ultrametric:** a distance with $c(x,z)\le\max\{c(x,y),c(y,z)\}$; cophenetic distances from a monotone tree always satisfy it
- **Inversion:** a merge lower than a merge below it — possible with centroid and median linkage, and it makes the dendrogram uncuttable at some heights
- **Leaf order:** the left-to-right order of leaves; any subtree may be flipped without changing the tree, so only vertical heights carry information

## The math

A hierarchy is a sequence of partitions, each obtained from the previous one by merging exactly two blocks:

$$
\mathcal P_0=\{\{x_1\},\dots,\{x_n\}\},\qquad \mathcal P_{t}=\mathcal P_{t-1}\setminus\{A_t,B_t\}\cup\{A_t\cup B_t\},\qquad (A_t,B_t)=\arg\min_{A\ne B\in\mathcal P_{t-1}} d(A,B)
$$

- $\mathcal P_t$: the partition after $t$ merges; it has $n-t$ clusters
- $d(A,B)$: linkage: dissimilarity between two clusters, built from point dissimilarities
- $h_t=d(A_t,B_t)$: height of merge $t$; the dendrogram draws node $t$ at this height

Because every partition refines the next, the clusterings for different $k$ are **nested** by construction — this is what a single run of k-means for each $k$ cannot promise.

## One update rule for every linkage

Recomputing $d(A,B)$ from all point pairs after every merge would be wasteful. Lance and Williams (1967) showed that the common linkages can all be updated from the old cluster distances alone. When $i$ and $j$ merge, the distance from the new cluster to any other cluster $k$ is

$$
d(i\cup j,\,k)=\alpha_i\,d(i,k)+\alpha_j\,d(j,k)+\beta\,d(i,j)+\gamma\,\bigl|d(i,k)-d(j,k)\bigr|
$$

- $d(i,k)$: current distance between clusters $i$ and $k$
- $\alpha_i,\alpha_j,\beta,\gamma$: coefficients that define the linkage (table below)
- $n_i,n_j,n_k$: cluster sizes

Lance–Williams coefficients. For Ward the rule is applied to squared Euclidean distances $d^2$.

| Linkage | αᵢ | β | γ | Equivalent to |
| --- | --- | --- | --- | --- |
| Single | ½ | 0 | −½ | $\min(d(i,k),d(j,k))$ — closest pair |
| Complete | ½ | 0 | +½ | $\max(d(i,k),d(j,k))$ — farthest pair |
| Average (UPGMA) | $\tfrac{n_i}{n_i+n_j}$ | 0 | 0 | mean of all cross-cluster pairs |
| Ward | $\tfrac{n_i+n_k}{n_i+n_j+n_k}$ | $\tfrac{-n_k}{n_i+n_j+n_k}$ | 0 | increase in within-cluster sum of squares |

Check single linkage: with $\alpha=\tfrac12,\gamma=-\tfrac12$ the rule is $\tfrac12(a+b)-\tfrac12|a-b|=\min(a,b)$. With $\gamma=+\tfrac12$ it becomes $\max(a,b)$. Which linkage to choose — chaining, compactness, outlier sensitivity — is the main subject of the agglomerative clustering article; here we care about what the resulting *tree* means.

## Deriving Ward's merge cost

Ward's method merges the pair that increases the total within-cluster sum of squares $\text{SSE}=\sum_{C}\sum_{x\in C}\lVert x-\mu_C\rVert^2$ the least — the k-means objective, minimized greedily one merge at a time. The increase has a closed form. For any set $C$ and any point $m$, $\sum_{x\in C}\lVert x-m\rVert^2=\sum_{x\in C}\lVert x-\mu_C\rVert^2+n_C\lVert\mu_C-m\rVert^2$ (the cross term vanishes because $\sum_{x\in C}(x-\mu_C)=0$). Apply it to $A$ and to $B$ with $m=\mu_{A\cup B}=\tfrac{n_A\mu_A+n_B\mu_B}{n_A+n_B}$:

$$
\Delta(A,B)=\text{SSE}(A\cup B)-\text{SSE}(A)-\text{SSE}(B)=n_A\lVert\mu_A-\mu_{AB}\rVert^2+n_B\lVert\mu_B-\mu_{AB}\rVert^2=\frac{n_A n_B}{n_A+n_B}\,\lVert\mu_A-\mu_B\rVert^2
$$

- $\mu_A,\mu_B$: centroids of the two clusters
- $n_A,n_B$: their sizes
- $\Delta(A,B)$: increase in total within-cluster squared error caused by the merge

The last step uses $\mu_A-\mu_{AB}=\tfrac{n_B}{n_A+n_B}(\mu_A-\mu_B)$ and the symmetric expression for $B$. So Ward is a centroid distance **weighted by a harmonic size factor**: merging two big clusters costs more than merging a big one with a small one at the same centroid distance, which is why Ward produces balanced, compact clusters. SciPy and scikit-learn report the height $\sqrt{2\Delta}$, which equals the plain Euclidean distance when two singletons merge (for B and C below, $\sqrt{2\cdot\tfrac12\cdot1.118^2}=1.118$).

## Why a cut gives a clean partition: the ultrametric

For single, complete, average and Ward linkage the merge heights never decrease, $h_1\le h_2\le\dots\le h_{n-1}$ (the linkage of a merged cluster to any $k$ is never smaller than the distance that triggered the merge). Define the **cophenetic distance** $c(x,y)$ as the height of the node where $x$ and $y$ first meet. Take three points: the two that meet first, say $x,y$, do so at $c(x,y)$, and $z$ joins their cluster later at a single height, so $c(x,z)=c(y,z)\ge c(x,y)$. Therefore

$$
c(x,z)\le\max\{c(x,y),\,c(y,z)\}\quad\text{for all }x,y,z
$$

- $c(x,y)$: cophenetic distance: height of the lowest dendrogram node containing both $x$ and $y$

This **strong triangle inequality** says every triangle is isosceles with a short base. It implies that "$c(x,y)\le h$" is an equivalence relation for each $h$ — which is exactly the statement that cutting at $h$ yields a partition. A dendrogram *is* an ultrametric, and hierarchical clustering can be read as **approximating your distances by an ultrametric**. Centroid and median linkage break monotonicity (inversions), and then a cut is no longer well-defined.

$$
r_{\text{coph}}=\operatorname{corr}\bigl(d(x_i,x_j),\,c(x_i,x_j)\bigr)\quad\text{over all } \tbinom{n}{2}\text{ pairs } i<j
$$

- $d(x_i,x_j)$: original dissimilarity
- $c(x_i,x_j)$: cophenetic distance from the tree
- $r_{\text{coph}}$: Pearson correlation: how faithfully the tree preserves the input distances (1 = perfectly)

## Where to cut

A cut at height $h$ keeps the merges with $h_t\le h$, giving $k(h)=n-\#\{t: h_t\le h\}$ clusters. Because heights are sorted, *any* $h$ in the open interval $(h_{n-k},h_{n-k+1})$ gives the same $k$ clusters; the **length of that interval** measures how robust the $k$-clustering is. The classic heuristics:

**Choosing the cut**

- **Fixed k:** cut where exactly k subtrees remain (`fcluster(Z, k, 'maxclust')`, `n_clusters=k`)
- **Fixed height:** cut at a distance with domain meaning, e.g. ≤ 3% sequence divergence (`distance_threshold`)
- **Largest gap:** cut in the middle of the largest jump $h_{t+1}-h_t$: the clusters survive the widest range of thresholds
- **Inconsistency:** for each link, $(h_t-\bar h)/s$ where $\bar h,s$ are the mean and std of the link heights within a few levels below it; cut links that are unusually tall relative to their subtree
- **Internal scores:** compute silhouette (or Calinski–Harabasz) for every k — cheap, because all cuts come from the same tree

## Worked example: eight points, average linkage

Eight points in the plane that the eye sees as three groups: a tight triple at the bottom left, a looser triple on the right, and a pair at the top.

The data. Highlighted: the right-hand group D, E, F, the loosest of the three.

| Point | x₁ | x₂ |
| --- | --- | --- |
| A | 1.0 | 2.5 |
| B | 2.5 | 1.5 |
| C | 3.5 | 2.0 |
| D | 6.0 | 4.0 |
| E | 7.5 | 7.0 |
| F | 10.0 | 4.5 |
| G | 4.0 | 8.5 |
| H | 4.5 | 10.0 |

Euclidean distance matrix (upper triangle). Bold: the smallest entry, B–C = 1.118, which is the first merge.

| d | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- |
| A | 1.80 | 2.55 | 5.22 | 7.91 | 9.22 | 6.71 | 8.28 |
| B |  | **1.12** | 4.30 | 7.43 | 8.08 | 7.16 | 8.73 |
| C |  |  | 3.20 | 6.40 | 6.96 | 6.52 | 8.06 |
| D |  |  |  | 3.35 | 4.03 | 4.92 | 6.18 |
| E |  |  |  |  | 3.54 | 3.81 | 4.24 |
| F |  |  |  |  |  | 7.21 | 7.78 |
| G |  |  |  |  |  |  | 1.58 |

**Seven merges by hand (average linkage: d(A,B) = mean of all cross pairs)**

1. **Merge 1: B + C at 1.118**, the smallest distance. Update with the size-weighted mean, e.g. $d(BC,A)=\tfrac12(1.80+2.55)=2.176$ and $d(BC,D)=\tfrac12(4.30+3.20)=3.751$.
2. **Merge 2: G + H at 1.581**, now the smallest entry. $d(GH,E)=\tfrac12(3.81+4.24)=4.025$, $d(GH,D)=5.555$.
3. **Merge 3: A + BC at 2.176.** The new triple's distance to D is $\tfrac13(5.22+4.30+3.20)=4.241$ — the same as the Lance–Williams update $\tfrac13 d(A,D)+\tfrac23 d(BC,D)=\tfrac13(5.22)+\tfrac23(3.751)$.
4. **Merge 4: D + E at 3.354.** The bottom-left triple and the top pair are already complete; the right-hand group starts forming. $d(DE,F)=\tfrac12(4.03+3.54)=3.783$.
5. **Merge 5: F + DE at 3.783.** Remaining clusters: $\{A,B,C\}$, $\{D,E,F\}$, $\{G,H\}$ with $d(DEF,GH)=5.691$, $d(DEF,ABC)=6.525$, $d(ABC,GH)=7.576$.
6. **Merge 6: GH + DEF at 5.691.** Then $d(ABC,DEFGH)=6.946$, the mean of all 15 cross pairs.
7. **Merge 7: ABC + DEFGH at 6.946.** One cluster; the tree is complete.

The merge log, which is the dendrogram. The jump after merge 5 (3.783 → 5.691, gap 1.908) is the largest.

| Merge | Joins | Height | Gap to next | Clusters after |
| --- | --- | --- | --- | --- |
| 1 | B + C | 1.118 | 0.463 | 7 |
| 2 | G + H | 1.581 | 0.595 | 6 |
| 3 | A + BC | 2.176 | 1.178 | 5 |
| 4 | D + E | 3.354 | 0.429 | 4 |
| 5 | F + DE | 3.783 | **1.908** | **3** |
| 6 | GH + DEF | 5.691 | 1.254 | 2 |
| 7 | ABC + DEFGH | 6.946 | — | 1 |

**Reading the tree**

1. **Cut at the largest gap**, $h=\tfrac12(3.783+5.691)=4.737$: merges 1–5 lie below it, so $k=8-5=3$ clusters $\{A,B,C\}$, $\{D,E,F\}$, $\{G,H\}$. Silhouette: **0.546**, higher than for $k=2$ (0.460) or $k=4$ (0.449).
2. **Other cuts are free.** At $h=3$ only merges 1–3 apply → 5 clusters $\{A,B,C\},\{G,H\},\{D\},\{E\},\{F\}$. At $h=6$ → 2 clusters $\{A,B,C\}$ vs the rest. No re-run needed.
3. **Cophenetic distances.** A and F first meet in the root, so $c(A,F)=6.946$ although $d(A,F)=9.22$; D and G meet at merge 6, $c(D,G)=5.691$ versus $d(D,G)=4.92$. Over all 28 pairs the cophenetic correlation is $r=0.809$.
4. **A new point** $q=(5,\,5.5)$. Its mean distance to the three clusters of the cut is 4.508 to ABC, **3.272** to DEF and 3.845 to GH, so it joins $\{D,E,F\}$ (its nearest single point is also D, at 1.803).

Same data, four linkages. Average linkage preserves the distances best (highest cophenetic r); single linkage chains D, E, F onto the bottom-left group and splits off only {G, H} at k = 2.

| Linkage | Merge heights | k = 2 split | Cophenetic r |
| --- | --- | --- | --- |
| Single | 1.12 1.58 1.80 3.20 3.35 3.54 3.81 | ABCDEF \| GH | 0.716 |
| Complete | 1.12 1.58 2.55 3.35 4.03 7.78 9.22 | ABC \| DEFGH | 0.805 |
| **Average** | 1.12 1.58 2.18 3.35 3.78 5.69 6.95 | ABC \| DEFGH | **0.809** |
| Ward | 1.12 1.58 2.47 3.35 3.93 8.42 12.18 | ABC \| DEFGH | 0.797 |

> Figure: The worked example as a live dendrogram. Drag the rose cut line: everything below it is coloured by flat cluster on both panels, and the scatter draws each merge as a link between the two children's centroids. It starts at the largest gap (h = 4.74, k = 3, silhouette 0.546, cophenetic r = 0.809 for average linkage). Press build to sweep the cut up one merge at a time; switch linkage to see single linkage's flat, chained tree (r = 0.716) or Ward's tall top merges (12.18). A and F are selected: distance 9.220 but cophenetic distance 6.946. The bridge dataset shows single linkage chaining two blobs through a line of points.

> **The tree is the model; k is a view:** All the expensive work — the distance matrix and the merges — happens once. Every flat clustering, from 8 singletons to 1 group, is a cheap cut of the same tree, and the clusterings are nested. That is why you can choose k *after* fitting, by looking at gaps or scoring each cut, instead of re-running k-means for every k.

## The algorithm, step by step

**Agglomerative hierarchical clustering**

1. **Distances.** Compute the $n\times n$ dissimilarity matrix ($\tbinom n2$ entries). Scale features first if they use different units.
2. **Initialize** $n$ singleton clusters, all active.
3. **Find** the pair of active clusters $(i,j)$ with the smallest linkage distance; record the merge $(i,j,h=d(i,j),n_i+n_j)$.
4. **Update** the distance from the new cluster $i\cup j$ to every other active cluster with the Lance–Williams rule; deactivate $i$ and $j$.
5. **Repeat** steps 3–4 until one cluster remains — $n-1$ merges. The merge list is the dendrogram (SciPy's linkage matrix $Z$).
6. **Cut** at a height or a $k$ to get labels; evaluate several cuts if $k$ is unknown.

**Complexity**

- **Naive:** $n-1$ scans of an $O(n^2)$ matrix → $O(n^3)$ time, $O(n^2)$ memory
- **Priority queue / nearest-neighbour chain:** $O(n^2)$ time for Ward, complete and average linkage (SciPy and fastcluster use NN-chain); memory still $O(n^2)$
- **Single linkage:** equals the minimum spanning tree: SLINK runs in $O(n^2)$ time and $O(n)$ memory
- **Memory wall:** the condensed distance matrix for $n=100{,}000$ has $\approx 5\times10^9$ entries — 40 GB of float64. Beyond roughly tens of thousands of points, summarize first (BIRCH) or use connectivity constraints
- **Cutting:** $O(n)$ per cut once the tree exists

## Divisive clustering (DIANA)

The top-down route splits instead of merges. Trying every bipartition is $O(2^{n})$, so Kaufman and Rousseeuw's **DIANA** uses a splinter heuristic: in the cluster with the largest diameter, move out the point with the largest average dissimilarity to the others, then keep moving points that are on average closer to the splinter group than to the rest. On the worked example, F has the largest mean distance (6.688) and starts the splinter; E, D, H and G follow, and the first split is $\{D,E,F,G,H\}$ vs $\{A,B,C\}$ — the same top split as average linkage. Divisive methods get the **top** of the tree right first (decided on global information), while agglomerative methods get the **bottom** right first; use divisive when you only want a few large clusters.

## Variants and tuning

The knobs that matter, in order of impact.

| Choice | Options | Effect |
| --- | --- | --- |
| Linkage | single · complete · average · Ward | Shapes the whole tree: single chains, complete and Ward favour compact balanced groups, average sits between. Ward requires Euclidean distances |
| Dissimilarity | Euclidean, Manhattan, cosine, correlation, Jaccard, edit distance, DTW… | Defines similarity; the only place domain knowledge enters. Correlation distance is standard for gene expression |
| Feature scaling | standardize, robust-scale, none | A feature in larger units dominates every distance and therefore every merge |
| Cut | k, height, largest gap, inconsistency, silhouette | Turns the tree into labels; can be changed after fitting at no cost |
| Connectivity constraint | k-NN graph, grid adjacency (`connectivity=`) | Only neighbours may merge: faster, and gives spatially contiguous clusters (image segmentation) |
| Direction | agglomerative · divisive (DIANA) · bisecting k-means | Bottom-up is exact for its linkage; top-down is greedy from the root |
| Scale-out | BIRCH pre-clustering, HDBSCAN | BIRCH builds the hierarchy on compact summaries; HDBSCAN builds a single-linkage tree on a density-based distance and extracts stable clusters automatically |

> **Related articles:** Linkage behaviour and the merge loop in detail: **agglomerative clustering**. Flat, centroid-based alternatives: **k-means** and **k-medoids**. Hierarchies for large data: **BIRCH**. Exemplar-based clustering without k: **affinity propagation**.

## In code

```python
import numpy as np

def hierarchical(X, linkage="average"):
    """Agglomerative clustering with Lance-Williams updates. Returns merges (a, b, height, size)."""
    n = len(X)
    D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1))
    D = np.pad(D, ((0, n - 1), (0, n - 1)))          # room for the n-1 new clusters
    size = np.r_[np.ones(n), np.zeros(n - 1)]
    active, merges = list(range(n)), []
    for step in range(n - 1):
        best = (np.inf, None, None)
        for x, i in enumerate(active):               # closest pair of active clusters
            for j in active[x + 1:]:
                if D[i, j] < best[0]:
                    best = (D[i, j], i, j)
        h, i, j = best
        new = n + step
        ni, nj = size[i], size[j]
        for k in active:
            if k in (i, j):
                continue
            nk = size[k]
            if linkage == "single":   d = min(D[i, k], D[j, k])
            elif linkage == "complete": d = max(D[i, k], D[j, k])
            elif linkage == "average":  d = (ni * D[i, k] + nj * D[j, k]) / (ni + nj)
            else:  # ward
                d = np.sqrt(((ni + nk) * D[i, k]**2 + (nj + nk) * D[j, k]**2 - nk * h**2) / (ni + nj + nk))
            D[new, k] = D[k, new] = d
        size[new] = ni + nj
        merges.append((min(i, j), max(i, j), h, int(ni + nj)))
        active = [k for k in active if k not in (i, j)] + [new]
    return merges

def members(merges, n, node):
    if node < n:
        return [node]
    a, b, _, _ = merges[node - n]
    return members(merges, n, a) + members(merges, n, b)

def cut(merges, n, h):
    """Flat labels: apply every merge at height <= h."""
    labels = np.arange(n)
    for a, b, height, _ in merges:
        if height > h:
            break
        idx = members(merges, n, a) + members(merges, n, b)
        labels[idx] = labels[idx].min()
    return np.unique(labels, return_inverse=True)[1]

def cophenetic(merges, n):
    C = np.zeros((n, n))
    for a, b, h, _ in merges:
        for i in members(merges, n, a):
            for j in members(merges, n, b):
                C[i, j] = C[j, i] = h
    return C

X = np.array([[1, 2.5], [2.5, 1.5], [3.5, 2], [6, 4], [7.5, 7], [10, 4.5], [4, 8.5], [4.5, 10]])
names = "ABCDEFGH"
merges = hierarchical(X, "average")
for a, b, h, s in merges:
    lab = lambda v: "".join(names[i] for i in members(merges, len(X), v))
    print(f"merge {lab(a):>5} + {lab(b):<5} at {h:.3f}  (size {s})")
print("cut at h=4.737 ->", cut(merges, len(X), 4.737))

D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
iu = np.triu_indices(len(X), 1)
r = np.corrcoef(D[iu], cophenetic(merges, len(X))[iu])[0, 1]
print(f"cophenetic correlation = {r:.3f}")
# merge     B + C     at 1.118  (size 2)
# merge     G + H     at 1.581  (size 2)
# merge     A + BC    at 2.176  (size 3)
# merge     D + E     at 3.354  (size 2)
# merge     F + DE    at 3.783  (size 3)
# merge    GH + FDE   at 5.691  (size 5)
# merge   ABC + GHFDE at 6.946  (size 8)
# cut at h=4.737 -> [0 0 0 1 1 1 2 2]
# cophenetic correlation = 0.809
```

From scratch: Lance–Williams agglomeration, cutting and cophenetic correlation in NumPy.

```python
import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster, cophenet
from scipy.spatial.distance import pdist
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score

X = np.array([[1, 2.5], [2.5, 1.5], [3.5, 2], [6, 4], [7.5, 7], [10, 4.5], [4, 8.5], [4.5, 10]])

# SciPy: build the whole tree once, then cut it as many ways as you like.
Z = linkage(X, method="average")             # (n-1) x 4: child, child, height, size
print(Z.round(3))                            # heights 1.118 1.581 2.176 3.354 3.783 5.691 6.946
r, _ = cophenet(Z, pdist(X))
print(f"cophenetic correlation: {r:.3f}")    # 0.809

for k in (2, 3, 4):
    labels = fcluster(Z, t=k, criterion="maxclust")
    print(k, labels, f"silhouette={silhouette_score(X, labels):.3f}")
# 2 [1 1 1 2 2 2 2 2] silhouette=0.460
# 3 [1 1 1 3 3 3 2 2] silhouette=0.546
# 4 [1 1 1 3 3 4 2 2] silhouette=0.449
print("cut at h=4.737:", fcluster(Z, t=4.737, criterion="distance"))   # [1 1 1 3 3 3 2 2]

# scikit-learn: same tree, cut by height (distance_threshold) or by k (n_clusters).
model = AgglomerativeClustering(n_clusters=None, distance_threshold=4.737,
                                linkage="average", compute_distances=True).fit(X)
print("sklearn labels:", model.labels_, "k =", model.n_clusters_)      # [1 1 1 0 0 0 2 2] k = 3
print("merge heights:", model.distances_.round(3))

# Assign a new point to the cluster with the smallest average distance.
q = np.array([5, 5.5])
lab = fcluster(Z, 3, "maxclust")
for c in np.unique(lab):
    print(c, round(np.linalg.norm(X[lab == c] - q, axis=1).mean(), 3))
# 1 4.508   (ABC)
# 2 3.845   (GH)
# 3 3.272   (DEF)  <- q joins D, E, F
```

SciPy builds and cuts the tree; scikit-learn gives the same labels. Outputs as comments.

> **Drawing it:** `scipy.cluster.hierarchy.dendrogram(Z, labels=list('ABCDEFGH'), color_threshold=4.737)` draws the tree with the k = 3 cut coloured; `seaborn.clustermap` reorders the rows and columns of a heatmap by the dendrogram, the standard view in genomics.

**Strengths**

- You do not know k and want to inspect structure at every scale before committing.
- The data are genuinely nested (taxonomies, phylogenies, product or topic hierarchies).
- You only have a dissimilarity matrix — strings, sequences, graphs — not vectors in a feature space.
- n is up to a few tens of thousands, so the O(n²) distance matrix fits in memory.
- Results must be deterministic: there is no random initialization as in k-means.

**Limitations**

- n is in the hundreds of thousands or more: O(n²) memory and at least O(n²) time rule it out without pre-clustering.
- You need to cluster new data repeatedly: there is no predict step; the tree must be rebuilt.
- Early mistakes matter: greedy merges are never undone, so one noisy point can misplace a whole branch.
- Clusters have very different densities or arbitrary shapes in noise — density methods such as DBSCAN or HDBSCAN handle this better.

- **Phylogenetics:** UPGMA (average linkage) on genetic distances builds species trees; the cophenetic distance is the estimated divergence time.
- **Gene-expression heatmaps:** Rows (genes) and columns (samples) are reordered by dendrograms on correlation distance to reveal co-expressed modules and patient subgroups.
- **Document and product taxonomies:** Clustering embeddings of articles or catalogue items gives a browsable topic → sub-topic tree instead of a flat list.
- **Customer segmentation at several granularities:** Marketing can work with 3 broad segments and drill into 12 sub-segments that nest exactly inside them.

> **Do not read meaning into the leaf order:** Any node's two children can be swapped without changing the tree, so two leaves drawn side by side may be far apart (in the example, F sits next to G and H only because the DEF and GH subtrees meet at 5.691). Only the height of the node where two leaves meet — the cophenetic distance — says how similar they are.

> **Unscaled features decide the tree:** Every merge is driven by distances, so a feature measured in thousands (income) swamps one measured in units (age). Standardize first, or choose a scale-free dissimilarity such as correlation distance, and check that the top splits are not just one dominant feature.

> **A high cophenetic correlation is not proof of clusters:** The cophenetic correlation measures how faithfully the tree reproduces your distances, not whether the clusters are real. Uniform random points still produce a dendrogram with apparent groups. Look for a clear gap in merge heights and check stability (bootstrap the rows, re-cluster, compare).

**Question:** In the worked example (average linkage), how many clusters does a cut at height h = 3.0 produce?

- A. 2
- B. 3
- C. 5
- D. 6

**Answer:** C. 5 — Merges 1–3 have heights 1.118, 1.581 and 2.176, all ≤ 3.0; merge 4 is at 3.354. Three merges applied to 8 points leave $8-3=5$ clusters: $\{A,B,C\},\{G,H\},\{D\},\{E\},\{F\}$.

**Question:** What is the cophenetic distance between A and F in the average-linkage tree?

- A. 9.220, their Euclidean distance
- B. 6.946, the root merge height
- C. 6.525, d(ABC, DEF)
- D. 3.783, the height where F joins DE

**Answer:** B. 6.946, the root merge height — A is in the ABC subtree and F in the DEFGH subtree; they first share a cluster at the root, merged at 6.946. The tree compresses their true distance 9.22 to 6.946.

**Question:** Why can every cut of a single-, complete-, average- or Ward-linkage dendrogram be read as a valid partition?

- A. Because the leaves are sorted by distance
- B. Because merge heights are monotone, so cophenetic distances form an ultrametric and ‘c(x,y) ≤ h’ is an equivalence relation
- C. Because the linkage is always Euclidean
- D. Because each cluster's centroid lies inside it

**Answer:** B. Because merge heights are monotone, so cophenetic distances form an ultrametric and ‘c(x,y) ≤ h’ is an equivalence relation — Monotone heights give $c(x,z)\le\max\{c(x,y),c(y,z)\}$; then $c\le h$ is transitive, so the points split into disjoint groups. Centroid and median linkage can create inversions and break this.

**Question:** Two clusters with 4 and 1 points have centroids 2 units apart. By how much does Ward's merge increase the within-cluster sum of squares?

- A. 0.8
- B. 3.2
- C. 4.0
- D. 8.0

**Answer:** B. 3.2 — $\Delta=\tfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2=\tfrac{4\cdot1}{5}\cdot 2^2=3.2$.

**Key points**

- Hierarchical clustering produces one tree of nested partitions; cutting it at height h (or to k subtrees) yields a flat clustering, and every k comes from the same fit.
- Agglomerative: start from singletons and merge the closest pair $n-1$ times; the Lance–Williams rule updates any standard linkage from old distances. Divisive (DIANA) splits from the top.
- Ward merges the pair with the smallest $\tfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2$ — the greedy k-means objective.
- Monotone merge heights make cophenetic distances an ultrametric; the cophenetic correlation measures how well the tree preserves the input distances.
- Choose the cut at a large gap in merge heights, by inconsistency, or by scoring each cut; on the example the largest gap gives k = 3 with silhouette 0.546.
- Cost is $O(n^2)$ memory and $O(n^2)$–$O(n^3)$ time; scale features, and pre-cluster (BIRCH) for large data.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
