esc
  • WorkflowsPages
  • Case studiesPages
  • Machine Learning FoundationsLearn
  • AI EngineeringLearn
  • AI Guardrails & Red TeamingLearn
  • UI/UXLearn
  • Design SystemsLearn
  • Production System DesignLearn
  • Book a callContact
  • Download ResumeContact
Let’s talk

I’ll build the agent for it.

Machine Learning Foundations / Core / 02.34

Hierarchical clustering: groups in groups

Some groups sit inside bigger groups, like folders in folders. Learn to build that tree by merging, then cut it where you like.

13 min readFree

Groups inside groups

The last lesson let a point belong to several groups at once. This one asks a different question: what if the groups themselves are nested? Think of a family tree. You have your own family. That family sits inside a wider set of cousins, which sits inside a whole clan. A supermarket works the same way: a shelf of pasta sits inside the dry-food aisle, which sits inside the store.

Hierarchical clustering finds that kind of nesting by itself. Scikit-learn's guide calls it a general family of clustering algorithms that build nested clusters by merging or splitting them successively.

Key words

Hierarchy
Groups arranged in levels, with small groups inside bigger ones.
Agglomerative
Bottom-up. Start with every point alone, then keep joining the closest groups.
Divisive
Top-down. Start with everything in one group, then keep splitting it.
Linkage
The rule for measuring how far apart two groups are.
Dendrogram
A tree diagram that shows which groups joined, and at what distance.
Cut
Slicing the tree at one height to get a flat set of groups.

Bottom-up or top-down

There are two ways to grow the tree. Wikipedia says strategies for hierarchical clustering generally fall into two categories.

Agglomerative is the bottom-up way. It begins with each data point as an individual cluster. At each step it merges the two most similar clusters, and it goes on until all points sit in a single cluster. Picture a disco where everyone starts alone. The closest two pair up, then pairs join pairs, until the room is one crowd.

Divisive is the top-down way. It starts with all points in a single cluster and splits it into smaller ones.

Wikipedia notes that in general the merges and splits are decided in a greedy manner. Greedy means each step picks whatever looks best right now, and never goes back to change an earlier choice. It also says agglomerative methods are more commonly used, and divisive ones are less common. So this lesson builds the agglomerative kind.

Tip

Wikipedia points out a nice bonus: any valid measure of distance can be used. The method does not even need the original measurements, only a table of how far apart each pair is.

The merge loop

The whole method is a short loop. Imagine eight friends scattered over a park, and you want to know who forms natural circles.

  1. 1

    1. Start alone

    Every point is its own group. Eight points means eight groups.

  2. 2

    2. Measure

    Work out how far apart each pair of groups is.

  3. 3

    3. Merge

    Join the two closest groups into one, and write down the distance at which they joined.

  4. 4

    4. Repeat

    Measure again with the new group in the mix and merge the next closest pair. Stop when only one group is left.

You end up with a record of every merge, in order, each with its distance. That record is the tree. Scikit-learn describes it this way: the root of the tree is the unique cluster that gathers all the samples, the leaves being the clusters with only one sample.

One catch is hiding in step 2. Measuring the distance between two single points is easy. But after a merge, a group holds several points. How far is a group from a point, or from another group? That is what linkage decides.

Linkage: how far apart are two groups?

Wikipedia says the linkage criterion determines how dissimilarity between sets of observations is computed. Between two crowds, you could measure the gap between the nearest people, the furthest people, or something in the middle.

  • Single

    The distance of the closest pair, one from each group. It is like two crowds linked by a single pair of friends holding hands. Wikipedia says it can handle clusters of arbitrary shape, but is highly sensitive to noise, because a single pair of close points is enough to merge two clusters.

  • Complete

    The distance of the furthest pair. Two groups count as close only if everyone in them is fairly close. Wikipedia says it is less susceptible to noise than single linkage, but is biased toward globular clusters of similar size and may break apart large ones.

  • Average

    The mean distance over every pair, one point from each group. It sits between the other two, so one oddball pair cannot decide everything.

d(A,B)=1∣A∣⋅∣B∣∑x∈A∑y∈Bd(x,y)d(A, B) = \frac{1}{|A| \cdot |B|} \sum_{x \in A} \sum_{y \in B} d(x, y)

In words: line up every pair made of one point from group A and one from group B. Add up all their distances, then divide by the number of pairs. That is average linkage, as Wikipedia writes it.

Ward is the fourth choice, and it works differently. It does not measure a gap. It asks: which merge makes the groups least messy? Wikipedia says Ward's minimum variance criterion minimizes the total within-cluster variance, and that at each step you find the pair of clusters that leads to the minimum increase in total within-cluster variance after merging. Variance is a number for how spread out a group is. Scikit-learn adds that Ward is similar to the k-means objective, tackled in a bottom-up way.

