Distance and Linkage Choices for Profile Clustering

Why Distance and Linkage Both Matter

Agglomerative hierarchical clustering repeatedly merges the two closest remaining objects, beginning with individual profiles and eventually forming one cluster. The meaning of “closest” depends on two choices: a dissimilarity between profiles and a linkage rule for measuring dissimilarity between clusters. These choices can change not just the heights of merges in a dendrogram, but which profiles are grouped together.

In genomic data, a profile may record measurements across genes, genomic regions, or other features. Before computing distances, the analyst must decide whether differences in measurement magnitude or differences in profile shape are scientifically relevant. The earlier material on distance concentration highlights an additional concern: in many dimensions, distances can become less discriminating. A distance calculation is therefore not a neutral step; it encodes what “similar profiles” means.

Definition: For two profiles \(x_i=(x_{i1},\ldots,x_{ip})\) and \(x_j=(x_{j1},\ldots,x_{jp})\) measured on the same \(p\) features, a dissimilarity \(d(i,j)\) is a nonnegative measure of their separation, with smaller values indicating greater similarity. A linkage rule defines the dissimilarity between two clusters from the dissimilarities between their members.

Distances require comparable measurements across profiles. If one feature is measured on a much larger numerical scale than others, it can dominate some distance calculations. Feature-wise standardization (centering and scaling each feature across profiles) is one common response when features have different units or scales and should contribute comparably. It is not automatically appropriate: if absolute variation across features is meaningful, scaling can remove information. Standardization also does not make the resulting features independent or remove outliers.

Feature-wise standardization and profile-wise centering are different operations. The former transforms each feature across the sample. The latter subtracts a profile’s own mean across its features, as part of calculating its correlation with another profile. Correlation dissimilarity focuses on pattern across features and is insensitive to a profile’s additive level and positive scale. Decide which form of similarity is relevant before choosing between these approaches.

Three Dissimilarities for Profiles

For profiles \(x_i\) and \(x_j\), Euclidean distance is the square root of the sum of squared feature-wise differences. Manhattan distance is the sum of the absolute feature-wise differences. Both use the measurement values directly, so level and magnitude differences contribute to separation.

d_E(i,j)=\sqrt{\sum_{g=1}^{p}(x_{ig}-x_{jg})^2}, \qquad d_M(i,j)=\sum_{g=1}^{p}|x_{ig}-x_{jg}|.

Euclidean distance gives greater influence to large individual discrepancies because differences are squared. Manhattan distance accumulates absolute discrepancies and is less dominated by a single large difference, although it is not immune to outliers. The two measures can rank pairs differently, particularly when one pair has a few large differences and another has many moderate ones.

The Pearson correlation \(r_{ij}\) between two profiles is their centered cross-product divided by the product of their centered lengths. A common correlation dissimilarity is \(d_C(i,j)=1-r_{ij}\). It is small when profiles have similar patterns across features, regardless of a positive shift or rescaling of either profile. A correlation of \(-1\) gives dissimilarity 2, not 0.

r_{ij}= \frac{\sum_{g=1}^{p}(x_{ig}-\bar{x}_i)(x_{jg}-\bar{x}_j)} {\sqrt{\sum_{g=1}^{p}(x_{ig}-\bar{x}_i)^2 \sum_{g=1}^{p}(x_{jg}-\bar{x}_j)^2}}, \qquad d_C(i,j)=1-r_{ij}.

Each profile must have nonzero variation across features for this correlation to be defined. Correlation is usually unstable as a summary of pattern when calculated across very few features. Also, \(1-r\) is a dissimilarity but is not generally a metric: in particular, it need not satisfy the triangle inequality. It should not be treated as an ordinary Euclidean distance without justification.

Worked Example: Euclidean and Manhattan Distances Can Rank Pairs Differently

Suppose three hypothetical profiles have two already comparable feature coordinates: \(A=(0,0)\), \(B=(2,0)\), and \(C=(1,1.5)\). These coordinates are illustrative common-scale measurements. Calculate the distances for each pair.

For \(A\) and \(B\), \(d_E(A,B)=\sqrt{(0-2)^2+(0-0)^2}=\sqrt{4}=2\), and \(d_M(A,B)=|0-2|+|0-0|=2\).

For \(A\) and \(C\), \(d_E(A,C)=\sqrt{(0-1)^2+(0-1.5)^2}=\sqrt{3.25}\approx1.803\), while \(d_M(A,C)=|0-1|+|0-1.5|=2.5\).

