# Agglomerative clustering

> Start with every point alone and repeatedly merge the closest pair; the linkage — single, complete, average, Ward — defines 'closest'.

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

**Agglomerative clustering:** is bottom-up hierarchical clustering: start with $n$ singleton clusters, and $n-1$ times merge the two clusters that are closest under a chosen **linkage** — a rule that turns point-to-point distances into a cluster-to-cluster distance. The sequence of merges and their heights is a tree (a dendrogram); cutting it gives a flat clustering with any number of clusters.

- **Task:** Unsupervised clustering (hard assignments), plus a full merge hierarchy
- **Input → output:** $n$ points (or any $n\times n$ dissimilarity matrix) → $n-1$ merges with heights; a cut gives labels $1,\dots,k$
- **Learns:** nothing parametric — the merge order and merge heights *are* the model
- **Training cost:** $O(n^2)$ memory for the distance matrix; $O(n^3)$ naive, $O(n^2\log n)$ with a priority queue, $O(n^2)$ for single (SLINK) and for Ward / complete / average with the nearest-neighbour chain
- **Prediction cost:** no native `predict` for new points — assign them by a rule (nearest member, nearest centroid) or train a classifier on the labels
- **Hyperparameters:** linkage, distance metric, number of clusters $k$ *or* a distance threshold, optional connectivity graph
- **Assumes:** the chosen distance is meaningful (scale features!); the linkage encodes the cluster shape you expect — compact (Ward, complete) or elongated (single)

## The problem

**k-means** asks you for $k$ before it starts, picks random seeds, needs a mean (so only works with Euclidean-style features) and assumes round clusters of similar size. You often don't know $k$; you may only have a dissimilarity matrix (edit distances between strings, 1 − correlation between genes); and you may care about *structure at several scales* — species inside genera inside families.

Agglomerative clustering removes all three restrictions. It is deterministic, needs only pairwise dissimilarities, and computes the clusterings for **every** $k$ in one run. The price is quadratic memory, greedy merges that can never be undone, and one design decision that changes everything: how to measure the distance between two *groups* of points. That decision — the linkage — is what this article is about. How to read a dendrogram and where to cut it is covered in the sibling article **Hierarchical clustering**.

## The idea

Imagine every point as an island. Repeatedly build a bridge between the two closest islands, fusing them into one. After $n-1$ bridges everything is one landmass. If you record *how long* each bridge was, you can later demolish the longest ones and recover the natural archipelago. The only question is what "closest" means once an island holds many points: the nearest shores (single), the farthest shores (complete), the average shore-to-shore distance (average), or how much the fused island would spread out (Ward).

**Vocabulary**

- **Proximity matrix:** the $n\times n$ table $D$ of current cluster-to-cluster distances; it shrinks by one row and column per merge
- **Linkage:** the function $d(A,B)$ between two sets of points, built from point distances $d(x,y)$
- **Merge height:** $h$, the linkage distance at which two clusters were fused; the $y$-coordinate of the join in the dendrogram
- **Dendrogram:** binary tree of the merges; leaves are points, each internal node is one merge drawn at its height
- **Cophenetic distance:** for two points, the height of the merge that first puts them in the same cluster; it is an *ultrametric* ($d(x,z)\le\max(d(x,y),d(y,z))$)
- **Lance–Williams update:** a one-line recurrence that gives $d(k, i\cup j)$ from $d(k,i)$, $d(k,j)$ and $d(i,j)$, so the matrix is updated without revisiting points
- **Chaining:** single linkage's tendency to join two groups through a thin line of intermediate points
- **Inversion:** a merge whose height is *lower* than an earlier one; impossible for single, complete, average and Ward, possible for centroid and median linkage
- **Connectivity constraint:** a sparse graph (e.g. $k$-nearest neighbours, pixel adjacency); only clusters joined by an edge may merge

## The math

Let $A$ and $B$ be clusters with $n_A$ and $n_B$ points, centroids $\mu_A,\mu_B$, and let $d(x,y)$ be the point distance (Euclidean unless stated). The four standard linkages are:

$$
d_{\text{single}}(A,B)=\min_{a\in A,\,b\in B} d(a,b)\qquad d_{\text{complete}}(A,B)=\max_{a\in A,\,b\in B} d(a,b)
$$

