I need to cluster units into $k$ clusters to minimize within-group sum of squares (WSS), but I need to ensure that the clusters each contain at least $m$ units. Any idea if any of R's clustering functions allow for clustering into $k$ clusters subject to a minimum cluster size constraint? kmeans() does not seem to offer a size constraint option.


Use EM Clustering

In EM clustering, the algorithm iteratively refines an initial cluster model to fit the data and determines the probability that a data point exists in a cluster. The algorithm ends the process when the probabilistic model fits the data. The function used to determine the fit is the log-likelihood of the data given the model.

If empty clusters are generated during the process, or if the membership of one or more of the clusters falls below a given threshold, the clusters with low populations are reseeded at new points and the EM algorithm is rerun.

  • $\begingroup$ Thanks, Marianna. I would prefer a solution that relies less heavily on (typically, unjustifiable) parametric models, but will definitely look into it. $\endgroup$ – Cyrus S Dec 12 '10 at 15:59

This problem is addressed in this paper:

Bradley, P. S., K. P. Bennett, and Ayhan Demiriz. "Constrained k-means clustering." Microsoft Research, Redmond (2000): 1-8.

I have an implementation of the algorithm in python.

  • $\begingroup$ This is perfect, thanks! I used the rPython package in R to create an interface to this implementation that I accessed from my R script. $\endgroup$ – Michael Ohlrogge Feb 27 '17 at 19:57
  • $\begingroup$ @MichaelOhlrogge do you have an example somewhere (github?) on the interface you wrote to call that python package form R? Thanks! $\endgroup$ – Matifou Feb 8 at 23:53
  • $\begingroup$ Sorry, I looked around my old code but couldn't find it anymore. $\endgroup$ – Michael Ohlrogge Feb 9 at 1:23

I think it would just be a matter of running the k means as part of an if loop with a test for cluster sizes, I.e. Count n in cluster k - also remember that k means will give different results for each run on the same data so you should probably be running it as part of a loop anyway to extract the "best" result

  • 1
    $\begingroup$ Thanks, Alex. I see a problem with this though: what if over the loops the solutions generated never satisfy the constraint? That could happen if k means were set to run with no cluster size constraint. I'd love a solution that avoids this. (The nature of the application is such that I really need to ensure clusters are of a minimum size.) $\endgroup$ – Cyrus S Dec 10 '10 at 21:50

How large is your data set? Maybe you could try to run a hierarchical clustering and then decide which clusters retain based on your dendrogram.

If your data set is huge, you could also combine both clustering methods: an initial non-hierarchical clustering and then a hierarchical clustering using the groups from the non-hierarchical analysis. You can find an example of this approach in Martínez-Pastor et al (2005)

  • $\begingroup$ Thanks, Manuel. This actually sounds like a very intriguing possibility. I need to think about whether the hierarchical partitioning would impose certain constraints that would prevent the algorithm from achieving the optimal cluster partitioning directly under the size constraint. But intuitively, I can see that this might work. $\endgroup$ – Cyrus S Dec 12 '10 at 16:01

This can be achieved by modifying the cluster assignment step (E in EM) by formulating it as a Minimum Cost Flow (MCF) linear network optimisation problem.

I have written a python package which uses Google's Operations Research tools's SimpleMinCostFlow which is a fast C++ implementation. Its has a standard scikit-lean API.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.