2
$\begingroup$

I have a clustering algorithm, where if I use an euclidian distance as similarity, it works well on any dataset. If I replace it by a cosine similarity (see my code bellow), it will give a degenerate results (will not work at all). Did I do an error in coding this cosine similarity or it is the cosine similarity that should by nature work only on some kind of data ?!

And by the way, this is a "similarity", is there any different between it and the "distance" ?

Here are example vectors from two datasets that I use. The second dataset may contain many repeated vectors:

Examples from dataset1: http://pastebin.com/6iYcqgWF

Examples from dataset2: http://pastebin.com/4MtLXwp7

Note: the square is just because the function is called under a root in the main program ..

// My squared  euclidean distance similarity 
float computeSqrDistance(vector<float> pos1, vector<float> pos2)
{
    float sum = 0;

    for(unsigned int i = 0; i < pos1.size(); ++i)
    {
        sum += pow( (pos1[i] - pos2[i]), 2.0 );
    }

    return sum;
}


// My squared cosine distance similarity 
float computeSqrDistance(vector<float> pos1, vector<float> pos2)
{
    float sum0 = 0, sum1 = 0, sum2 = 0;

    for(unsigned int i = 0; i < pos1.size(); ++i)
    {
        sum0 += pos1[i] * pos2[i];
        sum1 += (pos1[i]*pos1[i]);
        sum2 += (pos2[i]*pos2[i]);
    }

    float similarity = sum0 / ( sqrt(sum1) * sqrt(sum2) );

    similarity = 1 - (acos(similarity) / M_PI);

    return (similarity*similarity);
}
$\endgroup$
10
  • 1
    $\begingroup$ This is a dot product, right? you're trying to find theta between the two given a . b = |a||b|cos(theta)? $\endgroup$
    – Hans
    Jun 7, 2012 at 13:29
  • 1
    $\begingroup$ You can step this through in a debugger to determine whether the code implementation is correct. $\endgroup$
    – Oli Charlesworth
    Jun 7, 2012 at 13:31
  • 1
    $\begingroup$ 1. Why are you squaring your putative cosine distance; 2. why the arccos? $\endgroup$
    – Fred Foo
    Jun 7, 2012 at 13:32
  • 1
    $\begingroup$ @larsmans - I think the arccos comes from the way the angular silimarity is calculated from the cosine similarity; the ang. similarity is a proper distance metric, while cosine similarity is not. Not sure about the squaring $\endgroup$
    – Attila
    Jun 7, 2012 at 13:39
  • 1
    $\begingroup$ Can you please define what you mean by "works well" and "does not work at all"? $\endgroup$
    – gui11aume
    Jun 7, 2012 at 18:39

3 Answers 3

5
$\begingroup$

By the end of the function you take the arccosine of the computed score. Actually, according to the definition (see the Wikipedia page for example) you should not.

If you want the dissimilarity, I think you should just do

return (1 - sum0 / ( sqrt(sum1) * sqrt(sum2) ));

The similarity score will always be within $(-1,1)$, by direct application of the Cauchy-Schwarz inequality. If you want it to be within $(0,1)$ you can take the square or the absolute value. Actually, given your input, the similarity should always be in $(0,1)$ because all your values are positive.

By taking the arccosine you get an angle in radian between $0$ and $2\pi$. The gain of taking the arccosine and dividing by $2\pi$ is null, plus it is not what most people will call the cosine similarity.

A distance satisfies the axioms of a distance:

  1. $d(x,y)>0$ if $x\neq y$, and $d(x,x)=0$.
  2. $d(x,y)=d(y,x)$
  3. $d(x,z)\leq d(x,y)+d(y,z)$.

The third is known as the triangle inequality. A dissimilarity satisfies only 1. and 2.

$\endgroup$
3
  • $\begingroup$ The arccos as described in the wiki article is just to make the similarity within [0,1]. Actually I have the same problem even if I don'use the arccos at the end. i.e. even if I just use return (1 - sum0 / ( sqrt(sum1) * sqrt(sum2) )); $\endgroup$
    – shn
    Jun 7, 2012 at 14:30
  • $\begingroup$ Note that without the arccos, you don't need the 1- part. $\endgroup$
    – Aniko
    Jun 7, 2012 at 14:41
  • $\begingroup$ I've edited my post to add some example vectors from two datasets that I use. $\endgroup$
    – shn
    Jun 7, 2012 at 14:44
