I have 'n' observations which are classified in two classes: Class A and Class B. The observations are mis-balanced with Class A constituting around 90% of the samples and Class B around 10%. The observations are represented by 'd'-dimensional vectors. I am clustering the set using k-means clustering into 'c' clusters.

Once, I cluster these observations, I look at Class B's cluster distribution (ie. which cluster got how many class B observations). There are 'm' different ways (~500) of generating this cluster distribution by varying 'c', 'd' and one other parameter.

My goal is to identify set of parameters that yields best cluster distribution for class B. The best cluster distribution will have maximum number of Class B observations clustered into lesser (not least) number of clusters. Once, I identify "Class B" clusters, I will look at all Class A observations in those clusters and do some further analysis on them.

Problem: I am not sure how to quantify "best cluster distribution" so that I can compare these clustering results.

All suggestions are welcome !!!

Edit: End Goal: My end goal of this exercise is to identify those class A observations which display traits similar to class B. Say I form five clusters using both class A-Class B observations for a particular set of parameters. For these five clusters, I look at the assignment of Class B observations which for example looks like this: [2%, 40%, 45%, 3%, 10%]. Based on this I can clearly say that cluster 2 and 3 are "class B" clusters and all class A observations belonging to these clusters will show similar traits to class B. Now, my only problem is how do I quantify this "best clustering distribution" so that I can compare results from multiple runs.

In case, if you think there can be a better approach other than clustering to identify Class A observations that show traits similar to class B, then please do share. Thank you so much for your time and efforts !!!

  • 1
    $\begingroup$ If you know there are two classes (which seems to be what your first sentence says) why are you varying the number of clusters (or doing k-means)? In fact, if you know which observations go into which class, why are you doing cluster analysis at all? Why not a supervised method? $\endgroup$
    – Peter Flom
    Jan 17, 2015 at 12:12
  • $\begingroup$ Hi Peter, thanks for your response. I updated my post to give a big-picture overview for this exercise. If you think there can be a better way of doing this, then please let me know. $\endgroup$
    – PS1
    Jan 17, 2015 at 16:57

1 Answer 1


While I don't think the overall approach is viable - just trying out lots of parameters is a way to overfit, and if k-means would work on this data, you should be looking for reoccurring, stable, results - here is a classic measure for your evaluation: sun of squares.

You want the objects of one class $B$ to be concentrated in a few clusters. This happens if you choose the result that maximizes $$\sum_C |B\cap C|^2$$ where $C$ are your clusters.

There are many similar measures to be found in information theory. You are looking for “purity”.

  • $\begingroup$ Hi Anony-Mousse, thanks for your response. I tried looking for "purity" online but this was the closest I could find on wiki: en.wikipedia.org/wiki/Purity_(quantum_mechanics). Did you mean this or something else. In the process, I also ended up identifying "entropy". My goal should be to minimize entropy. $\endgroup$
    – PS1
    Jan 17, 2015 at 17:02
  • $\begingroup$ I also updated my post above to better reflect my end goal for this exercise, just in case if you think there can be a better alternative. Thanks once again. $\endgroup$
    – PS1
    Jan 17, 2015 at 17:03
  • $\begingroup$ Entropy, information gain, chi-squared, mutual information to name a few. The idea behind is usually some form of measuring how pure the subsets are. $\endgroup$ Jan 17, 2015 at 17:14

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.