Reducing over-clustering via the powered Chinese restaurant process

Jun Lu, Meng Li, David B. DunsonarXiv 2018 · DOI · arXiv

Abstract

Dirichlet process mixture (DPM) models tend to produce many small clusters regardless of whether they are needed to accurately characterize the data—this is particularly true for large data sets. However, interpretability, parsimony, data storage, and communication costs all are hampered by having overly many clusters. We propose a powered Chinese restaurant process (pCRP) to limit this kind of problem and penalize over-clustering. The method is illustrated using simulation examples and data with large and small sample sizes, including MNIST and the Old Faithful Geyser data.

Introduction

In Bayesian nonparametrics, the Dirichlet Process Mixture (DPM) is a foundational tool for clustering because it avoids the need to pre-specify the number of clusters. Instead, the model learns the appropriate complexity from the data. However, DPMs suffer from a well-documented "over-clustering" phenomenon: as the sample size $N$ increases, the model tends to generate numerous small, artifactual clusters that do not correspond to meaningful underlying structures.

While these extra components can improve fine-grained density estimation, they severely degrade interpretability. In applications like customer segmentation or genomics, a few robust clusters are far more valuable than hundreds of tiny ones. This paper introduces the powered Chinese Restaurant Process (pCRP), a simple yet effective modification to the clustering prior designed to suppress unnecessary small clusters and favor parsimonious models.

Methods: The Powered Chinese Restaurant Process

The standard Chinese Restaurant Process (CRP) is a metaphor for the clustering behavior of DPMs. In a CRP, the probability of a new data point joining an existing cluster $k$ is proportional to its current occupancy $N_k$. The pCRP modifies this by raising the cluster size to a power $r > 1$.

Graphical model representation of the pCRP.

The Power Tweak and "Rich-Get-Richer" Dynamics

In the pCRP, the probability of joining cluster $k$ is proportional to $N_k^r$. When $r > 1$, larger clusters become disproportionately more attractive, while smaller clusters are less likely to survive or attract new members. This creates a stronger penalty for starting new, tiny clusters.

Non-Exchangeability and Proportional Invariance

Unlike the standard CRP, the pCRP is non-exchangeable, meaning the order of data points affects the resulting distribution. This allows the model to utilize feedback from the current state to determine if a new cluster is truly justified. Crucially, the authors prove that the power function $x^r$ is the unique continuous function maintaining "proportional invariance"—the relative probability of joining one cluster over another remains stable even if all cluster sizes are scaled equally. This property ensures the parameter $r$ is robust across different sample sizes.

Experimental Results

The pCRP was evaluated against the standard CRP and a "CRP-Oracle" (a CRP with parameters tuned using ground truth knowledge).

Simulation Studies

In Gaussian mixture simulations with three true clusters, the standard CRP typically over-estimated the complexity, finding an average of 5.8 clusters. In contrast, the pCRP consistently identified approximately 3.5 clusters, staying much closer to the true structure. Notably, pCRP often outperformed the "CRP-Oracle," suggesting that simply adjusting the innovation parameter $\alpha$ is insufficient; a specific penalty on small clusters is required.

Comparison of cluster number stability across iterations for CRP-Oracle, standard CRP, and pCRP.

As shown in the figure above, the standard CRP (b) exhibits high variance and a tendency to explore models with excessive clusters (up to 12). The pCRP (c) demonstrates significantly higher stability, maintaining a lower cluster count that aligns more closely with the Oracle (a).

Real-World Data: MNIST and Old Faithful

  • MNIST: On a subset of handwritten digits (1-4), pCRP achieved superior Normalized Mutual Information (NMI) and lower Variation of Information (VI) compared to the standard CRP, indicating cleaner separation of digit classes.
  • Old Faithful: For this classic dataset ($N=272$), the pCRP correctly identified the two primary eruption patterns. The standard CRP, conversely, over-segmented the data into four clusters, creating redundant subdivisions.

Conclusion

The powered Chinese Restaurant Process provides a practical solution to the over-clustering problem in DPM models. By introducing a "rich-get-richer" mechanism through the power parameter $r$, it effectively penalizes small, artifactual clusters. While moving away from exchangeability is a departure from traditional Bayesian theory, the empirical gains in parsimony and interpretability are substantial. Future work will explore theoretical posterior convergence rates and the application of pCRP to non-Gaussian data types.

Summary updated

Abstract

Dirichlet process mixture (DPM) models tend to produce many small clusters regardless of whether they are needed to accurately characterize the data - this is particularly true for large data sets. However, interpretability, parsimony, data storage and communication costs all are hampered by having overly many clusters. We propose a powered Chinese restaurant process to limit this kind of problem and penalize over clustering. The method is illustrated using some simulation examples and data with large and small sample size including MNIST and the Old Faithful Geyser data.
BibTeX
@misc{lu2018reducing,
  author = {Jun Lu and Meng Li and David B. Dunson},
  title = {{Reducing over-clustering via the powered Chinese restaurant process}},
  year = {2018},
  eprint = {1802.05392},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.05392},
}

Loading related content...

Figure