Distance & Similarity Measures

A distance is part of the model. It tells an algorithm which changes should count as small, which should count as large, and which should not matter at all. Two perfectly implemented clustering runs can therefore reveal different, equally coherent structures because their geometries encode different questions.

Metric, dissimilarity, and similarity are different contracts #

The distinction matters because some indexes and algorithms use metric properties to prune work or prove behaviour. Cosine similarity is an angle-based score; $1-\text{cosine similarity}$ is a useful dissimilarity but is not a metric on arbitrary vectors. Squaring Euclidean distance preserves nearest-neighbour ordering but breaks the triangle inequality. Do not call a score a metric merely because a library places it in a distance module.

Numeric distances encode different notions of change #

For $x,y\in\mathbb R^p$, the Minkowski family is

$$d_q(x,y)=\left(\sum_{j=1}^{p}|x_j-y_j|^q\right)^{1/q},\qquad q\ge 1.$$

The exponent is not a robustness switch in isolation. Scaling, outliers, sparsity, and the downstream objective jointly determine behaviour. For $0<q<1$, the same expression is a quasi-metric: it encourages sparse coordinate differences but violates the triangle inequality.

Scale is a weighting decision #

If age is measured in years and income in euros, raw Euclidean distance lets the numerically larger unit dominate. Standardization replaces each difference with $(x_j-y_j)/s_j$, where $s_j$ is a training-set scale such as standard deviation or a robust alternative. This is equivalent to a diagonal weighted distance.

Standardized Euclidean distance still treats features as independent. Mahalanobis distance introduces a positive-semidefinite matrix $A$:

$$d_A(x,y)=\sqrt{(x-y)^\top A(x-y)}.$$

If $A=\Sigma^{-1}$, differences along high-variance correlated directions count less. More generally, $A=L^\top L$ means “transform by $L$, then use Euclidean distance.” A singular $A$ is allowed as a pseudometric: some directions collapse to zero because the model declares them irrelevant.

Direction, overlap, and exact mismatch answer different questions #

Cosine similarity

$$s_{\cos}(x,y)=\frac{x^\top y}{\lVert x\rVert_2\lVert y\rVert_2}$$

compares direction and discards magnitude. That is useful for term-frequency vectors when document length is nuisance information, but wrong when magnitude carries the signal. It is undefined for a zero vector unless an explicit convention is chosen.

For binary or set-valued data, distinguish presence from agreement:

• Hamming distance counts coordinate mismatches, including a 0/1 and a 1/0 symmetrically.
• Jaccard similarity $|A\cap B|/|A\cup B|$ ignores joint absences, so two sparse records are not judged similar merely because both lack thousands of features.
• Simple matching counts joint absences as agreements and is appropriate only when absence is informative.

Correlation distance removes both location and scale before comparing shape. It can call $(1,2,3)$ and $(100,200,300)$ identical; that is a feature or a bug depending on the question.

Mixed records need an explicit composite #

One distance rarely makes sense for numeric, ordinal, categorical, and set-valued columns simultaneously. A transparent composite is

$$D(x,y)=\frac{\sum_j w_j\,\delta_j(x_j,y_j)\,m_j(x,y)} {\sum_j w_j\,m_j(x,y)},$$

where $\delta_j$ is a type-appropriate per-feature dissimilarity, $w_j$ is an explicit importance weight, and $m_j$ is 1 only when feature $j$ is comparable for this pair. The denominator prevents pairs with more observed fields from automatically looking farther apart.

k-prototypes uses a less general but computationally convenient objective: squared numeric distance plus $\gamma$ times the number of categorical mismatches. The numeric centre is a mean and the categorical centre is a mode. Its $\gamma$ is not discovered by the formula; it is the exchange rate between two kinds of error and must be tuned or justified.

Distance between clusters is another decision #

A point metric does not determine hierarchical linkage. Single linkage uses the nearest cross-cluster pair and can form chains; complete linkage uses the farthest pair and favours compact groups; average linkage averages cross-pair distances. Ward's method is different again: it merges the pair that causes the smallest increase in within-cluster squared error and therefore belongs with Euclidean variance geometry, not an arbitrary dissimilarity matrix.

High dimensions flatten neighbourhoods #

As many weakly informative coordinates accumulate, nearest and farthest distances can become similar. Adding dimensions can therefore make “nearest” unstable even though every coordinate is valid. Feature selection, representation learning, sparsity-aware measures, or a learned metric may restore contrast, but each introduces supervised assumptions that must be validated out of sample.

A selection checklist #

1. State what transformations should leave similarity unchanged: translation, rotation, scale, magnitude, or category relabelling.
2. Separate semantic feature importance from measurement units.
3. Decide whether joint absence is evidence of similarity.
4. Define missing-value comparability instead of silently filling values.
5. Check the downstream algorithm's contract: metric, arbitrary dissimilarity, squared Euclidean objective, or kernel.
6. Fit all data-dependent geometry on training data and evaluate the entire pipeline.
7. Inspect neighbour examples and perturb individual features; a distance is understandable only when its local consequences match the domain question.