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.
$\begingroup$
$\endgroup$
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
2
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.
answered Jun 23, 2015 at 13:34
-
$\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$– MuhammadJun 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$– aamir23Aug 8, 2018 at 2:13
$\begingroup$
$\endgroup$
4
You could also use: $\frac{1}{e^{dist}}$ where dist is your desired distance function.
-
$\begingroup$ Can you please give any reference book/documentation related to this equation in which you found it? @Dougal $\endgroup$– JustlifeJun 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$– DanicaJun 11, 2017 at 13:02
-
$\begingroup$ @Justlife : Google for this one "encyclopedia of distances" and pick the result with the pdf document. $\endgroup$ Jun 12, 2017 at 23:04
-
$\begingroup$ Which is similar to: $sim = e^{-dist}$ $\endgroup$ Feb 16, 2021 at 20:19
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
1
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.
-
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$– DanicaJun 23, 2015 at 16:08
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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:
- Calculate the average vector for the exemplar set;
- Find the maximum distance $d^*$ between the average and the exemplar vectors;
- Decide on a suitable similarity $s^*$ for $d^*$;
- 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.
