7
$\begingroup$

I have a requirement using k-means cluster method with cosine similarity instead of Euclidean distance.

for example:

data a: a1 a2 a3 a4 ...
data b: b1 b2 b3 b4 ...

cosine similarity: $\displaystyle \frac{\mathbf{a}\cdot\mathbf{b}}{ |\mathbf{a}|\cdot|\mathbf{b}|}$

My problem is how I can re-calculate the centroid vector for each iteration base on cosine similarity?

Can I still use average e.g.: $\displaystyle \frac{(a_1 + b_1 + c_1)}{3}$ ?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ K-means clustering in its classic sense is only for cases X features dataset; and make use (indirectly) of Euclidean distances, not cosines or such. However, cosines are related to Euclidean distances. Plese read stats.stackexchange.com/q/81481/3277. What exactly do you need to do and what is at your disposal? $\endgroup$
    – ttnphns
    Oct 15, 2014 at 9:57
  • $\begingroup$ Hello,thank you for replying. In my project, I want to compare the different of kmeans cluster results between Eucliean distance and cosine similarity. $\endgroup$
    – vvilp
    Oct 15, 2014 at 11:22
  • $\begingroup$ I am not sure whether I can use the same method to generate the new centroid vector $\endgroup$
    – vvilp
    Oct 15, 2014 at 11:23
  • $\begingroup$ I can't know how your program of k-means clustering takes in and process cosines as input. Original k-means algo needs cases-by-variables input. From my link above (and further link there in it) one might learn that doing k-means directly on the cosines - if the program is capable of doing that - is equivalent to doing classic k-means based on variables each normalized to sum-of-squares = 1. $\endgroup$
    – ttnphns
    Oct 15, 2014 at 12:43

4 Answers 4

Reset to default
4
$\begingroup$

You can normalize the vectors in each cluster by their lengths and add them up, then normalize the sum. The result will be a unit vector in the direction of the centroid (a.k.a. prototype) vector. As far as the spherical k-means algorithm is concerned, the length of the centroid vector does not matter and is not used. This is because to calculate the cosine distance between each cluster member and the centroid, both vectors are normalized by their lengths. See the following excerpt from this article:

centroid computation

If you really need a centroid vector with a representative length, you can take the average of the lengths of the cluster members and multiply it by the unit centroid vector. But this would be completely your choice and would have nothing to do with the k-means algorithm (you could use any other type of averaging, arithmetic, geometric, or just the length of the average vector to compute the representative centroid lenght).

The formula posted by Vijay Rajan is effectively the same (except giving a centroid vector of non-unit length), but note that in that formula too the vectors must be normalized to unit length before applying the formula. When calculated properly, the centroid does indeed "bisect" the angle between the vectors. (I don't currently have the forum privilege to make this a comment on their response.)

Improve this answer
$\endgroup$
2
$\begingroup$

It should be safe to use the regular means of computing the mean with cosine - at least if your data is positive and does not include a zero vector.

Spherical k-means (that is the proper search term) IIRC normalizes the mean vectors to unit length.

Beware of corner cases: if your clustering degenerates and a cluster becomes empty, you may end up with a zero vector and get NaN values.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What to do if the data is not positive ? $\endgroup$
    – Nikana Reklawyks
    Dec 19, 2016 at 22:06
  • 2
    $\begingroup$ Then don't use Cosine $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 20, 2016 at 0:58
1
$\begingroup$

There are a few implementations of k-means (one k-means in R) which allows you to just input a distance matrix instead of actual data. There is package called 'proxy' on cran, that you use to find a cosine similarity formula based distance matrix of the data.

You can directly use this distance matrix in k-means.

Improve this answer
$\endgroup$
0
$\begingroup$

As per http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.7900&rep=rep1&type=pdf it says that you could add up all the vectors and then divide each vector element by the number of vectors.

See image excerpt from the article cited

I personally don't like this formula. The reason is that this does NOT BISECT the angle between 2 Vectors and origin. Example Angle at origin between [1,1] and [1,0] is 45 deg which is SQRT(2). But by the formula quoted in the book, the new vector which will now be the centroid, does not BISECT the angle. So as per formula 1/2 * [1+1, 0+1] which is [1,0.5]. This point does not lie on the bisector.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Could you for completeness add the reference to the book/article where this page comes from? Thanks! $\endgroup$
    – Andy
    Aug 12, 2015 at 12:32

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.