Hierarchical Agglomerative Clustering

K-Means Clustering makes you commit before you start: how many groups are there? Often you have no idea, and worse, the honest answer is "it depends how closely you look." Two energy names are one group at fine resolution and part of a much larger cyclical bloc at coarse resolution. Both statements are true. Hierarchical clustering refuses to choose — it builds the entire nested family of groupings, from $n$ singletons up to one big blob, and lets you pick the resolution afterwards.

Think of administrative geography. Villages merge into districts, districts into counties, counties into states. Nobody had to declare in advance that the country has exactly seventeen regions; the structure is a tree and you read it at whatever level you need. Agglomerative clustering builds exactly that tree, bottom-up, by a rule so simple it fits in one line: repeatedly merge the two closest clusters.

The algorithm and the one real choice

Start with $n$ clusters, one per point. Compute all pairwise distances. Find the smallest, merge that pair, record the distance at which they merged, and recompute distances from the new cluster to everything else. Repeat $n-1$ times and you are down to one cluster. Plotting each merge as a horizontal bar at its merge height gives a dendrogram.

The only genuine decision is what "distance between two clusters" means once a cluster holds more than one point. That rule is called the linkage:

• Single linkage — the distance between the two closest members. Finds long, stringy shapes; prone to chaining.
• Complete linkage — the distance between the two furthest members. Produces compact, similarly sized clusters.
• Average linkage — the mean over all cross-pairs. A middle course, and the usual default for correlation data.
• Ward linkage — merge whichever pair increases total within-cluster variance least. Behaves much like k-means, but hierarchically.

Worked example 1: four assets

Correlations between four names: $\rho_{AB} = 0.90$, $\rho_{CD} = 0.80$, $\rho_{AC} = 0.30$, $\rho_{AD} = 0.20$, $\rho_{BC} = 0.35$, $\rho_{BD} = 0.25$. Correlation is not a distance, so convert it with the standard transform $d = \sqrt{2(1-\rho)}$, which turns perfect correlation into zero distance and independence into $\sqrt{2}$:

$$d_{AB} = \sqrt{0.20} = 0.447, \quad d_{CD} = \sqrt{0.40} = 0.632$$

and the four cross pairs come out at $d_{AC} = 1.183$, $d_{AD} = 1.265$, $d_{BC} = 1.140$, $d_{BD} = 1.225$.

Merge 1. The smallest entry is $0.447$, so A and B join at height $0.447$. Merge 2. The smallest remaining is $0.632$, so C and D join at height $0.632$. Merge 3. Only two clusters are left. Under complete linkage their distance is the largest cross-pair, $\max(1.183, 1.265, 1.140, 1.225) = 1.265$, so they join there. (Under single linkage the same merge would sit at $1.140$ — the tree's shape is identical here, only its heights move.)

Cut the tree anywhere between $0.632$ and $1.265$ — say at $1.0$ — and you get exactly two clusters, $\{A, B\}$ and $\{C, D\}$. Cut at $0.5$ and you get three: $\{A,B\}$, $\{C\}$, $\{D\}$.

Worked example 2: linkage changes the answer

Five points on a line: $1, 2, 3, 4, 10$.

Under single linkage, $1$ and $2$ merge at distance $1$. The nearest member of $\{1,2\}$ to point $3$ is $2$, one unit away, so $3$ joins at height $1$ as well; then $4$ joins at height $1$ for the same reason. The blob has grown by stepping stones — this is chaining. Finally $10$ joins at $\min(|10-4|) = 6$. Heights: $1, 1, 1, 6$.

Under complete linkage, $1$ and $2$ merge at $1$, and $3$ and $4$ merge at $1$. Now $\{1,2\}$ and $\{3,4\}$ are at $\max(|1-4|, |1-3|, |2-4|, |2-3|) = 3$, while each is $9$ from $10$, so the two pairs merge at $3$ and $10$ joins last at $9$. Heights: $1, 1, 3, 9$.

Cut both trees at height $2$. Single linkage says $\{1,2,3,4\}$ and $\{10\}$; complete linkage says $\{1,2\}$, $\{3,4\}$ and $\{10\}$. Same five numbers, same algorithm, different structure — because the linkage rule is part of the model.

What this means in practice

The headline use in finance is portfolio construction. Hierarchical Risk Parity (López de Prado) clusters assets on correlation distance, reorders the covariance matrix so related names sit adjacent, and allocates down the tree — sidestepping the matrix inversion that makes Pitfalls of Mean-Variance Optimization so fragile. The same dendrogram is also how you discover that the official sector labels disagree with how things actually trade.

Cost is the practical limit: you need the full pairwise distance matrix, which is $O(n^2)$ memory, so a few thousand items is comfortable and a million is not. Below that, hierarchical clustering is usually the more informative first look, because the tree shows you whether there is structure before you commit to a number.