- $\min$: the closest pair across the two clusters — clusters are close if *any* members are close
- $\max$: the farthest pair — clusters are close only if *all* members are close; bounds the diameter of the merged cluster

$$
d_{\text{average}}(A,B)=\frac{1}{n_A n_B}\sum_{a\in A}\sum_{b\in B} d(a,b)
$$

- $n_A n_B$: number of cross pairs; average linkage (UPGMA) is the mean of all of them

**Ward's linkage** is different in kind: it is not a distance between members but the *cost* of the merge — how much the total within-cluster sum of squares grows. Define $\text{SSE}(S)=\sum_{x\in S}\lVert x-\mu_S\rVert^2$. Then

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

- $\Delta(A,B)$: increase in total within-cluster squared error caused by merging A and B
- $\mu_A,\mu_B$: centroids (means) of the two clusters
- $\tfrac{n_A n_B}{n_A+n_B}$: half the harmonic mean of the sizes: merging two big clusters costs more than absorbing one point

**Deriving Ward's merge cost**

1. Expand the SSE: $\text{SSE}(S)=\sum_{x\in S}\lVert x\rVert^2-n_S\lVert\mu_S\rVert^2$. The $\sum\lVert x\rVert^2$ terms of $A$, $B$ and $A\cup B$ cancel in $\Delta$, leaving $\Delta=n_A\lVert\mu_A\rVert^2+n_B\lVert\mu_B\rVert^2-(n_A+n_B)\lVert\mu_{AB}\rVert^2$.
2. The merged centroid is the size-weighted mean $\mu_{AB}=\dfrac{n_A\mu_A+n_B\mu_B}{n_A+n_B}$.
3. Substitute: $(n_A+n_B)\lVert\mu_{AB}\rVert^2=\dfrac{n_A^2\lVert\mu_A\rVert^2+2n_An_B\,\mu_A^\top\mu_B+n_B^2\lVert\mu_B\rVert^2}{n_A+n_B}$.
4. Subtract and collect over the common denominator: $\Delta=\dfrac{n_An_B\left(\lVert\mu_A\rVert^2-2\mu_A^\top\mu_B+\lVert\mu_B\rVert^2\right)}{n_A+n_B}=\dfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2$. $\blacksquare$
5. So Ward greedily makes the merge that **least increases the k-means objective**. scikit-learn and SciPy report the height $h=\sqrt{2\Delta}$, which equals the plain Euclidean distance when two singletons merge.

Because each merge adds its $\Delta$, the Ward costs of all $n-1$ merges sum to the total SSE of the data around its grand mean, and the SSE of the $k$-cluster cut is the sum of the first $n-k$ costs. That is why Ward is the hierarchical cousin of k-means.

## One update rule for all linkages

Recomputing a linkage from the raw points after every merge would cost $O(n_A n_B)$ per pair. Lance and Williams (1967) showed that all the linkages above satisfy a single recurrence, so after merging $i$ and $j$ the new row of the proximity matrix comes straight from the old one:

$$
d(k,\,i\cup j)=\alpha_i\,d(k,i)+\alpha_j\,d(k,j)+\beta\,d(i,j)+\gamma\,\lvert d(k,i)-d(k,j)\rvert
$$

- $k$: any other cluster still active
- $\alpha_i,\alpha_j,\beta,\gamma$: coefficients that define the linkage (table below); they may depend on the sizes $n_i,n_j,n_k$
- $d$: for Ward, the recurrence runs on *squared* distances $d^2$

Lance–Williams coefficients $\alpha_i,\alpha_j,\beta,\gamma$ — each column is the coefficient of the term in its header. For single linkage, $\tfrac12(a+b)-\tfrac12\lvert a-b\rvert=\min(a,b)$; for complete, the $+$ sign gives $\max(a,b)$.

| Linkage | d(k,i) | d(k,j) | d(i,j) | \|d(k,i)−d(k,j)\| | Clusters tend to be |
| --- | --- | --- | --- | --- | --- |
| Single | ½ | ½ | 0 | −½ | chain-like, any shape |
| Complete | ½ | ½ | 0 | +½ | compact, bounded diameter |
| Average | $\frac{n_i}{n_i+n_j}$ | $\frac{n_j}{n_i+n_j}$ | 0 | 0 | in between; any metric |
| Ward (on $d^2$) | $\frac{n_i+n_k}{n_i+n_j+n_k}$ | $\frac{n_j+n_k}{n_i+n_j+n_k}$ | $\frac{-n_k}{n_i+n_j+n_k}$ | 0 | compact, similar sizes |

