How to get a valid distance metric?

Question

I have got a problem to devise a distance metric to get the similarity measurement of vectors. Someone suggested me to use dot product, which seems to me the same as the Cosine similarity metric; however in Wikipedia (Cosine Similarity), it mentioned Cosine similarity is not a proper distance metric as it does not have the triangle inequality property and it violates the coincidence axiom (the proper distance metric should satisfy the four conditions (distance metric)).

My questions are:

1. What are the proper distance metric? Please name some examples.

2. Are Dice's coefficient and Jaccard index proper distance metric?

3. Are there any disadvantages of using dot product? (One of the reasons for the popularity of dot product is that it is very efficient to evaluate).

Thanks a lot. A.

Answer 1

First of all, in many applications you do not need a distance metric, but a dissimilarity will be okay. So make sure that triangle inequality is needed.

In mathematics, triangle inequality is part of the definition of a metric, and distances in mathematics are synonymous to metrics. But in database literature, often distances are not required to be metric.

Second, we cannot recommend a metric for your data, if we don't know your data.

Third, Cosine is closely related to Euclidean distance. Assuming that all your data is normalized to unit length ($||x||=1=||y||$), then \begin{align*} \text{Euclid}^2(x,y)&=\sum_i (x_i-y_i)^2\\ &=\sum_ix^2+\sum_iy^2-2\sum_i x_iy_i\\ &=1+1-2\cdot x\cdot y\\ &=2(1-x\cdot y) \end{align*} Therefore, if your data is normalized to unit length, $$ \sqrt{1-x\cdot y} $$ is a metric. Because as just shown, $\sqrt{1-x\cdot y}=\sqrt{\frac{1}{2}}\text{Euclid}(x,y)$.

While this may get you overly excited that there is a metric based on the dot product, recall that this only holds if all your data lives on the unit circle and this is just Euclidean metric. If this is the behaviour you want, normalize your data and use Euclidean distance... Cosine distance is exactly this normalization. It includes normalization terms for the length of the vectors to ensure they are of unit length...

If your data is sparse, and you can afford to keep all vector lengths in memory, then this may be a faster way to compute Euclidean distance. If you have a sparsity of $s$, the expected sparsity of the dot product is $s^2$, so this can yield a substantial performance benefit of $1/s$, if you have a good implementation.

Update: it was pointed out to me that computing Euclidean this way can suffer from a numerical instability called "catastrophic cancellation".

Answer 2

What are the proper distance metric? Please name some examples.

Euclidean distance, Levenshtein distance, Manhattan distance. As you write, any distance metric satisfies the definition of a distance, so there are quite a number of them. In one of Gunnar Carlsson's articles on topological data analysis, he uses (what I believe are) original distance metrics for use in analysis of the particular subject matter of the paper. The only limitations are the constraints of the definition of a distance.

Are Dice's coefficient and Jaccard index proper distance metric?

Dice's coefficient violates the triangle inequality. From Wikipedia:

The simplest counterexample of this is given by the three sets {a}, {b}, and {a,b}, the distance between the first two being 1, and the difference between the third and each of the others being one-third. To satisfy the triangle inequality, the sum of any two of these three sides must be greater than or equal to the remaining side. However, the distance between {a} and {a,b} plus the distance between {b} and {a,b} equals 2/3 and is therefore less than the distance between {a} and {b} which is 1.

The Jaccard index is not a distance metric. But subtracting the Jaccard index from 1 yields a distance metric.

Are there any disadvantages of using dot product? (One of the reasons for the popularity of dot product is that it is very efficient to evaluate).

It's impossible to answer this question comprehensively without additional context. If your application requires a proper distance function, then perhaps you'll get into some trouble.

Answer 3

The choice of the metric depends on your problem. See this answer for a discussion on the cosine similarity and how to build a distance function based on it. Also, there is a reference on a paper discussing the issue of distance functions in a high dimensional setting.

The problem with cross product is that you need to use it with care. For example, it is usually a good idea to whiten your data (center and scale variance to 1) so that different scaling in features do not bias your results.