\section{Introduction}

Many clustering tasks require models that assume cluster sizes grow
linearly with the size of the data set. These tasks include topic
modeling, inferring population structure, and discriminating among
cancer subtypes. Infinitely exchangeable clustering models, including
finite mixture models, Dirichlet process mixture models, and
Pitman--Yor process mixture models, all make this linear growth
assumption, and have seen numerous successes when used for these
tasks. For other clustering tasks, however, this assumption is
undesirable. One prominent example is entity resolution. Entity
resolution (including record linkage and deduplication) involves
identifying duplicate\footnote{In the entity resolution literature,
  the term ``duplicate records'' does not mean that the records are
  identical, but rather that they are corrupted, degraded, or
  otherwise noisy representations of the same entity.}  records in
noisy databases~\cite{christen12data,christen12survey}, traditionally
by directly linking records to one another. Unfortunately, this
approach is computationally infeasible for large data sets---a serious
limitation in ``the age of big
data''~\cite{christen12data,winkler06overview}. As a result,
researchers increasingly treat entity resolution as a
clustering task, where each entity is implicitly associated with one
or more records and the inference goal is to recover the latent
entities (clusters) that correspond to the observed records (data
points)~\cite{steorts??bayesian,steorts15entity,steorts14smered}. In
contrast to other clustering tasks, the number of data points in each
cluster remains small, even for large data sets. Tasks like this
therefore require models that yield clusters whose sizes grow
sublinearly with the total number of data points. To address this
requirement, we define the \emph{microclustering property} in
section~\ref{sec:microclustering} and, in section~\ref{sec:nbnb},
introduce a new model that exhibits this property. Finally, in
section~\ref{sec:experiments}, we compare this model to several
commonly used infinitely exchangeable clustering models.

\section{The Microclustering Property}
\label{sec:microclustering}

To cluster $N$ data points $x_1, \ldots, x_N$ using a partition-based
Bayesian clustering model, one first places a prior over partitions of
$[N] = \{ 1, \ldots, N \}$. Then, given a partition $C_N$ of $[N]$,
one models the data points in each part $c \in C_N$ as jointly
distributed according to some chosen form. Finally, one computes the
posterior distribution over partitions and, e.g., uses it to identify
probable partitions of $[N]$. Mixture models are a well-known type of
partition-based Bayesian clustering model, in which $C_N$ is
implicitly represented by a set of cluster assignments $z_1, \ldots,
z_N$. One regards these cluster assignments as the first $N$ elements
of an infinite sequence $z_1, z_2, \ldots$, drawn a priori from
\begin{equation}
  \boldsymbol{\pi} \sim H \quad \textrm{and} \quad
 z_1, z_2, \ldots \,|\, \boldsymbol{\pi} \iid \boldsymbol{\pi},
 \label{eqn:mixture}
\end{equation}
where $H$ is a prior over $\boldsymbol{\pi}$ and $\boldsymbol{\pi}$ is a vector of mixture
weights with $\sum_l \pi_l \!=\! 1$ and $\pi_l \geq 0$ for all
$l$. Commonly used mixture models include (a) finite mixtures where
the dimensionality of $\boldsymbol{\pi}$ is fixed and $H$ is usually a Dirichlet
distribution; (b) finite mixtures where the dimensionality of $\boldsymbol{\pi}$
is a random variable~\cite{richardson97bayesian,miller15mixture}; (c)
Dirichlet process (DP) mixtures where the dimensionality of $\boldsymbol{\pi}$ is
infinite~\cite{sethuraman94constructive}; and (d) Pitman--Yor process
(PYP) mixtures, which generalize DP
mixtures~\cite{ishwaran03generalized}.

