I'm using k-means to cluster sentences according to the part-of-speech tags of the words in a sentence, and I have a nice, easy to understand visualization of the result, but I'm struggling to find a good method to quantify the result.

My starting point is a paper by Dowty which postulates that there is a certain fixed set of verb themes (e.g. causation, movement) which are supposedly different semantically and syntactically. To check this claim, I've done k-means clustering (k=8) on a large corpus of part-of-speech tagged sentences. Then, I took a small number (~50) of sentences from each of the resulting clusters, shuffled and hand-labelled them. With this, I made the following visualization of the label assignments per cluster:

cluster assignments chart

Now what I'm looking for is a way to compute the quality/usefulness of the clustering result given the distribution of labels. I'm looking for a value that should be high when most of any label ends up in few of the clusters, and 0 when the labels are equally distributed over the clusters. I have looked into Shannon entropy but I'm not sure if it is what I'm looking for conceptually, and not sure where else to look.

Any clues would be much appreciated!

  • $\begingroup$ Could you explain this plots to me and how you made them? they look very nice. Greetings! @Junuxx $\endgroup$ – JEquihua Jun 29 '12 at 17:51
  • $\begingroup$ @JEquihua: Thanks! In my dataset, I had 8 clusters, and 400 sentences that I labelled blindly, that is, without knowing from which cluster they came. So for every cluster I have a distribution of labels. That's what the plots show. I made the plot with a custom Python script, using the Python Imaging Library. $\endgroup$ – Junuxx Sep 9 '12 at 14:49

Have you had a look at the cluster analysis article in Wikipedia?

There is a whole section on external cluster evaluation measures. This seems to be exactly what you are looking for.


  • $\begingroup$ Thanks a lot, I'll have to study this a bit more but it seems the Adjusted Rand index is precisely what I was looking for! $\endgroup$ – Junuxx Jun 16 '12 at 14:16

I would use Percentage of Variance Explained (PVE) to evaluate clustering algorithm. Assume that 3-means, 4-means and 5-means clustering explains 60%, 95%, 97% of the variance in the original data set. In such cases, the natural selection would be 4-means clustering. But again this depends on the amount of variance you would want your algorithm to explain after applying clustering. Check out The Elbow Method to decide the number of clusters in k-means algorithm. You can also have a look at Hierarchical Clustering which does not require to fix the number of clusters before applying an algorithm.


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.