**Monotonicity.** For these four linkages, merging the closest pair $i,j$ can never bring the new cluster *closer* to any other cluster than the closer of its parts was ($d(k,i\cup j)\ge\min(d(k,i),d(k,j))$ whenever $d(i,j)$ was the minimum), so merge heights never decrease and the dendrogram has no inversions. Centroid linkage ($\lVert\mu_A-\mu_B\rVert$, with $\alpha=\tfrac{n_i}{n_i+n_j}$, $\beta=-\alpha_i\alpha_j$) violates this and can produce crossing dendrogram branches — one reason it is rarely used.

**What each hyperparameter does, mathematically**

- **linkage:** changes the set function $d(A,B)$: min, max, mean, or $\Delta$ — and therefore the merge order. Same data, different trees.
- **metric:** changes the point distances $d(x,y)$ every linkage is built from (Euclidean, Manhattan, cosine, precomputed). Ward requires Euclidean, because $\Delta$ is a squared-error identity.
- **n_clusters = k:** keeps the first $n-k$ merges. Equivalent to cutting the tree between heights $h_{n-k}$ and $h_{n-k+1}$.
- **distance_threshold = τ:** keeps every merge with $h<\tau$; $k$ then becomes an output. Use one or the other.
- **connectivity:** sets $d(A,B)=\infty$ unless some edge of the graph joins $A$ and $B$; enforces spatial contiguity and makes the search sparse and fast.

## Worked example: nine points, four linkages

Two tight groups (A–C on the left, F–H on the right), a two-point "bridge" (D, E) between them, and one outlier I above the bridge. The question each linkage answers differently: does the bridge belong to the left group, to the outlier, or to nobody?

The nine points.

| Point | x₁ | x₂ | Role |
| --- | --- | --- | --- |
| A | 1.0 | 1.0 | left group |
| B | 1.5 | 2.0 | left group |
| C | 2.0 | 1.2 | left group |
| D | 3.4 | 1.6 | bridge |
| E | 4.8 | 1.8 | bridge |
| F | 6.2 | 1.3 | right group |
| G | 6.6 | 2.4 | right group |
| H | 7.4 | 1.6 | right group |
| I | 4.2 | 4.2 | outlier |

Euclidean distances (lower triangle, 2 decimals). The smallest, d(B, C) = 0.94, is the first merge for every linkage.

| d | A | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| **B** | 1.12 |  |  |  |  |  |  |  |
| **C** | 1.02 | **0.94** |  |  |  |  |  |  |
| **D** | 2.47 | 1.94 | 1.46 |  |  |  |  |  |
| **E** | 3.88 | 3.31 | 2.86 | 1.41 |  |  |  |  |
| **F** | 5.21 | 4.75 | 4.20 | 2.82 | 1.49 |  |  |  |
| **G** | 5.77 | 5.12 | 4.75 | 3.30 | 1.90 | 1.17 |  |  |
| **H** | 6.43 | 5.91 | 5.41 | 4.00 | 2.61 | 1.24 | 1.13 |  |
| **I** | 4.53 | 3.48 | 3.72 | 2.72 | 2.47 | 3.52 | 3.00 | 4.12 |

**By hand: the first five merges (all linkages agree on the order)**

1. **Merge 1.** The smallest entry is $d(B,C)=0.94$ → cluster BC at height 0.94. For Ward the cost is $\Delta=\tfrac{1\cdot1}{2}(0.943)^2=0.445$, height $\sqrt{2\Delta}=0.94$.
2. **Update row BC** with Lance–Williams, e.g. for A: single $\min(1.12,1.02)=1.02$; complete $\max(1.12,1.02)=1.12$; average $\tfrac12(1.12+1.02)=1.07$; Ward $\sqrt{(2\cdot1.118^2+2\cdot1.020^2-0.943^2)/3}=1.11$.
3. **Merge 2.** The next-smallest entry is A–BC under every linkage (1.02 / 1.12 / 1.07 / 1.11), each below $d(G,H)=1.13$ → cluster ABC. Under complete linkage it wins by just 0.01.
4. **Merges 3 and 4.** $d(G,H)=1.13$ → GH; then F joins: single $\min(1.17,1.24)=1.17$, complete $\max=1.24$, average 1.20, Ward 1.23 → FGH.
5. **Merge 5.** $d(D,E)=1.41$ → DE. We now have four clusters: ABC, DE, FGH and I.