Equation~\ref{eqn:mixture} implicitly defines a prior over partitions
of $\mathbb{N} = \{ 1, 2, \ldots \}$. Any random partition
$C_{\mathbb{N}}$ of $\mathbb{N}$ induces a sequence of random
partitions $(C_N : N=1, 2, \ldots)$, where $C_N$ is a partition of
$[N]$. Via the strong law of large numbers, the cluster sizes in any
such sequence obtained via equation~\ref{eqn:mixture} grow linearly
with $N$, since with probability one, for all $l$, $\frac{1}{N}
\sum_{n=1}^N I(z_n \!=\! l) \rightarrow \pi_l$ as $N \rightarrow
\infty$, where $I(\cdot)$ denotes the indicator
function. Unfortunately, this linear growth assumption is not
appropriate for entity resolution and other tasks that require
clusters whose sizes grow sublinearly with $N$.

To address this requirement, we therefore define the
\emph{microclustering property}: A sequence of random partitions $(C_N
: N=1, 2, \ldots)$ exhibits the microclustering property if $M_N$ is
$o_p(N)$, where $M_N$ is the size of the largest cluster in
$C_N$. Equivalently, $M_N \,/\, N \rightarrow 0$ in probability as $N
\rightarrow \infty$.



A clustering model exhibits the microclustering property if the
sequence of random partitions implied by that model satisfies the
above definition. No mixture model can exhibit the microclustering
property (unless its parameters are allowed to vary with $N$). In
fact, Kingman's paintbox
theorem~\cite{kingman78representation,aldous85exchangeability} implies
that any exchangeable partition of $\mathbb{N}$, such as a partition
obtained using equation~\ref{eqn:mixture}, is either equal to the
trivial partition in which each part contains one element or satisfies
$\liminf_{N \rightarrow \infty} M_N \,/\, N > 0$ with positive
probability. By Kolmogorov's extension theorem, a sequence of random
partitions $(C_N : N=1, 2, \ldots)$ corresponds to an exchangeable
random partition of $\mathbb{N}$ whenever (a) each $C_N$ is
exchangeable and (b) the sequence is consistent in
distribution---i.e., if $N' \!<\! N$, the distribution of $C_{N'}$
coincides with the marginal of $C_{N'}$ obtained using the
distribution of $C_N$. Therefore, to obtain a nontrivial model that
exhibits the microclustering property, one must sacrifice either (a)
or (b). Previous work~\cite{wallach10alternative} sacrificed (a);
here, we instead sacrifice (b).

\section{A Model for Microclustering}
\label{sec:nbnb}

In this section, we introduce a new model for microclustering. We
start by defining
\begin{equation}
  K \sim \textrm{NegBin}\,(a, q) \quad \textrm{and} \quad
 N_1, \ldots, N_K \,|\, K \iid \textrm{NegBin}\,(r, p),
  \label{eqn:nbnb}
\end{equation}
for $a, r \,>\, 0$ and $q, p \in (0, 1)$. Note that $K$ and some of
$N_1, \ldots, N_K$ may be zero. We then define $N = \sum_{k=1}^K N_k$
and, given $N_1, \ldots, N_K$, generate a set of cluster assignments
$z_1, \ldots, z_N$ by drawing a vector uniformly at random from the
set of permutations of $(\underbrace{1,\ldots,1}_\text{$N_1$
  times},\underbrace{2,\ldots,2}_\text{$N_2$
  times},\ldots\ldots,\underbrace{K,\ldots,K}_\text{$N_K$ times})$.

The cluster assignments $z_1, \ldots, z_N$ induce a random partition
$C_N$ of $[N]$, where $N$ is itself a random variable---i.e., $C_N$ is
a random partition of a random number of elements. We call the
resulting marginal distribution of $C_N$ the NegBin--NegBin (NBNB)
model. If $\mathscr{C}_N$ denotes the set of all possible partitions
of $[N]$, then $\bigcup_{N=1}^{\infty} \mathscr{C}_N$ is the set of
all possible partitions of $[N]$ for $N \in \mathbb{N}$. In
appendix~\ref{sec:appendix_a}, we show that under the NBNB model, the
probability of any given $C_N \in \bigcup_{N=1}^{\infty}
\mathscr{C}_N$ is
\begin{equation}
  \label{eqn:prob_C_N_main_text}
  P(C_N) = \frac{p^N}{N!}\, a^{(|C_N|)}\,
  \frac{(1-q)^a \left(q\,(1-p)^r\right)^{|C_N|}}{\left(1 - q\,(1-p)^r\right)^{a + |C_N|}} \, \prod_{c \in
    C_N} r^{(|c|)},
  \end{equation}
where $x^{(m)} = x\,(x + 1) \ldots (x + m - 1)$ for $m \in \mathbb{N}$
and $x^{(0)} \!=\! 1$. We use $|\cdot|$ to denote the cardinality of a
set, so $|C_N|$ is the number of (nonempty) parts in $C_N$ and $|c|$
is the number of elements in part $c$. We also show that if we replace
the negative binomials in equation~\ref{eqn:nbnb} with Poissons, then
we obtain a limiting special case of the NBNB model. We call this
model the permuted Poisson sizes (PERPS) model. Under certain
conditions, the PERPS model is equivalent to the linkage structure
prior~\cite{steorts14smered,steorts??bayesian}.


In practice, $N$ is usually observed. Conditional on $N$,
the NBNB model implies that
\begin{equation}
  P(C_N \,|\, N) \propto a^{(|C_N|)}\,\beta^{|C_N|} \, \prod_{c \in C_N}
  r^{(|c|)},
\end{equation}
where $\beta = \left(q\,(1 - p)^r\right) \,/\, \left( 1 -
q\,(1-p)^r\right)$. This equation leads to the following
``reseating algorithm''---much like the Chinese restaurant process
(CRP)---derived by sampling from $P(C_N \,|\, N, C_N \!\setminus\! n)$,
where $C_N \!\setminus\!  n$ is the partition obtained by removing
element $n$ from $C_N$:
\begin{itemize}
\item for $n = 1,\ldots,N$, reassign element $n$ to
  \begin{itemize}
  \item an existing cluster $c \in C_N \!\setminus\! n$ with
    probability $\propto |c| + r$,
  \item a new cluster with probability $\propto
    (|C_N \!\setminus\! n|+ a)\,\beta r$.
  \end{itemize}
\end{itemize}
We can use this algorithm to draw samples from $P(C_N \,|\, N)$, however,
unlike the CRP, it does not produce an exact sample if used to
incrementally construct a partition from the empty set. When the NBNB
model is used as the prior in a partition-based clustering
model---e.g., as an alternative to equation~\ref{eqn:mixture}---the
resulting Gibbs sampling algorithm for $C_N$ is similar to this
algorithm, but accompanied by appropriate likelihood
terms. Unfortunately, this algorithm is slow for large data sets. We
therefore propose a faster Gibbs sampling algorithm---the
\emph{chaperones algorithm}---in appendix~\ref{sec:appendix_b}.

In appendix~\ref{sec:appendix_c}, we present empirical evidence that
suggests that the sequence of partitions $(C_N : N = 1, 2, \ldots)$
implied by the NBNB model does indeed exhibit the microclustering
property.

\section{Experiments}
\label{sec:experiments}

In this section, we compare the NBNB and PERPS models to several
commonly used infinitely exchangeable clustering models: mixtures of
finite mixtures (MFM)~\cite{miller15mixture}, DP mixtures, and PYP
mixtures. We assess how well each model ``fits'' partitions typical of
those arising in entity resolution and other tasks involving clusters
whose sizes grow sublinearly with $N$. We use two observed
partitions---one simulated and one real. The simulated partition
contains 5,000 elements, divided into 4,500 clusters. Of these, 4,100
are singleton clusters, 300 are clusters of size two, and 100 are
clusters of size three. This partition represents data sets in which
duplication is relatively rare---roughly 91\% of the clusters are
singletons.  The real partition is derived from the Survey on
Household Income and Wealth (SHIW), conducted by the Bank of Italy
every two years. We use the 2008 and 2010 data from the Fruili region,
which consists of 789 records. Ground truth is available via unique
identifiers based upon social security numbers; roughly 74\% of the
clusters are singletons.

For each data set, we consider four statistics: the number of
singleton clusters, the maximum cluster size, the mean cluster size,
and the 90\% quantile of cluster sizes. We compare each statistic's
true value, obtained using the observed partition, to its distribution
under each of the models, obtained by generating 5,000 partitions
using the models' ``best'' parameter values. For simplicity and
interpretability, we define the best parameter values for each model
to be the values that maximize the probability of the observed
partition---i.e., the maximum likelihood estimate (MLE). The intuition
behind our approach is that if the observed value of a statistic is
not well-supported by a given model, even with the MLE parameter
values, then the model may not be appropriate for that type of data.

We provide plots summarizing our results in
figures~\ref{fig:simulated} and~\ref{fig:real}. The models are able to
capture the mean cluster size for each data set, although the NBNB
model's values are slightly low. For the SHIW partition, none of the
models do especially well at capturing the number of singleton
clusters or the maximum cluster size, although the NBNB and PERPS
models are the closest. For the simulated partition, neither the PYP
mixture model or the PERPS model are able to capture the maximum
cluster size. The PERPS model also does poorly at capturing the 90\%
quantile. Overall, the NBNB model appears to fit both data sets better
than the other models, though no one model is clearly superior to the
others. These results suggest that the NBNB model merits further
exploration as a prior for entity resolution and other tasks involving
clusters whose sizes grow sublinearly with $N$.

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=1.0\textwidth]{figures/simulated.jpg}
    \caption{Results for the simulated partition. Each plot contains a
      boxplot depicting the distribution of a single statistic under
      each of the five models, obtained using the MLE parameter values
      (provided in appendix~\ref{sec:appendix_d}). The dashed
      horizontal line indicates the true value of the statistic.}
    \label{fig:simulated}
  \end{center}
