2000 · 346 citations · 6 references
K‑Means clustering can produce empty or very small clusters, especially when the number of dimensions is 10 and the desired number of clusters is 20. The study proposes adding k constraints to enforce a minimum cluster size. The authors incorporate a minimum‑size constraint into the optimization and analyze the resulting assignment step. Preliminary experiments show the constrained method reduces poor local solutions and yields a more accurate data summary. Contrained K‑Means Clustering 1.
We consider practical methods for adding constraints to the K-Means clustering algorithm in order to avoid local solutions with empty clusters or clusters having very few points. We often observe this phenomena when applying K-Means to datasets where the number of dimensions is n 10 and the number of desired clusters is k 20. We propose explicitly adding k constraints to the underlying clustering optimization problem requiring that each cluster have at least a minimum number of points in it. We then investigate the resulting cluster assignment step. Preliminary numerical tests on real datasets indicate the constrained approach is less prone to poor local solutions, producing a better summary of the underlying data. Contrained K-Means Clustering 1
6
Algorithms for Clustering Data
Warren S. Sarle, Anil K. Jain, Richard C. Dubes · Technometrics · 1990 · 7.8K citations
Patricia Bradley, O. L. Mangasarian · Journal of Global Optimization · 2000 · 395 citations
Clustering via Concave Minimization
Paul S. Bradley, O. L. Mangasarian, W. Nick Street · 1996 · 227 citations