24
$\begingroup$

I am using $k$ means clustering to cluster speaker voices. When I compare an utterance with clustered speaker data I get (Euclidean distance-based) average distortion. This distance can be in range of $[0,\infty]$. I want to convert this distance to a $[0,1]$ similarity score. Please guide me on how I can achieve this.

$\endgroup$

6 Answers 6

31
$\begingroup$

If $d(p_1,p_2)$ represents the euclidean distance from point $p_1$ to point $p_2$,

$$\frac{1}{1 + d(p_1, p_2)}$$

is commonly used.

$\endgroup$
2
  • $\begingroup$ Please correct me if I am wrong, if we have $X = (x_1,x_2,x_3,...,x_t)$ and $Y = (Y_1,Y_2,Y_3,...,Y_n)$ where each $ x $ and $ y $ is of dimension $ D $. Then we can define similarity such as, $$Similarity = \frac{1}{t} \sum\limits_{i=1}^t \frac{1}{ 1+ minDistance(x_i, Y)}$$. $\endgroup$
    – Muhammad
    Commented Jun 23, 2015 at 22:27
  • 1
    $\begingroup$ I understand that the plus 1 in the denominator is to avoid divide by zero error. But I have found that the plus one value disproportionately affects d(p1,p2) values that are greater than 1 and ultimately reduces similarity score significantly. Is there another way to do this? Maybe s = 1-d(p1,p2) $\endgroup$
    – aamir23
    Commented Aug 8, 2018 at 2:13
15
$\begingroup$

You could also use: $\frac{1}{e^{dist}}$ where dist is your desired distance function.

$\endgroup$
5
  • $\begingroup$ Can you please give any reference book/documentation related to this equation in which you found it? @Dougal $\endgroup$
    – Justlife
    Commented Jun 11, 2017 at 12:55
  • $\begingroup$ @AnimeshKumarPaul I didn't write this answer, just improved its formatting. But it's frequently used as a version of e.g. a "generalized RBF kernel"; see e.g. here. That question concerns whether the output is a positive definite kernel; if you don't care about that, though, it at least satisfies an intuitive notion of similarity that more distant points are less similar. $\endgroup$
    – Danica
    Commented Jun 11, 2017 at 13:02
  • 1
    $\begingroup$ @Justlife : Google for this one "encyclopedia of distances" and pick the result with the pdf document. $\endgroup$ Commented Jun 12, 2017 at 23:04
  • $\begingroup$ Which is similar to: $sim = e^{-dist}$ $\endgroup$ Commented Feb 16, 2021 at 20:19
  • $\begingroup$ Just looked at Encyclopedia of Distances, as suggested by @NeuroMorphing, and it looks fantastic and comprehensive: link.springer.com/book/10.1007/978-3-642-30958-8 $\endgroup$
    – Scott H
    Commented Jul 16 at 16:35
13
$\begingroup$

It sounds like you want something akin to cosine similarity, which is itself a similarity score in the unit interval. In fact, a direct relationship between Euclidean distance and cosine similarity exists!

Observe that $$ ||x-x^\prime||^2=(x-x^\prime)^T(x-x^\prime)=||x||+||x^\prime||-2||x-x^\prime||. $$

While cosine similarity is $$ f(x,x^\prime)=\frac{x^T x^\prime}{||x||||x^\prime||}=\cos(\theta) $$ where $\theta$ is the angle between $x$ and $x^\prime$.

When $||x||=||x^\prime||=1,$ we have $$ ||x-x^\prime||^2=2(1-f(x,x^\prime)) $$ and $$ f(x,x^\prime)=x^T x^\prime, $$

so

$$ 1-\frac{||x-x^\prime||^2}{2}=f(x,x^\prime)=\cos(\theta) $$ in this special case.

From a computational perspective, it may be more efficient to just compute the cosine, rather than Euclidean distance and then perform the transformation.

$\endgroup$
0
10
$\begingroup$

How about a Gaussian kernel ?

$K(x, x') = \exp\left( -\frac{\| x - x' \|^2}{2\sigma^2} \right)$

The distance $\|x - x'\|$ is used in the exponent. The kernel value is in the range $[0, 1]$. There is one tuning parameter $\sigma$. Basically if $\sigma$ is high, $K(x, x')$ will be close to 1 for any $x, x'$. If $\sigma$ is low, a slight distance from $x$ to $x'$ will lead to $K(x,x')$ being close to 0.

$\endgroup$
1
  • 1
    $\begingroup$ Note that this answer and @Unhandled exception's are very related: this is $\exp\left( - \gamma d(x, x')^2 \right)$, where that one [introducing a scaling factor] is $\exp\left( - \gamma d(x, x') \right)$, a Gaussian kernel with $\sqrt{d}$ as the metric. This will still be a valid kernel, though the OP doesn't necessarily care about that. $\endgroup$
    – Danica
    Commented Jun 23, 2015 at 16:08
1
$\begingroup$

If you are using a distance metric that is naturally between 0 and 1, like Hellinger distance. Then you can use 1 - distance to obtain similarity.

$\endgroup$
0
$\begingroup$

All answers given so far are correct in the sense that they will convert a distance $d \in [0, \infty]$ to a similarity $ s \in [0, 1]$, such that:

  • $(d \rightarrow 0) \Rightarrow (s \rightarrow 1)$
  • $(d \rightarrow \infty) \Rightarrow (s \rightarrow 0)$

However, a point that is not often addressed is the scale of $d$. When working with similarity, we commonly want to use a threshold — say of $0.5$ — to decide whether two vectors are "similar enough". But unless vector distances are relatively short, most reciprocal-based conversion methods will rapidly approach zero, making it hard to find an adequate threshold.

For example, imagine a domain where $d < 100$ for "similar" vectors. Using the common reciprocal conversion:

$$s = \frac{1}{1 + d}$$

The similarity between two vectors such that $d = 49$ will be $0.02$ — a rather counter-intuitive value for "close" similarity.

An alternative in this case is to use a conversion method that takes into account the expected distance range. For example, given an empirical upper distance limit $d_{max}$, we can calculate $s$ as:

$$s = 1 - min \left ( \frac{d}{d_{max}} , 1 \right )$$

In the above case, setting $d_{max} = 200$ would lead to $s = 0.755$, which is a much more intuitive result for two "similar" vectors.

The question remains of how to choose $d_{max}$. In the common scenario where we want to identify a vector's class by comparing it with an exemplar set, a simple procedure would be:

  1. Calculate the average vector for the exemplar set;
  2. Find the maximum distance $d^*$ between the average and the exemplar vectors;
  3. Decide on a suitable similarity $s^*$ for $d^*$;
  4. Calculate $d_{max}$ such that:

$$d_{max} = \frac{d^*}{(1 - s^*)}$$

If we set $s^* = 0.9$, that would make $d_{max}$ equal to ten times the maximum distance between the exemplar set average and its entries.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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