Up to here the linkages differ only in *heights*. The sixth merge is where they disagree. Here are all six cluster-to-cluster distances at that moment:

Linkage distances between the four clusters after merge 5. Bold = the minimum, i.e. the sixth merge. Ward's column is the height $\sqrt{2\Delta}$, with $\Delta$ (the SSE increase) in brackets.

| Pair | Single (min) | Complete (max) | Average (mean) | Ward √(2Δ) (Δ) |
| --- | --- | --- | --- | --- |
| ABC – DE | **1.46** (C–D) | 3.88 (A–E) | 2.65 | 4.05 (8.22) |
| DE – FGH | 1.49 (E–F) | 4.00 (D–H) | 2.68 | 4.08 (8.33) |
| DE – I | 2.47 (E–I) | **2.72** (D–I) | **2.60** | **2.89 (4.17)** |
| FGH – I | 3.00 (G–I) | 4.12 (H–I) | 3.55 | 4.30 (9.25) |
| ABC – I | 3.48 (B–I) | 4.53 (A–I) | 3.91 | 4.76 (11.35) |
| ABC – FGH | 4.20 (C–F) | 6.43 (A–H) | 5.28 | 9.09 (41.28) |

**By hand: the last three merges**

1. **Single linkage** merges ABC + DE at 1.46 (the C–D gap), then ABCDE + FGH at 1.49 (the E–F gap): the bridge has *chained* both groups together. The outlier joins last at 2.47.
2. **Complete linkage** refuses that chain: ABC–DE is judged by its farthest pair A–E = 3.88. Instead DE + I merges at 2.72; then DEI + FGH at 4.12; finally ABC at 6.43 (A–H, the diameter of the whole set).
3. **Average** (2.60, 2.97, 4.18) and **Ward** (2.89, 4.70, 8.01) make the same merges as complete. Ward's three costs $\Delta=4.17,\,11.02,\,32.07$ plus the first five $(0.445+0.615+0.640+0.753+1.000=3.45)$ add up to $50.72$ — exactly the total SSE of the nine points around their mean.
4. **Cut at $k=3$** (keep the first 6 merges). Single: {A, B, C, D, E} · {F, G, H} · {I}. Complete, average, Ward: {A, B, C} · {D, E, I} · {F, G, H}. Ward's 3-cluster SSE is $3.45+4.17=7.63$.
5. **A new point** $x=(5.5,,2.0)$. There is no `predict`, so choose a rule. Nearest member: E at 0.73 → Ward cluster **DEI**. Nearest centroid: FGH's centroid (6.73, 1.77) is 1.26 away versus 1.47 for DEI's (4.13, 2.53) → **FGH**. Under single linkage the nearest-member rule puts it in **ABCDE**.

All eight merge heights. Rows 6–8 are where the linkages part ways; the cophenetic correlation (how well tree heights reproduce the original distances) is 0.28 for single and 0.73–0.74 for the others.

| Merge | Single | Complete | Average | Ward |
| --- | --- | --- | --- | --- |
| 1 | B+C 0.94 | B+C 0.94 | B+C 0.94 | B+C 0.94 |
| 2 | A+BC 1.02 | A+BC 1.12 | A+BC 1.07 | A+BC 1.11 |
| 3 | G+H 1.13 | G+H 1.13 | G+H 1.13 | G+H 1.13 |
| 4 | F+GH 1.17 | F+GH 1.24 | F+GH 1.20 | F+GH 1.23 |
| 5 | D+E 1.41 | D+E 1.41 | D+E 1.41 | D+E 1.41 |
| 6 | **ABC+DE 1.46** | **DE+I 2.72** | **DE+I 2.60** | **DE+I 2.89** |
| 7 | ABCDE+FGH 1.49 | DEI+FGH 4.12 | DEI+FGH 2.97 | DEI+FGH 4.70 |
| 8 | +I 2.47 | +ABC 6.43 | +ABC 4.18 | +ABC 8.01 |

