k-means cluster, How to re-calculate centroid when using cosine similarity?

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}$ ?

• 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? Oct 15 '14 at 9:57
• Hello,thank you for replying. In my project, I want to compare the different of kmeans cluster results between Eucliean distance and cosine similarity. Oct 15 '14 at 11:22
• I am not sure whether I can use the same method to generate the new centroid vector Oct 15 '14 at 11:23
• 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. Oct 15 '14 at 12:43

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:

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.)

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.

• What to do if the data is not positive ? Dec 19 '16 at 22:06
• Then don't use Cosine Dec 20 '16 at 0:58

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.

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

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.

• Could you for completeness add the reference to the book/article where this page comes from? Thanks!
– Andy
Aug 12 '15 at 12:32