# Human in-the-Loop Estimation of Cluster Count in Datasets via
Similarity-Driven Nested Importance Sampling

Gustavo Perez, Daniel Sheldon, Grant Van Horn, Subhransu Maji
University of Massachusetts Amherst
<EMAIL_ADDRESS>
###### Abstract

Identifying the number of clusters serves as a preliminary goal for many data
analysis tasks. A common approach to this problem is to vary the number of
clusters in a clustering algorithm (e.g., ‘k’ in $k$-means) and pick the value
that best explains the data. However, the count estimates can be unreliable
especially when the image similarity is poor. Human feedback on the pairwise
similarity can be used to improve the clustering, but existing approaches do
not guarantee accurate count estimates. We propose an approach to produce
estimates of the cluster counts in a large dataset given an approximate
pairwise similarity. Our framework samples edges guided by the pairwise
similarity, and we collect human feedback to construct a statistical estimate
of the cluster count. On the technical front we have developed a nested
importance sampling approach that yields (asymptotically) unbiased estimates
of the cluster count with confidence intervals which can guide human effort.
Compared to naive sampling, our similarity-driven sampling produces more
accurate estimates of counts and tighter confidence intervals. We evaluate our
method on a benchmark of six fine-grained image classification datasets
achieving low error rates on the estimated number of clusters with
significantly less human labeling effort compared to baselines and alternative
active clustering approaches.

##  1 Introduction

# Sampled pairs / # Vertices

Figure 1: Our human-in-the-loop approach to estimate the number of clusters
$(k)$ in a dataset. (a) A simple approach is to use $k$-means with the “elbow
heuristic.” (b) Active clustering approaches (e.g., pck-means [1]) use
pairwise constraints to improve clustering. (c) Our sampling-driven approach
uses similar constraints, but produces (asymptotically) unbiased estimates and
confidence intervals of $k$ directly. (bottom) On the CUB dataset [33] our
approach converges to the true $k=200$ with far fewer constraints than
alternatives and improves over the baselines (e.g., $k$-means, connected
components, or mean-shift).

Consider the widely studied problem of estimating the number of clusters in a
dataset. This question often arises in preliminary data analysis and is a
distinct goal than actually clustering the data. For instance, an ecologist
might want to estimate the number of animal species in a habitat using a vast
collection of camera trap images for a wildlife survey, or a social media
company might be interested in estimating the number of unique users visiting
their website from uploaded photographs. Beyond surveys, estimating the
categories in a dataset is an intermediate step for techniques for novel
category discovery, out-of-distribution robustness, and incremental learning
of AI systems [32, 6, 17].

A common approach to this problem is to vary the number of clusters in a
clustering algorithm such as the value of $k$ in $k$-means, and pick the value
according to some heuristic, such as the “elbow method” [31]. However, this
process has drawbacks. First, there are many choices of the clustering
algorithm and heuristics to choose from, making the process subjective.
Second, images represented using off-the-shelf deep networks can result in a
poor approximation to the true similarity $\hat{s}(u,v)\neq s(u,v)$. The
latter is particularly true when deploying networks on out-of-distribution
scenarios, or on challenging tasks such as in fine-grained domains. For
instance, Fig. 1 shows that employing $k$-means with the elbow heuristic on
the CUB dataset [33] estimates 52 categories, while the actual count is 200.
While these results were derived using ImageNet pretrained ResNet
representations, we also observe high error rates for other network
architectures (e.g., ViTs [11]), and pre-training strategies such as
iNaturalist [16], CLIP [26], and self-supervised learning [4].

We propose a human-in-the-loop approach that improves estimates using human
feedback on pairwise similarity. Unlike previous work in active clustering
(e.g., constrained $k$-means algorithms [1]), our approach is based on
statistical estimation. We estimate the number of clusters by sampling edges
guided by the approximate pairwise similarity between the nodes. Human
feedback on these edges, in the form of “similar” or “dissimilar” nodes, is
used to construct a statistical estimate of the number of clusters as well as
a confidence interval around it. We derive the approach by framing it as a
problem of estimating the number of connected components in a graph, and
derive a nested importance sampling (NIS) approach for estimating this
quantity. We theoretically show that the estimator is unbiased, i.e.,
converges to the true number of clusters in expectation. The confidence
intervals can guide the amount of human feedback needed, for example an end
user can stop screening when the confidence intervals are sufficiently small.
Our approach can employ any off-the-shelf image similarity and does not
require fine-tuning deep representations that underlie metric-learning
approaches, and hence can be practical for non-AI experts with resource
constraints.

We conduct experiments on six datasets where the goal is to estimate the
number of categories in the datasets. These datasets span challenging fine-
grained domains, exhibit different data distributions (short vs. long-tailed),
and varying number of categories. We also experiment with a variety of image
representations including ImageNet pretrained ResNets [14], self-supervised
DINO ViTs [4], and language-based CLIP [26], and compare the performance with
alternative active clustering approaches. Compared to active clustering
baselines such as pairwise constrained $k$-means (pc$k$-means [1]) and simple
Monte Carlo sampling for estimation, our approach achieves 70% relative error
reduction for the same amount of human supervision (sampled edges). Our
approach also has low bias and produces accurate confidence intervals. On most
datasets, our method produces estimates that are within 10% of the true number
of clusters after querying $n$ edges where $n$ is the number of images in the
dataset. Our main contributions are:

  * •

We propose a novel approach combining nested importance sampling with human-
in-the-loop feedback that produces asymptotically unbiased estimates of the
number of clusters in large image collections (§ 3).

  * •

We design confidence intervals that provide intuitive feedback for guiding
human effort and setting stopping conditions (§ 3.2).

  * •

We report extensive experiments on a benchmark of six fine-grained image
classification datasets with different data distributions and large numbers of
categories, demonstrating that our method consistently achieves significantly
lower error than other baselines with similar human effort (§ 4).

