Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Hierarchical Clustering

English · فارسی

Hierarchical Clustering

Computer Science Dept, Ferdowsi University of Mashhad

Where this page sits

Section 14.3.12 of Hastie et al. (2009) (pp. 520-528) is the alternative to choosing KK before you look at the data. Instead of one partition, it builds a nested family of partitions, one per level, and leaves the choice of level to the user - after the structure has been seen.

This page develops the section as it stands: the two paradigms, the dendrogram and what can be read from it, the three linkage rules and the defects of each, the divisive algorithm, and the warnings. An application to colour histograms of images is on the image-clustering page; this page is the method behind it.

What you should be able to do at the end

  • describe agglomerative and divisive clustering and say what each needs from the user;

  • read a dendrogram, cut it, and know what the height means;

  • say what a linkage rule is, write the three standard ones, and name the defect of each;

  • explain why single and complete linkage ignore monotone transformations of the distances while group average does not;

  • compute the cophenetic correlation and say why it is a weak guarantee.

1. Two paradigms

Agglomerative (bottom-up) starts with NN singleton clusters and, at each of the N−1N-1 steps, merges the two clusters with the smallest intergroup dissimilarity. Divisive (top-down) starts with one cluster containing everything and, at each step, splits one existing cluster into two, choosing the split with the largest between-group dissimilarity. Both produce N−1N-1 levels and both can be drawn as a rooted binary tree: the leaves are the observations, each internal node is a merge (or a split), and the root is the whole data set.

The tree becomes a picture when the heights are chosen sensibly. All agglomerative methods, and some divisive ones, are monotone: the dissimilarity at which clusters are merged increases with the level. Then the vertical position of a node can be drawn proportional to its merger value, leaves at zero, and the result is a dendrogram.

What the dendrogram is not is a model of the data. The book devotes a paragraph to the caution (p. 522):

Hierarchical methods impose hierarchical structure whether or not such structure actually exists in the data.

Marginal advice follows: the picture is a description of the clustering the algorithm produced, not of the data itself.

2. What the dendrogram can be trusted for

Cutting the dendrogram horizontally splits the data into the clusters whose branches cross the cut, which is exactly “stop merging when the dissimilarity exceeds a threshold”. A cut gives a partition; all cuts together give the nested family.

