Distance and the Curse of Dimensionality, machine learning lesson

A store describes each customer by the distance to the store in kilometers and the number of orders per week. Which two customers are most alike? Similarity-based methods such as k-nearest neighbors and clustering answer with a number computed from the feature vectors, and that number depends on the units, on how the features are weighted and on how many features there are. This lesson compares Euclidean distance with cosine similarity, shows the weights hidden in a choice of units, and works out exactly how distances concentrate in one stated high-dimensional model.

Key terms

Distance measure

Definition A distance measure, or dissimilarity, assigns a number $d(\mathbf{x}, \mathbf{z}) \ge 0$ to two feature vectors $\mathbf{x}$ and $\mathbf{z}$ in $\mathbb{R}^p$ , with smaller values meaning more alike. It is a metric when, for all vectors $\mathbf{x}$ , $\mathbf{y}$ and $\mathbf{z}$ , it is zero exactly when the two vectors are equal, it is symmetric, $d(\mathbf{x}, \mathbf{z}) = d(\mathbf{z}, \mathbf{x})$ , and it satisfies the triangle inequality

d(\mathbf{x}, \mathbf{z}) \le d(\mathbf{x}, \mathbf{y}) + d(\mathbf{y}, \mathbf{z}) .

The Euclidean and Manhattan distances

\begin{aligned} \lVert \mathbf{x} - \mathbf{z} \rVert_2 &= \sqrt{\sum_{j=1}^{p} (x_j - z_j)^2} , \\[0.4em] \lVert \mathbf{x} - \mathbf{z} \rVert_1 &= \sum_{j=1}^{p} \lvert x_j - z_j \rvert \end{aligned}

are metrics on $\mathbb{R}^p$ . The squared Euclidean distance is not a metric, because it can break the triangle inequality, yet it is the quantity that k-means minimizes. Every such number is computed in the representation supplied, so the choice of features, units and weights is part of the model.

In plain words A distance turns the question of how alike two records are into one number. Euclidean distance is the straight-line length of the difference vector, and Manhattan distance adds the absolute differences coordinate by coordinate. Neither knows what one unit of a feature means, so the number is only as meaningful as the representation it is computed in.

Example For $\mathbf{x} = (1, 2)$ and $\mathbf{z} = (4, 6)$ in a common dimensionless scale, the difference is $(3, 4)$ . The Euclidean distance is $\sqrt{9 + 16} = 5$ , the Manhattan distance is $3 + 4 = 7$ and the squared Euclidean distance is 25. For the points 0, 1 and 2 on a line, the squared distances are 1 from 0 to 1, 1 from 1 to 2 and 4 from 0 to 2. Since $4 > 1 + 1$ , the squared distance breaks the triangle inequality.

Cosine similarity

Definition For nonzero vectors $\mathbf{x}$ and $\mathbf{z}$ in $\mathbb{R}^p$ , the cosine similarity is

\cos(\mathbf{x}, \mathbf{z}) = \frac{\mathbf{x}^{\top}\mathbf{z}}{\lVert \mathbf{x} \rVert_2 \, \lVert \mathbf{z} \rVert_2} ,

the cosine of the angle between the two vectors. By the Cauchy-Schwarz inequality it lies in $[-1, 1]$ . It equals 1 exactly when $\mathbf{z} = c\mathbf{x}$ for some $c > 0$ , it equals $-1$ exactly when $c < 0$ , and it does not change when either vector is multiplied by a positive number. It is undefined when either vector is zero, since a norm in the denominator is then 0. The cosine distance $1 - \cos(\mathbf{x}, \mathbf{z})$ is a common dissimilarity but not a metric, since it is 0 for different vectors that point the same way and it can break the triangle inequality. After each nonzero vector is divided by its norm,

\begin{aligned} &\left\lVert \frac{\mathbf{x}}{\lVert \mathbf{x} \rVert_2} - \frac{\mathbf{z}}{\lVert \mathbf{z} \rVert_2} \right\rVert_2^2 \\[0.4em] &\quad = 2\bigl(1 - \cos(\mathbf{x}, \mathbf{z})\bigr) , \end{aligned}

so ranking candidates from most to least similar by cosine similarity gives the same order as ranking the unit vectors from nearest to farthest by Euclidean distance.

In plain words Cosine similarity compares directions and ignores lengths. Two profiles with the same proportions score 1, however different their totals are. That suits questions about mix or composition, such as the word proportions of documents, and it is the wrong choice when the size itself carries the signal, such as total demand.

Example For $\mathbf{x} = (1, 2)$ and $\mathbf{z} = (4, 6)$ , the dot product is $4 + 12 = 16$ and the norms are $\sqrt{5}$ and $\sqrt{52}$ , so

\cos(\mathbf{x}, \mathbf{z}) = \frac{16}{\sqrt{260}} \approx 0.9923 ,