By symmetry, \(d_E(B,C)=\sqrt{3.25}\approx1.803\), and \(d_M(B,C)=2.5\). Thus Euclidean distance makes \(A\)-\(C\) and \(B\)-\(C\) the closest pairs (tied), whereas Manhattan distance makes \(A\)-\(B\) the closest pair. If these are the only three profiles, the first hierarchical merge differs by distance choice. The numbers are hypothetical; in an actual analysis, feature scaling and the relevance of the two features would need to be justified.

Worked Example: Correlation Dissimilarity Compares Pattern

Consider hypothetical profiles \(A=(1,2,3,4)\), \(B=(1,2,4,3)\), and \(C=(1,2,3,5)\), each measured over four features. For \(A\) and \(C\), the means are \(\bar{x}_A=2.5\) and \(\bar{x}_C=2.75\). Their centered vectors are \((-1.5,-0.5,0.5,1.5)\) and \((-1.75,-0.75,0.25,2.25)\).

The centered cross-product sum is \(2.625+0.375+0.125+3.375=6.5\). The centered sums of squares are \(5\) for \(A\) and \(3.0625+0.5625+0.0625+5.0625=8.75\) for \(C\). Therefore,

r_{AC}=\frac{6.5}{\sqrt{5(8.75)}}=\frac{6.5}{\sqrt{43.75}} \approx 0.9827, \qquad d_C(A,C)=1-r_{AC}\approx 0.01729.

For \(A\) and \(B\), the centered vectors are \((-1.5,-0.5,0.5,1.5)\) and \((-1.5,-0.5,1.5,0.5)\). Their cross-product sum is \(4\), and each centered sum of squares is \(5\), so \(r_{AB}=4/\sqrt{25}=0.8\) and \(d_C(A,B)=0.2\). Under correlation dissimilarity, \(A\) and \(C\) have much more similar profiles than \(A\) and \(B\). This describes similarity of pattern across these features, not similarity of absolute expression level.

Linkage Rules and Their Consequences

Once profile-to-profile dissimilarities have been defined, linkage determines how to compare clusters. For clusters \(G\) and \(H\), single linkage uses the closest cross-cluster pair, complete linkage uses the most distant pair, and average linkage uses the mean cross-cluster dissimilarity. Here \(|G|\) denotes the number of profiles in cluster \(G\).

D_{\text{single}}(G,H)=\min_{i\in G,\,j\in H}d(i,j), \qquad D_{\text{complete}}(G,H)=\max_{i\in G,\,j\in H}d(i,j), \qquad D_{\text{average}}(G,H)= \frac{1}{|G||H|} \sum_{i\in G}\sum_{j\in H}d(i,j).

Single linkage can connect clusters through a chain of near neighbors even when the endpoints of the chain are far apart. Complete linkage discourages clusters with distant members, but a single unusual profile can determine its maximum. Average linkage summarizes all cross-cluster pairs; its value can still be affected by outliers and cluster composition.

Ward linkage is a different kind of rule. With Euclidean coordinates, it merges the pair of clusters that produces the smallest increase in the total within-cluster sum of squared deviations from cluster means. For clusters \(G\) and \(H\), the increase is

\Delta(G,H)= \frac{|G||H|}{|G|+|H|} \left\|\bar{x}_G-\bar{x}_H\right\|^2,

where \(\bar{x}_G\) and \(\bar{x}_H\) are the coordinate-wise cluster means. This criterion favors compact groups under squared Euclidean geometry. Ward linkage is not simply another formula for combining arbitrary dissimilarities: its standard sum-of-squares interpretation requires Euclidean feature coordinates. Applying it to correlation dissimilarities, for example, does not automatically preserve that interpretation.

Worked Example: Linkage Changes the Next Merge

Use hypothetical two-feature profiles \(A=(0,0)\), \(B=(1,0)\), \(C=(-1.1,0)\), and \(D=(0.5,1.5)\), with Euclidean dissimilarity. The closest pair is \(A,B\), at distance 1, so all three agglomerative rules considered next begin with \(G=\{A,B\}\).

The distances from \(A\) to \(C\) and \(B\) to \(C\) are 1.1 and 2.1. Thus the single-link distance from \(G\) to \(C\) is 1.1, the complete-link distance is 2.1, and the average-link distance is \((1.1+2.1)/2=1.6\).

