Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 46 / 4

Write $x_r,x_t$ for two rows of the data matrix and $\delta =x_r-x_t$. Three possible dissimilarities for continuous variables are the following.

The Euclidean distance isIt is simple and has the usual geometric interpretation when coordinates have comparable units. Its disadvantage is sensitivity to the numerical scales: a change of units or a high-variance variable can dominate it. Strongly correlated coordinates can also give repeated weight to essentially the same information. Squared Euclidean distance is useful in some methods, but is not itself a metric because it need not satisfy the triangle inequality.

The standardized Euclidean distance iswhere $s_j^2$ is the sample variance of coordinate $j$ across individuals. It measures differences in standard-deviation units and is invariant under positive coordinate rescalings when the scales are estimated consistently. It is useful for differently measured variables, but requires nonzero sample variances, ignores correlations between coordinates and can give excessive influence to a low-variance noisy variable. With fixed positive scales it is a Euclidean distance after a diagonal change of coordinates, so it is a metric.

The Mahalanobis distance iswhere $S$ is the pooled sample covariance matrix of all individuals. If $S=C{C}^T$ is its Cholesky decomposition, then $d_M=\Vert C^{-1}\delta {\Vert }_2$: it is Euclidean distance in whitened coordinates. It adjusts for both scales and correlations, avoiding duplicate weight for highly correlated variables, and is invariant under nonsingular affine transformations when the sample covariance matrix is transformed accordingly. No multivariate normal distribution assumption is required merely to define the distance. However, $S$ must be a positive-definite matrix; when there are too few observations or dependent coordinates, its inverse is unavailable. Estimation of $S^{-1}$ can also be unstable and sensitive to outliers. These trade-offs determine whether covariance adjustment is preferable to the simpler distances.

A metric dissimilarity $d$ must satisfy nonnegativity, separation, symmetry and the triangle inequality:The underlying objects must be specified: here they are binary measurement profiles, rather than labels attached to individuals.

Let $n_{11},n_{00},n_{10},n_{01}$ count coordinate pairs of the indicated types. The simple matching coefficient is $S=(n_{11}+n_{00})/4$, so its complementary dissimilarity is $(n_{10}+n_{01})/4$. Counting mismatches in every pair gives the dissimilarity matrixFor the Jaccard coefficient, joint absences are excluded: $J=n_{11}/(n_{11}+n_{10}+n_{01})$. Thus the Jaccard distance is $1-J$, givingOnly the pair of individuals two and four has a joint absence. Their profiles have one shared presence, two mismatched presences and one joint absence, giving dissimilarities $2/4$ and $2/3$, respectively. All other pairs have a presence in at least one profile at every coordinate, so the two denominators coincide.

For the requested metric property of simple matching dissimilarity, write a general pair of $p$-coordinate binary profiles as $x,y$. Thenwhich is the normalized Hamming distance. It is nonnegative and symmetric, and equals zero exactly when all coordinates match. For each coordinate, a mismatch between $x_j$ and $z_j$ forces a mismatch between $x_j,y_j$ or between $y_j,z_j$. ThereforeSumming and dividing by $p$ proves the triangle inequality, establishing all four metric properties. Simple matching dissimilarity is a metric on binary profiles. If two separately labelled individuals have identical profiles, it gives zero distance between them, so on those labels it is only a pseudometric. The four profiles here are distinct, so this distinction does not prevent $D_S$ from defining a metric on the given sample.

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, $d(C,D)=10.3>5.9+1.2$. 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 $A,D$, merging at $1.2$. Among the remaining clusters the next closest pair is $B,E$, merging at $2.6$. The three intercluster dissimilarities are nowConsequently $AD$ merges with $BE$ at $4.2$, using the cross-pair $A,B$. The remaining point $C$ joins at $\min (5.9,7.6,10.3,5.4)=5.4$, using $C,E$. The dendrogram thus hasThe close pairs $AD$ and $BE$ are the clearest early groupings. A cut between $2.6$ and $4.2$ produces these two pairs and the singleton $C$; a cut between $4.2$ and $5.4$ produces $ADBE$ and $C$. Single-linkage clustering builds chains through close cross-pairs, so the merge at $4.2$ does not mean every pair in $ADBE$ is that close: $d(D,E)=7.8$. 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 $AD$ at $1.2$ and $BE$ at $2.6$. SubsequentlyThus $C$ joins $BE$ at $7.6$. The final maximum between $AD$ and $BCE$ is $d(D,C)=10.3$, givingBoth the topology and the later heights of the dendrogram change: complete-linkage clustering attaches $C$ to $BE$ before joining that group to $AD$, 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.