Measuring k-means clustering quality on training and test sets

Question

I'm working on implementing streaming k-means in Mahout. The code is mostly done and we're talking about how to integrate the code.

As part of the quality evaluations, I want to know how the clustering performs on the 20 newsgroups data set.

Initially, I downloaded it, converted all the e-mails into vectors, ran the clustering and got some measurements. I collected:

• the distance from each point in a cluster to its center as: the quartiles, the mean, the standard deviation;
• the number of points in each cluster;
• the cluster id;
• the type of algorithm being tested;
• the experiment run (I ran each algorithm multiple times to get an average so that the JVM has time to warm up and JIT compile whatever it can).

The algorithm itself is here.

I did this to all the data in the 20 newsgroups set. However, I've been asked to rerun the experiment taking into account the training and test set split available in a different version of the same data set.

Here's where my question comes in:

I know I need to get the clusters on the training set. But after I get the clusters, how do I use the test set?

I can assign each point to the cluster that is closest to it, but really, the 20 clusters I get are a very poor reflection of the 20 original newsgroups.

Using TF-IDF encoding, and random projections to 100 dimensions (from the 90K+ original dimensions), the original classes get mixed up in the new clusters. However, the clusters I get are more compact than the clusters produced by the actual newsgroup clusters.

So, basically:

1. I don't think the classes in the test set are useful at all (this is not a classification problem).
2. But without the classes, how is the separation in training and test sets even meaningful?
3. I can assign the points to clusters, but without readjusting the centers, what would I be measuring?
4. If I do readjust the centers, why bother with training and test sets at all?

Edit (more context): I'm working on implementing a faster clustering algorithm that behaves like k-means on top of MapReduce. It uses streaming k-means to get a sketch of the data and then collects the sketches and applies ball k-means.

I was asked to use the 20 newsgroups data set and I want to compare the quality of the clusters I get using the new algorithm with the existing methods.

@Anony-Mousse mentioned that this might not be the best choice (I think that's true). But given this data set, I need to compare its out of sample characteristics with its in sample characteristics – but I don't know what they should be!.

In a nutshell, what do I even use the test set for?

Answer 1

The problem, in particular with k-means applied to real world, labeled data is that clusters will usually not agree with your labels very well, unless you either generated the labels by using a similar clustering algorithm (self-fulfilling prophecy), or the data set is really simple.

Have you tried computing the k-means-statistics such as sums of squares etc. on the original data set? I would not at all be surprised if they are substantially worse than after running k-means.

I figure it's just another case of the algorithm does not fit to your problem.

Evaluating clustering algorithms is really hard. Because you actually want to find something you do not know yet. Even if the clustering would reproduce the original labels it then actually failed, because it did not tell you something new, and then you could just have used the labels instead.

Maybe the most realistic evaluation for a clustering algorithm is the following: if you incorporate the result from the clustering algorithm into a classification algorithm, does it improve the classification accuracy significantly? I.e. treat clustering as a preprocessing/support functionality for an algorithm that you can evaluate reasonably.