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.
$\begingroup$
$\endgroup$
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
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.
answered Dec 11, 2010 at 6:33
-
$\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 SCommented Dec 12, 2010 at 15:59
-
$\begingroup$ Can this be done with K-means also? If after several iterations, too few points are assigned to a centroid, just randomly generate a new centroid? $\endgroup$– tmldwnCommented Aug 31, 2020 at 11:51
$\begingroup$
$\endgroup$
3
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
rPythonpackage in R to create an interface to this implementation that I accessed from my R script. $\endgroup$ Commented Feb 27, 2017 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$– MatifouCommented Feb 8, 2020 at 23:53
-
$\begingroup$ Sorry, I looked around my old code but couldn't find it anymore. $\endgroup$ Commented Feb 9, 2020 at 1:23
$\begingroup$
$\endgroup$
1
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
-
3$\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 SCommented Dec 10, 2010 at 21:50
$\begingroup$
$\endgroup$
1
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)
answered Dec 11, 2010 at 8:04
-
$\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 SCommented Dec 12, 2010 at 16:01
$\begingroup$
$\endgroup$
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.
