I'm wondering if anybody can point me to work on the evaluation of unsupervised learning where there are a very large (say hundreds of millions) number of points and manual labelling can only ever be obtained for a small fraction of the points.

To elaborate, most clustering evaluations assume gold standard labels for the data points. While I can feasibly obtain this for a small number of points (say in the thousands, or perhaps tens of thousands) this is a small fraction of the total. Furthermore it is obviously not possible to cluster only the labelled points, since the presence of all the unlabelled data would fundamentally change the shape of the solution. The labels are also not well defined (they are a function of the items contained in the cluster) so assigning manual labels to points individually is unlikely to be consistent.

One possibility that occurred to me is to label the pairs of points as to whether they should be linked or not: however, chosen at random two points have a vanishingly small chance of being linked, so the true positive rate on the links would have very high variance.

I would appreciate if anyone knows of work in a similar area that they could point me to, or can describe an evaluation strategy known to work in such circumstances.

EDIT: One thing that makes my application hard to evaluate, besides the scale, is the number of clusters. Typically I'll have perhaps an order of magnitude fewer clusters than data points (on average 10 points per cluster), and so random sampling of the points to label will lead to almost no sampled points in the same cluster. This means getting creative with sampling a single point, and then evaluating in its neighbourhood, is likely to be much more productive but also potentially introduce more bias.

  • $\begingroup$ why are you doing unsupervised clustering rather than classification anyway, if you have a labelling. Why not use eg random forests to develop a classification based on the existing labelled data... I don't see how you can expect unsupervised clustering to ever hit on your desired labelling $\endgroup$
    – seanv507
    Commented Sep 15, 2014 at 11:05
  • $\begingroup$ By labelling, I mean I can assign a small sub-sample of points to their correct group. Labels are arbitrary identifiers. There are far more groups than I can hope to sample, so learning a classifier for each label is not possible. It is possible to learn a link detector from the scale of labelled data, but that still needs clustering to be applied thereafter to solve the global problem. It is this I'm interested in evaluating $\endgroup$ Commented Sep 16, 2014 at 8:24
  • $\begingroup$ I think it would help if you gave the actual problem you are trying to solve. basically clustering will find things based on a distance measure...but are all coefficients in your vector equally important in determining the true group? this is something unsupervised learning cannot find out. $\endgroup$
    – seanv507
    Commented Sep 16, 2014 at 8:56
  • $\begingroup$ I'm sorry, I don't understand your comment. I'm solving a standard clustering problem, which has the property that it's very large and has a large number of clusters relative to the number of data points (perhaps 1 cluster per 10 data points). I was looking for direction to previous work where this clustering problem is evaluated relative to a gold standard partition on a tiny fraction of the data, and whether there were standard practices for this. $\endgroup$ Commented Sep 17, 2014 at 13:32

1 Answer 1


All the clustering evaluation measures I've seen an be computed on a sample only.

So you could measure quality by how well it agrees with your reference clustering on the labeled data only. Have a look at ARI, for example. It's straightforward to compute it on a subset only.

The question is whether this does help solve you an actual problem. If you overfit on your labels, you might as well use classification; and classification will always be better.

  • $\begingroup$ Yeah, I agree about the overfitting part. One interesting aspect of the problem I'm looking at is that the number of classes is huge (perhaps one order of magnitude less than the number of instances), and so randomly sampling points for labelling is a very poor idea. I will elaborate in the question, as it was remiss of me to leave this out! $\endgroup$ Commented Sep 15, 2014 at 8:43
  • $\begingroup$ You can also only select a few clusters for labeling. ARI does not need to have labeled instances in every cluster. But if you choose the clusters to label poorly that of course will cause problems. $\endgroup$ Commented Sep 15, 2014 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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