The distances from \(A\) to \(D\) and \(B\) to \(D\) are both \(\sqrt{(0.5)^2+(1.5)^2}=\sqrt{2.5}\approx1.581\). Consequently, all three linkage distances from \(G\) to \(D\) are approximately 1.581. The remaining distance between \(C\) and \(D\) is \(\sqrt{(1.6)^2+(1.5)^2}=\sqrt{4.81}\approx2.193\).

Single linkage therefore merges \(G\) with \(C\) next, because \(1.1\) is the smallest candidate distance. Complete linkage instead merges \(G\) with \(D\), because \(1.581\) is less than both \(2.1\) and \(2.193\). Average linkage also merges \(G\) with \(D\), because \(1.581\) is less than both \(1.6\) and \(2.193\). The same observations and Euclidean distance thus produce different cluster membership at the next step solely because the linkage rule changes.

A Practical Choice and Its Checks

A defensible analysis connects the dissimilarity and linkage to the scientific meaning of a profile. If absolute differences across scaled features matter, Euclidean or Manhattan distance may be suitable. If relative pattern across features matters more than a profile’s level or positive scale, correlation dissimilarity may be useful. If a compact partition under squared Euclidean variation is the goal, Ward linkage is a natural candidate, provided its geometric assumptions are met.

Before interpreting a dendrogram, check the input and the consequences of the choices. Confirm that profiles are measured on the same features and that missing values have not been handled in a way that makes pairwise distances incomparable. Inspect feature scales and unusually influential observations. Compare plausible scaling, dissimilarity, and linkage choices: a dramatic change in early merges signals that the grouping is choice-sensitive, not that one dendrogram has revealed a uniquely correct answer. In high dimensions, also ask whether distance values distinguish profiles usefully, rather than assuming that a computed distance is informative.

There is no universally best combination. Euclidean and Manhattan distances retain level and magnitude information; correlation focuses on shape and can discard meaningful level differences. Single linkage can reveal chains but may create elongated clusters, while complete and average linkage respond differently to extreme cross-cluster pairs. Ward’s compactness objective is specific to Euclidean sum-of-squares geometry. These methods describe structure in the chosen representation; clustering alone does not establish biological categories or causal mechanisms.

Common Mistakes

Assuming standardization is automatic. Standardizing can prevent scale dominance, but can also give noisy or low-variance features undue influence. Explain why features should contribute comparably before scaling.
Calling \(1-r\) an ordinary metric. It is a useful correlation dissimilarity, but it need not satisfy the triangle inequality. Do not assume results that require metric or Euclidean geometry.
Confusing profile shape with profile level. Two profiles can have correlation 1 while differing greatly in magnitude. Use correlation when pattern is the target, not as a substitute for checking level.
Treating linkage as a cosmetic setting. As the four-profile example shows, linkage can change which cluster forms next, not merely the vertical scale of the dendrogram.
Using Ward linkage with any dissimilarity by default. Its standard interpretation is the increase in within-cluster sum of squares under Euclidean coordinates; arbitrary dissimilarities do not inherit that meaning.

Key takeaway: Clustering results depend jointly on what profile differences count, how features are scaled, and how cluster-to-cluster dissimilarity is defined. State these choices, check their assumptions, and examine whether the resulting groups are sensitive to reasonable alternatives.

Check Your Understanding

Try each question, then compare your reasoning with the solutions.

For \(x=(0,0)\) and \(y=(3,4)\), calculate Euclidean and Manhattan distance. Which is larger?
What aspect of two profiles does \(1-r\) emphasize, and what important aspect can it ignore?
Two clusters have all cross-cluster dissimilarities equal to 2, 4, 5, and 9. Calculate their single-, complete-, and average-link distances.
Why can single linkage produce a chain-like cluster, and how does complete linkage respond differently?
Why does Ward linkage require care when the input is a correlation dissimilarity matrix?

Solutions. (1) \(d_E=\sqrt{3^2+4^2}=5\), while \(d_M=|3|+|4|=7\); Manhattan distance is larger. (2) It emphasizes similarity in centered profile pattern across features; it can ignore absolute level and positive scale. (3) Single linkage is the minimum, 2; complete linkage is the maximum, 9; average linkage is \((2+4+5+9)/4=5\). (4) Single linkage merges clusters whenever any pair of members is close, allowing a sequence of near neighbors to connect distant endpoints. Complete linkage uses the most distant cross-pair, discouraging such a merge when any members are far apart. (5) Ward’s usual interpretation is minimizing the increase in within-cluster squared deviations in Euclidean coordinates. A correlation dissimilarity is not generally a Euclidean distance, so that sum-of-squares interpretation does not automatically apply.