I'm applying a Hierarchical Agglomerative Clustering (HAC) for grouping my data and I need to determine the number of the cluster automatically. To determine the optimal number of cluster, I obtain the the best cluster combination which maximizes the similarity of each member in one cluster and minimizes the similarity between clusters.

So far my strategy is working well. But I have one case where my HAC algorithm is totally failed, as you can see in this image there are two groups (in upper right) which the variance of each members is really small (very small compared to others...). I expect my clustering would end like this, but unfortunately, this is what i get. The data with larger variance, ends up with small partitions instead group them into three bigger clusters

because of these two groups, which each data is really similar (almost the same) with each other, it messed up with optimization strategy to determine the best number of cluster of my HAC algorithm.

I want to ask if there's any optimization strategy especially for HAC which can deal with this kind of case. So far I'm still looking for any strategy which considers variance of the data but I'm still not sure,

Currently the best strategy that popped out in my head is :

  1. Automatically detect the sub-clusters (or sub-tree of dendogram of HAC) which are considered having small variance (or the similarity is really close)
  2. Discard them
  3. Recalculate HAC.

The problem is how do I define "small value of variance"?

If you know any better strategy i would be happy to know :)

  • $\begingroup$ I think your intuition is correct, but defining a "small value of variance" could be tricky. As a first pass, I would try an ensemble approach e.g. bagging. $\endgroup$ – Sameer Dec 4 '12 at 16:30
  • $\begingroup$ It isn't hierarchical, but my suggestion might be useful. Can you use something like Gaussian Mixture Modeling to fit it, and to generate higher sample volumes for your clusters? Then you could perform robust hierarchical modeling and not have small sample size hurt your convergence. $\endgroup$ – EngrStudent Jul 12 '13 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.