curse of dimensionality affects nearest neighbors algorithms

Topics

• curse of dimensionality

Many machine learning algorithms rely on distances between data points as their input, sometimes the only input, especially so for clustering and ranking algorithms. Also, increased dimensionality leads to data sparsity. This means that even if a data point ranks closest to another data point, it can still be very, very far.

In the paper When is Nearest Neighbors Meaningful? the authors argue that for many data distribution and distance functions, the ratio of distances between nearest and farthest neighbors is almost 1 (so more or less the same).

Example

For any point $A$, let’s assume ${\mathrm{dist}}_{\min }(A)$ is the minimum distance between $A$ and its nearest neighbor, while ${\mathrm{dist}}_{\max }(A)$ is the maximum distance between $A$ and its farthest neighbor.

In 1-D, 2-D or even 3-D,

$$\frac{{\mathrm{dist}}_{\max }(A)-{\mathrm{dist}}_{\min }(A)}{{\mathrm{dist}}_{\min }(A)}>0$$

But, as the dimensions increase, i.e. $\dim \to \infty$,

$$\underset{\dim \to \infty }{\lim }\frac{{\mathrm{dist}}_{\max }(A)-{\mathrm{dist}}_{\min }(A)}{{\mathrm{dist}}_{\min }(A)}\to 0$$

That is, for a $d$-dimensional space, given $n$ random points, any given pair of points are almost equidistant to each other as $d\to \infty$. In such cases, any machine learning algorithms which are based on the distance measure including KNN algorithm (k-Nearest Neighbor) tend to fail.

Related