Hierarchical clustering

Prerequisites

• k-means, for comparison.
• Distances between points.
• Binary trees: a dendrogram is one.

The analogy

How it works

Linkage: the distance between two clusters must be defined: single linkage uses the closest pair of members, complete the farthest pair, average the mean of all pairs.

Start with the merges by hand

Points A = 1, B = 2, C = 6, D = 8, single linkage. Predict, then open "Check".

Finish the picture: a different linkage

Same points, complete linkage (farthest pair).

• The first two merges. Predict them.
  Check

  Still A–B at 1 and C–D at 2: for single points, all linkages agree.

• The final merge height. Predict it.
  Check

  The farthest members are A = 1 and D = 8: height 7 instead of 4. Complete linkage gives tighter, rounder clusters; single linkage can chain long thin groups.

Full worked calculation

Four points on a line, A = 0, B = 1, C = 5, D = 7, clustered bottom-up twice: once with single linkage (closest pair) and once with complete linkage (farthest pair). Every distance-matrix update is shown.

1. 1Start: every point is its own cluster

   $$\{A\}, \{B\}, \{C\}, \{D\} \qquad \text{smallest distance: } d(A, B) = 1$$

   The distance matrix above holds all $\binom{4}{2} = 6$ pairwise distances. Agglomerative clustering always merges the two closest clusters first, here A and B.

2. 2Single linkage: update the matrix

   $$d(\{AB\}, C) = \min(5, 4) = 4, \qquad d(\{AB\}, D) = \min(7, 6) = 6, \qquad d(C, D) = 2$$

   With single linkage, the distance between two clusters is the distance between their closest members. The row for A and the row for B collapse into one row by taking the minimum.

3. 3Single linkage: second merge

   $$\min(4, 6, 2) = 2 \;\Rightarrow\; \text{merge } C \text{ and } D \text{ at height } 2$$

   The smallest entry is now C–D. We record the height (2) at which they join: it becomes the height of that branch in the dendrogram.

4. 4Single linkage: last merge

   $$d(\{AB\}, \{CD\}) = \min(4, 6, 5, 7) = 4 \;\Rightarrow\; \text{merge at height } 4$$

   Only two clusters remain, so they merge. The dendrogram heights are 1, 2, 4.

5. 5Complete linkage: same start, different update

   $$d(\{AB\}, C) = \max(5, 4) = 5, \qquad d(\{AB\}, D) = \max(7, 6) = 7$$

   Complete linkage uses the farthest members, so the merged row takes the maximum. The first two merges (AB at 1, CD at 2) are the same as before.

6. 6Complete linkage: last merge

   $$d(\{AB\}, \{CD\}) = \max(4, 6, 5, 7) = 7 \;\Rightarrow\; \text{merge at height } 7$$

   The final merge happens much higher (7 instead of 4) because complete linkage measures the full width of the combined cluster: from A at 0 to D at 7.

7. 7Cut the dendrogram

   $$\text{cut at height } 3: \; \{A, B\}, \{C, D\} \qquad \text{cut at height } 1.5: \; \{A, B\}, \{C\}, \{D\}$$

   You choose the number of clusters after the fact by drawing a horizontal line through the tree. A big gap between merge heights (2 to 7 here) signals a natural number of clusters, 2.

The rule in plain words

Start with every point as its own cluster. Repeatedly merge the two clusters with the smallest linkage distance, recording the merge height, until one cluster is left.

Cut the dendrogram at a chosen height (or where the gap between merges is largest) to get the clusters.

The code

Read this code after you have done the merges by hand. It will make more sense.

double single_link(double a[], int na, double b[], int nb) {     /* closest pair */
    double best = INFINITY;
    for (int i = 0; i < na; i++)
        for (int j = 0; j < nb; j++)
            if (fabs(a[i] - b[j]) < best) best = fabs(a[i] - b[j]);
    return best;
}

double complete_link(double a[], int na, double b[], int nb) {   /* farthest pair */
    double worst = 0;
    for (int i = 0; i < na; i++)
        for (int j = 0; j < nb; j++)
            if (fabs(a[i] - b[j]) > worst) worst = fabs(a[i] - b[j]);
    return worst;
}

flowchart TD
  A["each point is its own cluster"] --> B["compute linkage distances between clusters"]
  B --> C["merge the closest two, record the height"]
  C --> D{"only one cluster left?"}
  D -->|no| B
  D -->|yes| E["cut the dendrogram to get k clusters"]
          

How costly is it?

The two most common linkages between clusters $P$ and $Q$:

Best for: small to medium datasets where you want to see the structure at every scale, such as gene expression or taxonomies.

• Pro: No need to choose $k$ in advance; the dendrogram shows all levels.
• Pro: Works with any distance measure and gives an interpretable tree.
• Con: $O(n^2)$ memory and $O(n^2)$–$O(n^3)$ time: too slow for very large datasets.
• Con: Merges are never undone, so an early bad merge stays; results depend on the linkage.

Common mistakes

• Mixing up single (minimum) and complete (maximum) linkage.
• Forgetting to update the distance matrix after each merge.
• Reading the horizontal order of leaves as meaningful; only the heights matter.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• No $k$ is needed upfront because the dendrogram contains every number of clusters at once.
• Merge heights show strength of grouping because they record the distance at which clusters joined.
• It needs $n - 1$ merges because each merge reduces the number of clusters by one.
• Linkage changes the result because it defines what "closest clusters" means.
• It scales poorly because it needs distances between all pairs of points.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is hierarchical clustering like building a family tree from the bottom up?
   Sample answer

   The closest relatives are joined first, then larger branches, until everyone is in one family, and the tree records the order.

2. Do single-linkage clustering on A = 1, B = 2, C = 6, D = 8.
   Sample answer

   Merge A–B at 1, C–D at 2, then the two groups at 4 (closest members B and C).

3. Why does single_link start best at INFINITY?

   A good answer says what the first comparison does.

   Sample answer

   So the first pair's distance is always smaller and becomes the starting minimum; any finite start could be smaller than every real distance.

4. So what is agglomerative hierarchical clustering, in one sentence?
   Sample answer

   A method that repeatedly merges the two closest clusters, starting from single points, and records the merges as a dendrogram.

5. Why does the final merge height differ between single and complete linkage?

   A good answer uses the A, B, C, D numbers.

   Sample answer

   Single linkage uses the closest members, B and C, distance 4; complete linkage uses the farthest, A and D, distance 7.

6. What does hierarchical clustering cost?
   Sample answer

   $O(n^2)$ memory for distances and $O(n^2)$ to $O(n^3)$ time depending on the algorithm.

7. Give two pros and two cons.
   Sample answer

   Pros: no need to pick $k$, and an interpretable dendrogram with any distance. Cons: slow and memory-hungry on large data, and merges can't be undone.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the complexity and Ward's method. I'd keep the family-tree analogy, the four-point merges, the dendrogram cut, and "merge the closest, cut where you like".

External resources

• scikit-learn: Hierarchical clustering: linkages and dendrogram examples.
• Wikipedia: Hierarchical clustering: linkage criteria and complexity.
• SciPy: dendrogram: drawing dendrograms in Python.

Videos

• YouTube search: StatQuest hierarchical clustering: StatQuest with a heatmap example.