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}$ ?
 A: 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.)
A: 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.
A: 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.
A: 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.
