13
$\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$
15
$\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$
  • $\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 Jun 23 '15 at 22:27
  • $\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 Aug 8 '18 at 2:13
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please give any reference book/documentation related to this equation in which you found it? @Dougal $\endgroup$ – Justlife Jun 11 '17 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$ – Dougal Jun 11 '17 at 13:02
  • $\begingroup$ @Justlife : Google for this one "encyclopedia of distances" and pick the result with the pdf document. $\endgroup$ – Unhandled exception Jun 12 '17 at 23:04
6
$\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$
  • $\begingroup$ I'm confused by your notation here. Is $\lVert x, x' \rVert^2$ supposed to be $\lVert x - x' \rVert^2$ (in which case I think the relation is incorrect, as it doesn't account for $\lVert x \rVert$ or $\lVert x' \rVert$), or something based on $\langle x, x' \rangle$? The cosine similarity I'm familiar with is simply $x^T x' / (\lVert x \rVert \lVert x' \rVert)$, though Wikipedia says the "angular similarity" $1 - \frac2\pi \frac{x^T x'}{\lVert x \rVert \lVert x' \rVert}$ is also sometimes called that. $\endgroup$ – Dougal Jun 23 '15 at 16:21
  • $\begingroup$ @Dougal Blah. Correct. I've revised to make it intelligible. $\endgroup$ – Sycorax says Reinstate Monica Jun 23 '15 at 16:44
  • $\begingroup$ Cool. Note though that since the OP said distances are unbounded, it seems like we don't have $\lVert x \rVert = 1$. Also, your expansion of $\lVert x - x' \rVert^2$ is mistaken; it should be $\lVert x \rVert^2 + \lVert x' \rVert^2 - 2 x^T x'$, though the rest of your post handles it correctly. :) $\endgroup$ – Dougal Jun 23 '15 at 16:52
3
$\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
    $\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$ – Dougal Jun 23 '15 at 16:08
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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