an angle of about 7.1 degrees. The vector $2\mathbf{x} = (2, 4)$ has cosine similarity 1 with $\mathbf{x}$ , although its Euclidean distance from $\mathbf{x}$ is $\sqrt{5} \approx 2.236$ . For the triangle inequality, take $(1, 0)$ , $(1, 1)$ and $(0, 1)$ . The cosine distance from the first vector to the third is $1 - 0 = 1$ , while each of the two steps through $(1, 1)$ has cosine distance $1 - 1/\sqrt{2} \approx 0.293$ , a total of about 0.586.

Feature weighting

Definition A weighted squared Euclidean distance with weights $w_j \ge 0$ is

d_w^2(\mathbf{x}, \mathbf{z}) = \sum_{j=1}^{p} w_j \, (x_j - z_j)^2 .

Feature weighting is the choice of these weights, made on purpose or implied by the units. Measuring feature $j$ in a unit that is $a$ times smaller multiplies its values by $a$ and its squared differences by $a^2$ , which is the same as multiplying $w_j$ by $a^2$ . Standardization with the training mean $\bar{x}_j$ and training standard deviation $s_j > 0$ of each feature gives the weights $w_j = 1/s_j^2$ in the original units. These statistics are computed on the training data only and applied unchanged to validation, test and new cases. A feature with $s_j = 0$ in the training data needs a declared rule, such as dropping it, because the division is undefined. A weight of zero removes a feature from the comparison.

In plain words Every distance on several features already contains weights, and the units choose them unless someone chooses on purpose. Standardization makes one training standard deviation the unit on every axis, which removes the dependence on units. Equal scale is not equal importance, though. A feature of pure noise gets the same standardized influence as a meaningful one, so domain knowledge, feature selection or a learned metric may set better weights.

Example Multiply the second coordinate of $(1, 2)$ and $(4, 6)$ by 100, as a switch to a unit 100 times smaller would. The difference becomes $(3, 400)$ and the distance becomes $\sqrt{9 + 160{,}000} \approx 400.011$ instead of 5, although the observations did not change. Now suppose the training standard deviations of the two features are 1.5 and 2 in the original units. The standardized differences are $3/1.5 = 2$ and $4/2 = 2$ , so the standardized distance is $\sqrt{8} \approx 2.828$ . In the new unit the second standard deviation is 200 and the second difference is 400, so the standardized difference is still 2 and the standardized distance does not change.

Curse of dimensionality

Definition The curse of dimensionality is the collective name for difficulties that grow with the number of features $p$ when the amount of data does not grow fast enough. Three of them concern distances. The first is coverage. Splitting the range of each feature into $b$ bins gives $b^p$ cells, so a fixed number of examples leaves almost every cell empty as $p$ grows. The second is the size of neighborhoods. For data spread uniformly over the unit cube $[0, 1]^p$ , a smaller cube that holds a fraction $r$ of the data needs edge length $r^{1/p}$ , which tends to 1 as $p$ grows, so a neighborhood that holds only a few points is no longer local. The third is irrelevant features. Euclidean distance adds the squared differences of all features, so many features unrelated to the target can outweigh the few that matter. How strong these effects are depends on the data distribution. Data with many recorded features often lie near a structure of much lower dimension, and then the number of columns alone overstates the difficulty.

In plain words Each added feature multiplies the room the data must fill. With many independent features, the nearest neighbors stop being near in any absolute sense, and sums over many noisy coordinates can drown a useful signal. Methods built on local neighborhoods, such as k-nearest neighbors and clustering, feel these effects first.

Example With 10 bins per axis there are 10 cells in one dimension, 100 in two and $10^{20}$ in twenty. A million examples occupy at most $10^{6}$ of those $10^{20}$ cells, a fraction of at most $10^{-14}$ . For uniform data in ten dimensions, a cube that holds 1 percent of the data has edge length $0.01^{1/10} \approx 0.63$ , so it spans 63 percent of the range of every feature.

Distance concentration

Definition Distance concentration is the tendency, under some data distributions, of distances to vary little relative to their typical size as the dimension grows, so that the nearest and the farthest points of a sample lie at nearly the same distance in ratio. One model where this can be computed exactly takes two independent random points $\mathbf{x}$ and $\mathbf{z}$ in $[0, 1]^d$ whose $2d$ coordinates are independent and uniform on $[0, 1]$ . Each coordinate difference $W_j = x_j - z_j$ has $E[W_j^2] = 1/6$ and $E[W_j^4] = 1/15$ , so $\operatorname{Var}(W_j^2) = 1/15 - 1/36 = 7/180$ . The squared distance $D^2 = \sum_j W_j^2$ is a sum of $d$ independent terms, so

\begin{gathered} E[D^2] = \frac{d}{6} , \\[0.4em] \operatorname{Var}(D^2) = \frac{7d}{180} , \\[0.4em] \frac{\operatorname{SD}(D^2)}{E[D^2]} = \sqrt{\frac{7}{5d}} . \end{gathered}

