Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 46 4 c Solution Created 2026-10-03 Updated 2026-10-14
There is a defect in the stated geometric interpretation of the data. The supplied numbers cannot be Euclidean distances, becauseThey violate the triangle inequality; independently, . Nevertheless, both clustering algorithms are defined for this symmetric dissimilarity matrix. The calculations below retain the supplied numbers and use agglomerative clustering of nonmetric dissimilarities, rather than silently inventing Euclidean replacement data.
In single-linkage clustering, the intercluster dissimilarity isThe closest pair is , merging at . Among the remaining clusters the next closest pair is , merging at . The three intercluster dissimilarities are nowConsequently merges with at , using the cross-pair . The remaining point joins at , using . The dendrogram thus hasThe close pairs and are the clearest early groupings. A cut between and produces these two pairs and the singleton ; a cut between and produces and . Single-linkage clustering builds chains through close cross-pairs, so the merge at does not mean every pair in is that close: . The data alone do not prescribe a unique number of clusters.
For complete-linkage clustering, replace the minimum by the maximum:The first two merges remain at and at . SubsequentlyThus joins at . The final maximum between and is , givingBoth the topology and the later heights of the dendrogram change: complete-linkage clustering attaches to before joining that group to , rather than merging the two pairs first. Its control of the largest within-cluster separation makes it less susceptible to the chaining seen with single-linkage clustering.
Single-linkage and complete-linkage dendrograms for the supplied five-subject dissimilarities
. Details. 