Scikit-learn also warns about a "rich get richer" behavior that leads to uneven cluster sizes. In its words, single linkage is the worst strategy for this, and Ward gives the most regular sizes. But Ward cannot be used with other distance measures, so for those average linkage is a good alternative.

Let us make the three gap-measuring rules concrete. Below are two small groups of points, A, B, C and D, E, F. The code measures all nine pairs between them and prints the closest, the furthest and the mean.

Python
import math

points = {
    "A": (1.0, 1.0), "B": (1.6, 2.1), "C": (2.3, 1.4),
    "D": (5.0, 5.0), "E": (5.9, 5.8), "F": (6.4, 4.7),
}
left, right = ["A", "B", "C"], ["D", "E", "F"]

# every distance between one point on the left and one on the right
pairs = [math.dist(points[p], points[q]) for p in left for q in right]

print("pairs measured:", len(pairs))
print("single   (closest pair):   ", round(min(pairs), 2))
print("complete (furthest pair):  ", round(max(pairs), 2))
print("average  (mean of pairs):  ", round(sum(pairs) / len(pairs), 2))

Output

pairs measured: 9
single   (closest pair):    4.47
complete (furthest pair):   6.86
average  (mean of pairs):   5.57

The same two groups are 4.47 apart by single linkage, 6.86 by complete linkage and 5.57 by average linkage. Keep 5.57 in mind, because it comes back in the worked example.

Quick check

Two crowds are joined by one thin bridge of people between them. Which linkage is most likely to merge them into one group early?

Build it from scratch

Now the whole loop in plain Python, with average linkage. We use eight made-up points with names A to H. Each is a spot on a map, given as an x and a y. The shapes were set up so we know the answer: A, B, C live in one corner, D, E, F in the middle, and G, H far away on the right.

The code does four things. It merges until one group is left, printing each merge with its distance. It then cuts the tree at height 7.0 and at height 3.0. Last, it draws a tiny text dendrogram. A line starting with + is a merge, with the distance at which it happened. A line starting with - is a single point. The deeper a line is indented, the earlier that join happened.

Python
import math
from itertools import combinations

# 8 made-up points on a map: (x, y), each with a name.
points = {
    "A": (1.0, 1.0), "B": (1.6, 2.1), "C": (2.3, 1.4),
    "D": (5.0, 5.0), "E": (5.9, 5.8), "F": (6.4, 4.7),
    "G": (11.0, 1.5), "H": (11.7, 2.9),
}

def dist(p, q):
    return math.dist(points[p], points[q])

def average_link(c1, c2):
    # the mean distance over every pair: one point from each cluster
    pairs = [dist(p, q) for p in c1 for q in c2]
    return sum(pairs) / len(pairs)

clusters = [(name,) for name in points]   # start: every point alone
merges = []                               # (distance, left group, right group)
while len(clusters) > 1:
    # find the closest pair of clusters
    a, b = min(combinations(clusters, 2), key=lambda pair: average_link(*pair))
    height = average_link(a, b)
    clusters.remove(a)
    clusters.remove(b)
    clusters.append(a + b)
    merges.append((height, a, b))
    print(f"merge {len(merges)}: {'+'.join(a)} and {'+'.join(b)} at distance {height:.2f}")

def cut(height):
    # replay only the merges that happened at or below this height
    groups = [(name,) for name in points]
    for h, a, b in merges:
        if h <= height:
            groups.remove(a)
            groups.remove(b)
            groups.append(a + b)
    return sorted(groups)

print()
for h in (7.0, 3.0):
    groups = cut(h)
    print(f"cut at height {h}: {len(groups)} groups")
    for g in groups:
        print("   ", " ".join(sorted(g)))

# A tiny text dendrogram: each line shows a merge, indented by how late it happened.
tree = {(name,): name for name in points}
for h, a, b in merges:
    tree[a + b] = (h, tree[a], tree[b])

def draw(node, depth=0):
    pad = "  " * depth
    if isinstance(node, str):
        print(pad + "- " + node)
    else:
        print(f"{pad}+ joined at {node[0]:.2f}")
        draw(node[1], depth + 1)
        draw(node[2], depth + 1)

print()
draw(tree[tuple(clusters[0])])

Output

merge 1: B and C at distance 0.99
merge 2: D and E at distance 1.20
merge 3: A and B+C at distance 1.31
merge 4: F and D+E at distance 1.32
merge 5: G and H at distance 1.57
merge 6: A+B+C and F+D+E at distance 5.57
merge 7: G+H and A+B+C+F+D+E at distance 8.08