##  2 Related Work

#### Estimating the Number of Clusters in a Dataset

A common approach involves representing the elements in the dataset using some
embedding (e.g., deep networks for images), using a clustering algorithm such
as $k$-means [13], mean-shift [8], or graph-based approach [3, 29, 12], and
calculating the number of clusters based on a heuristic. For instance, with
mean-shift, it is common to set the bandwidth parameter based on a nearest-
neighbor analysis, while for $k$-means, it is common to select $k$ based on
some measure of “clusterness.” For example, we can calculate the within-
cluster sum of squares (WCSS) for several $k$ values and select the $k$ using
the “elbow method” heuristic – the inflection point in the curve representing
diminishing improvements. However, there are many choices of embeddings,
clustering algorithms, and heuristics to choose from, making the process ad-
hoc and subjective.

#### Metric Learning and Active Clustering

The similarity function over elements (often a metric) significantly impacts
the quality of clustering. While off-the-shelf deep networks (e.g., ResNet
[14] and ViTs [11]) can be readily used to compute image similarity, often
these do not yield precise estimates of the number of clusters or the
clustering itself. This is particularly challenging for out-of-domain
deployment of models. For example, on the CUB dataset, the nearest neighbor
accuracy with ImageNet pre-trained ResNet representations is only 45%, while
using $k$-means with the elbow heuristic yields only 52 clusters instead of
the desired 200 clusters. Although metric learning [21, 18] approaches have
been widely studied to improve the underlying similarity using human feedback
(e.g., pairwise [19] and triplet-based [15] learning), we focus on active
clustering approaches which aim to incorporate these constraints to improve
clustering on top of an off-the-shelf embedding or similarity. This is
primarily motivated by the fact that deep metric learning requires significant
computing resources and expertise to set the large number of hyperparameters
associated with training, which makes it impractical for many practitioners.
Therefore we compare with constrained $k$-means algorithms that use ‘must-
link’ and ‘cannot-link’ constraints within the $k$-means clustering framework
[1]. Various heuristics for selecting these constraints have been proposed –
[1] select pairwise constraints using a _farthest-first_ traversal scheme,
while [9] uses $k$-means with a large $k$ and selects constraints to merge the
small clusters into larger ones. While these approaches improve clustering
over the baseline $k$-means algorithm, they are not designed to directly
estimate the number of clusters, nor do they provide statistical guarantees on
the estimate. Our proposed sampling-based approach results in a consistent
estimator of the cluster count and produces accurate confidence intervals (§
5). The amount of human effort required depends both on the quality of the
pairwise similarity as well as the level of precision needed for estimation.

#### Applications and Related Problems

Apart from preliminary data exploration, estimating the number of clusters is
often the primary goal for many tasks. For example, estimating the number of
individuals in a population using similarity at the individual level (e.g.,
face ID, animal ID), or at the species level to support biodiversity surveys
conducted with autonomous cameras or audio traps (e.g., iNaturalist, Sound ID,
etc.). Discovering categories also arises in life-long learning systems that
must learn about novel categories during long-term deployment. In generalized
category discovery (GCD) [32, 6], the goal is to cluster all images given the
cluster labels for a subset of images. The problem is more challenging than
traditional semi-supervised learning due to the presence of novel clusters.
However, we find that the performance of existing GCD approaches is limited by
the accuracy of estimating the number of novel clusters. Often existing
approaches make the unrealistic assumption that this quantity is known. We
show our approach for estimating the number of clusters has a higher impact on
improving GCD than using active clustering algorithms.

##  3 Method

Assume that we have a collection of images
$\operatorname{\mathcal{D}}=\\{x_{i}\\}_{i=1}^{n}$ where each image $x_{i}$
belongs to a cluster $y_{i}\in{\cal Y}$. Our goal is to calculate the total
number of clusters $K=|{\cal Y}|$ in $\operatorname{\mathcal{D}}$. We assume
labels $y_{i}\in\operatorname{\mathcal{Y}}$ are unknown but we have access to
an image embedding $\Phi(\cdot)$ which can be used to compute an approximate
pairwise similarity $\hat{s}(x,z)=f\left(\Phi(x),\Phi(z)\right)$ between
images $x$ and $z$ for some function $f$ (such as the dot product). The true
similarity is $s(x,z)=1$ if images $x$ and $z$ belong to the same cluster and
is $s(x,z)=0$ otherwise. We assume this can be obtained by using human
feedback in the form of “same cluster or not” for the pair of images. Our goal
is to estimate $K$ as accurately as possible using a small amount of human
feedback given the approximate similarity $\hat{s}(x,z)$.

######  Lemma 1.

Consider a graph $G=(V,E)$ with vertices $u,v\in V=\\{1,...,n\\}$
corresponding to images $x_{u}$, with an edge $e_{uv}\in E$ between $u$ and
$v$ if the images $x_{u}$ and $x_{v}$ belong to the same cluster. Let
$d(u)=|\\{e_{uv}\in E\\}|$ be the degree of vertex $u$. Then the number of
clusters $K$ in the dataset $\mathcal{D}$ is equal to the number of connected
components in $G$, and can be computed as:

$K=\text{CC}(G)=\sum_{u=1}^{n}\frac{1}{1+d(u)}.$ (1)

Figure 2: Counting clusters in a graph. The number of clusters
$k=\sum_{u=1}^{n}1/(1+d(u))$, where $d(u)$ is degree of node $u$. In this
example $k=4\times 1/4+3\times 1/3+2\times 1/2=3$.

###### Proof of Lemma 1.

It is easy to see that the $G$ is a collection of cliques, with the clique
containing $u$ of size $1+d(u)$. The total contribution of the vertices in
this clique is $(1+d(u))\times(1/(1+d(u)))=1$, i.e., each clique contributes a
total of 1 to Eq. 1, adding up to the total number of cliques or connected
components in $G$. See Fig. 2 for an example. ∎

