# Quantifying how successful results of clustering are with a test

I have a three types of experiments with many measurements taken. I want to show that using clustering on the unlabelled measurements, I can uncover the three groups. Now using kmeans plus, I get around 60% accuracy. Which if it was binary, would be poor, but how do I quantify how good that is for three categories? Is there a p value I can compute and compare against? I am thinking that if there were 100 categories 60% for the correct labelling is great and far from random, so how can I do this with a test?

• any specific reason you want to use clustering? Aug 26, 2011 at 8:19
• Are your measurements 1d, 2d ... ? Can you put up a scatter plot / 3x3 confusion matrix for your data or, even better (many eyes) for some synthetic data ? Aug 26, 2011 at 9:21
• @Denis:The data is 112d. Therefore I don't think I can use a scatter plot.
– Vass
Aug 30, 2011 at 15:35
• @Vass, indeed (although you could project down to 2d with PCA, to plot). Are any of of the points labelled, for comparison ? Aug 30, 2011 at 16:37
• @Denis, they are not labelled, but I know from which category they were produced
– Vass
Sep 18, 2011 at 19:50

You can get a p-value from a Monte Carlo resampling approach.

Take your number of obserations (n) and randomly distribute them into k groups. Repeat this procedure many times (10,000+). Count the number of times in which this process yields a clustering equal to or better than your own. Put that number over the total number of Monte Carlo trials, and that's your p-value: the chance of getting a clustering as good or better than yours by chance alone.

I agree with Greg Snow, though, that a p-value isn't a measure of prediction strength. Reporting the p-value along with Cohen's kappa and (of course) the descriptive statistics would probably be a good idea.

• is this not related to consensus clustering in a way or consensus statistics? The kappa of Cohen is more useful to see how different algorithms for clustering perform, still very interesting. But unless I have not understood the same algorithm can be used multiple times independently for a Cohen kappa?
– Vass
Sep 20, 2011 at 12:15
• To be honest I am not really sure. I think Cohen's kappa (or simply a confusion matrix) can provide a good picture of how well a clustering algorithm performs for -your- data, and not just how well the algorithm performs in general. Mostly I was just suggesting that a p-value derived from this approach, while informative, does not tell the whole story. The reason is that if you know your data is clustered, it's not surprising that a clustering algorithm performs better than random selection (and thus has a low p value).
– Jeff
Sep 21, 2011 at 18:31
• that is actually what I ended up doing. Luckily the random fluctuations reach this configuration less than the p-value. thanks!
– Vass
Sep 22, 2011 at 22:56

You could use Cohen's kappa test for the 3 x 3 classification table (actual membership by clustering membership).

Testing for a statistically significant relationship and quantifying the quality of predictions are 2 very different proceedures. With enough data it is possible to show something is statistically significant even when the effect is to small to care about. For your example with 3 groups (assuming they are the same size) we would expect a completely random clasiffication to get the right answer $\frac13$ of the time. A method that was correct 35% of the time could be found to have a very small p-value, but would not be a practical improvement above 33%. On the other hand, with small data you may have a classifier that is right 90% of the time but not statistically significant.