# Clustering quality measure

I have a clustering algorithm (not k-means) with input parameter $k$ (number of clusters). After performing clustering I'd like to get some quantitative measure of quality of this clustering. The clustering algorithm has one important property. For $k=2$ if I feed $N$ data points without any significant distinction among them to this algorithm as a result I will get one cluster containing $N-1$ data points and one cluster with $1$ data point. Obviously this is not what I want. So I want to calculate this quality measure to estimate reasonability of this clustering. Ideally I will be able to compare this measures for different $k$. So I will run clustering in the range of $k$ and choose the one with the best quality. How do I calculate such quality measure?

UPDATE:

Here's an example when $(N-1, 1)$ is a bad clustering. Let's say there are 3 points on a plane forming equilateral triangle. Splitting these points into 2 clusters is obviously worse than splitting them into 1 or 3 clusters.

-
To me this is not obvious. I see clusters that in reality have different sizes all the time... –  Anony-Mousse Apr 27 '12 at 6:41

The choice of metric rather depends on what you consider the purpose of clustering to be. Personally I think clustering ought to be about identifying different groups of observations that were each generated by a different data generating process. So I would test the quality of a clustering by generating data from known data generating processes and then calculate how often patterns are misclassified by the clustering. Of course this involved making assumtions about the distribution of patterns from each generating process, but you can use datasets designed for supervised classification.

Others view clustering as attempting to group together points with similar attribute values, in which case measures such as SSE etc are applicable. However I find this definition of clustering rather unsatisfactory, as it only tells you something about the particular sample of data, rather than something generalisable about the underlying distributions. How methods deal with overlapping clusters is a particular problem with this view (for the "data generating process" view it causes no real problem, you just get probabilities of cluster membership).

-
+1 for highlighting the distinction between model-based clustering vs. purely distance-based unsupervised clustering. –  chl Jan 15 '11 at 10:58
I think both purpose have their faire use in different settings. There are many context were you actually do to only look at the data at hand (eg. outlier definition). Also, before being able to get to different data generating processes, you need exploration which is best done with your second definition... –  Etienne Low-Décarie Apr 27 '12 at 13:41
I do agree Etienne that both methods have their uses. However I would also say that whether an observation is an outlier or not implicitly makes some assumptions about the data generating process, so the second form of clustering is perhaps only for the first step in understanding the data when you are trying to orient yourself properly. –  Dikran Marsupial Apr 27 '12 at 14:42

Since clustering is unsupervised, it's hard to know a priori what the best clustering is. This is research topic. Gary King, a well-known quantitative social scientist, has a forthcoming article on this topic.

-
+! Yup; @Max What do you thing this "obvious" clustering would be? –  mbq Jan 14 '11 at 17:33
@mbq: Actually I don't know what would be a good clustering for this. By "obvious" I ment that (N-1, 1) is definitely not a good clustering for this. A better clustering would be only one cluster, so no clustering at all. Or maybe some clustering with the number of clusters more than 2. –  Max Jan 14 '11 at 18:19
You link seems to be broken. –  Etienne Low-Décarie Apr 27 '12 at 13:41

Here you have a couple of measures, but there are many more:

SSE: sum of the square error from the items of each cluster.

Inter cluster distance: sum of the square distance between each cluster centroid.

Intra cluster distance for each cluster: sum of the square distance from the items of each cluster to its centroid.

Maximum Radius: largest distance from an instance to its cluster centroid.

Average Radius: sum of the largest distance from an instance to its cluster centroid divided by the number of clusters.

-
I've tried using intra in inter cluster distance, but couldn't think of something usefull for a cluster with one point. Also I don't have a center point. I only have distances between points. –  Max Jan 15 '11 at 12:52
The higher the inter cluster distance the better, you can measure it by calculating the distances between the center of the clusters. –  mariana soffer Jan 17 '11 at 23:47

As others have pointed out, there are many measures of clustering "quality"; most programs minimize SSE. No single number can tell much about noise in the data, or noise in the method, or flat minima — low points in Saskatchewan.

So first try to visualize, get a feel for, a given clustering, before reducing it to "41". Then make 3 runs: do you get SSEs 41, 39, 43 or 41, 28, 107 ? What are the cluster sizes and radii ?

(Added:) Take a look at silhouette plots and silhouette scores, e.g. in the book by Izenman, Modern Multivariate Statistical Techniques (2008, 731p, isbn 0387781889).

-

You ran into the Clustering Validation area. My student did validation using techniques described in:

A. Banerjee and R. N. Dave. Validating clusters using the hopkins statistic. 2004 IEEE International Conference on Fuzzy Systems IEEE Cat No04CH37542, 1:p. 149–153, 2004.

It is based on the principle, that if a cluster is valid then data points are uniformly distributed within a cluster.

But before that you should determine if your data has any so called Clustering Tendency i.e. if it is worth clustering and optimum number of clusters:

S. Saitta, B. Raphael, and I. F. C. Smith. A comprehensive validity index for clustering. Intell. Data Anal., 12(6):p. 529–548, 2008.

-

If the clustering algorithm isn't deterministic, then try to measure "stability" of clusterings - find out how often each two observations belongs to the same cluster. That's generaly interesting method, useful for choosing k in kmeans algorithm.

-

A method such as that used in unsupervised random forest could be used.

Random Forest algorithms treat unsupervised classification as a two class problem, were a whole different artificial and random data set is created from the first data set by removing the dependency structure in the data (randomization).

You could then create such a artificial and random data set, apply your clustering model and compare you metric of choice (eg. SSE) in your true data and your random data.

Mixing in randomization, permutation, bootstrapping,bagging and/or jacknifing could give you a measure similar to a P value by measuring the number of times a given clustering model gives you a smaller value for you true data than your random data using a metric of choice (eg. SSE, or out of bag error prediction).

Your metric is thus difference (probability, size difference,...) in any metric of choice between true and random data.

Iterating this for many models would allow you to distinguish between models.

This can be implemented in R.

randomforest is available in R

-
+1, I like this idea; however, randomization / permuting the data will only break relations b/t variables, this wouldn't work if there is clustering w/i a single variable. –  gung Aug 29 at 16:00