Curse of dimensionality- does cosine similarity work better and if so, why? [duplicate]

Question

When working with high dimensional data, it is almost useless to compare data points using euclidean distance - this is the curse of dimensionality.

However, I have read that using different distance metrics, such as a cosine similarity, performs better with high dimensional data.

Why is this? Is there some mathematical proof / intuition?

My intuition is that it's because the cosine metric is only concerned with the angle between data points, and the fact that the plane between any two data points and the origin is 3 dimensional. But what if two data points have a very small angle but lie "far away" from each other (in an absolute difference sense) - then how would they still be considered close / similar?

Answer 1

Contrary to various unproven claims, cosine cannot be significantly better.

It is easy to see that Cosine is essentially the same as Euclidean on normalized data. The normalization takes away one degree of freedom. Thus, cosine on a 1000 dimensional space is about as "cursed" as Euclidean on a 999 dimensional space.

What is usually different is the data where you would use one vs. the other. Euclidean is commonly used on dense, continuous variables. There every dimension matters, and a 20 dimensional space can be challenging. Cosine is mostly used on very sparse, discrete domains such as text. Here, most dimensions are 0 and do not matter at all. A 100.000 dimensional vector space may have just some 50 nonzero dimensions for a distance computation; and of these many will have a low weight (stopwords). So it is the typical use case of cosine that is not cursed, even though it theoretically is a very high dimensional space.

There is a term for this: intrinsic dimensionality vs. representation dimensionality.

Answer 2

However, I have read that using different distance metrics, such as a cosine similarity, performs better with high dimensional data.

Most likely depends on context.

The cosine distance is not impervious to the curse of dimensionality - in high dimensions two randomly picked vectors will be almost orthogonal with high probability, see 0.2 Funny facts from these notes.

Answer 3

Cosine similarity is correlation, which is greater for objects with similar angles from, say, the origin (0,0,0,0,....) over the feature values. So correlation is a similarity index. Euclidean distance is lowest between objects with the same distance and angle from the origin. So, two objects with the same angle (corr) can have a far distance (Euclidean) from one another.

I wouldn't say that Euclidean distance is useless for anything. Correlation will identify objects with similar feature values but with additive or multiplicative translations between the objects. For example, two objects $\textbf{x}_i=(1,2,3,4)$ and $\textbf{x}_j=(1,4,6,8)$ which are a multiplicative constant of 2 away from each other will have perfect correlation (unity). Also, two objects $\textbf{x}_i=(1,2,3,4)$ and $\textbf{x}_j=(1.25,2.25,3.25,4.25)$ which are an additive constant of 0.25 away from each other will have perfect correlation (unity). However, Euclidean distance, $d(\textbf{x}_i, \textbf{x}_j)>0$ -- will be greater than zero.

The problem you are looking for is called the "overlap problem", where in the above two examples of perfect correlation, objects can be perfectly correlated but with different distances.

In hierarchical cluster analysis, if you want agglomeration of objects with almost the same levels of features values (i.e, almost the same objects), you would use Euclidean distance. However, if you want to agglomerate together objects with similar patterns that may vary by constant additive or multiplicative translation, then you would use correlation, or 1 minus correlation, which makes correlation look like a distance with range [0,2].

In biology for example, you want to preferably use correlation to identify genes which may be co-regulated or associated (correlated), whose expression patterns correlate together ("co-vary" --> covariance) over the objects. In this case, however, using Euclidean distance would only identify genes with the same level of expression, which won't mean much when trying to find co-regulatory genes. Euclidean distance is best for finding like objects with feature values that are low or high together.

FYI-curse of dimensionality is commonly a problem that creates the "small sample problem" $(p>>n)$, when there are too many features compared to the number of objects. It doesn't have anything to do with distance metrics, since you can always mean-zero standardize, normalize, use percentiles, or fuzzify feature values to get away from issues of scale.