Figure 3: Proposed framework for counting clusters in a dataset. (a) We
represent that dataset graph $G$ and estimate the number of connected
components for an (unknown) pairwise similarity. (b) First we compute an
_approximate_ similarity between images using an embedding. (c) We sample
vertices $u_{i}$ from the distribution $Q(u)$ which biases the samples towards
vertices with low (estimated) degree. (d) We then sample nodes of $v_{i,j}$
from $q_{u_{i}}(v)$ biased towards neighbors. (e) Human feedback on the
sampled pairs is used to estimate the number of clusters with confidence
intervals.

###  3.1 Estimation via Nested Sampling

The above lemma provides a way to estimate the number of connected components
$\text{CC}(G)$ by sampling.

$\text{CC}(G)=\sum_{u=1}^{n}\frac{1}{1+d(u)}=n\mathbb{E}_{u\sim\text{Unif}(1,n)}\left[\frac{1}{1+d(u)}\right].$
(2)

Thus, one approach to estimate the number of connected components is to sample
$N$ vertices and estimate their degrees by querying a human if an edge exists
between the vertex and all other $n-1$ vertices in the graph. This would
require $N\times(n-1)$ queries, saving over $(n-1)^{2}$ queries for exact
estimation. However, one can estimate the degree of a vertex by sampling as
well. This suggests a two-step Monte Carlo (MC) approach for estimation.
First, we sample $N$ vertices $u_{1},\ldots,u_{N}$. For each sampled vertex
$u_{i}$, we then sample $M$ nodes $v_{i,1},\ldots,v_{i,M}$ uniformly at
random, query a human to obtain $s(u_{i},v_{i,j})$ for each potential
neighbor, and estimate the degree of the vertex $u_{i}$ as:

$\hat{d}(u_{i})=\frac{n-1}{M}\sum_{j=1}^{M}s(u_{i},v_{i,j}).$ (3)

From this, we can estimate the number of connected components as:

$\widehat{\text{CC}}_{\text{MC}}(G)=\frac{n}{N}\sum_{i=1}^{N}\frac{1}{1+\hat{d}(u_{i})}.$
(4)

This nested Monte Carlo estimate is unbiased for the expected number of
connected components, i.e., it converges to the true mean under mild
assumptions (see Appendix). One can also construct a sample estimate of the
variance and confidence intervals around the mean (we will derive the
expressions for a general sampling distribution in the next section). The
number of queries required to construct the estimate scales as $N\times M$,
which is more efficient than the earlier approach of $N\times n$. However, the
variance of the estimator can be high for graphs where the degrees of the
vertices vary significantly.

######  Remark.

Our problem is related to work on estimating the number of connected
components in a graph in sub-linear time. The randomized algorithm proposed in
[5, 2] use a similar sampling argument but their cost model is different. They
assume the edges in the graph are provided as an adjacency list and run
breadth-first-search starting from each node for a number of steps till the
size of the connected components exceeds a threshold—a threshold of
$1/\epsilon$ gives an $n\epsilon$ additive approximation to CC. In our setting
the true edges are unknown—we instead have a noisy pairwise similarity—and
have to pay a cost to reveal an edge, and hence the same approach is not
applicable.

###  3.2 Estimation via Nested Importance Sampling

Importance sampling [25] uses a proposal distribution $q$ and replaces the
expectation of a quantity $f(x)$ under $p$ as:

$\operatorname{\mathbb{E}}_{p}\left[f(x)\right]=\operatorname{\mathbb{E}}_{q}\left[\frac{p(x)}{q(x)}f(x)\right].$
(5)

The equality holds for any proposal distribution $q$ that satisfies
$p(x)f(x)>0\implies q(x)>0$. Moreover, one can show that the optimal proposal
distribution $q(x)\propto p(x)f(x)$ for which the estimator has zero variance.

Algorithm 1 Estimating cluster count $k$ using NIS

1:$N\leftarrow$ Number of sampled vertices

2:$M\leftarrow$ Number of sampled edges per vertex

3:$\hat{s}(u,v)\leftarrow$ Approximate pairwise similarity

4:for i = 1,…,N do

5: Sample $u_{i}\sim Q(u)$

6: Sample $v_{i,1},...,v_{i,M}\sim q_{u_{i}}(v)$

7:
$\hat{d}(u_{i})\leftarrow\frac{1}{M}\sum_{j=1}^{M}\frac{s(u_{i},v_{i,j})}{q_{u_{i}}(v_{i,j})}$
// Human feedback$\triangleright$ Eq. (7)

8:end for

9:$\widehat{\text{CC}}_{\text{NIS}}\leftarrow\frac{1}{N}\sum_{i=1}^{N}\left(\frac{1}{\bar{Q}(u_{i})}\times\frac{1}{1+\hat{d}(u_{i})}\right)$
$\triangleright$ Eq. (6)

We are interested in computing various expectations under a uniform
distribution $p$, and one can show that the optimal proposal distribution to
samples nodes to estimate $\text{CC}(G)$ in Eq. 1 is $Q(u)\propto 1/(1+d(u))$,
while that to samples edges to estimate the degree $\hat{d}(u)$ in Eq. 3 is
$q_{u}(v)\propto s(u,v)$.

However, sampling from these distributions requires knowledge of the true
$s(u,v)$ which is unknown. But we can construct proposals using the
approximate pairwise similarity $\hat{s}(u,v)\in[0,1]$. This can be computed
using the similarity between a pair of images estimated from their feature
embeddings. Then, we can set $Q(u)\propto 1/(1+\sum_{v\neq u}\hat{s}(u,v))$ as
the proposal distribution to sample a set of vertices $I$ of size $N$. For
each sampled vertex $u_{i}$, we sample a set of $M$ nodes $v_{i,j}$ from the
distribution $q_{u}(v)\propto\hat{s}(u,v)$. The
$\widehat{\text{CC}}_{\text{NIS}}(G)$ obtained using importance sampling is:

