3
$\begingroup$

I am trying to use R to do Kmeans clustering and as most people I ran into the challenge of determining when to finish. I have 10,000 items and potentially 10 times of that down the road. My goal is to create a series of clusters with minimal size (e.g. 50 items per cluster) OR reasonably similar items. In other words, I don't want any of my output clusters to be too small (even if the items are quite different from each other), but I also don't mind if the clusters are too big as long as the items are similar enough.

I imagine I can use some kind of divisive hierarchical approach. I can start by building a small number of clusters and examine each cluster to determine if it needs to be split into more clusters. I can keep doing this till all clusters meet my stopping criteria.

I wonder if anyone knows good information on how other people do this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

There is a whole family of hierarchical clustering which should suit your needs, as it creates a tree, where each level represents the bigger (more general) clusters. Analysis of this structure and some custom cutting will bring you to described solution.

In R you can check out this source http://cran.r-project.org/web/views/Cluster.html , where you will find some hierarchical clustering implementations.

The easiest approach would be to:

  • run hierarchical clustering (any) and analyze the tree and select clusters generality which fits your constraints
  • cluster with any existing method, and then prune the small clusters (remove them iteratively and assign each point to the nearest of the remaining clusters).
Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm running into a similar issue -- can you please describe in more details (preferably a reproducible example) on how to set a minimum size of members per cluster? Although hierarchical clustering will let you prune small clusters, this has to be done manually, and I haven't come up with a succinct, straightforward way to do this automatically. $\endgroup$
    – Bryan
    Commented Nov 1, 2013 at 17:11
  • $\begingroup$ You have a tree structure - simply traverse it from the leafs and cut off those which are too small - it is few lines of code. $\endgroup$
    – lejlot
    Commented Nov 1, 2013 at 19:26
  • $\begingroup$ Yes, but then you have to iterate over and over until you get a cluster that's an acceptable size. Then you have to go back and re-cluster what you pruned. So, especially with large data sets with non-obvious correlative groups, it is very time consuming to manually prune. $\endgroup$
    – Bryan
    Commented Nov 2, 2013 at 0:13
  • $\begingroup$ You just go once through whole tree, and you don't recluster anything. $\endgroup$
    – lejlot
    Commented Nov 2, 2013 at 5:20

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.