Dendrograms and linkage methods: Question bank

Before we start, the notation used below must mean exactly one thing:

Definition The symbols this page relies on

Cluster = a group of one or more data points. A single point is a "singleton" cluster.
$∣ A ∣$ = the size (count of points) of cluster $A$ . The bars mean "how many members", nothing else. So if $A = {p, q, r}$ then $∣ A ∣ = 3$ .
$d (a, b)$ = the distance function between two points $a$ and $b$ . It is a metric: it is never negative, equals $0$ only when $a = b$ , is symmetric ( $d (a, b) = d (b, a)$ ), and obeys the triangle inequality. Think "how far apart on the map", e.g. straight-line (Euclidean) distance.
$μ_{A}$ = the centroid (average position) of cluster $A$ , defined coordinate-by-coordinate as $μ_{A} = \frac{1}{∣ A ∣} \sum_{a \in A} a$ . It is the "balance point" of the cloud of points.
$∥ v ∥$ = the length (Euclidean norm) of a vector $v$ , i.e. $∥ v ∥ = v_{1}^{2} + v_{2}^{2} + \dots$ . So $∥ μ_{A} - μ_{B} ∥$ is just the straight-line distance between the two centroids, and $∥ μ_{A} - μ_{B} ∥^{2}$ is that distance squared.

Definition Dendrogram — the structure we keep referring to

A dendrogram is the tree drawn by agglomerative clustering. Four parts, so the questions below have precise words to lean on:

Leaves = the singleton clusters at the bottom, one per original data point; their left-to-right position is only a layout order, not a measurement.
Branches = the vertical lines that rise from leaves or from earlier merges.
Merge (a horizontal bar joining two branches) = the moment two clusters combine into one.
Merge height = the y-value of that bar; it equals the linkage distance between the two clusters at merge time. Higher bar = more dissimilar.
Cut = a horizontal line drawn across the whole tree at some height $h$ ; the number of branches it crosses is the number of clusters you get by "stopping" there.

To ground the "min vs max vs mean" family before you argue about it, study the figure below.

Figure — Dendrograms and linkage methods

Walk it: the teal dots are cluster $A$ , the plum dots are cluster $B$ . The orange solid line connects the closest pair — that single length is the single-linkage distance ( $\approx 4.19$ ). The ink dashed line connects the farthest pair — that length is the complete-linkage distance ( $\approx 5.65$ ). The two $\times$ marks are the centroids; average linkage is the mean of all nine dashed-and-solid connections (boxed value $\approx 4.85$ ), which lands between the orange and the dashed line but is not their midpoint — notice the boxed number is not $\frac{4.19 + 5.65}{2}$ . This is the whole point of the "average is not the min–max midpoint" trap below.

Now the tie-breaking edge case, made concrete.

Walk it: three leaves $P, Q, R$ where $d (P, Q) = d (Q, R)$ exactly — a tie (dotted orange line at height 2). Left tree merges $P$ – $Q$ first; right tree merges $Q$ – $R$ first. Both are perfectly valid outputs of the same data and the same linkage rule; the algorithm simply picks one when distances tie. So when the last True/False item says "the dendrogram is unique", these two pictures are the counterexample.

True or false — justify

Single linkage always produces the same clustering as complete linkage on the same data

False — they merge in different orders because single uses the closest pair and complete the farthest pair, so the whole tree (and any horizontal cut) can differ dramatically.

In a dendrogram, the horizontal position (x-axis) of a leaf encodes its distance from other points

False — the x-axis is just a layout ordering of leaves to keep branches from crossing; only the height (y-axis) encodes dissimilarity.

Merge heights along any root-to-leaf path never decrease as you go up the tree

True for single, complete, average, and Ward on a valid distance matrix — each merge is at least as high as the merges beneath it; a decrease (called an inversion) signals a non-monotonic linkage, which these four avoid.

Average linkage is literally the average of the single-linkage and complete-linkage distances

False — it is the mean over all

∣ A ∣ \cdot ∣ B ∣

point-pairs, which is generally not the midpoint of the min and the max.

Ward's linkage requires you to pick a point-distance metric like Manhattan

False in practice — Ward is derived from squared Euclidean distances to centroids, so it is only well-defined (and only minimizes variance) for Euclidean space.

Cutting a dendrogram lower always gives you more clusters than cutting it higher

True — a lower horizontal line crosses more vertical branches, and each crossed branch is one cluster; height is dissimilarity, so low cut = many tight groups.

If two clusters have identical centroids, Ward's distance between them is zero regardless of their spread

True — Ward's formula is

\frac{∣ A ∣ ∣ B ∣}{∣ A ∣ + ∣ B ∣} ∥ μ_{A} - μ_{B} ∥^{2}

, and

μ_{A} = μ_{B}

makes the norm zero even if the clusters overlap heavily.

Single linkage between two clusters can be smaller than the distance between their centroids

True — one close pair of border points can be nearer than the centroids are, which is exactly why single linkage forms chains.

Complete linkage distance between two clusters is always at least as large as their average linkage distance

True — the maximum of a set of pairwise distances is never below their mean, so

d_{complete} \geq d_{average} \geq d_{single}

always.

Centroid linkage and average linkage are the same because both involve "averaging"

False — centroid linkage averages the points first then takes one distance (

∥ μ_{A} - μ_{B} ∥

), whereas average linkage takes the distances first then averages them; the two differ because distance is a non-linear function of position.

The dendrogram is unique for a given dataset and linkage method