\end{figure}

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=1.0\textwidth]{figures/real.jpg}
    \caption{Results for the SHIW partition. This figure's
      interpretation is the same as that of
      figure~\ref{fig:simulated}.}
    \label{fig:real}
  \end{center}
\end{figure}

\section{Discussion}

Infinitely exchangeable clustering models assume that cluster sizes
grow linearly with the size of the data set. Although this assumption
is appropriate for some tasks, many other tasks, including entity
resolution, require clusters whose sizes instead grow sublinearly. The
microclustering property, introduced in
section~\ref{sec:microclustering}, provides a way to characterize
models that address this requirement. The NBNB model, introduced in
section~\ref{sec:nbnb}, exhibits this property. The figures in
section~\ref{sec:experiments} show that in some ways---specifically
the number of singleton clusters and the maximum cluster size---the
NBNB model can fit partitions typical of those arising in entity
resolution better than several commonly used mixture models. These
results suggest that the NBNB model merits further exploration as a
prior for tasks involving clusters whose sizes grow sublinearly with
the size of the data set.

\section*{Acknowledgments}

We would like to thank to Tamara Broderick, David Dunson, Merlise
Clyde, and Abel Rodriguez for conversations that helped form the ideas
contained in this paper. In particular, Tamara Broderick played a key
role in developing the idea of small clustering. JWM was supported in
part by NSF grant DMS-1045153 and NIH grant 5R01ES017436-05.  BB, AZ,
and RCS were supported in part by the John Templeton Foundation. RCS
was supported in part by NSF grant SES-1534412. HW was supported in
part by the UMass Amherst CIIR and by NSF grants IIS-1320219 and
SBE-0965436.

\bibliographystyle{unsrt} 