Two numbers measure how well the tree represents the dissimilarities it was built from:

  • the cophenetic dissimilarity Cii′C_{ii'} of two observations is the height at which they first join the same cluster;

  • the cophenetic correlation is the correlation between the N(N−1)/2N(N-1)/2 input dissimilarities and their cophenetic counterparts.

A high correlation sounds like validation, and the book explains why it is not. The Cii′C_{ii'} have only N−1N-1 distinct values among N(N−1)/2N(N-1)/2 pairs, so the tree has far fewer degrees of freedom than the matrix; and they must satisfy the ultrametric inequality

Cii′≤max⁡{Cik,Cki′}(14.40)C_{ii'} \le \max\{C_{ik}, C_{ki'}\} \qquad \text{(14.40)}

for every triple. In a Euclidean picture that forces every triangle to be isosceles with the unequal side no longer than the two equal ones - a very special geometry. General dissimilarities are not like that, so the correlation measures how close the tree comes to a shape it is required to have anyway.

3. Linkage: what “distance between two clusters” means

Agglomerative merging needs a dissimilarity between groups, computed from the pairwise dissimilarities between their members. Three rules are standard, with GG and HH two groups:

ruledefinitiontendency
single (SL)dSL(G,H)=min⁡i∈G, i′∈Hdii′d_{SL}(G,H) = \min_{i\in G,\, i'\in H} d_{ii'} (14.41)chaining: long thin clusters
complete (CL)dCL(G,H)=max⁡i∈G, i′∈Hdii′d_{CL}(G,H) = \max_{i\in G,\, i'\in H} d_{ii'} (14.42)compact clusters, may violate closeness
group average (GA)dGA(G,H)=1NGNH∑i∈G∑i′∈Hdii′d_{GA}(G,H) = \frac{1}{N_G N_H}\sum_{i\in G}\sum_{i'\in H} d_{ii'} (14.43)compromise, scale dependent

Each has a characteristic failure, and the failures are dual:

  • Single linkage needs only one small dissimilarity for two groups to be called close, so it happily chains observations through close intermediates. The result is a cluster with a huge diameter DG=max⁡i,i′∈Gdii′D_G = \max_{i,i'\in G} d_{ii'} (14.44), long and thin. This is the classic “chaining” defect.

  • Complete linkage needs all cross-pairs to be small, so it produces compact clusters - and can put an observation in a cluster whose other members are further from it than members of another cluster are. Compact, but not “close”.

  • Group average sits between them, and pays for it in scale invariance: applying a monotone increasing transformation hh to the dissimilarities changes the average, so the result can change. Single and complete use only the ordering of the distances and are invariant under any such hh. The book uses this invariance as an argument in their favour.

There is one more argument, of the kind this course cares about. If each cluster is a sample from a density pkp_k, then dGA(G,H)d_{GA}(G,H) estimates

∬d(x,x′) pG(x) pH(x′) dx dx′,(14.45)\iint d(x,x')\, p_G(x)\, p_H(x')\, dx\, dx', \qquad \text{(14.45)}

a property of the two densities - it converges as N→∞N \to \infty. Single linkage converges to zero and complete linkage to infinity regardless of the densities, so it is unclear what population quantity either estimates.

4. The three trees on one data set

The data below are three groups in the plane plus a bridge of points joining the first two, which is the configuration single linkage was made to fail on.

<Figure size 1200x360 with 3 Axes>

The cophenetic correlation differs across the three panels, and the book’s point is that it does not settle anything: all three trees are valid descriptions of their own merge sequence. What differs is the shape of the answer, and that is visible without any coefficient.

The next cell makes the difference numerical: cut each tree at three clusters and measure the diameter of the widest cluster, and the agreement with the true groups.

   method  ARI vs truth   max diameter  clusters
   single         0.271           9.94         3
 complete         0.581           5.39         3
  average         0.570           4.55         3

Single linkage puts the bridge and both groups it joins into one cluster with a diameter of the order of the whole bridge; complete and average keep the groups compact. On data where the groups are genuinely compact and well separated, all three agree - which is precisely the situation in which the choice does not matter.

5. Scale invariance, checked

The claim is that single and complete depend only on the ordering of the dissimilarities, while group average uses their values. The cell below applies h(d)=d3h(d) = d^3 - strictly increasing, so the ordering is untouched - rebuilds the three trees from the transformed distances, and compares the resulting three-cluster partitions with the untransformed ones.

   method    same partition after d -> d^3    ARI
   single                             True  1.000
 complete                             True  1.000
  average                            False  0.897

Single and complete answer “True”: with the same data and the same ordering, they rebuild exactly the same tree, because min⁡\min and max⁡\max of a monotone function are the monotone function of the min⁡\min and max⁡\max. Group average can answer “False”, and when it does, the reason is that the average of cubes is not the cube of the average: three small distances and one large one trade places.

This is not a curiosity. Distances are often rescaled - to a correlation, to a similarity, to a rank - and the question “does the clustering survive the rescaling?” has a definite answer for two of the three rules and not for the third.

6. Divisive clustering

Top-down clustering has been studied far less. Using K-means with K=2K = 2 at every node is the obvious version, and it inherits the two problems of that method: it depends on a starting configuration, and the sequence of splits need not be monotone, so it cannot be drawn as a proper dendrogram.

The book gives Macnaughton Smith’s algorithm, which avoids both. Start with one group GG containing everything. Take the observation whose average dissimilarity from the others is largest, and make it the first member of a second group HH. Then repeatedly move to HH the observation of GG for which

(average dissimilarity to H)−(average dissimilarity to the rest of G)\text{(average dissimilarity to } H) - \text{(average dissimilarity to the rest of } G)

is largest, stopping when that difference turns negative. The result is a split into two groups; apply it recursively, choosing at each level the cluster with the largest diameter (14.44) to split next.

K = 2: cluster sizes [17, 16], ARI with the true groups -0.048
K = 3: cluster sizes [16, 9, 8], ARI with the true groups -0.071

The split sequence is nested by construction - level K+1K+1 refines level KK - which is exactly what K-means cannot promise, and what makes the tumour example prefer a hierarchical answer.

The ARI printed above is the second warning of the section in practice: on this data the first split runs across the groups, so nesting guarantees that the levels refine each other and says nothing about whether any level is right. A hierarchy is a structure the procedure always produces; a useful hierarchy is a property of the data.

7. Ordering the observations

Because the leaves of a dendrogram can be flipped at every internal node, the tree fixes a partial order at best. The book adds a rule (S-PLUS’s default: at each merge, put the tighter subtree to the left) and uses it to order both axes of the expression matrix, producing Figure 14.14. The ordering turns a table into a picture: neighbouring columns are similar samples, neighbouring rows are genes that behave alike, and blocks become visible.

Summary

  • Agglomerative clustering merges the closest pair 199 times; divisive clustering splits the most heterogeneous group. Both give a nested family, not one partition.

  • The dendrogram is readable because merger heights are monotone; the horizontal cut chooses KK after the fact.

  • Single linkage chains, complete linkage gives compact but not necessarily close clusters, group average is the compromise that depends on the scale of the distances.

  • The cophenetic correlation measures how tree-like the dissimilarities are, and the ultrametric inequality says how restrictive “tree-like” is.

  • K-means with different KK does not give a nested family; hierarchical clustering does, and that is why the book prefers it for the microarray data.

Exercises

  1. Cut each of the three trees at four clusters and recompute the table of ARI and diameters. Which method is stable under the change of KK?

  2. Remove the bridge from the data and rerun the comparison. Does single linkage still fail?

  3. Verify the ultrametric inequality for a small tree by computing all cophenetic distances with cophenet. Find a triple where the inequality is tight.

  4. Build a data set where group average changes its partition under h(d)=d3h(d) = d^3, and explain which average moved.

  5. Implement the divisive algorithm with K-means (K=2K=2) instead of Macnaughton Smith and check monotonicity of the split heights. Does it ever decrease?

  6. Cluster the iris data with the three linkages, cut at three clusters, and compare with the species labels. Which rule finds setosa first?

Sources

  • The two paradigms, the dendrogram, the cophenetic correlation, (14.40)-(14.45), the Macnaughton Smith algorithm and Figure 14.14: §14.3.12 of Hastie et al. (2009), pp. 520-528.

  • The application to image histograms, which reuses the same scipy functions: Image-Clustering-Hierarchical.

  • The superiority of a nested family for the tumour data: Tumor-Microarray-Example, §14.3.8.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7