2.5.4 · D5Unsupervised Learning
Question bank — Hierarchical clustering (agglomerative - divisive)
This bank assumes you have met the vocabulary from the parent note: a cluster (a group of points), a linkage criterion (a rule for the distance between two clusters, see Single-Link vs Complete-Link), a dendrogram (the tree that records merges and their heights, see Dendrogram Visualization), and a distance metric (the rule for distance between two points, see Distance Metrics). If any of those feels shaky, go back before continuing.
True or false — justify
Hierarchical clustering finds the globally optimal set of clusters.
False. Each merge is a greedy local choice (merge the currently-closest pair) and is never undone, so an early bad merge is locked in forever — see Gredy Algorithms.
Agglomerative and divisive clustering always produce the same dendrogram on the same data.
False. Agglomerative builds bottom-up merging closest pairs; divisive builds top-down by splitting, so their greedy decisions differ and the trees can disagree, especially in the middle levels.
You must choose the number of clusters K before running agglomerative clustering.
False. The whole point is you build the full tree once with no K, then cut it afterward — unlike K-Means Clustering, which needs K up front.
The height at which two branches join in a dendrogram equals the distance between the two clusters being merged.
True. Merge height is defined as the linkage distance at that step, which is exactly why big height jumps signal natural boundaries.
Changing only the linkage criterion (metric fixed) cannot change the final clusters.
False. Linkage decides which clusters count as "closest", so single vs complete vs Ward can give completely different shapes on identical points — see the chaining example in the parent note.
In agglomerative clustering the number of clusters strictly decreases by exactly one each iteration.
True. Two clusters merge into one per step, so clusters reach in exactly merges — this is why the tree has internal joins.
Single linkage is the safest default because it "connects the nearest points".
False. That same nearest-point rule causes the chaining effect: a line of intermediate points can bridge two truly separate clusters into one.
Ward's method tends to produce compact, roughly equal-sized clusters.
True. Ward merges the pair that minimizes the increase in within-cluster sum of squares (see Within-Cluster Sum of Squares), which penalizes stretched or lopsided merges.
Cutting the dendrogram at a lower height gives fewer clusters.
False. A lower horizontal cut crosses more vertical lines, so it gives more, smaller clusters; a higher cut gives fewer.
Once you have the dendrogram, re-running with a different cut height requires recomputing the whole tree.
False. The tree already encodes every granularity; changing the cut is just sliding a horizontal line — no recomputation needed. That reusability is hierarchical clustering's main selling point.
Spot the error
"We used single linkage, so the two well-separated clusters with a few stray points between them came out clean."
Error: stray points between clusters are exactly what single linkage chains through, merging the two groups. Complete or average linkage would resist this.
"Ward's formula is , the product of sizes times squared centroid distance."
Error: it is missing the denominator. The correct factor is , so the coefficient shrinks as clusters grow, not just the raw product.
"Divisive clustering is preferred in practice because splitting is cheaper than merging."
Error: divisive is more expensive — optimally choosing a split faces subsets, so people usually approximate with K=2 K-Means and still prefer agglomerative (see Time Complexity Analysis).
"Complete linkage distance is the average of all pairwise distances between the two clusters."
Error: complete linkage is the maximum (farthest pair). The average of all pairwise distances is average linkage (UPGMA).
"Naive agglomerative clustering is , and a heap makes it ."
Error: naive is and a priority queue brings it to — you can never beat because you must at least look at every pair once.
"A tall vertical segment in the dendrogram means the two points at its leaves are noisy."
Error: a tall segment means the two clusters it joins were very dissimilar (a big merge-distance jump), which marks a natural cluster boundary, not noise.
"We normalized the update using the Lance-Williams formula with to reproduce single linkage."
Error: single linkage uses (the negative picks the minimum of the two distances); gives complete linkage (the maximum).
Why questions
Why does hierarchical clustering give a tree instead of a flat set of labels like K-Means?
Because it records the entire sequence of merges (or splits) with their heights, so relationships at every granularity are preserved rather than collapsed to one chosen K.
Why is the merge height, not the merge itself, what tells you where to cut?
Small heights mean similar things joined; a sudden large height means you have started merging genuinely different groups, so the gap in heights — not the pairing — locates the boundary.
Why can two different distance metrics (e.g. Euclidean vs cosine) reorder the whole dendrogram?
They change which points count as "close", so the very first greedy merges differ, and because merges are permanent, that early divergence cascades through the entire tree.
Why does Ward's method require centroids while single and complete linkage do not?
Ward reasons about variance, so it needs the cluster mean ; single and complete only compare individual point-to-point distances (min or max) and never form a centroid.
Why does the greedy nature of agglomerative clustering not make it non-deterministic?
Given a fixed metric and linkage, the "closest pair" is fully determined at each step (ties aside), so the output is repeatable — deterministic and greedy are different properties; being greedy just means not globally optimal.
Why is average linkage often described as a compromise between single and complete?
Single uses only the closest pair (prone to chaining), complete only the farthest (prone to breaking large clusters); averaging over all pairs balances both extremes.
Edge cases
What does the dendrogram look like for point?
A single leaf with no merges — there are zero internal joins because , so there is no tree structure at all.
Two clusters have identical centroids but very different spreads — what does Ward's linkage report?
Ward's value is , so it would eagerly merge them despite different spreads, since Ward only sees centroid separation, not internal variance.
All pairwise distances are exactly equal (points on a regular simplex) — what happens?
Every merge is a tie, so the result depends on the tie-breaking rule; the dendrogram is essentially arbitrary because no pair is genuinely "closest".
You cut the dendrogram at a height above the final (root) merge — how many clusters?
One: cutting above the root crosses no internal vertical line, so all points stay in a single cluster.
You cut below every merge height (at height 0) — how many clusters?
Exactly : each leaf is its own cluster because no merge has occurred yet at that height.
A duplicate point appears twice at the same location — what is its merge height?
Zero, since between identical points; they merge first at height 0 regardless of linkage, appearing as a join right at the leaf level.
How does single linkage behave on two touching clusters (zero gap between nearest points)?
It merges them immediately at height , treating them as one cluster — single linkage cannot separate groups that share a near-touching boundary, unlike density methods like DBSCAN.
Recall Fast self-test
The chaining effect belongs to which linkage? ::: Single linkage. Naive agglomerative time complexity? ::: , or with a heap. Higher cut on the dendrogram means more or fewer clusters? ::: Fewer. Ward's coefficient in front of ? ::: .