Why is Euclidean distance not a good metric in high dimensions?

I read that 'Euclidean distance is not a good distance in high dimensions'. I guess this statement has something to do with the curse of dimensionality, but what exactly? Besides, what is 'high dimensions'? I have been applying hierarchical clustering using Euclidean distance with 100 features. Up to how many features is it 'safe' to use this metric?

-
Closely related: Euclidean distance is usually not good for sparse data? as pointed out by facuq. –  cardinal May 19 '14 at 2:22
This is likely too basic for you; I wrote a series of blog posts on the subject of the Euclidean metric in higher dimensions and how that impacts searching vector spaces for nearest matches. blogs.msdn.com/b/ericlippert/archive/tags/… –  Eric Lippert May 19 '14 at 3:02
@HorstGrünbusch see answers below for some references. Variance of distances becomes small compare to the average. So at some point, you run into trouble choosing thresholds, weights, ordering; and you may even get numerical precision problems, too. But if your data is sparse, it likely is of much lower intrinsic dimensionality. –  Anony-Mousse May 19 '14 at 8:17
"high dimensions" seems to be a misleading term - some answers are treating 9-12 as "high dimensions", but in other areas high dimensionality would mean thousands or a million dimensions (say, measuring angles between bag-of-words vectors where each dimension is the frequency of some word in a dictionary), and 100 dimensions would be called low, not high. –  Peteris May 20 '14 at 7:58
This question could really do with some context. Not good for what? –  Szabolcs May 20 '14 at 21:04

A great summary of non-intuitive results in higher dimensions comes from "A Few Useful Things to Know about Machine Learning" by Pedro Domingos at the University of Washington:

[O]ur intuitions, which come from a three-dimensional world, often do not apply in high-dimensional ones. In high dimensions, most of the mass of a multivariate Gaussian distribution is not near the mean, but in an increasingly distant “shell” around it; and most of the volume of a high-dimensional orange is in the skin, not the pulp. If a constant number of examples is distributed uniformly in a high-dimensional hypercube, beyond some dimensionality most examples are closer to a face of the hypercube than to their nearest neighbor. And if we approximate a hypersphere by inscribing it in a hypercube, in high dimensions almost all the volume of the hypercube is outside the hypersphere. This is bad news for machine learning, where shapes of one type are often approximated by shapes of another.

The article is also full of many additional pearls of wisdom for machine learning.

I agree with @Dilip's statement that more than nine dimensions are difficult to work with. A rule of thumb I've heard is to not cluster with more than 12, but I'm not aware of any more rigorous demonstration of this than Dilip's geometric example.

-
this reference is awesome –  Antoine Sep 17 at 21:30

The notion of Euclidean distance, which works well in the two-dimensional and three-dimensional worlds studied by Euclid, has some properties in higher dimensions that are contrary to our (maybe just my) geometric intuition which is also an extrapolation from two and three dimensions.

Consider a $4\times 4$ square with vertices at $(\pm 2, \pm 2)$. Draw four unit-radius circles centered at $(\pm 1, \pm 1)$. These "fill" the square, with each circle touching the sides of the square at two points, and each circle touching its two neighbors. For example, the circle centered at $(1,1)$ touches the sides of the square at $(2,1)$ and $(1,2)$, and its neighboring circles at $(1,0)$ and $(0,1)$. Next, draw a small circle centered at the origin that touches all four circles. Since the line segment whose endpoints are the centers of two osculating circles passes through the point of osculation, it is easily verified that the small circle has radius $r_2 = \sqrt{2}-1$ and that it touches touches the four larger circles at $(\pm r_2/\sqrt{2}, \pm r_2/\sqrt{2})$. Note that the small circle is "completely surrounded" by the four larger circles and thus is also completely inside the square. Note also that the point $(r_2,0)$ lies on the small circle.

Next, consider a $4\times 4 \times 4$ cube with vertices at $(\pm 2, \pm 2, \pm 2)$. We fill it with $8$ osculating unit-radius spheres centered at $(\pm 1, \pm 1, \pm 1)$, and then put a smaller osculating sphere centered at the origin. Note that the small sphere has radius $r_3 = \sqrt{3}-1$ and the point $(r_3,0,0)$ lies on the surface of the small sphere.

Generalizing, we can consider a $n$-dimensional hypercube of side $4$ and fill it with $2^n$ osculating unit-radius hyperspheres centered at $(\pm 1, \pm 1, \ldots, \pm 1)$ and then put a "smaller" osculating sphere of radius $$r_n = \sqrt{n}-1\tag{1}$$ at the origin. The point $(r_n,0,0, \ldots, 0)$ lies on this "smaller" sphere.

