How to evaluate "external" quality of clustering?

Question

Let's say you want to cluster some objects, say documents, or sentences, or images.

On the technical side, you first represent these object somehow so that you could calculate distance between them, and then you feed those representations to some clustering algorithm.

Externally, however, you just want to group similar (in some sense -- and that's where things become pretty vague for me) objects together. For example, in case of sentences we want for clusters to contain sentences about similar topic/concept; we feel that sentences "oh look at this pic of a cute lolcat" and "facebook revealed new shiny feature tonight" should be in different clusters.

What are the usual approaches for measuring this "external" quality of clustering? I.e. we want to measure how well our clustering procedure groups initial objects (sentences, images); we're not interested in internal measures (like averaged cluster radius, clusters sparseness), since those measures deal with objects' representations, not with real objects. Meaning, the chosen representation may be awful, and even if internal measures is great, externally we'll end up with clusters that are complete junk from our vague, subjective, "some sense"-ish point of view.

P.S. Having limited knowledge in clustering domain, I suspect I may be asking about really obvious thing, or my terminology may sound strange to clustering experts. If so, please advice what should I read on the subject.

P.P.S. Just in case, I asked the very same question on Quora: http://www.quora.com/How-to-evaluate-external-quality-of-clustering

Answer 1

I do not perfectly understand what you mean by internal and external quality. I assume that internal refers to a measure computed on the obtained partition while external is the result that you would like to obtain.

Usually, internal measure aims at comparing the within cluster distance compared to the distance between the cluster. Intuitively, if clusters are dense and well separated, then you have a good clustering. As this is the objective of clustering, you cannot really do better, unless you ask people to look at your partitions and say whether or not they are good.

If the resulting clustering does not seems good to you, it is probably that either your points are not correctly placed or your distance is not adapted to your problem. For example, suppose that your expected clusters form long parallel rectangle in your representation. If you use an euclidean distance, you won't be able to find the expected partition.

To solve this problem, if in the resulting partition, you find that their is points in the same cluster that should not belong together, then ask yourself why the chosen distance considered them as close. Then, just build (or read about) a new distance function that avoid this problem.

To sum up, if you find that the computed partition does not make sense, it is not necessarily because your quality measure is wrong, but more likely because the clustering performed the wrong task. Finding a good distance and space representation is probably the main task when doing clustering.

Answer 2

Based on what I understand from your question...

It sounds like you are clustering based on one set of characteristics, but then wanting the clusters to ideally reflect other characteristics that your clustering wasn't based on. The way to fix this is to give everything some thought before estimating any models, and making sure your "internal" charateristics match up with the "external" ones. In other words, if you want sentences that are clustered based on topic, then the crux is to find the distance metric (or whatever) that reflects that. EDIT: This is also basically what Mougel says.

That said, maybe you don't have any ideas on how to do this at the start and want to experiment a bit. The trouble with clustering is that the class labels are unknown...but from your example it seems like a person could look at the individual results and decide if they were happy with the clustering. So you could cluster, then take a manageable random sample of the output and see how well it did for yourself. Extending from this, you could assign class labels at the start and turn this into a classification problem.

Bottom line: I'm not aware of a "statistical" or automated approach to this - this seems like a problem that will be solved with more user input and thoughfulness.

Answer 3

Solving a real problem takes a combination of technique and domain knowledge. You're asking about technique, and you're getting good answers on that front. But you can't really succeed without some defined domain knowledge. Your main task is to elicit, focus, distill, etc, that domain knowledge. Then you'll be able to properly apply a technique.

So you need to help them (whoever it is that's waving their arms and crying "No good, no good!" about your clusters) focus. If you're clustering photos, make or solicit 20 specific examples of good clusters (of say 5 photos each), and 20 specific examples of bad clusters. You can then take the advice of the other answers in this thread and try to align your clustering distance with the answers.*

This is the part of statistics that books and classes really don't cover. It's the consultant side of the coin. But I can't see any way you'll succeed without doing it. (Even if the them is you.)

_* There are also semi-supervised techniques that use some labeled data and mostly unlabeled data, but as a first step you can explore your data with what labels you can elicit and then figure out what metric works best.