Clustering quality measure

Question

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.

Answer 1

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).

Answer 2

The Silhouette can be used to evaluate clustering results. It does so by comparing the average distance within a cluster with the average distance to the points in the nearest cluster.

Answer 3

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.

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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.

Answer 8

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