Exercises — Dendrograms and linkage methods

• Single = the smallest = $5.66$ (closest pair).
• Complete = the largest = $8.49$ (farthest pair).
• Average = mean of all four $=\frac{7.07+8.49+5.66+7.07}{4}=7.07$.

What we did: just applied "min / max / mean" to the same list of numbers — the numbers never change, only the rule that picks from them.

• The height = the cluster-distance $d(A,B)$ at the moment $A$ and $B$ merged. Low bar → merged early because they were similar; tall bar → merged late because they were dissimilar.
• A horizontal cut at height $h$ produces as many clusters as it crosses vertical lines. Cut low ⇒ many small clusters; cut high ⇒ few big ones.

The four pairwise distances (see figure — two clusters as vertical bars 3 apart):

• $d((0,0),(3,0))=\sqrt{3^2+0^2}=3$
• $d((0,0),(3,2))=\sqrt{9+4}=\sqrt{13}\approx 3.606$
• $d((0,2),(3,0))=\sqrt{9+4}=\sqrt{13}\approx 3.606$
• $d((0,2),(3,2))=\sqrt{9+0}=3$

Single $=\min =3$. Complete $=\max =\sqrt{13}\approx 3.606$.

Notice the two horizontal segments (length $3$) are the closest connections; the two diagonals are the farthest.

Sum the four $=3+\sqrt{13}+\sqrt{13}+3=6+2\sqrt{13}\approx 13.211$. Pairs $=|A|\cdot |B|=2\cdot 2=4$. $d_{\text{average}}=\frac{6+2\sqrt{13}}{4}\approx \frac{13.211}{4}\approx \mathrm{3.303.}$ As expected it sits between single ($3$) and complete ($3.606$).

Step 1 — centroids (average of coordinates): ${\mu }_A=\left(\frac{0+2+1}{3},\frac{0+0+1}{3}\right)=(1,\frac{1}{3}),{\mu }_B=\left(\frac{6+7}{2},\frac{6+7}{2}\right)=(6.5,6.5).$ Step 2 — squared centroid gap: $\Vert {\mu }_A-{\mu }_B{\Vert }^2=(1-6.5{)}^2+(\frac{1}{3}-6.5{)}^2=30.25+38.028=\mathrm{68.278.}$ Step 3 — size weight $\frac{|A||B|}{|A|+|B|}=\frac{3\cdot 2}{3+2}=\frac{6}{5}=1.2$: $d_{\text{Ward}}=1.2\times 68.278\approx \mathrm{81.93.}$

Smallest distance is $d(P,Q)=1$, so $P,Q$ merge first at height $1$. Now the cluster $\{P,Q\}$ vs $R$ under single linkage $=\min (d(P,R),d(Q,R))=\min (4,3)=3$. So the final merge happens at height $3$. Dendrogram: $P$–$Q$ join at $1$, then that pair joins $R$ at $3$.

$\{P,Q\}$ merge first at $1$ (unchanged — this is a within-step choice on identical pairwise numbers). Complete linkage: $d(\{P,Q\},R)=\max (d(P,R),d(Q,R))=\max (4,3)=4$. Why higher: complete uses the farthest member $P$ (distance $4$), while single used the nearest member $Q$ (distance $3$). Complete is conservative, so merges always sit at $\ge$ the single-linkage height.

The five close points chain together one gap at a time (each gap $=1$), forming one long cluster at low heights. The outlier at $20$ stays separate until the very end (distance $\ge 16$ to its nearest neighbour). Because single linkage only needs one short bridge, a chain of intermediate points would let far-apart groups merge cheaply — this is the chaining effect. Here there's no bridge to the outlier, so it merges last and tall.

Pairwise: $d(A,B)=1,d(B,C)=2,d(C,D)=5,d(A,C)=3,d(A,D)=8,d(B,D)=7$.

• Merge 1 (height $1$): $A,B$ (smallest). Cluster $\{A,B\}$.
• Recompute single-link distances from $\{A,B\}$: to $C=\min (3,2)=2$; to $D=\min (8,7)=7$.
• Merge 2 (height $2$): $\{A,B\}$ with $C$ → $\{A,B,C\}$.
• Single-link $\{A,B,C\}$ to $D=\min (8,7,5)=5$.
• Merge 3 (height $5$): $\{A,B,C\}$ with $D$ → all together.

