Foundations — Dendrograms and linkage methods

Before you can read the parent note, you must be able to read every squiggle it writes. Below is every symbol and idea it uses, built from the ground up. Nothing is assumed. If the parent leaned on it, we build it here first.

0. A point, and where it lives

We will keep every example in 2D so you can see it. Our running pair of clusters — the ones the parent uses for single, complete, and average linkage — are:

• $A=\{(0,0),(1,1)\}$ — two dots near the bottom-left corner
• $B=\{(5,5),(6,6)\}$ — two dots up in the top-right

Look at the picture: four chalk dots. Two are huddled near the origin (that's cluster $A$, pale yellow), two are huddled far away (that's cluster $B$, chalk blue). This one image is the stage for the min/max/sum linkage examples. (Ward's linkage in §6 needs a different, clearly-announced pair — watch for it.)

1. Distance between two points — $d(a,b)$

The parent writes $d(a,b)$ everywhere. It means: how far apart are two dots? We measure it with a ruler laid straight between them — the Euclidean distance.

Why the square root of squares? Because of the right triangle. Walk right by $(a_1-b_1)$, then up by $(a_2-b_2)$: those are the two legs of a right triangle whose hypotenuse is the direct path. Pythagoras says (leg)² + (leg)² = (hypotenuse)², so the straight distance is the square root of the two squared legs.

2. What a symbol like $A$, $B$, and $|A|$ mean

Sizes of the clusters that appear on this page:

• Running $A=\{(0,0),(1,1)\}$ has $|A|=2$.
• Running $B=\{(5,5),(6,6)\}$ has $|B|=2$.
• The Ward example's cluster (introduced later in §6) $A^{\prime }=\{(0,0),(2,0),(1,1)\}$ has $|A^{\prime }|=3$.

Why the topic needs this: Average and Ward's linkage divide by counts like $|A|\cdot |B|$. If you don't know $|A|$ just means "how many dots in $A$," those formulas are unreadable.

3. The symbol $a\in A$ — "$a$ is a point sitting inside bag $A$"

The parent writes things like ${\min }_{a\in A,b\in B}d(a,b)$. In plain words: look at every dot $a$ taken from bag $A$, paired with every dot $b$ taken from bag $B$. With the running clusters $|A|=2$ and $|B|=2$ there are $2\times 2=4$ such pairs — exactly the four distances the parent lists.

The picture shows all four pairing-lines drawn between the two clusters. Every linkage method is just a different way of choosing which of these lines to report.

4. $\min$ and $\max$ — pick the smallest / biggest

Why the topic needs them:

• Single linkage = $\min$ of the four lines → the closest pair. Picture: the shortest of the four chalk lines in figure s03.
• Complete linkage = $\max$ of the four lines → the farthest pair.

5. $\sum$ — add up a whole list

Two stacked $\sum$'s just mean a double loop: outer loop over $a$, inner loop over $b$.

Why the topic needs it: Average linkage is the sum of all lines, shared out evenly. Without $\sum$ you can't state "consider every relationship at once."

6. The centroid $\mu$ and the length bars $\Vert \cdot \Vert$

Ward's linkage introduces two new symbols. Both have clean pictures.

7. Reading the tree: axes of a dendrogram

Cutting the tree with a horizontal line at height $h$ chops the tree into pieces: the number of vertical lines the cut crosses is the number of clusters you keep. Cut low → many tiny clusters; cut high → few big clusters.

Prerequisite map

Each node below matches a heading above: "cluster A and size bars" is §2, "all pairs a in A b in B" is §3, and so on.

Read it as: points give distances; distances over all pairs feed the min/max/sum rules; sizes and centroids feed Ward; and all four rules feed the merge heights of the dendrogram.

For the Hinglish version of the parent walkthrough, see 2.5.05 Dendrograms and linkage methods (Hinglish).

Equipment checklist

Cover the right side and answer each before revealing.