Hierarchical Clustering in Data Mining

Hierarchical clustering is an unsupervised technique that groups similar data points into clusters, but it does something the more familiar partitioning methods (like k-means) do not: instead of producing one flat set of groups, it builds an entire tree of groupings, from every point alone at the bottom to every point together at the top. That tree is called a dendrogram, and it is the reason hierarchical clustering is chosen over simpler methods whenever the right number of clusters is itself unknown.

Why Build a Tree Instead of Just Picking Groups?

Partitioning methods like k-means require you to decide the number of clusters, k, before the algorithm runs. That is a real limitation: on a genuinely unfamiliar dataset, nobody knows in advance whether the natural grouping is into three segments or eight.

Hierarchical clustering sidesteps the problem by refusing to commit to a single number of clusters at all. It computes the entire sequence of groupings — every possible number of clusters from 1 to n, all in one run — and represents that sequence as a tree. Deciding "how many clusters" becomes a matter of choosing where to slice the tree afterward, with the full picture in front of you, rather than a guess you have to make before seeing any results.

The Two Directions: Agglomerative and Divisive

Hierarchical clustering runs in one of two directions.

Agglomerative (bottom-up) starts with every data point as its own cluster and repeatedly merges the two closest clusters, one merge at a time, until only one cluster containing everything remains. This is also called AGNES (Agglomerative Nesting), and it is by far the more commonly used of the two, mainly because merging two clusters is computationally simpler than deciding how to split one.

Divisive (top-down) starts with all data in a single cluster and repeatedly splits it into smaller clusters based on dissimilarity, continuing until every point is its own cluster or a target number of clusters is reached. Divisive clustering is used less often because deciding where to split a cluster is a harder combinatorial problem than deciding which two clusters to merge.

Agglomerative Clustering: A Worked Example With Real Numbers

Understanding the algorithm's mechanics requires an example with actual numbers, not just labeled points merging in an unexplained order — the "distance" that drives every merge has to be defined, and how it is defined changes the result.

Take five customers, described by a single feature — their spend in hundreds of rupees — so the distances are easy to verify by hand:

Customer:  A    B    C    D    E
Spend  :   2    3    9    19   21

The pairwise distance matrix (simple absolute difference, since this is one dimension) is:

      A    B    C    D    E
A     0    1    7    17   19
B     1    0    6    16   18
C     7    6    0    10   12
D    17   16   10    0    2
E    19   18   12    2    0

The algorithm's steps, exactly as it runs:

1. Every point starts as its own cluster: (A), (B), (C), (D), (E).

2. Find the two closest clusters and merge them. The smallest number in the matrix is 1, between A and B. Merge: (AB), (C), (D), (E).

3. Recompute distances involving the new cluster, and merge again. The next smallest distance is 2, between D and E — untouched by the previous merge. Merge: (AB), (C), (DE).

4. Continue merging the closest remaining pair. Now C must be compared against the cluster (AB), not against A and B separately. This is where the choice of linkage criterion — how to define the distance between two clusters, as opposed to two points — starts to matter, and different choices from here onward produce different trees from the same data.

Linkage Criteria: Why the Same Data Can Give Different Trees

Single linkage defines the distance between two clusters as the distance between their closest pair of points. Comparing C to (AB): distance(C,A)=7, distance(C,B)=6, so single linkage uses the minimum, 6. Comparing (DE) to (AB) would use distance(D,A)=17 vs distance(E,B)=18, again taking the minimum.

Complete linkage defines cluster distance as the distance between their farthest pair of points. Comparing C to (AB): the maximum of 7 and 6 is 7 — one unit more than single linkage gave.

Continuing single linkage on this data: C joins (AB) at distance 6, giving (ABC); then (ABC) merges with (DE) at distance 10 (the smallest cross-cluster point-pair distance, C–D). The final merge distance is 10.

Continuing complete linkage instead: C joins (AB) at distance 7; then (ABC) merges with (DE) at distance 19 (the single farthest pair, A–E). The final merge distance is 19.

Same five points, same first two merges — but the third and fourth merge distances differ (6 vs 7, then 10 vs 19), because the two linkage rules disagree about what "distance between clusters" means once a cluster contains more than one point. A third common choice, average linkage, would use the mean of all point-pair distances between the two clusters, landing somewhere between the single- and complete-linkage figures. A fourth, Ward's method, does not use point-pair distances at all — it merges whichever pair of clusters causes the smallest increase in total within-cluster variance, which tends to produce more evenly sized clusters than the other three.

This is the detail that most introductions to hierarchical clustering skip, and it matters in practice: two analysts running "hierarchical clustering" on identical data, with different linkage settings, can get genuinely different dendrograms, and neither is simply wrong. The linkage choice has to be reported alongside the result.

Reading the Dendrogram

The merge sequence above is exactly what a dendrogram plots: each merge becomes a horizontal line connecting the two merging branches, drawn at a height equal to the merge distance. Points that merge early (A and B, at distance 1) sit low in the tree, joined by a short branch; points that only merge at the very end (the full ABC group joining DE, at distance 10 or 19 depending on linkage) sit at the top, joined by a tall branch.

Choosing a number of clusters means drawing a horizontal line across the dendrogram at some height and counting how many vertical branches it crosses. Draw the line just above height 2 in the single-linkage tree, and it crosses three branches — (AB), (C), (DE) — giving three clusters. Draw it above height 6, and it crosses two — (ABC) and (DE). The dendrogram's real value is that this decision can be made visually, after seeing how far apart the natural groupings are, rather than committed to blindly in advance.

Divisive Hierarchical Clustering

Divisive clustering inverts this process:

• All data points start in a single cluster.
• The algorithm splits the cluster into two based on dissimilarity — often by first finding the most dissimilar point or sub-group and separating it out, then repeating within each resulting piece.
• Splitting continues until every point is isolated, or a target number of clusters is reached.

The result is still a dendrogram, read the same way — it is simply built by cutting from the top down instead of merging from the bottom up. It is used less often in practice mainly because evaluating every possible way to split a cluster into two is far more computationally expensive than evaluating every pair available to merge.

What the Irreversibility of Merging Actually Costs

Every merge or split made by hierarchical clustering is permanent: once C has been merged into (AB), no later step can un-merge it, even if a subsequent point turns out to be a better match for C than A or B are. This is a real limitation, not just a technical footnote — it means a single early mistake, caused by an outlier or a noisy measurement, propagates through every later merge and cannot be corrected by anything the algorithm does afterward. K-means, in contrast, reassigns points between clusters at every iteration and can recover from a bad initial assignment; hierarchical clustering cannot.

This same greediness is also what makes hierarchical clustering sensitive to noise and outliers. A single unusual point sitting between two otherwise well-separated groups can create a low-distance bridge that causes them to merge earlier than their real structure would suggest — a failure mode single linkage is particularly prone to, since it only needs the closest pair of points, not the whole clusters, to be near each other.

Where Hierarchical Clustering Fits

Hierarchical clustering is well suited to smaller-to-medium datasets where the natural number of groups is unknown and where a visual, explorable structure — the dendrogram itself — is valuable to whoever will interpret the result, such as in biological taxonomy (which is historically where the technique originated, in classifying species by similarity) or in exploratory customer segmentation. It becomes impractical on very large datasets, because computing and updating the full distance matrix at every merge step scales quadratically with the number of points, and because clusters of very different sizes or shapes are harder for it to separate cleanly than they are for density-based methods.