# How to evaluate the clustering result when cluster numbers are not equal to data set class

When apply clustering algorithm with the multi-class data set and class numbers are not equal to the result cluster numbers(For example , When we use K-Means algorithm by setting K = 3 apply with "yeast" data set that has 14 classes).

What is the proper way to evaluate the result in this situation ?

• Are your classes mutually disjoint? Do they also cover the data set, i.e., each item of it belongs to one and only one class? I'm trying to make sure I understand what you are talking about.. – MASL Nov 26 '15 at 14:26

If no pair of your classes are overlapping and they do classify each and every element of the data set, then they constitute a partition of that set. So does your clustering.

In such a case, I would suggest to use a distance metric to compare two partitions, instead of any bona fide index, even if it's popular -unless that index happens to be a metric as well.

One such distances for comparing partitions is the $VI$ index, rediscovered by Maria Meila$\phantom{,}^\dagger$ a few years back, but its origin dating back to the 80's in a physics paper by Zurek$\phantom{,}^{\ddagger}$.

How to calculate distance between two partitions P and Q:

1. Determine $P\wedge Q,$the "intersection" (I always mix up the words join and meet here) of P and Q. This is simply the partition formed by taking the intersection of each cluster of P against each cluster of Q.
2. For all three partitions $P$, $Q$, $P\wedge Q$ calculate their entropy $H$ defined as follows: $$H(P)=-\frac{1}{N}\sum_{i=1}^Np_i\log p_i\;,\;p_i\equiv\frac{n_i}{N}$$ where $N$ is the total number of elements you clustered/classified and $n_i$ is the number of elements within cluster/class $i$ of a given partition $P$.
3. The distance $d(P,Q)$ between partitions P and Q is then given by $$d(P,Q)=2H(P\wedge Q)-H(P)-H(Q)$$

The reason for using a real metric is simple: a metric satisfy the triangular inequality and our intuitions of "close" and "similar" heavily relies on that. Any ad-hoc measure of dis-similarity (distance) that doesn't satisfy the triangular inequality will eventually give you results like this: A is "$d$ away" from B (d being concrete number), with $d$ smaller than a given bound, say $D$. Then you find A close to C by an amount $d'<D$. If this distance were not a metric, it could then happen that the distance $d''$ between B and C is say $2D$. For a sound metric distance, it should be $d''\leq d+d'<2D$. In other words A would be "similar" to B and C, but the last two would be "different"/"not similar" from each other. This is counterintuitive.

The downside is that the VI distance may be computationally more expensive than calculating say a Rand index. The upside is that it's mathematically sound and makes sense.

You can use R to calculate the VI distance. You can also use Partanalyzer a program I wrote some time ago (https://github.com/MASantos/Partanalyzer). It needs a rewrite to make it more efficient, but it's open source, so you can modify it at will.

$\dagger$: Meila, M. Journal of Multivariate Analysis, 98, 873 (2007).

$\ddagger$: W.H. Zurek, Nature, vol.341, p.119 (1989).

The first step would be to train a couple of different algorithms/classifiers to get a rough idea of how good your results can be without changing your data.

Then, once you do your kmeans, you can use that information to possibly improve your data and then run it through your classifiers again to see if your results improve.

When I say "use that information to possibly improve your data", here's what I mean:

2,5,6,3,2

4,5,2,3,7

...

5,8,2,3,5

It is this data that you ran through your kmeans...using 3 clusters, each row of your data will 'belong' to a cluster...so add it to your data and your data becomes:

2,5,6,3,2,1,0,0 belongs to cluster 1

4,5,2,3,7,0,1,0 belongs to cluster 2

...

5,8,2,3,5,0,0,1 belongs to cluster 3

You could just add one column and make it 1,2,3 but some algorithms prefer the 0/1 method (one-hot encoding, dummy variable)

See, now you have a bit more information in your data than you started with. Having the before and after comparison models will let you know if it is actually useful information!

• (+1) Nice explanation with the example! – Dawny33 Nov 26 '15 at 6:33

Even if the number of clusters were equal, kt rarely holds that there is a one on one match of clusters to classes. For example, one class may be split into two clusters, and two classes may be indiscernible and thus in the same cluster.

In fact clustering is most interesting if it differs from your classes!

To compare clusterings (and classes) a number of metrics have been developed. Most are based on pair counting, and the Rand index is one of the most popular.

Instead of objects, you look at pairs of objects: are they in the same cluster and same class? Then the pair is "true positive".

See Wikipedia for more details.

• Ok , I have researched more about clustering evaluation by counting. The evaluation depends on 4 pairs of items SD = Same Cluster , Different Category DS = Different Cluster , Same Category DD = Different both cluster and category SS = Same cluster and category and with rand index the evaluation will be SS+DD / SS + SD + DS + DD I understand the concept , but I still wonder how to count the pairs. For example I have data 1 2 3 4 5 6 7 8 9 There are 3 categories (123) (456) (789) and 2 clusters (1256) (34789) How to count SD,DS,SS and DD ? – tanawatl Nov 26 '15 at 11:31
• And another question is if I need F1 result , how to calculate it (how to calculate , precision and recall )? – tanawatl Nov 26 '15 at 11:34
• @user3801162 "How to count SD,DS,SS and DD ?" By considering each pair and checking to what of these indexes it contributes to. Take 1,2. This adds one to SS; 1,3 adds one to DS, etc. – MASL Nov 26 '15 at 14:21
• If a cluster is (123) then you get pairs (12), (13), (23). – Has QUIT--Anony-Mousse Nov 26 '15 at 15:54

In cases where the number of discovered clusters differs from the number of real classes, I like to use the Maximum-match measure. Basically it tries to find an optimal matching between your results and the true classes.

Say you have a 3-class database and you found 4 clusters. Then you can get the following sample results:

$\left[\matrix{2 & 7 & 3 \\ 6 & 2 & 3 \\ 3 & 3 & 1 \\ 2 & 1 & 8}\right]$

Which can be read like this: cluster 1 has 2 elements from class 1, 7 from class 2 and 3 from class 3, and so on.

Maximum-match tries to find the 3x3 matrix with maximum trace (diagonal sum). In this case, it'd be

$\left[\matrix{ 6 & 2 & 3 \\ 2 & 7 & 3 \\ 2 & 1 & 8}\right]$

The final measure would be:

$mm = \frac{6+7+8}{41} = 0.51$

where 41 is the sum of all the elements of the 4x3 matrix.

This measure penalizes clustering methods that find extra clusters.

• You can achieve such penalization by a metric distance as the VI one mentioned above. It'd be d( 'Your Partition' , 'Real Clustering' ). – MASL Jan 13 '20 at 16:40