I have a data set, which form 3 known groups. I performed k-means clustering algorithm on the data set, setting the number of clusters to be 3 as well. I end up with 3 groups by k-means.

Wishing to see how well k-means algorithm has worked, I am trying to benchmark these k-means groups against the known groups. The problem is, I do not know the correspondence. Maybe, group 1 by k-means corresponds to the real group 3 or 2.

My idea is quite brutal: test all $3!=6$ possible correspondences. See which correspondence gives me the "best results". The "best result" may be defined as the lowest false/postive (I am not sure about this point either)?

Is there a standard/better way of finding the correspondence which in turn allows me to do the evaluation of the clustering quality?

  • $\begingroup$ Your question is pretty much the same as this one. Check comments on it, please. The empirical correspondence is found by diagonalizing the frequency cross-table. If clustering supports the existent classification correspondence will come obvious; if not - no clear correspondence will be. $\endgroup$ – ttnphns Oct 11 '14 at 8:42

Please read a chapter on cluster evaluation.

Since - usually - the number of clusters is much smaller than the data set size, the cost of comparing $O(k_1*k_2)$ clusters with each other is neglibile. (Also note, that in general you shouldn't assume that every clustering result as the same number of clusters $k$!)

However, assuming a 1:1 correspondence of clusters isn't a good idea. For example, one algorithm may have merged two clusters, and split another cluster. Then there are 1:2 and 2:1 correspondences instead!

The common approach to handlind this is known as pair counting, and used in popular clustering evaluation measures such as the Adjusted Rand Index (ARI).

Two things that seem to be badly supported so far:

  • hierarchical clustering results (e.g. OPTICS results)
  • noise and outliers (e.g. DBSCAN results)

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.