Study time: about 3.5 hours. About 20 of the 30 clustering written marks, plus 10 coding marks. This was not on the class test — prioritise it.
Some questions ask for a taxonomy: small groups inside larger groups. Agglomerative hierarchical clustering builds that taxonomy from the bottom up.
Start with every observation alone. Repeatedly merge the two closest clusters until one cluster remains. The record of merges is a dendrogram: height marks the dissimilarity at which a merge happened. Horizontal spacing in the plot is layout, not distance.
Once two clusters merge, they never separate at higher levels. Early merge mistakes propagate. The fit itself is deterministic for a fixed dissimilarity and linkage — no seed, no nstart.
Cutting the tree at a height, or asking for K groups with cutree, yields a partition you can silhouette and profile exactly as in k-means.
Between clusters G and H,
d_{\mathrm{SL}}(G,H)=\min_{i\in G,\,i'\in H}d_{ii'} \qquad\text{(single: nearest neighbours)},
d_{\mathrm{CL}}(G,H)=\max_{i\in G,\,i'\in H}d_{ii'} \qquad\text{(complete: furthest neighbours)},
d_{\mathrm{GA}}(G,H)=\frac{1}{N_G N_H}\sum_{i\in G}\sum_{i'\in H}d_{ii'} \qquad\text{(group average)}.
Same numbers, three answers. For d(3,1)=0.22 and d(6,1)=0.23,
| Linkage | d(\{3,6\},\{1\}) |
|---|---|
| Single | \min(0.22,0.23)=0.22 |
| Complete | \max(0.22,0.23)=0.23 |
| Average | \frac{1}{2}(0.22+0.23)=0.225 |
Single can chain through a bridge point: one close pair is enough to merge elongated shapes. Complete waits until every pair between groups is close enough, so clusters tend to be more compact and balanced. Average is a compromise with a clear “mean pairwise gap” reading.
# Four points: two tight pairs far apart
pts <- matrix(c(0, 0, 0.1, 0, 5, 5, 5.1, 5.2), ncol = 2, byrow = TRUE)
rownames(pts) <- c("A", "B", "C", "D")
d <- dist(pts)
d A B C
B 0.1000000
C 7.0710678 7.0007142
D 7.2835431 7.2138755 0.2236068hc <- hclust(d, method = "single")
plot(hc, main = "Single linkage", xlab = "", sub = "")
cutree(hc, k = 3)A B C D
1 1 2 3 hc <- hclust(d, method = "complete")
plot(hc, main = "Complete linkage", xlab = "", sub = "")
cutree(hc, k = 3)A B C D
1 1 2 3 hc <- hclust(d, method = "average")
plot(hc, main = "Average linkage", xlab = "", sub = "")
cutree(hc, k = 3)A B C D
1 1 2 3 Dissimilarities among four observations (exercise-set pattern):
# Symmetric matrix with zeros on diagonal
lab <- c("A", "B", "C", "D")
M <- matrix(0, 4, 4, dimnames = list(lab, lab))
M["A", "B"] <- M["B", "A"] <- 2
M["A", "C"] <- M["C", "A"] <- 6
M["A", "D"] <- M["D", "A"] <- 10
M["B", "C"] <- M["C", "B"] <- 5
M["B", "D"] <- M["D", "B"] <- 9
M["C", "D"] <- M["D", "C"] <- 4
d4 <- as.dist(M)
hc4 <- hclust(d4, method = "complete")
hc4$height[1] 2 4 10cutree(hc4, k = 2)A B C D
1 1 2 2 Mechanism. The smallest entry is d(A,B)=2, so merge \{A,B\} first at height 2. Complete linkage distance from \{A,B\} to C is \max(6,5)=6; to D is \max(10,9)=10. Next smallest among remaining is d(C,D)=4, so merge \{C,D\} at height 4. Final merge height is \max of all cross pairs between \{A,B\} and \{C,D\}, which is 10. Cutting to K=2 recovers the two pairs.
Reuse silhouette, negative counts, subsample stability, and profiles from the k-means workflow. Extra hierarchical facts:
x <- scale(as.matrix(df[, numeric_cols]))
d <- dist(x, method = "euclidean")
hc <- hclust(d, method = "average") # or "single" / "complete"
plot(hc)
groups <- cutree(hc, k = 3)
sil <- cluster::silhouette(groups, d)
mean(sil[, "sil_width"])Compare linkages on the same dist object. Do not rebuild distances differently between methods unless the question asks for that.
On the toy routes file:
dist.table().routes <- read.csv("data/hierarchical-clustering-lab-toy.csv")
# Keep numeric feature columns only
num <- routes[sapply(routes, is.numeric)]
x <- scale(as.matrix(num))
d <- dist(x)
hc <- hclust(d, method = "average")
plot(hc, labels = FALSE, main = "Average linkage", xlab = "", sub = "")
groups <- cutree(hc, k = 3)
table(groups)groups
1 2 3
7 8 8 For clusters G and H, single-linkage dissimilarity is…
Using the four-point complete-linkage matrix above, state the first merge height and the K=2 partition.
GPS tracks form elongated routes; a few isolated errors remain. Why is single linkage risky?
Single linkage K=2 has higher average silhouette than average linkage K=3, but K=2 merely separates salinity extremes while the brief asks for multivariate handling profiles. Strongest conclusion?
Why does hierarchical clustering need no nstart?