Hierarchical Clustering (Dendrogram)

Clustering without choosing k first

K-means needs the number of clusters in advance. Hierarchical clustering does not: it builds a whole tree of clusters, from single points up to one big cluster, and you pick the number afterwards.

The usual version is agglomerative (bottom-up):

start with every point as its own cluster
repeat until one cluster is left:
    find the two closest clusters
    merge them, and record the merge and its distance

The record is drawn as a dendrogram: leaves at the bottom, and a join for every merge at the height of its distance.

What does “closest clusters” mean?

The distance between two points is clear, but between two groups of points it needs a rule, the linkage:

Linkage	Distance between clusters	Tends to give
Single	the closest pair of points	long chains; sensitive to noise points between groups
Complete	the farthest pair of points	compact, round clusters of similar size
Average (UPGMA)	the mean over all pairs	something in between
Ward	the increase in total within-cluster variance	compact clusters, similar to k-means

The example

Eleven points: a group at the bottom left (A, B, C, D), one at the bottom right (E, F, G), one at the top (H, I, J), and K in between the bottom-left and the top group.

The first merges are the same for every linkage, because for two single points all linkages agree: B–D at 1.02, then E–G at 1.166. Then they differ:

Linkage	Merge heights (in order)
Single	1.02, 1.166, 1.204, 1.342, 1.414, 1.442, 1.526, 2.163, 2.608, 4.669
Complete	1.02, 1.166, 1.342, 1.612, 1.628, 1.931, 2.28, 4.0, 7.612, 8.497
Average	1.02, 1.166, 1.342, 1.513, 1.628, 1.729, 1.768, 3.367, 5.895, 6.386

The heights only go up in each list. A merged cluster is never closer to anything than its parts were, so the dendrogram has no crossings (with these three linkages).

Where does K go?

• Single linkage: K is only 2.163 from D, so it joins the bottom-left group. Then the closest pair between {A, B, C, D, K} and {H, I, J} is K–H, only 2.608 apart, so the top group joins too, before the right group. One point in between was enough to chain two groups together.
• Complete linkage: what counts is the farthest member. The farthest point of the top group (I) is 4.0 from K, but the farthest point of the bottom-left group (A) is 4.30 away. So K joins the top group (at 4.0), and the two bottom groups merge before that cluster joins them.

Cut both trees into 2 clusters and you get completely different answers:

Linkage	2 clusters
Single	{A, B, C, D, H, I, J, K} and {E, F, G}
Complete	{A, B, C, D, E, F, G} and {H, I, J, K}

Neither is “wrong”. The linkage is part of the definition of a cluster, so choose it to match what you want.

Cutting the dendrogram

To get k clusters, draw a horizontal line through the dendrogram so that it crosses k vertical lines; everything below each crossing is one cluster. Equivalently, stop the merging after n − k merges. A good place to cut is a long gap between two consecutive merge heights: those clusters stayed apart for a long time. In the single-linkage tree, the biggest gap (2.608 to 4.669) suggests 2 clusters; in the complete-linkage tree, the biggest gap (4.0 to 7.612) suggests 3.

Hierarchical clustering versus k-means

	Hierarchical (agglomerative)	K-means
Number of clusters	chosen afterwards, by cutting	must be given in advance
Result	a whole tree (dendrogram)	one flat partition
Deterministic	yes	no, depends on the random start
Cluster shapes	depends on linkage (single: any shape)	round, similar size
Cost	O(n²) memory, O(n² log n) to O(n³) time	O(n · k · iterations)

Single linkage is closely related to the minimum spanning tree: its merges are exactly the edges that Kruskal’s algorithm adds, in the same order.

Code

import math

POINTS = {'A': (1.0, 1.5), 'B': (1.8, 2.4), 'C': (2.6, 1.2), 'D': (2.0, 3.4),
          'E': (7.2, 2.0), 'F': (8.5, 2.8), 'G': (7.8, 1.0),
          'H': (4.6, 7.4), 'I': (5.6, 8.4), 'J': (4.0, 8.6), 'K': (3.2, 5.2)}

def d(a, b):
    (x1, y1), (x2, y2) = POINTS[a], POINTS[b]
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

LINKAGE = {
    'single':   lambda c1, c2: min(d(a, b) for a in c1 for b in c2),      # closest pair
    'complete': lambda c1, c2: max(d(a, b) for a in c1 for b in c2),      # farthest pair
    'average':  lambda c1, c2: sum(d(a, b) for a in c1 for b in c2) / (len(c1) * len(c2)),
}

def agglomerate(kind):
    """Merge the two closest clusters until one is left. Returns the merges as (cluster, cluster, height)."""
    clusters = {p: [p] for p in POINTS}
    merges = []
    while len(clusters) > 1:
        keys = sorted(clusters)
        dist, a, b = min((LINKAGE[kind](clusters[a], clusters[b]), a, b)
                         for i, a in enumerate(keys) for b in keys[i + 1:])
        clusters[a + b] = clusters.pop(a) + clusters.pop(b)
        merges.append((a, b, round(dist, 3)))
    return merges

def cut(merges, k):
    """Undo the last k - 1 merges: the clusters that exist after len(POINTS) - k merges."""
    clusters = {p: [p] for p in POINTS}
    for a, b, _ in merges[:len(POINTS) - k]:
        clusters[a + b] = clusters.pop(a) + clusters.pop(b)
    return sorted(sorted(c) for c in clusters.values())

for kind in LINKAGE:
    merges = agglomerate(kind)
    print(kind, [h for _, _, h in merges])
    print('   last merges:', merges[-3:])
    print('   2 clusters:', cut(merges, 2))
# single [1.02, 1.166, 1.204, 1.342, 1.414, 1.442, 1.526, 2.163, 2.608, 4.669]
#    last merges: [('ABDC', 'K', 2.163), ('ABDCK', 'HJI', 2.608), ('ABDCKHJI', 'EGF', 4.669)]
#    2 clusters: [['A', 'B', 'C', 'D', 'H', 'I', 'J', 'K'], ['E', 'F', 'G']]
# complete [1.02, 1.166, 1.342, 1.612, 1.628, 1.931, 2.28, 4.0, 7.612, 8.497]
#    last merges: [('HJI', 'K', 4.0), ('ACBD', 'EGF', 7.612), ('ACBDEGF', 'HJIK', 8.497)]
#    2 clusters: [['A', 'B', 'C', 'D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K']]
# average [1.02, 1.166, 1.342, 1.513, 1.628, 1.729, 1.768, 3.367, 5.895, 6.386]
#    last merges: [('HJI', 'K', 3.367), ('ACBD', 'HJIK', 5.895), ('ACBDHJIK', 'EGF', 6.386)]
#    2 clusters: [['A', 'B', 'C', 'D', 'H', 'I', 'J', 'K'], ['E', 'F', 'G']]

The same heights come out of scipy.cluster.hierarchy.linkage(points, method='single') (or 'complete', 'average'), and scipy.cluster.hierarchy.dendrogram draws the tree.

Common mistakes

• Reading the leaf order as meaningful. Leaves can be swapped at every join without changing the tree. Only the heights of the joins carry information.
• Using centroid distance and expecting single linkage. Each linkage defines cluster distance differently, and gives different trees.
• Forgetting to scale features. Like every distance-based method, hierarchical clustering is dominated by the feature with the largest range.
• Cutting at a fixed number without looking. The dendrogram shows where the big gaps are; use them.
• Running it on huge data sets. The O(n²) distance matrix becomes too large. Use k-means or a sampling approach instead.