$\widehat{\text{CC}}_{\text{NIS}}(G)=\frac{1}{N}\sum_{i=1}^{N}\left(\frac{1}{Q(u_{i})}\times\frac{1}{1+\hat{d}(u_{i})}\right),\
u_{i}\sim Q(u),$ (6)

where, $\hat{d}(u_{i})$ is estimated as:

$\hat{d}(u_{i})=\frac{1}{M}\sum_{j=1}^{M}\frac{s(u_{i},v_{i,j})}{q_{u_{i}}(v_{i,j})},\quad
v_{i,1},...,v_{i,M}\sim q_{u_{i}}(v).$ (7)

Algorithm 1 and Fig. 3 describe the overall scheme.

The proposal $Q(u)$ biases the distribution towards isolated vertices, i.e.,
ones that have low degrees, as they contribute the most toward the number of
clusters. The second biases the distribution towards sampling nodes that are
likely to be connected, i.e., to have high $\hat{s}(u,v)$. Note the only place
human feedback is required is in computing $\hat{d}(u)$ in Eq. 7 consisting of
$M$ queries. Hence the overall query complexity of the approach is $N\times
M$, similar to the simple Monte Carlo estimator. But if the similarity
function $\hat{s}(u,v)$ is a good approximation to the true similarity then we
expect the estimator to have a lower variance.

###  3.3 Variance and Confidence Intervals

| CUB | Cars | Aircraft | Flowers | Herb19 | iNaturalist
---|---|---|---|---|---|---
$|\mathcal{D}|$ | 11788 | 16185 | 10000 | 8189 | 34225 | 40000
$|\mathcal{Y}|$ | 200 | 196 | 100 | 102 | 683 | 1010

Table 1: Proposed datasets in our benchmark. We show the number of images
$|\mathcal{D}|$ and classes $|\mathcal{Y}|$ per dataset.

######  Theorem 1.

Assume $Q(u)>0$ for all $u$ and $q_{u}(v)>0$ for all $u,v$. Let
$\widehat{\text{CC}}_{N,M}$ denote the estimator using $N$ sampled vertices
and $M$ sampled edges per vertex. For any $M>0$, the estimator
$\widehat{\text{CC}}_{N,M}$ is asymptotically normal, i.e.,

$\sqrt{N}(\widehat{\text{CC}}_{N,M}-\mu_{M})\stackrel{{\scriptstyle
D}}{{\rightarrow}}\mathcal{N}(0,\sigma^{2}_{1,M})\text{ as $N\to\infty$},$ (8)

where
$\mu_{M}=\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{N,M}]=\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{1,M}]$
and $\sigma^{2}_{1,M}=\operatorname{Var}(\widehat{\text{CC}}_{1,M})$.
Furthermore, the bias $|\mu_{M}-\text{CC}|$ is $O(1/M)$. Together these facts
imply that the estimator is consistent as both $N$ and $M$ go to infinity,
i.e., $\lim_{N\to\infty,M\to\infty}\widehat{\text{CC}}_{N,M}=\text{CC}$.

Asymptotic normality justifies the construction of confidence intervals as
follows: let $\hat{\sigma}^{2}_{1,M}$ be the sample variance of
$\frac{1}{Q(u_{i})}\times\frac{1}{1+\hat{d}(u_{i})}$ and use the confidence
interval $\widehat{\text{CC}}_{N,M}\pm
z_{0.025}\cdot\hat{\sigma}_{1,M}/\sqrt{N}$.

###### Proof of Theorem 1.

The estimator $\widehat{\text{CC}}_{N,M}$ is the sample average of $N$
identically distributed copies of

$\widehat{\text{CC}}_{1,M}=\frac{1}{Q(u_{1})}\times\frac{1}{1+\hat{d}(u_{1})}.$
(9)

Therefore
$\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{N,M}]=\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{1,M}]$
and the asymptotic normality result holds by the central limit theorem as long
as $\mu_{M}$ and $\sigma^{2}_{1,M}$ are finite. The quantity
$\frac{1}{Q(u_{1})}\times\frac{1}{1+\hat{d}(u_{1})}$ is bounded above by our
assumption that $Q(u)>0$ and $q_{u}(v)>0$. Together with the fact that the
support of the joint sample space $(u_{1},v_{1,1},\ldots,v_{1,M})$ is finite,
this implies $\mu_{M}$ and $\sigma^{2}_{1,M}$ are finite. It remains to show
that the bias is $O(1/M)$. This can be proved by the delta method, but also
follows from a result of Rainforth et al. [27], which applies to our setting
to assert that the mean-squared error of $\widehat{\text{CC}}_{N,M}$ is
$O(\frac{1}{N}+\frac{1}{M^{2}})$. Because mean-squared error equals variance
plus squared bias, this necessitates that the bias, which only depends on $M$,
is $O(\frac{1}{M})$. ∎

######  Remark.

Rainforth et al. [27] describe the optimal allocation of samples when
$T=NM\to\infty$ and found that it occurs when $N$ grow proportionally to
$M^{2}$ in our setting. However, in applications with finite $T$, the lowest
error occurred for $N\propto T^{\alpha}$ with $\alpha$ between 0.5 and 0.6,
which suggests selecting $N$ to be approximately proportional to $M$ may be
better in practice (See § 4–Parameters for NIS).

##  4 Experiments

This section describes the experimental setup, including datasets, models used
for computing image similarity, baselines for estimating the number of
clusters, and the evaluation metrics.