The relative spread shrinks like $1/\sqrt{d}$ . More generally, take a fixed number $n$ of points whose squared distances $D_1^2, \dots, D_n^2$ from a query share one distribution with finite variance. If its relative spread $\operatorname{SD}(D^2)/E[D^2]$ tends to 0 as $d$ grows, Chebyshev’s inequality shows that each ratio $D_i^2/E[D^2]$ tends to 1 in probability, and then so does the ratio of the largest to the smallest distance. The conclusion needs that condition, and it can fail. Correlated coordinates, a low intrinsic dimension, heavy tails or a few strongly informative directions can keep distances informative.

In plain words In this model, almost every pair of points is about the same distance apart when measured against the typical distance. The absolute spread does not vanish. In simulations the distance $D$ keeps a standard deviation between about 0.23 and 0.25 for every dimension tried from 1 to 1000, while its mean grows roughly like $\sqrt{d/6}$ . Nearest-neighbor methods rely on the gap between near and far relative to the typical distance, so with such data the nearest neighbor is, in ratio, barely nearer than a typical point. The computation describes one stated distribution and does not prove that all high-dimensional distances are useless.

Example The relative spread of the squared distance is $\sqrt{0.7} \approx 0.837$ at $d = 2$ and $\sqrt{0.014} \approx 0.118$ at $d = 100$ . A seeded simulation of the same model draws 100 points and one query 200 times in each dimension and records the ratio of the farthest to the nearest distance. Its median falls from about 21 at $d = 2$ to about 2.6 at $d = 10$ , 1.3 at $d = 100$ and 1.09 at $d = 1000$ .

import numpy as np

rng = np.random.default_rng(5312)
for d in (2, 10, 100, 1000):
    ratios = []
    for _ in range(200):                      # 200 repetitions
        X = rng.random((100, d))              # 100 points, uniform coordinates
        q = rng.random(d)                     # one query from the same model
        dist = np.sqrt(((X - q) ** 2).sum(axis=1))
        ratios.append(dist.max() / dist.min())
    print(d, np.median(ratios))               # farthest over nearest

Check yourself

Two constructed purchase profiles count the items bought in two product types, $(2, 4)$ and $(3, 6)$ . Find their Euclidean distance and their cosine similarity. Which comparison suits grouping customers by their relative purchasing mix, and what does it leave out?

Show the answer

The difference is $(1, 2)$ , so the Euclidean distance is $\sqrt{1 + 4} = \sqrt{5} \approx 2.236$ . The second profile is 1.5 times the first, so the cosine similarity is 1. The direct computation agrees, since the dot product is $6 + 24 = 30$ and the product of the norms is $\sqrt{20} \cdot \sqrt{45} = \sqrt{900} = 30$ .

Cosine similarity suits relative mix, because both customers buy the two types in the proportion 1 to 2, and it rightly calls them identical in that respect. It discards the total volume, 6 items against 9. For a question such as inventory planning, where volume matters, a comparison that keeps magnitude is needed, such as Euclidean distance on suitably scaled counts or a separate feature for the total.

A query and two stored points have ten standardized features, and only the first feature is related to the target. Point B differs from the query by 0.1 in the first feature and by 1 in each of the other nine. Point C differs by 2 in the first feature and agrees with the query in the other nine. Which point is nearer in Euclidean distance, and which is nearer on the first feature alone?

Show the answer

The squared distances are $0.1^2 + 9 \cdot 1^2 = 9.01$ for B and $2^2 = 4$ for C, so C is nearer, at distance 2 against about 3.002. On the first feature alone B is nearer, at 0.1 against 2.

Standardization does not prevent this, because the features are already on a common scale. The nine irrelevant features add noise to every distance and reverse the ranking. Giving them weight zero, or selecting features, restores the comparison that matters, and such choices should be made with training and validation data rather than the test set.

In the uniform model of this lesson, find $E[D^2]$ and the relative spread of $D^2$ at $d = 20$ . Then suppose instead that every coordinate of a point equals one uniform variable, so that $\mathbf{x} = (U, \dots, U)$ and $\mathbf{z} = (V, \dots, V)$ with $U$ and $V$ independent and uniform on $[0, 1]$ . Find the relative spread of $D^2$ in this model. What does the comparison show?

Show the answer

At $d = 20$ the mean is $20/6 = 10/3 \approx 3.333$ and the variance is $140/180 = 7/9$ , so the standard deviation is $\sqrt{7}/3 \approx 0.882$ and the relative spread is

\sqrt{\frac{7}{100}} \approx 0.265 .

In the second model $D^2 = d\,(U - V)^2$ . Its mean is $d/6$ and its variance is $d^2 \cdot 7/180$ , so the relative spread is

\frac{\sqrt{7/180}}{1/6} = \sqrt{1.4} \approx 1.183

for every $d$ . The points lie on the diagonal of the cube, a one-dimensional structure inside $d$ dimensions, and their distances do not concentrate at all. Concentration depends on the distribution of the data, not on the number of columns alone.

Distance and the Curse of Dimensionality

Key terms

Distance measure

Cosine similarity

Feature weighting

Curse of dimensionality

Distance concentration

Check yourself

How this lesson connects

Builds on

Used later in