Abstract
The Dirichlet Process Gaussian Mixture Model (DPGMM) is often used to cluster data when the number of clusters is unknown. One main DPGMM inference paradigm relies on sampling. Here we consider a known state-of-the-art sampler, analyze its failure modes, and show how to improve it, often drastically. Concretely, in that sampler, whenever a new cluster is formed it is augmented with two subclusters whose labels are initialized at random. Upon their evolution, the subclusters serve to propose a split of the parent cluster. We show that the random initialization is often problematic and hurts the otherwise-effective sampler. Specifically, we demonstrate that this initialization tends to lead to poor split proposals and/or too many iterations before a desired split is accepted. This slows convergence and can damage the clustering. As a remedy, we propose two drop-in-replacement options for the subcluster-initialization subroutine. The first is an intuitive heuristic while the second is based on deep learning. We show that the proposed approach yields better splits, which in turn translate to substantial improvements in performance, results, and stability.
Introduction: The "Randomness" Trap in Bayesian Clustering
Clustering data without a predefined number of groups ($K$) is a fundamental challenge in unsupervised learning. The Dirichlet Process Gaussian Mixture Model (DPGMM) provides a robust Bayesian framework for this task. A state-of-the-art approach for DPGMM inference is the SubC sampler. This algorithm maintains two "subclusters" within every existing cluster to periodically propose "splits." If a proposed split has a high Hastings Ratio, it is accepted, allowing the model to dynamically discover new clusters.
However, a critical bottleneck exists: the original SubC sampler initializes these subclusters randomly. This "blind spot" often results in two subclusters that are statistically indistinguishable. Because Markov Chain Monte Carlo (MCMC) processes move incrementally, it can take hundreds of iterations for these subclusters to drift apart and reveal the data's underlying structure. Frequently, the sampler fails to accept the split altogether, leading to a significant underestimation of the true number of clusters.
Methodology: Smart Splits via SplitNet
To address the limitations of random initialization, this research introduces two "drop-in" replacements for the subcluster-initialization subroutine:
- 2-means Heuristic: A straightforward approach using the K-means algorithm (with $K=2$) to provide a non-overlapping, deterministic starting point for subclusters.
- SplitNet: A deep learning model designed to predict the most likely binary split of a point cloud instantaneously.
SplitNet utilizes a Set Transformer architecture, which is uniquely suited for this task due to its permutation invariance and ability to handle variable input sizes. By employing self-attention mechanisms, SplitNet learns to identify regions of high density and the geometric "seams" between potential clusters. Notably, SplitNet is trained entirely on synthetic Gaussian Mixture data. Since the ground truth of these generated mixtures is known, the network can be trained to recognize optimal splits without manual labeling, demonstrating remarkable synthetic-to-real generalization.
Experimental Results and Analysis
The proposed methods were evaluated against standard benchmarks, including synthetic GMMs and real-world image datasets (MNIST, Fashion-MNIST, CIFAR, and STL-10). For complex images, features were extracted using unsupervised models like SCAN and reduced via PCA.
The results indicate that the SplitNet-augmented sampler is one to two orders of magnitude faster than traditional Bayesian methods, such as scikit-learn's DPGMM or Memoized Online Variational Bayes (moVB). In challenging 2D scenarios where baseline samplers might infer $K \approx 10$ for a ground truth of $K=20$, the SplitNet approach converges to the correct number almost immediately.
As shown in the quantitative analysis, the complexity of the clustering task increases as the number of ground truth clusters grows, particularly in lower-dimensional spaces where clusters are more likely to overlap. SplitNet maintains high stability and accuracy (measured by ARI) across these varying conditions.
Conclusion
This work demonstrates that the common practice of random initialization in subcluster-based samplers is a source of noise that actively sabotages MCMC efficiency. By replacing randomness with "smart" proposals from SplitNet, the DPGMM becomes a far more powerful and reliable tool for discovery. While scaling to extremely high dimensions remains a computational challenge for training, the "geometry of a split" learned by SplitNet on synthetic data proves to be a universal feature that significantly enhances clustering performance on real-world data.
Summary updated