Mostly true, but ties (two pairs at exactly the same distance) can be broken arbitrarily, producing different-looking trees that are all valid — see the second figure above.

Spot the error

"To find d(A,B) with single linkage, take the two closest centroids."

Wrong — single linkage is defined as the minimum over point pairs, so a centroid never even enters the formula; using centroids would ignore the close border points that single linkage exists to detect. Centroids belong to centroid/Ward rules.

"Ward's distance is just the Euclidean distance between the two centroids."

False because that description is centroid linkage; Ward measures the increase in variance on merging, which works out to

\frac{∣ A ∣ ∣ B ∣}{∣ A ∣ + ∣ B ∣} ∥ μ_{A} - μ_{B} ∥^{2}

— dropping the size weight and the square gives a wrong merge order whenever cluster sizes differ.

"Average linkage: average the points of A, average the points of B, then take the distance between those averages."

That is centroid linkage, and it differs because

distance of the means \neq = mean of the distances

in general (a consequence of the distance function being non-linear) — average linkage averages the pairwise distances themselves.

"Complete linkage is immune to outliers because it uses the maximum distance."

Backwards — because it takes the maximum, a single far-flung outlier raises that maximum and inflates the cluster-to-cluster distance, so complete linkage is in fact more exposed to outliers than average linkage, not immune.

"I cut the dendrogram at height 6, and it crossed 3 branches, so I have 6 clusters."

False because cluster count reads off branches crossed, not the height value — the two axes measure different things (dissimilarity vs count), so 3 branches means 3 clusters.

"Single linkage avoids the chaining effect because it looks at nearest neighbors."

Precisely backwards — nearest-neighbor merging is the mechanism of chaining, because a string of close stepping-stone points lets two otherwise separate clusters link up through the gap.

"Reading a dendrogram, the first merge to happen is the one drawn highest."

False because height equals merge distance and the algorithm always merges the closest pair first — so the earliest merge is the lowest bar, while the highest bar is the final join of everything.

Why questions

Why does single linkage tend to create long, snake-like clusters?

Because it only needs one close pair to merge, a trail of stepping-stone points can chain distant regions into a single elongated cluster.

Why does Ward's method produce clusters that resemble k-means output?

Both minimize within-cluster squared distance to a centroid, so Ward greedily builds the same tight, roughly spherical, variance-minimizing groups.

Why do we weight Ward's centroid distance by

\frac{∣ A ∣ ∣ B ∣}{∣ A ∣ + ∣ B ∣}

instead of using the raw squared distance?

Because merging two clusters raises total variance by exactly that weighted amount; the size factor accounts for how many points get pulled toward the new joint centroid.

Why can't we just use "distance between points" and skip linkage methods entirely?

Once a cluster holds several points there is no single "the point" to measure from, so we need a rule (min, max, mean, or centroid-based) to collapse many pairwise distances into one cluster-to-cluster number.

Why does the height axis of a dendrogram matter more than the leaf order?

Height carries the actual dissimilarity information used to decide cutting and cluster count, while leaf order is a cosmetic layout choice that can be permuted without changing the clustering.

Why is average linkage often chosen as a "safe default"?

It uses every pairwise distance, so no single closest or farthest pair dominates, giving a balanced, outlier-tolerant compromise between single and complete.

Why might complete linkage split one true elongated cluster into pieces?

Its farthest-pair criterion refuses to merge groups whose extreme ends are far apart, so a long natural cluster looks "too wide" and gets kept separate.

Edge cases

What is the linkage distance (single, complete, average) between two singleton clusters

{a}

and

{b}

All three collapse to the plain point distance

d (a, b)

, since there is only one pair, so min = max = mean.

What does Ward's distance equal for two singletons

{a}

and

{b}

\frac{1 \cdot 1}{1 + 1} ∥ a - b ∥^{2} = \frac{1}{2} ∥ a - b ∥^{2}

— half the squared Euclidean distance, not the raw distance, which is why Ward heights are not directly comparable to single/complete heights.

If a cluster contains a single point, what is its centroid and its within-cluster variance?

The centroid is the point itself and the variance is zero, because the only member sits exactly at its own mean.

Two clusters are identical sets of points — what is their single-linkage distance?

Zero, because the closest pair can be a point matched with its own copy at distance 0 (or, more properly, this situation shouldn't arise since agglomerative clustering never keeps duplicate clusters).

At the very start of agglomerative clustering with

n

points, how many clusters exist and what are they?

n

singleton clusters — every point is its own cluster, and the algorithm merges them one pair at a time until one cluster remains.

If every pairwise point distance is equal, what happens to the dendrogram?

All merges occur at the same height, giving a flat, star-like tree where the cluster structure is essentially arbitrary — a sign the data has no real hierarchy.

What happens to a dendrogram cut placed above the topmost merge?

It crosses only the single root branch, yielding exactly one cluster containing all points.

What happens to a cut placed below every merge?

It crosses all

n

leaf branches, returning every point as its own singleton cluster.

Can single, complete, and average linkage ever give the exact same merge order?

Yes — on data with well-separated compact clusters where the closest, farthest, and mean pairs all agree on which clusters are nearest, the three can coincide.

Recall One-line memory hooks

Single = closest pair (chains). Complete = farthest pair (compact, outlier-shy). Average = mean of all pairs (balanced). Centroid = one distance between the two means. Ward = size-weighted centroid gap squared (k-means-like). Height = dissimilarity ::: leaf order = cosmetics only.