Similarity and Distance

At the heart of every clustering algorithm lies a deceptively simple question: How similar are two data points? This question seems trivial—we can often tell at a glance whether two objects are alike. But translating human intuition about similarity into mathematical precision reveals surprising depth and complexity.

The choice of similarity or distance measure is arguably the most important decision in clustering. Two clustering runs on identical data with identical algorithms can produce completely different results based solely on the distance metric. A metric that works beautifully for images may fail catastrophically for text; a measure ideal for low dimensions may become meaningless in high dimensions.

This page equips you with a rigorous understanding of distance and similarity: the mathematical properties they must satisfy, the most important metrics for different data types, and the crucial considerations for choosing the right measure for your problem.

Before diving into specific measures, we must distinguish between two related but fundamentally different concepts: distance and similarity. While they're often used interchangeably in casual discussion, they have distinct mathematical properties.

Distance (Dissimilarity):

A distance function $d: X \times X \rightarrow \mathbb{R}$ quantifies how different two objects are. Higher values mean objects are more dissimilar. Distances are unbounded above—there's no maximum distance.

Similarity:

A similarity function $s: X \times X \rightarrow \mathbb{R}$ quantifies how alike two objects are. Higher values mean objects are more similar. Similarities are often bounded (e.g., between 0 and 1).

The Relationship:

Distance and similarity are inversely related. Given a distance $d$, common transformations to similarity include:

$$s = \frac{1}{1 + d} \quad \text{(bounded between 0 and 1)}$$

$$s = e^{-d} \quad \text{(exponential decay)}$$

$$s = e^{-d^2/2\sigma^2} \quad \text{(Gaussian kernel)}$$

Conversely, given a bounded similarity in $[0, 1]$:

$$d = 1 - s \quad \text{(linear transformation)}$$

$$d = -\log(s) \quad \text{(logarithmic, for positive similarities)}$$

A metric (or distance function) on a set $X$ is a function $d: X \times X \rightarrow \mathbb{R}$ that satisfies four fundamental properties. Understanding these properties is crucial because they guarantee that our intuitive notion of "distance" behaves consistently.

The Four Axioms of a Metric:

For all $x, y, z \in X$:

1. Non-negativity: $d(x, y) \geq 0$

   • Distance is never negative. Two points can be identical (distance 0) but never "negatively distant."

2. Identity of Indiscernibles: $d(x, y) = 0 \Leftrightarrow x = y$

   • Zero distance means the points are identical, and vice versa.

3. Symmetry: $d(x, y) = d(y, x)$

   • The distance from A to B equals the distance from B to A.

4. Triangle Inequality: $d(x, z) \leq d(x, y) + d(y, z)$

   • The direct path is never longer than going through an intermediate point.

Relaxed Notions:

Not all useful measures satisfy all four axioms:

• Pseudometric: Violates identity (distinct points can have zero distance). Example: distance between equivalence classes.

• Quasimetric: Violates symmetry ($d(x,y) eq d(y,x)$). Example: travel time with one-way streets.

• Semimetric: Violates triangle inequality. Example: some edit distances.

Clustering algorithms often work with measures that aren't true metrics. This is fine, but you should be aware of which guarantees you're losing and how that affects algorithm behavior.

The most widely used distances for numerical data belong to the Minkowski family, parameterized by a single value $p \geq 1$. For vectors $x, y \in \mathbb{R}^d$:

$$d_p(x, y) = \left( \sum_{i=1}^{d} |x_i - y_i|^p \right)^{1/p}$$

This elegant formulation unifies several important distances under a single framework.

Geometric Interpretation:

Different values of $p$ define different shapes for the "unit ball" (the set of all points at distance 1 from the origin):

• $p = 1$: Diamond/hypercube rotated 45°
• $p = 2$: Circle/hypersphere (round)
• $p \rightarrow \infty$: Square/hypercube aligned with axes

This geometric difference has profound implications for clustering. Euclidean distance treats all directions equally, while Manhattan distance emphasizes axis-aligned differences.

When to Use Each:

For many applications, the magnitude of vectors is irrelevant—only their direction matters. Cosine similarity measures the angle between vectors, making it ideal for comparing documents, user preferences, or any data where scale is arbitrary.

Definition:

$$\cos(x, y) = \frac{x \cdot y}{|x|2 \cdot |y|2} = \frac{\sum{i=1}^{d} x_i y_i}{\sqrt{\sum{i=1}^{d} x_i^2} \cdot \sqrt{\sum_{i=1}^{d} y_i^2}}$$

This measures the cosine of the angle $\theta$ between vectors:

• $\cos(x, y) = 1$ when vectors point in the same direction ($\theta = 0°$)
• $\cos(x, y) = 0$ when vectors are orthogonal ($\theta = 90°$)
• $\cos(x, y) = -1$ when vectors point in opposite directions ($\theta = 180°$)

Converting to Distance:

Cosine similarity ranges from -1 to 1 (for general vectors) or 0 to 1 (for non-negative vectors). Common distance transformations:

$$d_{\text{cosine}}(x, y) = 1 - \cos(x, y) \quad \text{(cosine distance, range [0, 2])}$$