$k$-NN accuracy $\uparrow$ Model CUB Cars Aircraft Flowers Herb.19 iNat.
ResNet [14] 45.0 22.8 24.9 82.7 14.3 16.6 DINO [4] 50.9 31.7 39.3 94.4 27.8
26.7 CLIP [26] 78.4 92.6 57.1 98.0 25.8 38.5

Table 2: $k$-NN accuracy using ResNet50, DINO ViT-B/8, and CLIP ViT-L/14 on
our benchmark that includes CUB, Stanford Cars, FGVC Aircraft, Oxford Flowers,
Herbarium19, and iNaturalist. CLIP performs the best for most datasets. We use
$k=5$.

#### Datasets

We evaluate our approach on six fine-grained image classification datasets,
where the goal is to estimate the number of categories (see Tab. 1) — Caltech-
UCSD Birds (CUB) [33] consists of 11,788 images of 200 bird species, Stanford
Cars [20] contains 16,185 images of 196 car models, FGVC Aircraft [22]
comprises 10,000 images of 100 aircraft models, Oxford Flowers [24] includes
8,189 images of 102 flower categories, Herbarium19 [30] contains over 46,000
specimens from more than 680 species of the flowering plant family
Melastomataceae, and iNaturalist [16] 2019 features around 270,000 images from
a total of 1,010 species, from which we uniformly randomly sample 40,000
images from the train and validation sets.

#### Image Encoding

We consider a variety of image embeddings using off-the-shelf deep networks.
Specifically, we consider ImageNet pretrained ResNets [14], self-supervised
DINO ViTs [4], and language-based CLIP [26] image encoders. For pretrained
CNNs, we use the features from the last fully connected layer of a ResNet50
[14]. For DINO, we consider the version ViT-B/8, and for CLIP, we use ViT-L/14
feature embeddings. Note that while ResNet50 and DINO encoders are trained
with ImageNet [10], the CLIP ViT-L/14 is trained with LAION [28], which might
overlap with some of the datasets in our benchmark. Table 2 shows the $k$-NN
accuracy across datasets using the Euclidean distance over these embeddings.
CLIP representations often perform best, but the low accuracy on the
Herbarium, iNaturalist, and Aircraft poses a challenge for clustering.

Error rate $\downarrow$ Baseline CUB Cars Aircraft Flowers Herb.19 iNat. mean-
shift [8] 92.8 74.5 184.7 90.5 93.8 98.9 $k$-means [13] 61.3 66.0 46.7 41.2
61.0 70.3 conncomp. 46.9 34.5 203.7 42.2 97.5 55.0

Table 3: Baselines performance on estimating $k$. Error for all baselines for
the unsupervised case (i.e., no human-in-the-loop). The errors are averaged
over the three feature embeddings, i.e., ResNet50, DINO ViT-B/8, and CLIP
ViT-L/14. $k$-means and conncomp outperform mean-shift in the majority of the
datasets. $k$-means WCSS elbow curves are shown in Fig. A5 in the Appendix.

#### Baselines Approaches

We employ three baselines for estimating the number of clusters. The first is
mean-shift clustering [8], which discovers modes in the feature embedding
space. We set the bandwidth parameter adaptively as the average distance
between samples and their nearest neighbor, and estimate the number of
clusters as the number of modes. The second method is $k$-means [13]. To
calculate the _optimal_ $k$, we plot the within-cluster sum of squares
$\mathcal{J}_{\text{km}}=\sum_{i\in G}||{c_{i}}-u_{i}||^{2}_{2}$, where
$c_{i}$ is the cluster center corresponding to $u_{i}$. The elbow is
identified as the value of $k$ where the slope becomes approximately constant.
Lastly, we use connected components (conncomp) after thresholding the
similarity values $\hat{s}(u,v)$ of our graph $G$. To find the optimal
threshold, we use the same procedure as the $k$-means elbow; that is, we
calculate $\mathcal{J}_{\text{km}}$ for different thresholds and return the
threshold at the elbow.

#### Active Clustering

We use pairwise constrained $k$-means (pc$k$-means [1]). For a given $k$, the
objective is:

$\mathcal{J}_{\text{pckm}}=\sum_{i\in G}||c_{i}-u_{i}||^{2}_{2}+\\\
\sum_{(i,j)\in\operatorname{\mathcal{M}}}\alpha\mathbbm{1}[l_{i}\neq
l_{j}]+\sum_{(i,j)\in\operatorname{\mathcal{C}}}\beta\mathbbm{1}[l_{i}=l_{j}],$

where $\operatorname{\mathcal{M}}$ and $\operatorname{\mathcal{C}}$ are the
sets of _must-link_ and _cannot-link_ constraints, respectively, and $l_{i}$
denotes the cluster index for $i$. Scalars $\alpha,\beta>0$ trade off the
$k$-means objective with the cost of violating constraints. We select
empirically $\alpha=\beta=1$. While solving the problem exactly is intractable
[1], the authors propose an algorithm which estimates cluster assignments in a
greedy manner by minimizing the incremental cost of an assignment. Besides
solving the objective, there are several ways to actively query pairs to
reduce human effort. We compare random sampling and a sampling scheme proposed
in [1]. It uses a _farthest-first_ sampling scheme to query the relationship
between existing clusters and a point farthest from all the points that have
been added so far. The idea is to rapidly explore the dataset to find at least
one member for each cluster, after which the samples cover the dataset. Given
a set of constraints, we can pick the optimal $k$ using the elbow heuristic on
the $\mathcal{J}_{\text{pckm}}$ objective.

|
---|---

# sampled pairs / # vertices

Figure 4: Error rate for estimating $k$ per human effort for all the datasets
in our benchmark. We use the similarity matrix built from the $k$-means
solution obtained using ResNet50 features (left) and CLIP ViT-L/14 (right)–See
§ 4. The human effort is measured as the ratio of the number of sampled pairs
to the total images in the dataset. Results behave similarly with DINO (See
Appendix). Estimated counts yielding errors higher than 100% are not shown.