4
$\begingroup$

Make sure that you do not have an all-0 vector in your data set!

Because for this object, the distances will degenerate. I figure you might get either an exception or NaN.

Also make sure to not confuse similarity and distance. Similarity will be high for similar objects, a distance would be low. There are two common variants of inverting the cosine similarity to a "distance": either by taking 1-angle, the other is arccos(angle).

Be careful when using it as a "distance", as it clearly is not a proper metric. It is undefined for the 0 vector, it violates coincidence (vectors (1,1) and (2,2) have distance 0!) and it probably won't satisfy the triangle inequality either.

$\endgroup$
7
  • $\begingroup$ So what should I return instead of 1-angle, when I have an all-0 vector in my dataset ? because it is actually the case. And I have also sometimes some repeated data (same vectors). $\endgroup$
    – shn
    Jun 7, 2012 at 19:14
  • $\begingroup$ All good points (+1)! $\endgroup$
    – gui11aume
    Jun 7, 2012 at 19:15
  • $\begingroup$ There is no sensible value for the point 0. Whichever you choose, it will misbehave in one situation or another. The most sensible value is actually NaN - not a number. Think of it: what is the angle between a vector x and 0? There is no angle. It's not 0, and it's also not infinity. $\endgroup$ Jun 7, 2012 at 19:24
  • $\begingroup$ Do you mean that I can use this dissimilarity only if I do not have an all-0-vector in my dataset ? What should I do if I have it ?! $\endgroup$
    – shn
    Jun 7, 2012 at 20:34
  • $\begingroup$ You can always preprocess your data set. For example, you can remove the 0 vectors, and process them differently. $\endgroup$ Jun 7, 2012 at 22:03
3
$\begingroup$

I checked out the example vectors. The algorithm gives larger squared similarity for vectors in the same group:

v1, v2: 0.772201
v3, v4: 0.670776

I got somewhat smaller squared similarity for vectors in different groups:

v1, v2: 0.585961
v1, v3: 0.606588
v2, v3: 0.543307
v2, v4: 0.555077

I think your problem is that you would like to get distance, not similarity. Just modify the end of your second function this way:

float distance = 1 - similarity;
return distance * distance;
$\endgroup$
9
  • $\begingroup$ awsome, this works better ! I have some questions then to complete your answer: 1) What is the difference between the similarity and the distance here ? 2) Knowing that the function should return a squared distance, is it different if I do: float distance = 1 - (similarity); return distance*distance; instead of float distance = 1 - (similarity*similarity); return distance; as you suggested ? $\endgroup$
    – shn
    Jun 7, 2012 at 16:48
  • $\begingroup$ Conceptually, squared similarity is the "opposite" of distance. 0 squared similarity means maximum distance, and a squared similarity of 1 means 0 distance. So I would use my formula above. Another option: float distance = 1 - abs(similarity); return distance; $\endgroup$
    – kol
    Jun 7, 2012 at 16:55
  • $\begingroup$ but 1 - abs(similarity); is the "distance", or the "squared distance" ? Because my function should return the squared distance. So I should return pow( (1 - abs(similarity)), 2); right ? $\endgroup$
    – shn
    Jun 7, 2012 at 17:02
  • $\begingroup$ Sorry I have to go home now, I will write an answer in about an hour. $\endgroup$
    – kol
    Jun 7, 2012 at 17:06
  • $\begingroup$ Ok. By the way, the function return "nan" (not defined) instead of 0, when we compute the distance between two same vectors (v1 and v1), because actually the value of similarity just after float similarity = sum0 / ( sqrt(sum1) * sqrt(sum2) ); is not 1 but 1.000000263 for example. And moreover, sometimes I have a 0 vector (where all values are 0) so sum0 sum1 or sum2 may be 0 ! How can I have a cosine distance function that handle this cases ? $\endgroup$
    – shn
    Jun 7, 2012 at 18:00

Your Answer

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

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