Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

share|improve this question

6 Answers 6

up vote 11 down vote accepted

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.
share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
+1 This adds thoughtful and useful analysis to the other answers. –  whuber Jun 11 '12 at 12:44

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.

share|improve this answer

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.

share|improve this answer

There's a paper that 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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.