K-means on cosine similarities vs. Euclidean distance (LSA)

Question

I am using latent semantic analysis to represent a corpus of documents in lower dimensional space. I want to cluster these documents into two groups using k-means.

Several years ago, I did this using Python's gensim and writing my own k-means algorithm. I determined the cluster centroids using Euclidean distance, but then clustered each document based on cosine similarity to the centroid. It seemed to work pretty well.

Now I am trying to do this on a much larger corpus of documents. K-means is not converging, and I'm wondering if it's a bug in my code. I read recently that you shouldn't cluster using cosine similarity, because k-means only works on Euclidean distance. Even though, as I mentioned, it appeared to work fine in my smaller test case.

Now I come across this on the LSA Wikipedia page:

Documents and term vector representations can be clustered using traditional clustering algorithms like k-means using similarity measures like cosine.

So which is it? Can I use cosine similarity or not?

Answer 1

Yes, you can use it. The problem is, that the cosine similarity is not a distance, that is why it is called similarity. Nevertheless, it can be converted to a distance as explained here.

In fact, you can just use any distance. A very nice study of the properties of distance functions in high dimensional spaces (like it is usually the case in information retrieval) is On the Surprising Behavior of Distance Metrics in High Dimensional Space. It does not compare Euclidean vs. cosine though.

I came across with this study where they claim that in high dimensional spaces, both distances tend to behave similarly.

Answer 2

Euclidean distance is not suitable for comparing documents or clusters of documents. When comparing documents, one key issue is normalization by document length. Cosine similarity achieves this kind of normalization, but euclidean distance does not. More over, documents are often modeled as multinomial probability distributions (so called bag of words). Cosine similarity is an approximation to the JS-divergence which is a statistically justified method for similarity. One key issue with documents and cosine is that one should apply proper tf-idf normalization to the counts. If you are using gensim to derive the LSA representation, gensim already does that.

Another useful observation for your use case of 2 clusters is that you can get a good non-random initialization because LSA is just SVD. You do it in the following way:

• Take just the first component of each document (assuming the first component is the top singular vector).
• Sort those values by keeping track of the document ids for each value.
• cluster 1 = document ids corresponding to top e.g. 1000 (or more) values
• cluster 2 = document ids corresponding to bottom e.g. 1000 (or more) values
• just average the vectors for each cluster and normalize by vector length.
• Now apply k-means to this initialization. This means just iterate (1) assigning documents to the current closest centroid and (2) averaging and normalizing new centroids after reassignment

Answer 3

Yes, the same centroid update by vector average works.

See m=1 case in the Section 2.2 of this paper. w's are the weights and the weights are all 1 for base k-mean algorithms.

The paper uses properties of the Cauchy-Schwartz inequality to establish the condition that minimizes the cost function for k-mean.

Also remember that cosine similiarity is not a vector distance. Cosine dissimiliarity is. (This should be a good search term.) Hence when you update the partition, you are looking for arg max as opposed to arg min.