Euclidean distance is usually not good for sparse data?

Question

I have seen somewhere that classical distances (like Euclidean distance) become weakly discriminant when we have multidimensional and sparse data. Why? Do you have an example of two sparse data vectors where the Euclidean distance does not perform well? In this case which similarity should we use?

Answer 1

I believe it is not so much the sparsity, but the high dimensionality usually associated with sparse data. But maybe it is even worse when the data is very sparse. Because then the distance of any two objects will likely be a quadratic mean of their lengths, or $$\lim_{dim\rightarrow\infty}d(x,y) = ||x-y|| \rightarrow_p \sqrt{||x||^2 + ||y||^2}$$

This equation holds trivially if $\forall_i x_i=0 \vee y_i=0$. If you increase the dimensionality and sparseness enough so that it holds for almost all attributes, the difference will be minimal.

Even worse: if you normalized your vectors to have length $||x||=1$, then the euclidean distance of any two objects will be $\sqrt{2}$ with high probability.

So as a rule of thumb, for Euclidean distance to be usable (I'm not claiming useful or meaningful) the objects should be non-zero in $3/4$ of attributes. Then there should be a reasonable number of attributes where $|y_i| \neq |x_i-y_i| \neq |x_i|$ so the vector difference becomes useful. This also applies to any other norm-induced difference. Because in the situation above $|x-y| \rightarrow_p |x + y|$

I don't think this is a desirable behavior for distance functions to become largely independent of the actual difference, or the absolute difference converging to the absolute sum!

A common solution is to use distances such as Cosine distance. On some data they work very well. Roughly speaking, they only look at attributes where both vectors are non-zero. An interesting approach is discussed in the reference below (they didn't invent it, but I like their experimental evaluation of the properties) is to use shared nearest neighbors. So even when vectors x and y have no attributes in common, they might have some common neighbors. Counting the number of objects connecting two objects is closely related to graph distances.

There is a lot of discussion on distance functions in:

• Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
  M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert and A. Zimek
  SSDBM 2010

and if you do not prefer scientific articles, also on Wikipedia: Curse of Dimensionality

Answer 2

I'd suggest starting with Cosine distance, not Euclidean, for any data with most vectors nearly orthogonal, $x \cdot y \approx$ 0.
To see why, look at $|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$.
If $x \cdot y \approx$ 0, this reduces to $|x|^2 + |y|^2$: a crummy measure of distance, as Anony-Mousse points out.

Cosine distance amounts to using $x / |x|$, or projecting the data onto the surface of the unit sphere, so all $|x|$ = 1. Then $|x - y|^2 = 2 - 2\ x \cdot y$
a quite different and usually better metric than plain Euclidean. $ x \cdot y$ may be small, but it's not masked by noisy $|x|^2 + |y|^2$.

$x \cdot y$ is mostly near 0 for sparse data. For example, if $x$ and $y$ each have 100 terms non-zero and 900 zeros, they'll both be non-zero in only about 10 terms (if the non-zero terms scatter randomly).

Normalizing $x$ /= $|x|$ may be slow for sparse data; it's fast in scikit-learn.

Summary: start with cosine distance, but don't expect wonders on any old data.
Successful metrics require evaluation, tuning, domain knowledge.

Answer 3

I believe this is related to the curse of dimensionality / concentration of measure but I can no longer find the discussion that motivates this remark. I believe there was a thread on metaoptimize but I failed to Google it...

For text data, normalizing the vectors using TF-IDF and then applying cosine similarity will probably yield better results than euclidean distance as long documents (with many words) can share the same topics hence be very similar to short documents sharing a high number of common words. Discarding the norm of the vectors helps in that particular case.

Answer 4

Part of the curse of dimensionality is that data start to spread out away from the center. This is true for multivariate normal and even when the components are IID (spherical normal). But if you want to strictly speak about Euclidean distance even in low dimensional space if the data have a correlation structure Euclidean distance is not the appropriate metric. If we suppose the data are multivariate normal with some nonzero covariances and for sake of argument suppose the covariance matrix is known. Then the Mahalanobis distance is the appropriate distance measure and it is not the same as Euclidean distance which it would only reduce to if the covariance matrix is proportional to the identity matrix.

Answer 5

Here is a simple toy example illustrating the effect of dimensionality in a discrimination problem.

Heuristic. The key issue here is that the Euclidian norm gives the same importance to any direction. This constitutes a lack of a priori, and as you certainly know in high dimension there is no free lunch (i.e. if you don't known what you are searching for, then why noise is not what you are searching for). I would say that for any problem there is a limit of information that is necessary to find something else than noise. This limit is related somehow to the "size" of the area you are trying to explore with regard to the "noise" level (i.e. level of uninformative content). In high dimension if you have the a priori that your signal is sparse then you can remove non sparse vector with metric that fill the space with sparse vector or by using thresholding.

Framework Assume that $\xi$ is a gaussian vector with mean $\nu$ and diagonal covariance $\sigma Id$ ($\sigma$ is known) and that you want to test the simple hypothesis

$$H_0: \;\nu=0,\; Vs \; H_{\theta}: \; \nu=\theta $$ (for a given $\theta\in \mathbb{R}^n$) $\theta$ is not necessarily known in advance.

Test statistic with energy. The intuition you certainlly have is that it is a good idea to evaluate the norm/energy $\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$ of you observation $\xi$ to build a test statistic. Actually you can construct a standardized centered (under $H_0$) version $T_n$ of the energy $T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$. That makes a critical region at level $\alpha$ of the form $\{T_n\geq v_{1-\alpha}\}$ for a well chosen $v_{1-\alpha}$

Power of the test and dimension. In this case it is an easy probabiliy exercice to show the following formula for the power of your test:

$$P_{\theta}(T\leq v_{1-\alpha})=P\left (Z\leq \frac{v_{1-\alpha}}{\sqrt{1+2\|\theta\|_2^2/(n\sigma^2)}}-\frac{\|\theta\|^2_2}{\sqrt{2n\sigma^4+2\sigma^2\|\theta\|_2^2/(n\sigma^2)}}\right )$$ with $Z$ a sum of $n$ iid random variables with $\mathbb{E}[Z]=0$ and $Var(Z)=1$.

This means that the power of your test is increased by the energy of your signal $\|\theta\|^2_2$ and decreased by $n$.

Toward a test with a thresholded statistic. If you do not have much energy in your signal but if you know a linear traformation that can help you to have this energy concentrated in a small part of your signal, then you can build a test statistic that will only evaluate the energy for the small part of your signal. If you known in advance where it is concentrated (for example you known there cannot be high frequencies in your signal) then you can obtain a power in the preceding test with $n$ replaced by a small number and $\|\theta\|^2_2$ allmost the same... If you do not know it in advance you have to estimate it this leads to well known thresholding tests.

Note that this argument is exactly at the root many papers such as

• A Antoniadis, F Abramovich, T Sapatinas, and B Vidakovic. Wavelet methods for testing in functional analysis of variance models. International Journal on Wavelets and its applications, 93 :1007–1021, 2004.
• M. V. Burnashef and Begmatov. On a problem of signal detection leading to stable distribution. Theory of probability and its applications, 35(3) :556–560, 1990.
• Y. Baraud. Non asymptotic minimax rate of testing in signal detection. Bernoulli, 8 :577–606, 2002.
• J Fan. Test of significance based on wavelet thresholding and neyman’s truncation. JASA, 91 :674–688, 1996.
• J. Fan and S-K Lin. Test of significance when data are curves. JASA, 93 :1007–1021, 1998.
• V. Spokoiny. Adaptative hypothesis testing using wavelets. Annals of Statistics, 24(6) :2477–2498, december 1996.