On Controlling the Size of Clusters in Probabilistic Clustering

Aditya Jitta, Arto Klami

Introduction

In unsupervised learning, clustering is typically treated as a density estimation task where data points are assumed to be independent and identically distributed (i.i.d.). While effective for discovering spatial structures, standard algorithms like k-means or Gaussian Mixture Models (GMMs) offer little control over the resulting cluster sizes. This "size-agnostic" nature often leads to undesirable outcomes, such as the "rich-get-richer" effect in non-parametric models, where a few massive clusters dominate. In practical applications like workload balancing or team formation, practitioners often require clusters that adhere to specific size constraints or distributions.

Problem Formulation: Breaking Point Independence

The fundamental limitation of traditional clustering lies in the assumption that each data point chooses its cluster independently. To control cluster size, one must break this independence and perform a joint assignment of all points. Aditya Jitta and Arto Klami (AAAI-18) propose a paradigm shift: instead of $N$ independent objects, the model should treat the clusters as the primary units of generation. In this framework, each cluster independently determines its size $s$ based on a user-defined prior distribution $p(s)$.

Methodology

The authors introduce a probabilistic framework where the joint probability of data $X$ and assignments $Z$ is maximized under cluster-size constraints. The assignment step is formulated as a constrained optimization problem. Two primary methods are proposed:

  1. Method 1 (Binary Integer Programming): A general formulation using indicator variables for point-to-cluster and cluster-to-size assignments. This approach can accommodate any discrete prior distribution.
  2. Method 2 (Mixed Integer Programming): Designed for log-concave priors (e.g., Poisson), this method utilizes a piece-wise linear approximation of the log-prior.
Figure 2: Impact of different cluster size priors on the resulting partitions. The top row shows the log-prior $p(s)$, and the bottom row shows the corresponding clustering of a 2D dataset.

As shown in Figure 2, the choice of prior $p(s)$ allows for precise "steering" of the clustering process. A prior centered at 50 preserves the natural three-cluster structure of the data, while a prior centered at 25 forces the algorithm to split these natural groups into smaller, equal-sized units.

Experimental Results

The framework was evaluated on various synthetic datasets to test qualitative control, scalability, and automatic complexity inference.

Qualitative Control and Complexity

By setting a non-zero probability for empty clusters ($p(s=0) > 0$), the model can automatically determine the optimal number of active clusters. Starting with a large initial $K$, the optimization "prunes" unnecessary clusters that do not fit the desired size distribution or data density.

Computational Efficiency

Despite the NP-hard nature of integer programming, the authors found that modern solvers like Gurobi can handle datasets with tens of thousands of points efficiently.

Figure 3: Convergence of log-likelihood over time for Method 1 (solid) and Method 2 (dashed) across different dataset sizes (N). Method 1 consistently demonstrates superior efficiency.

Experimental results (Figure 3) indicate that Method 1 (BIP) is generally more efficient than Method 2 (MIP), even when the latter's log-concave assumptions are met. For a dataset of 10,000 points, Method 1 reaches a high-quality solution significantly faster than the piece-wise linear approximation approach.

Conclusion

The proposed framework provides a robust way to incorporate domain knowledge about cluster sizes into probabilistic clustering. By shifting the generative focus to clusters and utilizing integer programming for joint assignment, the model achieves a level of control that standard i.i.d. models cannot match. Future work may address the subjectivity of prior selection and further improve scalability for million-scale datasets.

Summary updated

Abstract

Classical model-based partitional clustering algorithms, such ask-means or mixture of Gaussians, provide only loose and indirect control over the size of the resulting clusters. In this work, we present a family of probabilistic clustering models that can be steered towards clusters of desired size by providing a prior distribution over the possible sizes, allowing the analyst to fine-tune exploratory analysis or to produce clusters of suitable size for future down-stream processing.Our formulation supports arbitrary multimodal prior distributions, generalizing the previous work on clustering algorithms searching for clusters of equal size or algorithms designed for the microclustering task of finding small clusters. We provide practical methods for solving the problem, using integer programming for making the cluster assignments, and demonstrate that we can also automatically infer the number of clusters.
BibTeX
@inproceedings{jitta2018controlling,
  author = {Aditya Jitta and Arto Klami},
  title = {{On Controlling the Size of Clusters in Probabilistic Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11793},
}
Figure