Heights in order: $1,2,5$.

• Merge 1 (height $1$): $A,B$ (identical first step).
• Complete distances from $\{A,B\}$: to $C=\max (3,2)=3$; to $D=\max (8,7)=8$.
• Merge 2 (height $3$): $\{A,B\}$ with $C$.
• Complete $\{A,B,C\}$ to $D=\max (8,7,5)=8$.
• Merge 3 (height $8$): all together.

Heights: $1,3,8$ vs single's $1,2,5$. Every merge from step 2 on is taller or equal because complete always grabs the farthest point.

Cut at any height $h$ with $2<h<5$ (say $h=3.5$). This line sits above the merges at $1$ and $2$ but below the merge at $5$, so it separates the tree into $\{A,B,C\}$ and $\{D\}$. Why: cutting removes the top-most (tallest) links that lie above $h$; here only the height-$5$ link is cut, splitting the top junction into its two branches.

Pairwise distances:

• $d((0,0),(1,3))=\sqrt{1+9}=\sqrt{10}\approx 3.162$

• $d((0,0),(3,3))=\sqrt{9+9}=\sqrt{18}\approx 4.243$

• $d((2,0),(1,3))=\sqrt{1+9}=\sqrt{10}\approx 3.162$

• $d((2,0),(3,3))=\sqrt{1+9}=\sqrt{10}\approx 3.162$

• Single $=\min =\sqrt{10}\approx 3.162$

• Complete $=\max =\sqrt{18}\approx 4.243$

• Average $=\frac{3\sqrt{10}+\sqrt{18}}{4}\approx \frac{9.487+4.243}{4}=\frac{13.730}{4}\approx 3.432$

Ward: centroids ${\mu }_A=(1,0),{\mu }_B=(2,3)$; $\Vert {\mu }_A-{\mu }_B{\Vert }^2=(1-2{)}^2+(0-3{)}^2=1+9=10$; weight $\frac{2\cdot 2}{2+2}=1$; so $d_{\text{Ward}}=10$.

Ordering of the min/avg/max trio: $3.162\le 3.432\le 4.243$ ✓ (single $\le$ average $\le$ complete always holds — a mean can't beat its own min or exceed its own max). Ward lives on a different scale (squared distance) so we don't slot it in this chain.

Let the set of pairwise distances be $S=\{d(a,b)\}$. Single picks $\min S$, complete picks $\max S$. For any non-empty finite set, $\min S\le \max S$ by definition of min/max — so $d_{\text{single}}\le d_{\text{complete}}$ always. Equality happens exactly when $\min S=\max S$, i.e. when every cross-pair distance is identical (all of $S$ is one repeated value). Geometrically: e.g. two singletons ($|A|=|B|=1$, only one pair), or perfectly symmetric configurations where all cross-distances coincide.

${\mu }_A=(0,0)$. For $B$: ${\mu }_B=\left(\frac{0+4+2}{3},\frac{0+0+2\sqrt{3}}{3}\right)=\left(2,\frac{2\sqrt{3}}{3}\right)=(2,1.1547)$. $\Vert {\mu }_A-{\mu }_B{\Vert }^2=2^2+(1.1547{)}^2=4+1.3333=5.3333$. Weight $\frac{|A||B|}{|A|+|B|}=\frac{1\cdot 3}{1+3}=\frac{3}{4}=0.75$. $d_{\text{Ward}}=0.75\times 5.3333=\mathrm{4.0.}$ Comment: even though $A$'s single point sits on a vertex of $B$ (distance $0$ to one member!), Ward reports $4$ — because Ward measures the centroid gap and the variance increase, not the nearest point. A single-linkage view here would report $0$. This is why Ward and single can disagree drastically.

Single linkage of $A=\{(0,0),(0,2)\}$, $B=\{(3,0),(3,2)\}$ ::: $3$ Complete linkage of the same ::: $\sqrt{13}\approx 3.606$ First merge is identical across all linkages when every cluster is a singleton ::: True — all reduce to point-to-point distances Ward distance of $A=\{(0,0)\},B=\{(0,0),(4,0),(2,2\sqrt{3})\}$ ::: $4.0$