# sampled pairs / # vertices

Figure 5: Error rate for estimating $k$ using $k$-means-derived features and
raw features $\Phi(x_{i})$ For CUB and Cars datasets with CLIP ViT-L/14
feature embeddings. Using both features results in comparable error rates.
Comparisons with other datasets and feature embeddings are shown in the
Appendix.

# sampled pairs / # vertices

Figure 6: Error rate for estimating $k$ per dataset with ResNet50 features.
The human effort is measured as the ratio of the number of sampled pairs to
the total images in the dataset. See Fig. A3 in the Appendix for the results
with DINO ViT-B/8 and CLIP ViT-L/14. Overestimated counts yielding errors
higher than 100% are not shown in the results.

#### Similarity Metric

The similarity metric can be built using any image feature $\Phi$ as
$\hat{s}(u,v)=f(\Phi(x_{i}),\Phi(x_{j}))$ for some function $f$, such as dot
product or cosine similarity. However, we found the following scheme useful
for making comparisons consistent with the $k$-means approach, which is the
best-performing baseline. Instead of using the embeddings $\Phi(x_{i})$, we
use soft assignments from the _optimal_ $k$-means solution. Formally, the new
embeddings are defined as:

$w_{i}=\left(...,\exp\left(-\frac{||\Phi(x_{i})-c_{k}||^{2}_{2}}{2\sigma^{2}}\right),...\right),~{}~{}k=1,...,K,$
(10)

where $c_{k}$ are the centroids from the $k$-means solution. We define
$\sigma$ empirically on CUB dataset for each feature embeddings as 7, 5, and 4
for ResNet, DINO, and CLIP respectively. Then, we use the correlation between
a pair of embeddings $w_{i}$ and $w_{j}$ as the similarity metric:

$\hat{s}(u,v)=\frac{(w_{i}-\bar{w}_{i})\cdot(w_{j}-\bar{w}_{j})}{||w_{i}-\bar{w}_{i}||_{2}||w_{j}-\bar{w}_{j}||_{2}},$
(11)

where $\bar{w}_{i}$ and $\bar{w}_{j}$ are the means of $w_{i}$ and $w_{j}$,
respectively. Using raw features $\Phi(x_{i})$ with correlation similarity
yields similar performance (See Fig. 4 and Fig. 5), but using the $k$-means-
derived distances results in an initial error rate of our sampling approach
that is comparable to $k$-means, making comparisons easier. More details in
Fig. A4.

#### Parameters for Nested-IS

There is a trade-off between the number of sampled vertices $N$ and sampled
neighbors per vertex $M$. Increasing $N$ will reduce the variance of the
estimation of the number of clusters, and increasing $M$ will reduce the
variance of each vertex degree estimate. We select the optimal ratio
empirically on CUB with ResNet50 features and apply it to the other datasets
and feature embeddings. We chose an optimal sampling ratio of $N:M=1:7$, i.e.,
we sample $7N$ neighbors per vertex.

#### Evaluation Metric and Human Effort

Error is measured as $|\text{CC}-\widehat{\text{CC}}|/\text{CC}$, the
fractional absolute difference between the estimated $\widehat{\text{CC}}$ and
the true number of clusters CC. Human effort is measured as the number of
pairwise queries used for estimation. To account for variable dataset sizes,
we report the number of sampled pairs normalized by the size of the dataset;
i.e., a human effort of $1$ means that we have queried as many pairs as there
are images in the dataset. We also assume that human feedback is noise-free,
and in our case, they can accurately predict if a pair of images belong to the
same category.

##  5 Results

We compare our method to the baselines described in § 4 that include pairwise
constrained $k$-means (pc$k$-means) and nested Monte Carlo sampling (Nested-
MC) from Eq. (4).

#### Baselines Perform Poorly

Techniques like mean-shift, $k$-means, and conncomp perform poorly, with about
60% error on average, despite using state-of-the-art image embeddings to
compute similarity (see Fig. 4). For instance, $k$-means estimates $60$
clusters for CUB instead of $200$, $250-300$ clusters instead of $683$ for
Herbarium19, and $300$ clusters instead of $1010$ for iNaturalist. Estimates
using mean-shift and conncomp are even worse. One reason is that choosing
hyperparameters for clustering is particularly challenging. For instance, the
WCSS curve as a function of $k$ looks rather smooth (see Fig. A5), and there
is no clear “elbow.” Another reason is that the underlying similarity is
imperfect, as is also indicated by the $k$-NN accuracy. Improving this through
deep metric learning approaches would require significant resources and
expertise to set various parameters and may not pan out when supervision is
limited [23].

#### Nested-IS outperforms Nested-MC

Both Nested-MC and Nested-IS improve over the baselines as more human feedback
is collected. As described in § 3.1, Nested-MC samples edges uniformly at
random, while Nested-IS is driven by the pairwise similarity and leads to an
error reduction at a much faster rate as seen in Fig. 4 and Fig. A3.
Specifically, we get relative error reductions of $67-70\%$ over Nested-MC
when roughly $n$ pairs have been sampled, where $n$ is the number of nodes,
i.e., the size of the dataset. Error rates are around $15\%$ with roughly $2n$
sampled edges.

#### Nested-IS outperforms Active Clustering

We compare our method to pairwise constrained $k$-means with similar human
effort. Constraints can be sampled randomly or using _farthest-first_ sampling
scheme (pc$k$-means-AL) as described in § 4. Fig. 1 shows that AL improves
over the random sampling baseline, and across datasets pc$k$-means-AL performs
similarly as Nested-MC. However, Nested-IS handily outperforms active
clustering—see Fig. 4 for average and Fig. 6 for per dataset results using
ResNet embeddings. The Appendix contains results for other embeddings where
the trends are similar.