> Figure: The nine points merging, with the dendrogram growing below. Switch linkage at any step. On a search step the white segment shows what the linkage measures: the closest pair (single), the farthest pair (complete, dashed), every cross pair (average) or the gap between centroids (Ward, ✕). Single linkage chains ABC + DE at 1.46 and ABCDE + FGH at 1.49 and leaves the outlier I for last (2.47); complete, average and Ward instead merge DE + I at 2.72 / 2.60 / 2.89. The last step cuts the tree at k = 3.

> **Single linkage is a minimum spanning tree:** The single-linkage merges are exactly the edges of the Euclidean minimum spanning tree, added in Kruskal order (shortest first): here B–C, A–C, G–H, F–G, D–E, C–D, E–F, E–I. Cutting the $k-1$ longest MST edges gives the single-linkage $k$-clustering. That is why single linkage finds any shape that is *connected by small gaps*, and also why one stray point in a gap is enough to fuse two clusters.

## The algorithm, step by step

**Agglomerate(X, linkage)**

1. **Initialise.** Make $n$ singleton clusters. Compute the $n\times n$ distance matrix $D$ (squared for Ward). $O(n^2 d)$ time, $O(n^2)$ memory.
2. **Find the closest pair.** $(a,b)=\arg\min_{i\ne j}D_{ij}$ over active clusters.
3. **Merge.** Record $(a,b,h=D_{ab},\;n_a+n_b)$ — one row of the SciPy linkage matrix $Z$.
4. **Update.** Overwrite row $a$ with $d(k,a\cup b)$ for every active $k$ via Lance–Williams; deactivate row $b$. $O(n)$.
5. **Repeat** steps 2–4 until one cluster remains ($n-1$ merges).
6. **Cut.** For a flat clustering, keep the first $n-k$ merges (or all with $h<\tau$) and label the connected groups.

**Complexity**

- **Naive:** a full scan for the minimum each round: $n$ rounds × $O(n^2)$ = $O(n^3)$ time
- **Priority queue:** a heap of each row's nearest neighbour: $O(n^2\log n)$ — the generic method for any Lance–Williams linkage
- **NN-chain:** follow nearest neighbours until two clusters are mutual nearest neighbours, merge them: $O(n^2)$ for Ward, complete and average (any *reducible* linkage). SciPy and scikit-learn use it.
- **SLINK / MST:** single linkage in $O(n^2)$ time and $O(n)$ memory; with a connectivity graph or a k-NN graph it becomes near-linear
- **Memory wall:** the condensed float64 distance matrix needs $8\cdot n(n-1)/2$ bytes: 40 GB at $n=100{,}000$. Beyond ~$10^4$–$10^5$ points, use connectivity constraints, **BIRCH** or a sample.

## Choosing a linkage

The worked example is not an accident: each linkage has a built-in idea of what a cluster looks like. Below, adjusted Rand index (1 = recovers the true groups exactly, 0 = chance) for scikit-learn's `AgglomerativeClustering` with the true $k$ on 300-point synthetic sets.

ARI by linkage. Single wins only on clean, well-separated non-convex shapes and collapses with a little noise; Ward is the best default for compact clusters, especially of unequal spread.

| Dataset | Single | Complete | Average | Ward |
| --- | --- | --- | --- | --- |
| Two moons, noise 0.05 | **1.00** | 0.30 | 0.43 | 0.24 |
| Two moons, noise 0.12 | 0.00 | 0.38 | 0.43 | **0.53** |
| 3 equal blobs | 0.57 | **0.98** | **0.98** | **0.98** |
| 3 blobs, unequal spread (σ = 0.5, 1.5, 1.0) | 0.57 | 0.74 | 0.57 | **0.93** |

**Practical tuning**

