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:
- 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.
- 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.
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.
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