Euclidean distance is usually not good for sparse data (and more general case)?

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

Here is a simple toy example illustrating the effect of dimension in a discrimination problem e.g. the problem you face when you want to say if something is observed or if only random effect is observed (this problem is a classic in science).

Heuristic. The key issue here is that the Euclidian norm gives the same importance to any direction. This constitutes a lack of prior, and as you certainly know in high dimension there is no free lunch (i.e. if you have no prior idea of what you are searching for, then there is no reason why some noise would not look like what you are searching for, this is tautology ...).

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 prior that your signal is sparse then you can remove (i.e. penalize) non sparse vector with a metric that fills the space with sparse vector or by using a thresholding technique.

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 certainly 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 probability exercise 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$. Practically speaking this means that when you increase the size $n$ of your problem if it does not increase the strength of the signal at the same time then you are adding uninformative information to your observation (or you are reducing the proportion of useful information in the information you have): this is like adding noise and reduces the power of the test (i.e. it is more likely that you are gonna say nothing is observed while there is actually something).

Toward a test with a threshold statistic. If you do not have much energy in your signal but if you know a linear transformation 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$ almost 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.

Answer 2

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 3

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 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

An axiomatic measure of sparsity is the so-called $\ell_0$ count, that counts the (finite) number of non-zero entries in a vector. With this measure, vectors $(1,0,0,0)$ and $(0,21,0,0)$ possess the same sparsity. And absolutely not the same $\ell_2$ norm. And $(1,0,0,0)$ (very sparse) has the same $\ell_2$ norm as $\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$, a very flat, non-sparse vector. And absolutely not the same $\ell_0$ count.

This function, neither a norm nor a quasinorm, is nonsmooth and nonconvex. Depending on the domain, its names are legion, for instance: cardinality function, numerosity measure, or simply parsimony or sparsity. It is often considered as unpractical for practical purposes since its use leads to NP hard problems.

While standard distances or norms (such as the $\ell_2$ Euclidian distance) are more tractable, one of their issues is their $1$-homogeneity: $$\| a.x\| = |a|\| x\|$$ for $a\neq 0$. This could be seen as non-intuitive, as the scalar product does not change the proportion of null entries in data ($\ell_0$ is $0$-homogeneneous).

So in pratice, some ressort to combinations of $\ell_p(x)$ terms ($p \ge1$), such as lasso, ridge or elastic net regularizations. The $\ell_1$ norm (Manhattan or Taxicab distance), or its smoothed avatars, is especially useful. Since works by E. Candès and others, one can explain Why $\ell_1$ Is a Good Approximation to $\ell_0$: A Geometric Explanation. Others have made $p < 1$ in $\ell_p(x)$, at the price of non-convexity issues.

Another interesting path is to re-axiomize the notion of sparsity. One of the recent notable works is Comparing Measures of Sparsity, by N. Hurley et al., dealing with the sparsity of distributions. From six axioms (with funny names like Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates, and Babies), a couple of sparsity indices emerged: one based on the Gini index, another on norm ratios, especially the one-over-two $\frac{\ell_1}{\ell_2}$ norm-ratio, shown below:

Although not convex, some proofs of convergence and some historical references are detailed in Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed $\frac{\ell _1}{\ell_2}$ Regularization. Some pseudo-norm/norm ratios $\ell_p/\ell_q$ are provided in SPOQ ℓp-Over-ℓq Regularization for Sparse Signal Recovery applied to Mass Spectrometry.

Answer 6

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 7

The paper On the surprising behavior of distance metrics in high dimensional space discusses the behaviour of distance metrics in high dimensional spaces.

They take on the $L_k$ norm and propose the manhattan $L_1$ norm as the most effective in high dimensional spaces for clustering purposes. They also introduce a fractional norm $L_f$ similar to the $L_k$ norm but with $f \in (0..1)$.

In short, they show that for high dimensional spaces using the euclidean norm as a default is probably not a good idea; we have usually little intuition in such spaces, and the exponential blowup due to the number of dimensions is hard to take into account with the euclidean distance.