I have a clustering of text documents, where each document is uniquely assigned to a cluster. I have a set of labels (keywords) attached to each document. That is, each label may be applied to many different documents and a document has many labels.

How can evaluate the quality of my clustering using the multilabels as a metric? All of the basic literature and implementations I've seen assume a one-to-one, many-to-one, or one-to-many mapping, but not a many-to-many mapping.


All the cluster evaluation measures I know only work for the one-label, one-cluster case. Most cannot even deal with unclustered objects.

A recent result is this:

Moulavi, D., Jaskowiak, P. A., Campello, R. J. G. B., Zimek, A., & Sander, J. (2014). Density-based clustering validation. In Proceedings of the 14th SIAM International Conference on Data Mining (SDM), Philadelphia, PA.

You should also check earlier work by these authors.

In this article we (disclosure, I am a coauthor of the following two references) discussed some of the problems of using class labels for cluster evaluation:

Färber, I., Günnemann, S., Kriegel, H. P., Kröger, P., Müller, E., Schubert, E., ... & Zimek, A. (2010, July). On using class-labels in evaluation of clusterings. In MultiClust: 1st international workshop on discovering, summarizing and using multiple clusterings held in conjunction with KDD (p. 1).

and here we propose an approach focused on "explaining" clusters:

Kriegel, H. P., Schubert, E., & Zimek, A. (2011, September). Evaluation of Multiple Clustering Solutions. In MultiClust@ ECML/PKDD (pp. 55-66).

One observation is that often clusters are better explained by e.g. a single color component, than by a label of the ground truth (which is not too surprising, as the color components had been used for clustering, whereas the labels have not).

For text data, it may be interesting to explore this further, to identify e.g. a set of keywords that clearly separates this cluster from others, to recognize if a clustering algorithm.

You should also explore the MultiClust workshop proceedings. Evaluation is a side topic there, if I remember correctly most of the contributions were on alternative clustering and similar methods to obtain overlapping clusters and the relationships to biclustering and pattern mining. I haven't following the multi-label direction the last years, so I cannot give you more detailed pointers.

  • $\begingroup$ This is a great starting point for someone new to the field, thanks for all the references! $\endgroup$ – Hooked Jan 14 '16 at 16:35

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.