- **Default:** Ward on standardized features. It optimizes the same objective as k-means, but needs no seeds and gives every $k$ at once.
- **Non-Euclidean data:** average linkage with `metric="precomputed"` (or cosine, Manhattan). Ward is undefined there.
- **Elongated / manifold clusters:** single linkage — but only after removing noise, or use **HDBSCAN**, which is a robust single linkage.
- **Choosing k:** look for a large jump between consecutive merge heights (here Ward: 1.41 → 2.89 → 4.70 → 8.01), then confirm with silhouette. On the example, silhouette at k = 3 is 0.45 for Ward and 0.40 for single.
- **Images, maps, time series:** pass `connectivity=` (a grid or k-NN graph): clusters stay contiguous and run time drops dramatically.
- **Compare trees:** cophenetic correlation between the tree's cophenetic distances and the original distances — higher means the tree is a more faithful summary (0.28 vs 0.73 here).

> **Single linkage chains through noise:** One line of points across a gap — or a single noise point in it — makes two clusters look connected, because single linkage only needs **one** short link. On noisy two-moons its ARI drops from 1.00 to 0.00: with $k=2$ it splits off **one** stray point as a "cluster" and lumps the other 299 together — just as it isolated I in the worked example.

> **Merges are never undone:** The algorithm is greedy: a merge made at height 1.12 cannot be reconsidered when it turns out to be bad at height 6. Complete linkage nearly merged GH before A+BC (1.13 vs 1.12) — a tiny change in the data can reorder early merges and reshape the whole tree. Check stability by re-running on bootstrap samples, or refine the cut with a few k-means iterations.

> **Scale before you cluster:** Every linkage is built from $d(x,y)$, so a feature measured in thousands dominates one measured in units. Standardize (or choose a metric that makes sense for your data) first. And remember that Ward with a `metric` other than Euclidean is mathematically meaningless — scikit-learn refuses it.

## In code

```python
import numpy as np

def lance_williams(method, ni, nj, nk):
    """Coefficients (alpha_i, alpha_j, beta, gamma) for d(k, i∪j)."""
    if method == "single":   return 0.5, 0.5, 0.0, -0.5
    if method == "complete": return 0.5, 0.5, 0.0, 0.5
    if method == "average":  return ni / (ni + nj), nj / (ni + nj), 0.0, 0.0
    if method == "ward":                      # works on squared distances
        t = ni + nj + nk
        return (ni + nk) / t, (nj + nk) / t, -nk / t, 0.0
    raise ValueError(method)

def agglomerative(X, method="ward"):
    n = len(X)
    D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
    if method == "ward":
        D = D ** 2
    np.fill_diagonal(D, np.inf)
    size = {i: 1 for i in range(n)}           # active cluster id -> size
    row = {i: i for i in range(n)}            # active cluster id -> row of D
    merges = []
    for new in range(n, 2 * n - 1):           # exactly n - 1 merges
        ids = list(size)
        R = [row[c] for c in ids]
        sub = D[np.ix_(R, R)]
        a, b = np.unravel_index(np.argmin(sub), sub.shape)
        i, j = ids[a], ids[b]
        ri, rj = row[i], row[j]
        h = D[ri, rj]
        for k in ids:                         # update row ri to hold d(k, i∪j)
            if k in (i, j):
                continue
            rk = row[k]
            ai, aj, be, ga = lance_williams(method, size[i], size[j], size[k])
            D[ri, rk] = D[rk, ri] = (ai * D[ri, rk] + aj * D[rj, rk]
                                     + be * D[ri, rj] + ga * abs(D[ri, rk] - D[rj, rk]))
        D[rj, :] = D[:, rj] = np.inf          # retire row rj
        merges.append((i, j, np.sqrt(h) if method == "ward" else h))
        size[new] = size.pop(i) + size.pop(j)
        row[new] = ri
    return merges

def cut(merges, n, k):
    """Replay the first n - k merges; return the k groups of point indices."""
    groups = {i: [i] for i in range(n)}
    for t, (i, j, _) in enumerate(merges[: n - k]):
        groups[n + t] = groups.pop(i) + groups.pop(j)
    return sorted(sorted(g) for g in groups.values())

X = np.array([[1, 1], [1.5, 2], [2, 1.2], [3.4, 1.6], [4.8, 1.8],
              [6.2, 1.3], [6.6, 2.4], [7.4, 1.6], [4.2, 4.2]])
names = "ABCDEFGHI"
for method in ["single", "complete", "average", "ward"]:
    merges = agglomerative(X, method)
    heights = " ".join(f"{h:.2f}" for _, _, h in merges)
    groups = ["".join(names[i] for i in g) for g in cut(merges, len(X), 3)]
    print(f"{method:8s} heights: {heights}   k=3: {groups}")
```

