I am trying to fit several cluster algorithms on one or across several subsets of a data matrix X, of shape (n_samples, n_features).

For example:

import numpy as np
from sklearn.cluster import KMeans

y_preds = list()
for X_ in np.array_split(X, 10, axis=0):  # for each subset of X
    dist = pairwise_distances(X_)  # compute similarity matrix
    y_preds.append(KMeans().fit_predict(dist))  # aggregate predicted cluster

Although the resulting clusters are very similar across subsets, the cluster labels are (obviously) random.

How can I aggregate these labels to estimate which set of cluster(s) most robustly fit the data, and ideally get an single robust cluster estimate (i.e. finding the most robust clusters across iterations)?

In other words, is there some bagging procedure for clustering?


Cross-validation only works for supervised methods.

If you run k-means multiple times, you will (usually) get different results, because of random initialization and local minima.

It's not as if any of these is substantially "wrong", nor is any one more correct than the others except for the rather irrelevant metric of least-squares (SSQ).

Even worse, there are k! solutions that are virtually identical (except for permutation of labels). Clustering does not produce labels comparable to classification labels. They are just random numbers. Usually, you choose 0,1,2,... as labels then. But they do not mean anything. Thus, it does not mean anything if a point was clustered 1 in one run, and 2 in another.

Because of this, all the classification metrics do not work either. Precision/Recall do not work when there is no "true label". You do not have "true positive" labeled objects.

What is commonly done is to switch from point labels to pairs. A pair is two objects thst belong to the same cluster. If two results agree on a pair, it's TP. If one has the pair, the other not, then FP/FN. And if neither has the pair: TN. Then you can derive several metrics from this. But this only works for a small subset of clustering algorithms (k-means is one where this works). It's not clear how you would use this for "cross validation". It will summarize how similar two results are (even when labels cannot be compared), but that won't give you correctness.

  • $\begingroup$ Thanks for the detailed response.Cross-validate was indeed misleading; I am trying to run clustering on several data subsets to find what is the most robust set of clusters. I understand that there is no ground truth in non-supervised methods. I will correct the question accordingly. $\endgroup$ – kingjr Mar 23 '16 at 14:39
  • $\begingroup$ Note that k-means A) won't give the same result even if you run it multiple times on the same data set, and B) it optimizes least-squares, so by definition the best result is the one with the least squared error on your data set. Any other "consensus" is worse by this objective - so why use something inferior? It's not as if they would take different aspects into account. Just some runs got stuck in a suboptimal solution, but they all agree o what should be the best solution. $\endgroup$ – Has QUIT--Anony-Mousse Mar 23 '16 at 15:12
  • $\begingroup$ Thanks. The question aims at being more general: how to aggregate clustering results. I'll correct it accordingly. $\endgroup$ – kingjr Mar 24 '16 at 16:39
  • $\begingroup$ Which will be a inferior solution with k-means. If you want to improve k-means, run it multiple times and keep the best run only. It does not get better or more reliable if you combine the best with worse solutions. $\endgroup$ – Has QUIT--Anony-Mousse Mar 24 '16 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.