How to tell if data is "clustered" enough for clustering algorithms to produce meaningful results?

Question

How would you know if your (high dimensional) data exhibits enough clustering so that results from kmeans or other clustering algorithm is actually meaningful?

For k-means algorithm in particular, how much of a reduction in within-cluster variance should there be for the actual clustering results to be meaningful (and not spurious)?

Should clustering be apparent when a dimensionally-reduced form of the data is plotted, and are the results from kmeans (or other methods) meaningless if the clustering cannot be visualized?

Answer 1

About k-means specifically, you can use the Gap statistics. Basically, the idea is to compute a goodness of clustering measure based on average dispersion compared to a reference distribution for an increasing number of clusters. More information can be found in the original paper:

Tibshirani, R., Walther, G., and Hastie, T. (2001). Estimating the numbers of clusters in a data set via the gap statistic. J. R. Statist. Soc. B, 63(2): 411-423.

The answer that I provided to a related question highlights other general validity indices that might be used to check whether a given dataset exhibits some kind of a structure.

When you don't have any idea of what you would expect to find if there was noise only, a good approach is to use resampling and study clusters stability. In other words, resample your data (via bootstrap or by adding small noise to it) and compute the "closeness" of the resulting partitions, as measured by Jaccard similarities. In short, it allows to estimate the frequency with which similar clusters were recovered in the data. This method is readily available in the fpc R package as clusterboot(). It takes as input either raw data or a distance matrix, and allows to apply a wide range of clustering methods (hierarchical, k-means, fuzzy methods). The method is discussed in the linked references:

Hennig, C. (2007) Cluster-wise assessment of cluster stability. Computational Statistics and Data Analysis, 52, 258-271.

Hennig, C. (2008) Dissolution point and isolation robustness: robustness criteria for general cluster analysis methods. Journal of Multivariate Analysis, 99, 1154-1176.

Below is a small demonstration with the k-means algorithm.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

The results are quite positive in this artificial (and well structured) dataset since none of the three clusters (krange) were dissolved across the samples, and the average clusterwise Jaccard similarity is > 0.95 for all clusters.

Below are the results on the 20 bootstrap samples. As can be seen, statistical units tend to stay grouped into the same cluster, with few exceptions for those observations lying in between.

You can extend this idea to any validity index, of course: choose a new series of observations by bootstrap (with replacement), compute your statistic (e.g., silhouette width, cophenetic correlation, Hubert's gamma, within sum of squares) for a range of cluster numbers (e.g., 2 to 10), repeat 100 or 500 times, and look at the boxplot of your statistic as a function of the number of cluster.

Here is what I get with the same simulated dataset, but using Ward's hierarchical clustering and considering the cophenetic correlation (which assess how well distance information are reproduced in the resulting partitions) and silhouette width (a combination measure assessing intra-cluster homogeneity and inter-cluster separation).

The cophenetic correlation ranges from 0.6267 to 0.7511 with a median value of 0.7031 (500 bootstrap samples). Silhouette width appears to be maximal when we consider 3 clusters (median 0.8408, range 0.7371-0.8769).

Answer 2

When are results meaningful anyway? In particular k-means results?

Fact is that k-means optimizes a certain mathematical statistic. There is no "meaningful" associated with this.

In particular in high dimensional data, the first question should be: is the Euclidean distance still meaningful? If not, don't use k-means. Euclidean distance is meaningful in the physical world, but it quickly loses meaning when you have other data. In particular, when you artificially transform data into a vector space, is there any reason why it should be Euclidean?

If you take the classic "old faithful" data set and run k-means on it without normalization, but with pure Euclidean distance, it already is no longer meaningful. EM, which in fact uses some form of "cluster local" Mahalanobis distance, will work a lot better. In particular, it adapts to the axes having very different scales.

Btw, a key strength of k-means is that it will actually just always partition the data, no matter what it looks like. You can use k-means to partition uniform noise into k clusters. One can claim that obviously, k-means clusters are not meaningful. Or one can accept this as: the user wanted to partition the data to minimize squared Euclidean distances, without having a requirement of the clusters to be "meaningful".

Answer 3

One way to quickly visualize whether high dimensional data exhibits enough clustering is to use t-Distributed Stochastic Neighbor Embedding (t-SNE). It projects the data to some low dimensional space (e.g. 2D, 3D) and does a pretty good job at keeping cluster structure if any.

E.g. MNIST data set:

Olivetti faces data set:

Answer 4

Surely, the ability to visually discern the clusters in a plotable number of dimensions is a doubtful criterion for the usefulness of a clustering algorithm, especially if this dimension reduction is done independently of the clustering itself (i.e.: in a vain attempt to find out if clustering will work).

In fact, clustering methods have their highest value in finding the clusters where the human eye/mind is unable to see the clusters.

The simple answer is: do clustering, then find out whether it worked (with any of the criteria you are interested in, see also @Jeff's answer).

Answer 5

I have just started using clustering algorithms recently, so hopefully someone more knowledgeable can provide a more complete answer, but here are some thoughts:

'Meaningful', as I'm sure you're aware, is very subjective. So whether the clustering is good enough is completely dependent upon why you need to cluster in the first place. If you're trying to predict group membership, it's likely that any clustering will do better than chance (and no worse), so the results should be meaningful to some degree.

If you want to know how reliable this clustering is, you need some metric to compare it to. If you have a set of entities with known memberships, you can use discriminant analysis to see how good the predictions were. If you don't have a set of entities with known memberships, you'll have to know what variance is typical of clusters in your field. Physical attributes of entities with rigid categories are likely to have much lower in-group variance than psychometric data on humans, but that doesn't necessarily make the clustering 'worse'.

Your second question alludes to 'What value of k should I choose?' Again, there's no hard answer here. In the absence of any a priori set of categories, you probably want to minimize the number of clusters while also minimizing the average cluster variance. A simple approach might be to plot 'number of clusters' vs 'average cluster variance', and look for the "elbow"-- where adding more clusters does not have a significant impact on your cluster variance.

I wouldn't say the results from k-means is meaningless if it cannot be visualized, but it's certainly appealing when the clusters are visually apparent. This, again, just leads back to the question: why do you need to do clustering, and how reliable do you need to be? Ultimately, this is a question that you need to answer based on how you will use the data.

Answer 6

To tell whether a clustering is meaningful, you can run an algorithm to count the number of clusters, and see if it outputs something greater than 1.

Like chl said, one cluster-counting algorithm is the gap statistic algorithm. Roughly, this computes the total cluster variance given your actual data, and compares it against the total cluster variance of data that should not have any clusters at all (e.g., a dataset formed by sampling uniformly within the same bounds as your actual data). The number of clusters $k$ is then chosen to be the $k$ that gives the largest "gap" between these two cluster variances.

Another algorithm is the prediction strength algorithm (which is similar to the rest of chl's answer). Roughly, this performs a bunch of k-means clusterings, and computes the proportion of points that stay in the same cluster. $k$ is then chosen to be the smallest $k$ that gives a proportion higher than some threshold (e.g., a threshold of 0.8).