Using a cosine similarity does not work for any dataset

Question

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);
}

Answer 1

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.

Answer 2

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.

Answer 3

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;