Visual walkthrough — Dendrograms and linkage methods

The parent note handed you four formulas. Three of them (single, complete, average) are just "look at the pairs of points and take min / max / mean" — easy to picture. But the fourth, Ward's linkage, arrived with a mysterious formula:

$d_{\text{Ward}}(A,B)=\frac{|A|\cdot |B|}{|A|+|B|}\Vert {\mu }_A-{\mu }_B{\Vert }^2$

Where did that fraction come from? Why squared distance between centroids? This page builds that single formula from nothing, one picture at a time. By the end you will see why it looks exactly like this and could never look any other way.

---

Step 0 — The symbols we will use (nothing assumed)

Before line one, let us name every object with a picture, so no symbol is ever a stranger.

We will only ever use these. Whenever a new one appears, we stop and earn it first.

---

Step 1 — The centroid: the balance-point of a cluster

WHAT. For a cluster $C$ with points $c_1,c_2,\dots$, the centroid is ${\mu }_C=\frac{1}{|C|}{\sum }_{c\in C}c$

• ${\sum }_{c\in C}c$ — the big Greek "S" ($\Sigma$, sigma) says "add up": add all the points component by component (all the x's, then all the y's), as defined in Step 0.
• $\frac{1}{|C|}$ — divide that sum by the count, giving the average position.

WHY. To talk about how far apart two clusters are, we first need a single point that stands for each cluster. The average location is the fairest such stand-in: it sits right in the middle of the dots, like the point where a flat cardboard cut-out of the cluster would balance on a pin.

PICTURE. The three blue dots have their centroid (yellow star) sitting dead-centre.

---

Step 2 — Spread: how "fat" is one cluster? (total sum of squares)

WHAT. The spread of cluster $C$ — properly its total sum of squares — is $\text{SS}(C)={\sum }_{c\in C}\Vert c-{\mu }_C{\Vert }^2$

• $c-{\mu }_C$ — the arrow from the centroid out to a point (subtract component by component, Step 0).
• $\Vert c-{\mu }_C{\Vert }^2$ — the squared length of that arrow, i.e. $(c_x-{\mu }_{C,x}{)}^2+(c_y-{\mu }_{C,y}{)}^2$.
• $\sum$ — add one such squared length for every point.

WHY squared, and why not just distance? We want a number that grows fast when points fly outward, and that never cancels (a point on the left must not undo a point on the right). Squaring does both: it is always positive, and it punishes far-away points harder than near ones. This is the same reason physics uses squared distance for "moment of inertia" — spread is literally the rotational fatness of the cluster.

PICTURE. Each red arrow is $c-{\mu }_C$; the shaded square on one arrow is its squared length. Spread = total shaded area over all arrows.

---

Step 3 — The cost of merging: what we actually minimize

WHAT. Merging $A$ and $B$ makes one big cluster $A\cup B$ ("$A$ union $B$" = all the dots together). The increase in spread caused by the merge is $\Delta =\text{SS}(A\cup B)-\text{SS}(A)-\text{SS}(B)$

• First term: spread of the merged blob, measured around its new centroid.
• Minus the spreads the two pieces already had on their own.
• $\Delta$ (Greek "delta", meaning change) is the extra fatness the merge introduces.

WHY this quantity? Ward's whole idea: at every step of hierarchical clustering, merge the pair whose $\Delta$ is smallest — the pair that costs the least extra spread. So $\Delta$ is Ward's linkage distance. Everything left is showing that this messy three-term expression collapses to something clean.

PICTURE. Left: two tidy clusters around their own centroids. Right: the same points now measured around the shared centroid — arrows got longer, area (spread) went up. That extra area is $\Delta$.

---

Step 4 — The key move: the new centroid sits between the old two

WHAT. The merged centroid is a weighted average of the two old centroids: ${\mu }_{A\cup B}=\frac{|A|{\mu }_A+|B|{\mu }_B}{|A|+|B|}$

• $|A|{\mu }_A$ — pull toward $A$'s centre, with strength = how many points $A$ has.
• $|B|{\mu }_B$ — pull toward $B$'s centre, weighted by $B$'s count.
• Divide by the total count so it stays inside the picture.

WHY. The overall balance-point of all the dots is the balance-point of the two sub-balance-points, each weighted by how much "mass" (how many points) it carries. A big cluster tugs the shared centroid closer to itself — exactly like a heavier child on a see-saw sitting nearer the pivot.

PICTURE. The green shared centroid lands on the line segment joining ${\mu }_A$ and ${\mu }_B$, nearer whichever cluster has more points.

---

Step 5 — The split identity (parallel-axis) that makes it collapse

Before we can say "the internal spread cancels", we must state and see the identity that lets it. This is the one honest piece of algebra on the page — everything hinged on it, so we picture it.

WHAT. Measure cluster $A$'s squared spread not around its own centroid ${\mu }_A$ but around any other point $m$. The parallel-axis split says: ${\sum }_{c\in A}\Vert c-m{\Vert }^2=\underset{\text{spread around own centre}}{\underbrace{\sum _{c\in A}\Vert c-{\mu }_A{\Vert }^2}}+\underset{\text{shift penalty}}{\underbrace{|A|\Vert {\mu }_A-m{\Vert }^2}}$