From scratch: generic Lance–Williams agglomeration (O(n³), for learning). Prints the merge heights of the worked example and the k = 3 cut.

```text
single   heights: 0.94 1.02 1.13 1.17 1.41 1.46 1.49 2.47   k=3: ['ABCDE', 'FGH', 'I']
complete heights: 0.94 1.12 1.13 1.24 1.41 2.72 4.12 6.43   k=3: ['ABC', 'DEI', 'FGH']
average  heights: 0.94 1.07 1.13 1.20 1.41 2.60 2.97 4.18   k=3: ['ABC', 'DEI', 'FGH']
ward     heights: 0.94 1.11 1.13 1.23 1.41 2.89 4.70 8.01   k=3: ['ABC', 'DEI', 'FGH']
```

Output

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

X = np.array([[1, 1], [1.5, 2], [2, 1.2], [3.4, 1.6], [4.8, 1.8],
              [6.2, 1.3], [6.6, 2.4], [7.4, 1.6], [4.2, 4.2]])
names = np.array(list("ABCDEFGHI"))

for link in ["single", "complete", "average", "ward"]:
    model = AgglomerativeClustering(n_clusters=3, linkage=link,
                                    compute_distances=True).fit(X)
    groups = [''.join(names[model.labels_ == c]) for c in np.unique(model.labels_)]
    coph, _ = cophenet(linkage(X, link), pdist(X))
    print(f"{link:8s} clusters={sorted(groups)}  heights={np.round(model.distances_, 2)}"
          f"  cophenetic r={coph:.2f}")

