9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ That topic indeed linger for long on this site. Just recent question: stats.stackexchange.com/q/120085/3277 (see further links there). What is awfully interesting is how you implemented k-means which processes cosines. If you describe your algorithm in your question it will help people answering it. $\endgroup$ – ttnphns Oct 16 '14 at 19:38
  • $\begingroup$ @ttnphns I actually generated cluster centroids using Euclidean distance (the mean of each dimension). However I then assigned each document to a cluster based on cosine similarity, rather than Euclidean distance. $\endgroup$ – Jeff Oct 16 '14 at 21:54
  • $\begingroup$ I then assigned each document to a cluster based on cosine similarity - Cosine between a doc and a centroid? And after all docs are assigned you update centroids in a usual (Euclidean) way, because coordinates of docs in the space are known. Is that so? $\endgroup$ – ttnphns Oct 16 '14 at 22:41
  • 1
    $\begingroup$ Only if sum of squared values for each document in your dataset is the same, your approach will work and will always converge. Because in that case (that is, all $h$'s of the same length) cosines between centroids and documents will be strictly monotonical with Euclidean distances between centroids and documents. But that will mean that using the cosines for assignment is needless and you may then use standard k-means algorithm's assignment based on the Euclidean distances. $\endgroup$ – ttnphns Oct 17 '14 at 5:39
  • 1
    $\begingroup$ What I'm beginning to think is that you may be looking for k-means performed on on a sphere, not in space. Angular k-means, so to speak. I suppose it is possible, but I never read or used such. $\endgroup$ – ttnphns Oct 17 '14 at 11:30
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This answer might be a good one if it describes how Yes, you can use it. (Is the idea to convert cosine to Euclidean distance similar to my answer?) $\endgroup$ – ttnphns Oct 16 '14 at 22:54
  • $\begingroup$ My understanding of k-means is different. It is not necessarily limited to the Euclidean distance (stat.uni-muenchen.de/~leisch/papers/Leisch-2006.pdf). Also See my second reference or this R package (cran.r-project.org/web/packages/cclust/cclust.pdf). I meant it really like in the wikipedia site. One just need a distance function. They refer to it as "angular similarity". $\endgroup$ – jpmuc Oct 17 '14 at 21:13
  • 1
    $\begingroup$ Perhaps (and thanks for sharing the paper!). But then all such "modifications" of k-means which differ from k-means in that they define centroid not as arithmetic mean in Euclidean space, should not be called k-means. $\endgroup$ – ttnphns Oct 18 '14 at 7:51
1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.