cut at height 7.0: 2 groups
    A B C D E F
    G H
cut at height 3.0: 3 groups
    A B C
    D E F
    G H

+ joined at 8.08
  + joined at 1.57
    - G
    - H
  + joined at 5.57
    + joined at 1.31
      - A
      + joined at 0.99
        - B
        - C
    + joined at 1.32
      - F
      + joined at 1.20
        - D
        - E

Read the merges from the top. Merge 1 joins B and C at 0.99, the closest pair in the data. D and E follow at 1.20. Then A joins B and C at 1.31, and F joins D and E at 1.32. Merge 5 pairs G and H at 1.57. So by merge 5 we hold three tidy groups: A B C, D E F and G H.

Then the distances jump. Merge 6 joins A+B+C with D+E+F at 5.57, which matches the average-linkage figure from the earlier code. The last merge brings in G and H at 8.08. The first five merges all happened below 1.6. The last two happened far higher. That jump is the story: three groups are real, and they are far from each other.

The dendrogram

The text tree at the bottom of the output is a very small dendrogram. Wikipedia says the name comes from two ancient Greek words meaning "tree" and "drawing".

Wikipedia gives the exact rule: the height of each node in the plot is proportional to the value of the intergroup dissimilarity between its two daughters. In plain words, a join drawn low means two close things. A join drawn high means two far things.

Scikit-learn adds that visual inspection can often be useful for understanding the structure of the data, though more so in the case of small sample sizes.

Tip

Read a dendrogram from the bottom up, like the algorithm did. Look for long vertical lines with nothing joining along them. They mean groups that stayed apart for a long stretch of distance.

Cutting the tree: you choose k later

Here is the nicest part. With k-means you had to pick k before starting. With hierarchical clustering you build the whole tree first and choose after. Wikipedia says the number of clusters is not determined automatically and must be chosen by analyzing the dendrogram. A common approach is to cut the dendrogram at a selected height.

Imagine slicing a tree with a flat knife. Whatever branches the knife passes through become the groups. Cut high and few thick branches fall away: few groups. Cut low and you get many small ones. Wikipedia's example says cutting the tree gives a partitioning clustering at a selected precision, and a lower cut gives more, smaller clusters.

Our code did exactly this. At height 7.0 it kept every merge up to 5.57 and left out the 8.08 one, so G and H stood apart from the other six: two groups. At height 3.0 it kept every merge up to 1.57 and left out both big merges: three groups, A B C, D E F and G H.

Which height is best? Wikipedia mentions a widely used heuristic: look for large vertical gaps in the dendrogram, which correspond to substantial increases in the distance between successive merges. In our data the biggest jump is from 1.57 to 5.57, so any cut in between gives three groups. A cut anywhere between 5.57 and 8.08 gives two.

Tip

Wikipedia adds a fair warning: dendrograms alone should not be used to definitively determine the number of clusters. Use the gaps as a hint, then check whether the groups make sense for your job.

Quick check

A dendrogram has five joins low down, then a long empty gap, then two joins near the top. Where do you cut to get the most natural groups?

The price: it gets slow

Hierarchical clustering has a catch. Every merge needs a look at how close the groups are. Wikipedia says the standard algorithm has a time complexity of O(n cubed) and requires Ω(n squared) memory, which makes it too slow for even medium data sets. The n is the number of points. Time complexity is a way of saying how fast the work grows as the data grows.

To feel it, look at how many pairs of points exist. This tiny script counts them.

Python
for n in (100, 1000, 10000):
    print(n, "points ->", n * (n - 1) // 2, "pairs of points")

Output

100 points -> 4950 pairs of points
1000 points -> 499500 pairs of points
10000 points -> 49995000 pairs of points

A hundred points make 4,950 pairs. Ten thousand points make nearly fifty million. The algorithm has to keep track of all of them, which is why the work balloons. Scikit-learn says agglomerative clustering is computationally expensive without connectivity constraints, because it considers at each step all the possible merges.

Wikipedia says agglomerative methods are most commonly used for small to medium-sized datasets, which is where the tree itself is the prize.

What to remember

  • The method

    Start with every point alone. Merge the two closest groups, note the distance, and repeat until one group is left. The record of merges is the tree.

  • Linkage

    Single uses the closest pair, complete the furthest pair, average the mean of all pairs, and Ward the merge that adds the least mess. Different rules, different groups.

  • Cutting

    Look for the biggest jump in the merge distances and cut there. You pick k after seeing the tree, not before. Beware: it gets slow on big data.

Next: probabilistic clustering, groups described as chances.

Sources

How is this lesson?

Last updated on 16 November 2026

Learn with me

Every lesson is free. I add new ones as I learn. Have a question, or want help with your own work? Book a short call.