• Left side: spread of $A$ measured from the far-away point $m$.
• First right term: the spread $A$ already had around its own centroid — unchanged.
• Second right term: an extra cost, $|A|$ (one per point) times the squared gap between $A$'s centre and the new reference point $m$.

WHY it is true (in one line). Write $c-m=(c-{\mu }_A)+({\mu }_A-m)$. Square the length: the two cross-terms sum to zero because ${\sum }_{c\in A}(c-{\mu }_A)=0$ (the centroid is exactly the point that makes the arrows from it cancel). What's left is the two squared pieces above. So the only price of moving the reference point is $|A|\Vert {\mu }_A-m{\Vert }^2$.

PICTURE. Same dots, two reference points. Around ${\mu }_A$ (yellow) the arrows are shortest possible; around a shifted point $m$ (red) every arrow is longer by exactly the same shift — that uniform stretch is the $|A|\Vert {\mu }_A-m{\Vert }^2$ term.

Now apply it with $m={\mu }_{A\cup B}$ (the shared centroid) to both $A$ and $B$: $\text{SS}(A\cup B)=[\text{SS}(A)+|A|\Vert {\mu }_A-{\mu }_{A\cup B}{\Vert }^2]+[\text{SS}(B)+|B|\Vert {\mu }_B-{\mu }_{A\cup B}{\Vert }^2]$

Subtract $\text{SS}(A)+\text{SS}(B)$ from both sides — those internal spreads cancel exactly (now you see why, not on faith): $\Delta =|A|\Vert {\mu }_A-{\mu }_{A\cup B}{\Vert }^2+|B|\Vert {\mu }_B-{\mu }_{A\cup B}{\Vert }^2$

Finally substitute the weighted centroid from Step 4. Both gaps ${\mu }_A-{\mu }_{A\cup B}$ and ${\mu }_B-{\mu }_{A\cup B}$ are just fractions of the single gap ${\mu }_A-{\mu }_B$, and the arithmetic tidies to the boxed result: $\boxed{\Delta =\frac{|A|\cdot |B|}{|A|+|B|}\Vert {\mu }_A-{\mu }_B{\Vert }^2}$

Read the survivor term by term, right where each piece sits:

• $\Vert {\mu }_A-{\mu }_B{\Vert }^2$ — how far apart the two balance-points are, squared. Far-apart clusters cost more to merge.
• $\frac{|A|\cdot |B|}{|A|+|B|}$ — the size weight. It is the product of the counts divided by their sum (this is not the harmonic mean — the harmonic mean would carry an extra factor of 2). It stays small when either cluster is tiny (merging a lone stray point is cheap) and grows when both clusters are big (merging two large populations is a big commitment).

---

Step 6 — Edge & degenerate cases (never leave the reader stranded)

WHAT / WHY / PICTURE, three special situations the formula quietly handles:

Case A — a singleton merge ($|A|=1$). The weight becomes $\frac{1\cdot |B|}{1+|B|}$, always less than 1. Merging a lone point is the cheapest kind of merge — the formula naturally makes strays join first.

Case B — identical centroids (${\mu }_A={\mu }_B$). Then $\Vert {\mu }_A-{\mu }_B{\Vert }^2=0$, so $\Delta =0$. Two clusters centred on the same spot cost nothing extra to merge — correct, since no balance-point had to move.

Case C — equal sizes ($|A|=|B|=n$). The weight simplifies to $\frac{n\cdot n}{2n}=\frac{n}{2}$, growing with cluster size. Merging two big balanced clusters is expensive — Ward resists it, which is why Ward builds tight, evenly-sized blobs.

---

The one-picture summary

Everything above in a single frame: two clouds → their centroids → the gap between centroids (squared) → dialed by cluster sizes → the height at which the dendrogram bar is drawn.

Recall Feynman retelling (say it out loud)

Imagine two herds of sheep. Each herd has a middle-of-the-flock spot — its centroid. When I herd them into one big flock, the sheep don't move relative to their own herd-mates, but the middle spot they measure from shifts. The parallel-axis rule says the only new cost of that shift is: one penalty per sheep, equal to the squared distance the herd's centre travelled. Add up both herds' penalties and it tidies into a squared gap between the two original middles, turned up or down by a size dial (product of counts over their sum). Ward's rule: always merge the two herds whose merge costs the least extra spread. That's the whole formula.

Recall Quick self-test

Why is squared distance used for spread and not plain distance? ::: So it's always positive (no cancellation) and punishes far points harder, matching "fatness". What does the parallel-axis split say about measuring spread from a shifted point? ::: You get the original spread PLUS $|C|$ times the squared shift of the centroid — the internal spread is untouched. Is the size weight the harmonic mean of the counts? ::: No — it's $\frac{|A||B|}{|A|+|B|}$, the harmonic mean would be twice this. If ${\mu }_A={\mu }_B$, what is $d_{\text{Ward}}$? ::: Zero — no balance-point had to move.

🇮🇳 Prefer Hinglish? Yeh walkthrough Hinglish mein →