#### Confidence Intervals are Calibrated

In addition to lower error rates, a key advantage of our approach is that it
also provides confidence intervals (CIs). Fig. 1– _bottom_ shows an example
where the confidence intervals are estimated on the CUB dataset using ResNet50
features. To estimate the quality of the CI estimation we calculate the
empirical coverage of the CI over 100 runs (i.e., the percentage of times the
estimated CIs contains the true count). Our method produces close to $95\%$
coverage using $z_{0.025}=1.96$ for a $95\%$ CI, as described in § 3.3, when
around $1\times$ of pairs are sampled across datasets, as shown in Fig. 7–
_top_.

|
---|---
|

# sampled pairs / # vertices

Figure 7: Confidence intervals’ coverage and Bias using ResNet50 and CLIP
ViT-L/14 feature embeddings on all datasets. (Top) Our method produces a CI
coverage close to $95\%$ (when using $z_{0.025}=1.96$ for a $95\%$ confidence
interval–§ 3.3) with less than $1\times$ of sampled pairs. (Bottom) Even
though our estimator has a negative bias for a low number of sampled pairs, it
rapidly reaches zero compared to random sampling (Nested-MC). See CI coverage
and Bias with DINO ViT-B/8 features in the Appendix.

#### Estimation Bias is Low

We calculate the empirical bias, denoted as
$\textsc{Bias}=\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{\text{NIS}}(G)]-\text{CC}(G)$
where $\operatorname{\mathbb{E}}[\widehat{\text{CC}}_{\text{NIS}}(G)]$ is the
expected count estimate after 100 runs. Fig. 7– _bottom_ shows that our
estimator has a negative bias initially, but it rapidly drops to 0. The
initial negative bias might explain the lower coverage of the CIs. Fig. A6 in
the Appendix shows that the ratio of the absolute value of the bias and the
standard deviation ($\textsc{Bias}/\sigma$) quickly falls below 0.1, in some
cases with as few as $0.2\times$ sampled pairs. Beyond this point, the error
contribution from bias is relatively small [7].

#### How Much do we Know about the Clustering?

In many situations we wish to also recover the clustering in a dataset, such
as in generalized category discovery [32]. Should human effort be used to
estimate the clustering directly using active clustering, or to estimate $k$
for $k$-means using our approach? To answer this we conduct the following
experiment. First, we can measure the accuracy of a clustering as:

$\textsc{Acc}=\max_{p\in\mathcal{P}(\mathcal{Y})}\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}[y_{i}=p(\hat{y_{i}})],$
(12)

where $\mathcal{P}(\mathcal{Y})$ is the set of all permutations of the class
labels. On a dataset, we compare the accuracy of clustering using $k$-means
with estimated $k$ using the elbow method, with the accuracy of active
pc$k$-means, and with $k$ estimated using Nested-IS with $k$-means using the
same amount of human effort. Fig. 8 shows the results. Surprisingly, we find
that accurately estimating $k$ has a bigger impact on the quality of
clustering than active clustering, which suggests that human effort is better
spent to estimate $k$ initially.

# clusters (k)

Figure 8: Clustering accuracy using the right number of clusters. Using the
improved $k$ and pairwise constraints (pc$k$-means+AL) improves the clustering
accuracy over $k$-means+elbow, while clustering accuracy with our estimated
$k$ improves accuracy further (pc$k$-means+NIS). We plot results with five
estimated $k$s and constraints from our proposed approach (blue stars). The
red shaded line indicates the true number of clusters in the dataset.

##  6 Discussion and Conclusion

We addressed the problem of estimating the number of clusters in a dataset and
introduced a Nested-IS approach. This method produces asymptotically unbiased
estimates of cluster counts along with accurate confidence intervals. Our
approach, which works atop any standard image similarity measure,
significantly reduces error compared to the Nested-MC estimator. Additionally,
its computational simplicity makes it more practical in low-resource settings,
where fine-tuning underlying networks might not be feasible. Direct estimation
of cluster numbers also surpasses active clustering baselines, leading to
improved dataset clustering with $k$-means. In most datasets, our model
achieves less than 20% error with $n$ pairs of images, roughly equivalent to
examining each image in the dataset once. We will publicly share the code for
our approach and the evaluation framework upon acceptance of the paper.

