# clustering evaluation for a special case

In my dataset each point comes from one of 3 classes, so the true labels are like [0,1,0,0,0,2,1....]. I have to cluster them in 200 clusters. I want each cluster to contain more points from the same class. So, a cluster such as [0,0,0,1] (C1) is a good cluster, whereas [1,2,1,0] (C2) is not.

I am trying to come up with an evaluation strategy for this. The harmonic mean of class frequencies seems like a starting point. For C1, it would be (1/3)+(1/1)+(1/(0+eps)), for C2: (1/2)+(1/1)+(1/1). Taking eps=0.1, obviously, C1 has a higher score.

But this would be affected by cluster size. Is there a way to eliminate that? Or better, does any evaluation protocol exist in the literature for this problem?

EDIT

I am trying to create a codebook of visual words from images. I have N images from 3 classes. These 3 classes are the true labels.

From each image, F number of d dimensional feature descriptors are created. So I have a data matrix of N*F rows and d columns. These are clustered in 200 clusters and the cluster centers are combined to create the codebook. I believe This is a standard procedure for this problem (https://en.wikipedia.org/wiki/Bag-of-words_model_in_computer_vision).

I expect the clusters to have some kind of homogeneity, i.e., in each cluster, most data points should from one class of image.

• It's unclear what you mean by a "cluster". For example, why not create classes of all zeros, all ones, and all twos? What constraints, if any, do you have on the sizes of the classes? What distinction are you trying to make with the phrase "true labels"? – whuber Feb 4 '16 at 20:57
• It looks like your data is a single vector of class labels. Is that correct, or are there other variables that can be considered "input" for which the label is the "output"? – EngrStudent Feb 4 '16 at 21:00
• I have added some clarification, please see if that makes it more clear. – rivu Feb 4 '16 at 21:09