Distance Metrics and Similarity Measures

A distance metric is a function $d: X \times X \to \mathbb{R}_{\ge 0}$ that quantifies dissimilarity between two points in a space $X$. For $d$ to qualify as a true metric, it must satisfy four axioms for all points $x, y, z$:

The triangle inequality is the deepest of these: it guarantees that distances behave consistently, so that "if $x$ is near $y$ and $y$ is near $z$, then $x$ cannot be too far from $z$." Algorithms that exploit spatial pruning (like ball-trees or DBSCAN's neighborhood queries) rely on this property for both correctness and speed. A similarity measure, by contrast, increases as points become more alike rather than less. Cosine similarity is the canonical example — it is not a metric in the strict sense (it fails the identity and triangle-inequality axioms without transformation), yet it is one of the most widely used comparison functions in high-dimensional and text-based unsupervised learning. Similarity and distance are convertible: $d = 1 - s$ or $d = \sqrt{2(1-s)}$ are common conversions when a similarity score needs to be plugged into a distance-based algorithm. The choice between these functions encodes an assumption about what "shape" of neighborhood matters. Euclidean distance treats all directions equally, producing spherical neighborhoods. Manhattan distance moves only along axes, producing diamond-shaped neighborhoods. Cosine similarity discards magnitude entirely, comparing only orientation. Mahalanobis distance stretches and rotates space according to feature covariance, producing ellipsoidal neighborhoods aligned with the data's own correlation structure. Every clustering algorithm downstream inherits exactly this geometry.

The four core measures

Euclidean distance (also $L_2$ distance) between vectors $x, y \in \mathbb{R}^n$:

This is straight-line distance — the generalization of the Pythagorean theorem to $n$ dimensions. It is the default assumption behind k-means, which minimizes total squared Euclidean distance to cluster centroids.

Manhattan distance (also $L_1$ or "city-block" distance):

This measures distance as if movement were restricted to a grid of streets (hence "city block"). It grows linearly rather than quadratically with per-coordinate deviation, making it less sensitive to a single large discrepancy — a useful robustness property when data has outliers or heavy-tailed noise.

Cosine similarity measures the angle $\theta$ between two vectors, ignoring their length:

Cosine similarity ranges over $[-1, 1]$ (or $[0,1]$ for non-negative data like word counts). A common cosine distance is $d_{\cos}(x,y) = 1 - \cos(\theta)$. This measure is preferred for text documents represented as word-frequency vectors, where document length (magnitude) is irrelevant but topical direction is what matters.

Mahalanobis distance incorporates the covariance structure $\Sigma$ of the data:

When $\Sigma$ is the identity matrix, this reduces exactly to Euclidean distance. When features are correlated or on different scales, $\Sigma^{-1}$ rescales and rotates the space so that one unit of Mahalanobis distance corresponds to one standard deviation along every direction, including diagonal directions defined by correlated features.

Step-by-step procedure for choosing and applying a metric

``` ALGORITHM: SelectAndApplyDistanceMetric INPUT: data matrix X (n points × d features), metric choice M OUTPUT: pairwise distance matrix D (n × n) 1. Inspect feature scales. IF features have very different units/ranges: standardize X (zero mean, unit variance per feature) OR use Mahalanobis distance with covariance estimated from X 2. Inspect feature correlation. IF features are strongly correlated: prefer Mahalanobis distance compute Sigma = Covariance(X) compute Sigma_inv = Inverse(Sigma) // or pseudo-inverse if singular 3. Inspect data semantics. IF data is sparse / high-dimensional (e.g. text, TF-IDF vectors): prefer cosine distance: d(x,y) = 1 - dot(x,y) / (norm(x) norm(y)) ELSE IF outliers/robustness matter: prefer Manhattan distance ELSE: default to Euclidean distance 4. Compute pairwise distances: FOR i in 1..n: FOR j in i+1..n: SWITCH M: CASE Euclidean: D[i][j] = sqrt(sum((X[i]-X[j])^2)) CASE Manhattan: D[i][j] = sum(abs(X[i]-X[j])) CASE Cosine: D[i][j] = 1 - dot(X[i],X[j]) / (norm(X[i])norm(X[j])) CASE Mahalanobis: diff = X[i]-X[j] D[i][j] = sqrt(diff^T Sigma_inv diff) D[j][i] = D[i][j] // symmetry D[i][i] = 0 for all i // identity 5. RETURN D ``` The algorithm is intentionally simple — the intellectual work happens in steps 1–3, the diagnosis of the data, not step 4, the arithmetic. This mirrors real practice: choosing the metric is a modeling decision, not a computational one.

The picture is the entire point: k-means with Euclidean distance can only ever discover circular (spherical, in higher dimensions) clusters, because its notion of "close" is a circle. Feed it elongated or correlated clusters and it will slice them incorrectly. Mahalanobis distance fixes exactly this failure by letting the "ball" become an ellipse aligned with the true covariance of the data.

Time complexity. Computing a single Euclidean, Manhattan, or cosine distance between two $d$-dimensional vectors takes $O(d)$ time — one pass over the coordinates. Computing the full pairwise distance matrix for $n$ points takes $O(n^2 d)$ time, since there are $O(n^2)$ pairs. This is unavoidable if all pairwise distances are genuinely required, though many algorithms (e.g., DBSCAN with spatial indexing) avoid materializing the full matrix by using k-d trees or ball-trees, reducing effective query cost to $O(\log n)$ per neighbor lookup in favorable dimensions. Mahalanobis distance is more expensive per pair: computing $(x-y)^\top \Sigma^{-1}(x-y)$ naively costs $O(d^2)$ because of the matrix-vector product, and the one-time cost of inverting the $d \times d$ covariance matrix is $O(d^3)$ (or $O(d^{2.37})$ with fast matrix multiplication, though this is rarely used in practice). For the full pairwise matrix this gives $O(n^2 d^2 + d^3)$. In practice, one instead computes the Cholesky factor $\Sigma^{-1} = L L^\top$ once ($O(d^3)$) and transforms all points via $x' = L^\top x$ ($O(nd^2)$ total), after which ordinary Euclidean distance in the transformed space reproduces Mahalanobis distance in $O(n^2 d)$ — the standard efficient implementation.

Space complexity. Storing the full pairwise distance matrix requires $O(n^2)$ space, which becomes prohibitive for large $n$ (a million points would need $10^{12}$ entries). Most production systems avoid this by computing distances on demand or using approximate nearest-neighbor structures.

Correctness — verifying the metric axioms. Euclidean and Manhattan distance are both instances of the general Minkowski distance family:

with $p=2$ giving Euclidean and $p=1$ giving Manhattan. The triangle inequality for this family is exactly Minkowski's inequality, a classical result in real analysis valid for all $p \ge 1$:

Substituting $u = x - y$, $v = y - z$ gives $d_p(x,z) = \|u+v\|_p \le \|u\|_p + \|v\|_p = d_p(x,y) + d_p(y,z)$, confirming the triangle inequality holds. Non-negativity, identity, and symmetry follow directly from the definition of absolute value and the even power in the $p=2$ case. Both are therefore bona fide metrics. Cosine distance is not a true metric in general. Consider three unit vectors where $\cos(\theta)$ can produce a violation of the triangle inequality in edge cases involving negative similarity; more fundamentally, cosine similarity itself is scale-invariant ($\cos$ of $x$ and $2x$ is $1$, meaning $d_{\cos}=0$ for distinct vectors), which directly violates the identity axiom ($d(x,y)=0$ should imply $x=y$). This is a deliberate and useful design choice: for text and embedding vectors, the magnitude is often an artifact of document length or normalization, and discarding it is exactly the point. The angular distance $d_\theta = \arccos(\cos(\theta))/\pi$ is a true metric (it does satisfy the triangle inequality since it is proportional to true angular separation on the unit sphere) and is used when metric guarantees are required alongside cosine-style comparison. Mahalanobis distance is a true metric whenever $\Sigma$ is symmetric positive definite. This follows because $d_{\text{Mah}}(x,y) = \|L^\top(x - y)\|_2$ for $L$ the Cholesky factor of $\Sigma^{-1}$ — i.e., it is exactly Euclidean distance after a fixed linear transformation. Since Euclidean distance is a metric and linear transformations preserve the triangle inequality (it is inherited via the transformed vectors), Mahalanobis distance inherits all four metric axioms directly.

Why this all matters for clustering correctness. k-means minimizes within-cluster sum of squared Euclidean distances; its convergence proof (monotonic decrease of the objective, guaranteed by Lloyd's algorithm) is specific to the Euclidean case. Using cosine similarity inside a naive k-means loop breaks this convergence guarantee unless the algorithm is adapted (spherical k-means normalizes centroids at each step to restore a valid objective). This is a direct, concrete instance of why the distance function is not swappable without re-examining the algorithm's correctness proof.

Consider four two-dimensional points representing customers by (annual spend in thousands, visits per year), before any standardization:

Naively, spend dominates because its scale (10–205) dwarfs visits (2–50). Compute Euclidean distance $d_E(A,B)$:

Under raw Euclidean distance, $A$ and $B$ (very different visit behavior, similar spend) look far closer to $A$ and $C$ (identical visit behavior, wildly different spend) — yet $d_E(A,B) \approx 48$ is much smaller than $d_E(A,C)\approx 190$, meaning Euclidean distance says $A$ is closer to $B$. That may or may not match intuition, but the danger is scale dominance: visits (range ~48) is contributing almost the entire distance value while spend differences of 190 units barely register relative to it in some comparisons. Let's check the full matrix to see the distortion clearly.

Here the pattern actually survives: $\{A,B\}$ and $\{C,D\}$ both cluster tightly (distances ~45–50) while cross-pairs are ~190–240, because the visits feature happens to separate the two true groups cleanly. But this is a fragile coincidence of the numbers chosen — in general, when one feature's scale dwarfs another's, Euclidean distance is dictated almost entirely by the large-scale feature, silently discarding the other feature's information. The standard fix (step 1 of the algorithm above) is standardization: rescale each feature to zero mean and unit variance before computing distance, so both features contribute comparably. Now consider a text-clustering scenario, where two documents are represented as term-frequency vectors over the vocabulary {data, model, cook}:

Euclidean distance between Doc 1 and Doc 2:

Euclidean distance between Doc 1 and Doc 3:

Euclidean distance incorrectly says Doc 1 is closer to the unrelated recipe (Doc 3) than to the topically identical, merely longer, Doc 2 — purely an artifact of document length. Now compute cosine similarity:

Cosine similarity correctly identifies Doc 1 and Doc 2 as identical in direction (same topic, different length) and Doc 3 as completely orthogonal (unrelated topic) — exactly the behavior wanted for text clustering, and exactly why cosine distance ($1-\cos$) is standard for document and embedding similarity.

Prasanta Chandra Mahalanobis, an Indian statistician and founder of the Indian Statistical Institute, developed his eponymous distance in 1936 to compare skull measurements across human populations — a problem where raw Euclidean distance failed because measurements like skull length and width were highly correlated. His insight, that distance should be measured relative to the data's own covariance rather than assuming independent, equally-scaled axes, remains the conceptual core of Mahalanobis distance in modern machine learning: from anomaly detection to Gaussian mixture models, where cluster membership probability is directly governed by Mahalanobis distance to each component's mean.

Distance metrics are the invisible substrate beneath nearly all unsupervised and semi-supervised systems. Recommendation engines compute cosine similarity between user or item embedding vectors to find "similar" products, since embedding magnitude often reflects popularity rather than meaning. Anomaly and fraud detection systems use Mahalanobis distance to flag transactions that deviate from the correlated structure of normal spending patterns, catching outliers invisible to naive Euclidean thresholds. Search engines and vector databases (used for retrieval-augmented generation in modern language model pipelines) index embeddings using cosine or Euclidean distance depending on how the embedding model was trained and normalized. Image and signal processing pipelines frequently choose Manhattan distance for robustness against sensor noise and outlier pixels. Genomics and bioinformatics use Mahalanobis-style covariance-aware distances when comparing gene expression profiles with strongly correlated features. Every one of these systems ultimately calls into the same handful of primitives described here, and every downstream clustering method — k-means's spherical assumption, hierarchical clustering's linkage criteria, DBSCAN's epsilon-neighborhoods — is a direct consequence of the distance function chosen at this foundational layer.

Ask the tutor: How does the choice between Euclidean and Mahalanobis distance change the shape of clusters found by a Gaussian mixture model?