Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 47 / 4

For rows $x_i,x_j$, three useful choices are Euclidean distance, standardized Euclidean distance, and Mahalanobis distance:The Euclidean choice is simple, rotation invariant and appropriate when the original coordinate scales carry comparable meaning. It is sensitive to scale changes, may be dominated by a high-variance variable and gives correlated or duplicate variables repeated influence. Squared Euclidean dissimilarity is sometimes used algorithmically, but removing the square root generally loses the triangle inequality.

The standardized Euclidean choice removes marginal units using fixed positive sample scales $s_r$. It gives equal marginal weight to variables, but ignores correlations and can magnify noise when an estimated variance is small. Constant variables require omission or an explicitly chosen positive external scale.

The Mahalanobis choice incorporates the full positive-definite sample covariance $S$, so it is Euclidean distance after whitening. It accounts for both scale and redundancy and is invariant under an invertible change of coordinates when $S$ is transformed consistently. However estimating $S$ requires enough observations and can be sensitive to extreme values; inversion is unstable near singularity and unavailable when $S$ is singular. With fixed positive scales or positive-definite $S$, all three square-root expressions are genuine metrics on the measurement space. Their different geometries encode different notions of which individuals should be considered similar.

A metric dissimilarity must satisfy, for all $x,y,z$, the four propertiesThey are nonnegativity, identity of indiscernibles, symmetry and the triangle inequality. The following two transformations of the simple matching coefficient behave differently at the identity.

For fixed $p\ge 1$, the complement of the simple matching coefficient is the fraction of coordinates that disagree:This is the normalized Hamming distance. It is nonnegative, symmetric, and is zero exactly when every coordinate agrees. At each coordinate,Summing and dividing by $p$ proves the triangle inequality. Therefore $d_1$ is a metric on the binary vectors.

For every binary vector $x$, $S_1(x,x)=1$, and henceThus $d_2$ is not a metric, because it fails identity of indiscernibles. It is nonnegative and symmetric. In fact it also satisfies the triangle inequality trivially: every value lies in $[1/2,1]$, so $d_2(x,z)\le 1\le d_2(x,y)+d_2(y,z)$. That does not repair its nonzero self-distance.

In agglomerative hierarchical clustering, start with eight singleton groups. Single-linkage clustering uses the smallest distance between cross-pairs; complete-linkage clustering uses the largest. Updating these cluster distances after each merge, one valid order of the tied merges givesThe merges at height $0.6$ may be reordered; they give the same requested three-cluster cuts. For example, the single-link distance from $AC$ to $BD$ is $\min (1.2,1.4,0.6,0.8)=0.6$, while its complete-link distance is their maximum $1.4$. After forming $EG$, its single-link distance to $H$ is $\min (0.9,1.2)=0.9$. The complete-link distance between $EG$ and $FH$ is $\max (1.2,0.9,1.5,1.2)=1.5$. Finally the closest cross-pair between $ABCD$ and $EFGH$ is $CG$ at $1.9$, while the farthest is $BF$ at $3.8$.

At three groups the partitions are thereforeTwo groups, $\{A,B,C,D\}$ and $\{E,F,G,H\}$, are more strongly supported by the merge heights. For single linkage the three-to-two merge is at $1.0$, close to the preceding height $0.9$, whereas the two-to-one merge is delayed until $1.9$. For complete linkage the three-to-two merge at $1.5$ is close to $1.4$, whereas the final merge jumps to $3.8$. Both methods agree on the two-group partition but split its second group differently when forced to return three groups. A three-group choice is possible if required substantively, but is not particularly compelling from these dissimilarities alone.