$$d_{\text{angular}}(x, y) = \frac{\arccos(\cos(x, y))}{\pi} \quad \text{(angular distance, range [0, 1])}$$

Relationship to Euclidean Distance:

For L2-normalized vectors (where $|x|_2 = |y|_2 = 1$), there's a beautiful relationship:

$$|x - y|_2^2 = 2(1 - \cos(x, y))$$

This means that for normalized data, Euclidean distance and cosine distance are monotonically related. Clustering with either gives the same results when data is normalized.

Important Caveat:

Cosine distance is not a metric—it violates the triangle inequality. This means:

• Ball trees and KD-trees won't work correctly
• Hierarchical clustering may behave unexpectedly
• Always verify that your algorithm is compatible with non-metric distances

Numerical distances like Euclidean don't apply to categorical data. You can't compute the "average" of {red, blue, green} or the "distance" between married and single. Specialized measures are required.

Simple Matching Coefficient:

For two categorical vectors $x, y$ with $d$ attributes:

$$d_{\text{simple}}(x, y) = \frac{\text{number of mismatches}}{d} = \frac{\sum_{i=1}^{d} \mathbb{1}[x_i eq y_i]}{d}$$

This treats each attribute equally and counts disagreements.

Hamming Distance:

$$d_{\text{Hamming}}(x, y) = \sum_{i=1}^{d} \mathbb{1}[x_i eq y_i]$$

The unnormalized count of differences. Originally defined for binary strings, but extends to any categorical data.

Jaccard Similarity (for Sets):

When features represent presence/absence (binary categorical), Jaccard measures the overlap:

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

Jaccard distance: $d_J(A, B) = 1 - J(A, B)$

This is particularly useful for:

• Document similarity (sets of words)
• User preferences (sets of liked items)
• Biological data (sets of genes/proteins)

Gower's Distance (Mixed Data):

Real-world data often mixes numerical and categorical features. Gower's distance handles this:

$$d_{\text{Gower}}(x, y) = \frac{\sum_{i=1}^{d} w_i \cdot d_i(x_i, y_i)}{\sum_{i=1}^{d} w_i}$$

where $d_i$ is an appropriate distance for feature $i$:

• For numerical: $d_i = |x_i - y_i| / \text{range}_i$
• For categorical: $d_i = \mathbb{1}[x_i eq y_i]$
• For ordinal: Can use rank difference

$w_i$ are feature weights (default 1, set to 0 for missing values).

Different domains have developed specialized distance measures tailored to their data characteristics. Understanding these expands your toolkit for real-world clustering problems.

Mahalanobis Distance:

Euclidean distance treats all features equally and assumes independence. Mahalanobis distance accounts for correlations and different variances:

$$d_M(x, y) = \sqrt{(x - y)^T \Sigma^{-1} (x - y)}$$

where $\Sigma$ is the covariance matrix of the data. This effectively:

• Normalizes each feature by its standard deviation
• Decorrelates correlated features
• Makes equidistant contours into ellipsoids aligned with the data distribution

When to use: When features have different scales or strong correlations; when you want distance relative to the data's natural variation.

Correlation-Based Distance:

Pearson correlation measures linear relationship between vectors:

$$r(x, y) = \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_i (x_i - \bar{x})^2} \cdot \sqrt{\sum_i (y_i - \bar{y})^2}}$$

Correlation distance: $d_r(x, y) = 1 - r(x, y)$

This measures whether vectors increase and decrease together, regardless of their absolute values or scales. Common in gene expression analysis where expression "profiles" matter.

Domain-Specific Examples:

One of the most important phenomena affecting distance-based methods is the curse of dimensionality. As the number of dimensions increases, distances behave in counterintuitive ways that can break clustering algorithms.

The Concentration of Distances:

Consider $n$ random points uniformly distributed in a $d$-dimensional unit hypercube. As $d$ increases:

$$\frac{d_{\max} - d_{\min}}{d_{\min}} \rightarrow 0 \quad \text{as } d \rightarrow \infty$$

This means that the relative difference between the nearest and farthest points vanishes. All points become approximately equidistant from each other! When everything is equally far apart, the concept of "nearest neighbor" becomes meaningless.

Why Does This Happen?

In high dimensions:

1. Volume concentrates at edges: In a hypercube, almost all volume is near the corners, not the center. A "shell" near the surface contains most points.

2. Many small contributions add up: Euclidean distance squares differences and sums them. With 1000 dimensions, even tiny per-dimension differences accumulate to large total distances.

3. Random vectors are nearly orthogonal: Random vectors in high dimensions are almost always perpendicular to each other, making angles uninformative.

Mitigation Strategies:

A Quantitative Example:

For $n$ points uniformly distributed in $[0, 1]^d$, the expected distance to the nearest neighbor scales as:

$$E[d_{\text{nearest}}] \propto n^{-1/d}$$

As $d$ increases, this approaches 1 (the diameter of the space) for any fixed $n$. To maintain the same expected nearest-neighbor distance as $d$ doubles, you need exponentially more data points.