## References

  * Basu et al. [2004] Sugato Basu, Arindam Banerjee, and Raymond J. Mooney.  Active semi-supervision for pairwise constrained clustering.  pages 333–344, 2004.
  * Berenbrink et al. [2014] Petra Berenbrink, Bruce Krayenhoff, and Frederik Mallmann-Trenn.  Estimating the number of connected components in sublinear time.  _Information Processing Letters_ , 114(11):639–642, 2014.
  * Boykov and Funka-Lea [2006] Yuri Boykov and Gareth Funka-Lea.  Graph cuts and efficient n-d image segmentation.  _Int. J. Comput. Vis._ , 70(2):109–131, 2006.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In _Proceedings of the International Conference on Computer Vision (ICCV)_ , 2021.
  * Chazelle et al. [2005] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan.  Approximating the minimum spanning tree weight in sublinear time.  _SIAM Journal on computing_ , 34(6):1370–1379, 2005.
  * Chiaroni et al. [2023] Florent Chiaroni, Jose Dolz, Ziko Imtiaz Masud, Amar Mitiche, and Ismail Ben Ayed.  Parametric information maximization for generalized category discovery, 2023.
  * Cochran [1977] William G Cochran.  _Sampling techniques_.  John Wiley & Sons, 1977.
  * Comaniciu and Meer [2002] Dorin Comaniciu and Peter Meer.  Mean shift: A robust approach toward feature space analysis.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 24(5):603–619, 2002.
  * Craenendonck et al. [2017] Toon Van Craenendonck, Sebastijan Dumancic, and Hendrik Blockeel.  Cobra: A fast and simple method for active clustering with pairwise constraints.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17_ , pages 2871–2877, 2017.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2009.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _ICLR_ , 2021.
  * ERDdS and R&wi [1959] P ERDdS and A R&wi.  On random graphs i.  _Publ. math. debrecen_ , 6(290-297):18, 1959.
  * Hartigan and Wong [1979] J. A. Hartigan and M. A. Wong.  A k-means clustering algorithm.  _JSTOR: Applied Statistics_ , 28(1):100–108, 1979.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Hoffer and Ailon [2015] Elad Hoffer and Nir Ailon.  Deep metric learning using triplet network.  In _Similarity-Based Pattern Recognition_ , pages 84–92, Cham, 2015. Springer International Publishing.
  * Horn et al. [2018] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alexander Shepard, Hartwig Adam, Pietro Perona, and Serge J. Belongie.  The inaturalist species classification and detection dataset.  In _CVPR_ , pages 8769–8778. IEEE Computer Society, 2018.
  * J et al. [2022] Joseph K J, Sujoy Paul, Gaurav Aggarwal, Soma Biswas, Piyush Rai, Kai Han, and Vineeth N Balasubramanian.  Novel class discovery without forgetting.  In _European Conference on Computer Vision (ECCV)_ , 2022.
  * KAYA and BİLGE [2019] Mahmut KAYA and Hasan Şakir BİLGE.  Deep metric learning: A survey.  _Symmetry_ , 11(9), 2019.
  * Koch et al. [2015] Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov.  Siamese neural networks for one-shot image recognition.  2015\.
  * Krause et al. [2013] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In _4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13)_ , Sydney, Australia, 2013.
  * Kulis [2013] Brian Kulis.  Metric learning: A survey.  2013\.
  * Maji et al. [2013] S. Maji, J. Kannala, E. Rahtu, M. Blaschko, and A. Vedaldi.  Fine-grained visual classification of aircraft.  Technical report, 2013.
  * Musgrave et al. [2020] Kevin Musgrave, Serge Belongie, and Ser-Nam Lim.  A metric learning reality check.  In _Computer Vision – ECCV 2020_ , pages 681–699, Cham, 2020. Springer International Publishing.
  * Nilsback and Zisserman [2008] Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In _Indian Conference on Computer Vision, Graphics and Image Processing_ , 2008.
  * Owen [2013] Art B. Owen.  _Monte Carlo theory, methods and examples_.  2013\.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 8748–8763. PMLR, 2021.
  * Rainforth et al. [2018] Tom Rainforth, Rob Cornish, Hongseok Yang, Andrew Warrington, and Frank Wood.  On nesting monte carlo estimators.  In _International Conference on Machine Learning_ , pages 4267–4276. PMLR, 2018.
  * Schuhmann et al. [2022] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev.  Laion-5b: An open large-scale dataset for training next generation image-text models.  In _Advances in Neural Information Processing Systems_ , pages 25278–25294. Curran Associates, Inc., 2022.
  * Shi and Malik [2000] Jianbo Shi and J. Malik.  Normalized cuts and image segmentation.  _IEEE Trans. on Pattern Analysis and Machine Intelligence_ , 22(8):888–905, 2000.
  * Tan et al. [2019] Kiat Chuan Tan, Yulong Liu, Barbara A. Ambrose, Melissa C. Tulig, and Serge J. Belongie.  The herbarium challenge 2019 dataset.  _ArXiv_ , abs/1906.05372, 2019.
  * Thorndike [1953] Robert Thorndike.  Who belongs in the family?  _Psychometrika_ , 18:267–276, 1953.
  * Vaze et al. [2022] Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman.  Generalized category discovery.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2022.
  * Wah et al. [2011] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The Caltech-UCSD Birds-200-2011 Dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology, 2011.

Supplementary Material

##  Appendix A Supporting Figures

|
---|---

# sampled pairs / # vertices

Figure A1: Error rate for estimating $k$ per human effort for all the datasets
in our benchmark. We use the similarity matrix built from the $k$-means
solution obtained using DINO ViT-B/8–See § 4. The human effort is measured as
the ratio of the number of sampled pairs to the total images in the dataset.

|  |
---|---|---

# sampled pairs / # vertices

Figure A2: Empirical bias and confidence intervals’ coverage  using DINO
ViT-B/8 feature embeddings for all datasets.

# sampled pairs / # vertices

Figure A3: Error rate per human effort per dataset. We use the similarity
matrix built from the $k$-means solution obtained using ResNet50 (top row),
DINO ViT-B/8 (middle row), and CLIP ViT-L/14 (bottom row) features (See § 4).
The human effort is measured as the ratio of the number of sampled pairs to
the total images in the dataset.

Figure A4: Error rate for estimating $k$ using $k$-means-derived features and
raw features $\Phi(x_{i})$ For all datasets with ResNet50 (top), DINO ViT-B/8
(middle), and CLIP ViT-L/14 (bottom) feature embeddings. Using both features
results in comparable error rates.  ResNet50 ImageNet
---
|  |  |  |  |
DINO ViT-B/8
|  |  |  |  |
CLIP ViT-L/14
|  |  |  |  |
Figure A5: $k$-means elbows for all datasets and feature embeddings using
unconstraint $k$-means and pc$k$-means with $1\times$ and $2\times$ pairwise
constraints sampled using the approach proposed in [1].

CUB-200-2011 | Stanford Cars | FGVC Aircraft
---|---|---
|  |
Oxford Flowers | Herbarum19 | iNaturalist
|  |

# sampled pairs / # vertices

Figure A6: Ratio of the absolute value of the bias and the standard deviation
per number of sampled pairs. The ratio drops rapidly below 0.1 where it can be
discarded as a disadvantage of the estimator [7].