Testing whether two datasets cluster similarly

Most questions about cluster analysis seem to come from people who have a single dataset and want to compare/quantify the similarity of different clustering approaches. This question is not that. Instead, my goal is to take two separate datasets, apply the same clustering technique, and then compare/quantify the similarity of the resulting clusters.

I'll make it a bit more concrete. Let's say I'm taking a survey, and I want to use hierarchical cluster analysis to reveal the latent groupings in the data. Survey A takes an hour to administer, whereas Survey B takes 5 minutes to administer. I can probably assume that the data obtained from Survey A are a better estimate of the real world, but I want to know how well Survey B stacks up. Clearly the actual numbers are going to differ, but if both surveys yield the same clusters, then it's probably better to just use the shorter one.

So the big question is: what's an appropriate metric for measuring how different two sets of clusters are? I've had a quick read through Comparing Clusters - An Overview, and my first sub-question is whether there's been subsequent development since this paper was written (2007). They tentatively advocate for measures based on mutual information (section 5), but then caution that it's not well worked-out. My second sub-question is whether it's even appropriate to apply these methods to clusters that are based on different datasets.

• By "different datasets", you probably mean that the two datasets have the same feature space, but may include different realizations. Correct? – Stephan Kolassa May 18 '16 at 6:37
• Yes, that's correct. – Matt May 18 '16 at 13:47
• Maybe a bit late but what about creating a pooled data set from your two surveys (A+B) and then compare the clustering results of clustering on A and B separately with that of on A+B. Also one can always use a bootstrap to get robustness. – DataD'oh Sep 1 '17 at 10:19
• Thanks- not at all too late! This is pretty close to what I've been doing: clustering (A+B), where A1 and B1 are treated as though they were independent, although in reality "1" is the same individual tested under different conditions (e.g. short vs. long form). After clustering the combined dataset, I then calculate how frequently both datapoints from a given individual were assigned to the same cluster. I then use monte carlo simulations to establish that agreement is more than chance, and Cohen's kappa (en.wikipedia.org/wiki/Cohen%27s_kappa) to measure the strength of agreement. – Matt Sep 2 '17 at 14:28
• @Matt, did you find any concrete answer to this problem eventually? – Artiga Mar 16 '18 at 10:28

"Clustering is an art, not a science."

If you give the same data set to two different researchers, they will usually/probably find very different clusterings. Because there are many decisions to make such as preprocessing and distance functions.

But if two researchers won't even agree on the same data set, how can you expect to draw conclusions from two different data sets?

• I take your point, but in this case it will be the same researchers working with datasets that are expected to be highly similar. Suppose we gave the exact same dataset to the same researcher using the same choices re: preprocessing and distance functions, we should get results that are either identical or pretty close, right? But then if we repeated the process with a drastically different dataset, we should get drastically different results. It seems like there ought to be a principled way of capturing/quantifying the degree of similarity/difference. – Matt May 18 '16 at 13:51
• Even then I think many clustering algorithms will be rather unstable. Consider k-means. Run it twice with different seeds, and you most often do get drastically different results, even if you do not change any data or parameter (except the random seed). Clusterings are much less reliable in my experience than you appear to assume. – Anony-Mousse May 18 '16 at 15:00
• I'm pretty new to cluster analysis, so it's very possible that I'm just too starry-eyed to grasp the limitations. But I'm not giving up yet. How about the following alternative: In the study, both surveys will be given to the same individual. I could then combine these two datasets, such that in the resulting file there would be two entries for each individual. I'd then perform hierarchical cluster analysis on the combined dataset and then simply count how often the two datapoints for one individual are assigned to the same cluster. Drawback: might preclude significance testing. – Matt May 20 '16 at 2:08

One problem with your scenario, which is unrelated to clustering, is that you want to check whether your results are similar, and it is always harder to do than testing whether they are different. Most statistical tools work well to detect differences that are larger than a certain threshold, and make a poor argument when you need to claim the opposite.

Here's one idea though. Say, you study your first dataset, and decide that it seems to have 3 clusters. You justify this selection properly, using one of the standard validity tests. Then you run k-clustering (or EM clustering) without randomization and assign each point of dataset 1 to a cluster.

Then you start subsetting your dataset, adding points from dataset 2 to it, one at a time, and running the same clustering algorithm every time. One point would not skew your clusters too much, so essentially you'll mark-up your dataset 2 using clusters defined by dataset 1.

Then you run same clustering algorithm on dataset 2 alone. Now for each point you know in which of 3 clusters it was put based on the dataset 1, and in which one - based on the dataset 2. You can calculate the share of this overlap, which is already telling. You can also calculate the p-value that this overlap is not random (but most probably it won't be random, unless your clusters are really spurious, so this test would not be too useful).

Arguing that the difference is small is harder. But in principle, you'll have to define how you expect your data to be different, if it is different. Then specify what is the biggest difference that you are willing to tolerate. Then somehow generate a set of surrogate datasets that are "different" with your "critical difference", and see how likely you are to get the actually observed overlap between dataset 2 cluster and dataset 1 cluster on a random dataset. But to do it, first and foremost, you need a good, well thought-through $H0$ hypothesis.

You can use other sorts of measurements as well: for example, you could compute the average separation (the mean of all pairwise distances) between the points from "matching clusters" in datasets 1 and 2. Or you could use entropy-based approaches. But regardless of the approach, proving that the clusters are different would be easy, while proving that they are "essentially the same" would require introduction of additional assumptions, and a good solid $H0$.

• Thanks! Your one-at-a-time approach is an interesting possibility that I hadn't considered. As to the larger issues you raise, I agree that demonstrating difference is much easier than demonstrating similarity: my problem is that rejecting the null hypothesis is basically uninteresting- what I need is more analogous to a measure of effect size than a measure of statistical significance. The datasets definitely have higher-than-chance similarity (e.g. p <.001 by monte carlo simulations), but that doesn't really address the question of how strongly they agree. – Matt Sep 2 '17 at 14:19
• One simple solution, as one of the commenters suggested, would really be to cluster the union of both datasets, and then check whether individually the datasets are significantly different than the union. If they aren't, here you go. I'm not sure it is the most straightforward argument, but at least it is simple to run. Anything better than that, I think, would require additional assumptions on what "being different" actually entails. – ampanmdagaba Sep 2 '17 at 19:41