# A new point: agglomerative clustering has no predict(); use a rule.
x_new = np.array([5.5, 2.0])
ward = AgglomerativeClustering(n_clusters=3, linkage="ward").fit(X)
nearest_member = ward.labels_[np.argmin(np.linalg.norm(X - x_new, axis=1))]
cents = np.array([X[ward.labels_ == c].mean(0) for c in range(3)])
nearest_centroid = np.argmin(np.linalg.norm(cents - x_new, axis=1))
print("1-NN rule  ->", ''.join(names[ward.labels_ == nearest_member]))
print("centroid   ->", ''.join(names[ward.labels_ == nearest_centroid]))
```

scikit-learn on the same points, plus the two rules for placing a new point.

```text
single   clusters=['ABCDE', 'FGH', 'I']  heights=[0.94 1.02 1.13 1.17 1.41 1.46 1.49 2.47]  cophenetic r=0.28
complete clusters=['ABC', 'DEI', 'FGH']  heights=[0.94 1.12 1.13 1.24 1.41 2.72 4.12 6.43]  cophenetic r=0.73
average  clusters=['ABC', 'DEI', 'FGH']  heights=[0.94 1.07 1.13 1.2  1.41 2.6  2.97 4.18]  cophenetic r=0.74
ward     clusters=['ABC', 'DEI', 'FGH']  heights=[0.94 1.11 1.13 1.23 1.41 2.89 4.7  8.01]  cophenetic r=0.73
1-NN rule  -> DEI
centroid   -> FGH
```

Output

> **SciPy for the full tree:** `scipy.cluster.hierarchy.linkage(X, "ward")` returns the whole merge matrix $Z$ (one row per merge: the two cluster ids, the height, the new size); `fcluster(Z, 3, "maxclust")` cuts it and `dendrogram(Z)` draws it. scikit-learn's `AgglomerativeClustering` is the estimator interface; set `distance_threshold` and `n_clusters=None` to get the full tree in `children_` and `distances_`.

**Strengths**

- You do not know $k$, or want clusterings at several scales from one run.
- You only have a dissimilarity matrix (strings, sequences, correlations) — use average or complete linkage.
- You need a deterministic, explainable result: the dendrogram shows exactly why each group formed.
- Clusters must be spatially contiguous (image segments, regions) — add a connectivity graph.

**Limitations**

- $n$ is beyond ~$10^4$–$10^5$ without constraints: the $O(n^2)$ distance matrix does not fit in memory.
- Data are noisy and you planned to use single linkage — chaining will merge clusters through noise.
- You need to cluster new points online: there is no `predict`, and merges cannot be revised.
- Clusters differ in density rather than separation — consider **DBSCAN** or **HDBSCAN**.

- **Phylogenetics:** UPGMA (average linkage) on genetic distances builds species trees; the ultrametric heights are read as divergence times under a molecular-clock assumption.
- **Gene-expression heatmaps:** Rows (genes) and columns (samples) are reordered by average linkage on 1 − correlation, so co-expressed genes appear as blocks next to their dendrogram.
- **Image segmentation:** Ward with a pixel-grid connectivity merges neighbouring pixels into superpixels and regions without crossing object boundaries.
- **Document & customer taxonomies:** Cosine distance with average linkage turns embeddings into a browsable topic or segment hierarchy that analysts can cut at the level they need.

**Question:** Cluster {P, Q} is merged. For another cluster K, d(K, P) = 3 and d(K, Q) = 5. What is d(K, P∪Q) under single, complete and average linkage?

- A. 3, 5, 4
- B. 5, 3, 4
- C. 3, 5, 8
- D. 4, 4, 4

**Answer:** A. 3, 5, 4 — Lance–Williams: single gives $\tfrac12(3+5)-\tfrac12\lvert3-5\rvert=3$ (the min), complete $\tfrac12(3+5)+\tfrac12\cdot2=5$ (the max), average with $n_P=n_Q=1$ gives $\tfrac12\cdot3+\tfrac12\cdot5=4$.

**Question:** Ward's linkage merges two single points that are 2 units apart. By how much does the total within-cluster SSE increase?

- A. 1
- B. 2
- C. 4
- D. √2

**Answer:** B. 2 — $\Delta=\tfrac{1\cdot1}{1+1}\lVert x-y\rVert^2=\tfrac12\cdot4=2$: each point is now 1 unit from the new centroid, contributing $1^2+1^2=2$. The reported height is $\sqrt{2\Delta}=2$, the original distance.

**Question:** In the worked example, why does single linkage cut {A, B, C, D, E} | {F, G, H} | {I} at k = 3 while Ward gives {A, B, C} | {D, E, I} | {F, G, H}?

- A. Single linkage uses squared distances
- B. Single linkage only needs one short link (C–D 1.46, E–F 1.49), so the bridge chains the groups; Ward pays for spreading a cluster out, so absorbing the outlier I into DE is cheapest (Δ = 4.17)
- C. Ward ignores the outlier
- D. They differ only because of floating-point ties

**Answer:** B. Single linkage only needs one short link (C–D 1.46, E–F 1.49), so the bridge chains the groups; Ward pays for spreading a cluster out, so absorbing the outlier I into DE is cheapest (Δ = 4.17) — After merge 5, the smallest single-link distance is ABC–DE = 1.46 (C–D), but the cheapest Ward merge is DE + I with $\Delta=4.17$ versus 8.22 for ABC + DE. The linkage, not the data, decides what the bridge belongs to.

**Question:** Roughly how much memory does the condensed float64 distance matrix need for n = 100,000 points?

- A. 80 MB
- B. 800 MB
- C. 40 GB
- D. 80 GB

**Answer:** C. 40 GB — $n(n-1)/2\approx5\times10^9$ pairs × 8 bytes $\approx 40$ GB. This quadratic memory, not the arithmetic, is what limits plain agglomerative clustering; connectivity constraints or BIRCH-style compression get around it.

**Key points**

- Start from $n$ singletons and make $n-1$ greedy merges of the closest pair; the merge heights form a dendrogram you can cut at any $k$.
- The linkage defines 'closest': single = nearest pair (MST, chains), complete = farthest pair (compact), average = mean pair (UPGMA), Ward = smallest SSE increase.
- Ward's cost is $\Delta=\tfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2$; the costs of all merges sum to the total SSE, so Ward is greedy k-means.
- One Lance–Williams recurrence updates the proximity matrix for every standard linkage in $O(n)$ per merge.
- Memory is $O(n^2)$ and merges are never undone; scale features, prefer Ward or average, avoid single on noisy data, and add connectivity for large or spatial data.

---

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