Abstract
Most generative models for clustering implicitly assume that the number of data points in each cluster grows linearly with the total number of data points. Finite mixture models, Dirichlet process mixture models, and Pitman-Yor process mixture models make this assumption, as do all other infinitely exchangeable clustering models. However, for some tasks, this assumption is undesirable. For example, when performing entity resolution, the size of each cluster is often unrelated to the size of the data set. Consequently, each cluster contains a negligible fraction of the total number of data points. Such tasks therefore require models that yield clusters whose sizes grow sublinearly with the size of the data set. We address this requirement by defining the microclustering property and introducing a new model that exhibits this property. We compare this model to several commonly used clustering models by checking model fit using real and simulated data sets.
Introduction
In traditional clustering applications, such as grouping news articles by topic, we generally expect that as the dataset grows, the number of articles per topic increases. Standard models like Dirichlet Process (DP) mixtures or Pitman-Yor Process (PYP) mixtures formalize this via the "rich-get-richer" property, where existing clusters tend to grow linearly with the total number of observations $N$.
However, in domains like entity resolution (identifying duplicate records in a database), this assumption is fundamentally flawed. If a database of 1,000 people grows to 1,000,000, the number of records per person (the cluster size) typically remains small and constant. Instead of larger clusters, we simply observe more clusters. This phenomenon requires a "microclustering" approach where cluster sizes grow sublinearly with $N$. Traditional models used for these tasks often overestimate cluster sizes and fail to account for the high frequency of singleton clusters.
The Microclustering Property and NBNB Model
The authors formally define the microclustering property: a sequence of partitions exhibits this property if the size of the largest cluster, $M_N$, grows slower than the total number of data points, such that $M_N = o_p(N)$.
To implement this, they propose the NegBin-NegBin (NBNB) model. Unlike exchangeable models that couple cluster growth to $N$, the NBNB model decouples the number of clusters ($K$) and the size of each cluster ($N_k$) using Negative Binomial distributions. This allows the number of clusters to scale nearly linearly with $N$, keeping individual clusters small.
To handle the computational challenge of performing inference with thousands of tiny clusters, the authors introduced the Chaperones algorithm. This localized Gibbs sampler restricts moves to clusters associated with two randomly selected "chaperone" points, making the process scalable for massive, sparse datasets.
Experimental Results
The NBNB and a related PERPS (Permuted Poisson Sizes) model were evaluated against standard benchmarks: DP, PYP, and Mixtures of Finite Mixtures (MFM). Tests were conducted on a synthetic dataset (5,000 elements, 4,500 clusters) and real-world data from the Survey on Household Income and Wealth (SHIW).
Key findings include:
- Singleton Accuracy: NBNB and PERPS significantly outperformed traditional models in capturing the high volume of singleton clusters. Traditional models like DP and PYP consistently underestimated the number of unique entities.
- Cluster Size Distribution: Traditional models tended to create a few overly large clusters. NBNB was the only model that consistently captured the maximum cluster size accurately and maintained the "long tail" of small clusters characteristic of microclustering tasks.
- Breaking the "Rich Get Richer" Bias: By moving away from the infinitely exchangeable framework, the NBNB model avoids the bias toward large clusters inherent in the Chinese Restaurant Process. Empirical tests confirmed that as the dataset size increased to $10^4$, the NBNB model's largest cluster size indeed shrank relative to $N$.
Conclusion
The microclustering property is essential for realistic modeling of datasets where clusters represent small, real-world entities. While adopting this property requires sacrificing mathematical "consistency in distribution," the resulting models provide a much better fit for tasks like entity resolution. Future work involves integrating these priors with sophisticated likelihood models for record linkage and further exploring hyperparameter sensitivity.
Summary updated