How to map clustering results to known groups?

Question

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?

Answer 1

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)