But, notice from $(1)$ that when $n = 4$, $r_n = 1$ and so the "smaller" sphere has unit radius and thus really does not deserve the soubriquet of "smaller" for $n\geq 4$. Indeed, it would be better if we called it the "larger sphere" or just "central sphere". Worse yet, when $n > 9$, we have from $(1)$ that $r_n >2$, and thus the point $(r_n, 0, 0, \ldots, 0)$ on the central sphere lies outside the hypercube of side $4$ even though it is "completely surrounded" by the unit-radius hyperspheres that "fill" the hypercube (in the sense of packing it). The central sphere "bulges" outside the hypercube in high-dimensional space. I find this very counter-intuitive because my mental translations of the notion of Euclidean distance to higher dimensions, using the geometric intuition that I have developed from the 2-space and 3-space that I am familiar with, do not describe the reality of high-dimensional space.

My answer to the OP's question "Besides, what is 'high dimensions'?" is $n \geq 9$.

-
–  cardinal May 20 '14 at 0:17

The best place to start is probably to read On the Surprising Behavior of Distance Metrics in High Dimensional Space by Aggarwal, Hinneburg and Keim . There is a currently working link here (pdf), but it should be very google-able if that breaks. In short, as the number of dimensions grows, the relative euclidean distance between a point in a set and its closest neighbour, and between that point and its furthest neighbour, changes in some non-obvious ways. Whether or not this will badly affect your results depends a great deal on what you're trying to achieve and what your data's like.

-

It is a matter of signal-to-noise. Euclidean distance, due to the squared terms, is particular sensitive to noise; but even Manhattan distance and "fractional" (non-metric) distances suffer.

Zimek, A., Schubert, E. and Kriegel, H.-P. (2012),
A survey on unsupervised outlier detection in high-dimensional numerical data.
Statistical Analy Data Mining, 5: 363–387. doi: 10.1002/sam.11161

It revisits the observations made in e.g. On the Surprising Behavior of Distance Metrics in High Dimensional Space by Aggarwal, Hinneburg and Keim mentioned by @Pat. But it also shows how out synthetic experiments are misleading and that in fact high-dimensional data can become easier. If you have a lot of (redundant) signal, and the new dimensions add little noise.

The last claim is probably most obvious when considering duplicate dimensions. Mapping your data set $x,y \rightarrow x,y,x,y,x,y,x,y,...,x,y$ increases representative dimensionality, but does not at all make Euclidean distance fail. (See also: intrinsic dimensionality)

So in the end, it still depends on your data. If you have a lot of useless attributes, Euclidean distance will become useless. If you could easily embed your data in a low-dimensional data space, then Euclidean distance should also work in the full dimensional space. In particular for sparse data, such as TF vectors from text, this does appear to be the case that the data is of much lower dimensionality than the vector space model suggests.

Some people believe that cosine distance is better than Euclidean on high-dimensional data. I do not think so: cosine distance and Euclidean distance are closely related; so we must expect them to suffer from the same problems. However, textual data where cosine is popular is usually sparse, and cosine is faster on data that is sparse - so for sparse data, there are good reasons to use cosine; and because the data is sparse the intrinsic dimensionality is much much less than the vector space dimension.

-

Euclidean distance is very rarely a good distance to choose in Machine Learning and this becomes more obvious in higher dimensions. This is because most of the time in Machine Learning you are not dealing with a Euclidean Metric Space, but a Probabilistic Metric Space and therefore you should be using probabilistic and information theoretic distance functions, e.g. entropy based ones.

Humans like euclidean space because it's easy to conceptualize, furthermore it's mathematically easy because of linearity properties that mean we can apply linear algebra. If we define distances in terms of, say Kullback-Leibler Divergence, then it's harder to visualize and work with mathematically.

-
It can be problematically, as KL Divergence isn't a metric. :-) –  agarie May 21 '14 at 21:52
If one needs symmetry, you can use Mutual Information, which as hinted at, can be defined in terms of KL. –  samthebest May 22 '14 at 14:53

Another facet of this question is this:

Very often high dimensions in (machine-learning/statistical) problems are a result of over-constrained features.

Meaning the dimensions are NOT independent (or uncorrelated), but Euclidean metrics assume (at-least) un-correlation and thus may not produce best results

So to answer your question the number of "high dimensions" is related to how many features are inter-depedennt or redundant or over-constrained

Additionally: It is a theorem by Csiszar (et al.) that Euclidean metrics are "natural" candidates for inference when the features are of certain forms

-
Euclidean metrics do not "assume... un-correlation". Euclidean distances work worst in high dimensions with uncorrelated variables. Consider the extreme case: you have very many dimensions that are all perfectly correlated, r=1, now your data are in fact uni-dimensional, & Euclidean distance works fine w/ uni-dimensional data. –  gung May 23 '14 at 0:04
No i dont think so, Euclidean distance by definition assumes un-correllated data (except if using generalized Euclidean distance with correllation matrix) –  Nikos M. May 23 '14 at 0:18
Features with total correlation (r=1) is a trivial example and equivalent to a "trivial correlation matrix", but maybe i'm wrong –  Nikos M. May 23 '14 at 0:21