CNMBI: Determining the Number of Clusters Using Center Pairwise Matching and Boundary Filtering

Ruilin Zhang; Haiyang Zheng; Hongpeng Wang

cs.CVMar 23, 2026

CNMBI: Determining the Number of Clusters Using Center Pairwise Matching and Boundary Filtering

Authors: Ruilin Zhang, Haiyang Zheng, Hongpeng Wang

Organizations: Harbin Institute of Technology, Shenzhen, Shenzhen, China · Peng Cheng Laboratory, Shenzhen, China

Abstract

One of the main challenges in data mining is choosing the optimal number of clusters without prior information. Notably, existing methods are usually in the philosophy of cluster validation and hence have underlying assumptions on data distribution, which prevents their application to complex data such as large-scale images and high-dimensional data from the real world. In this regard, we propose an approach named CNMBI. Leveraging the distribution information inherent in the data space, we map the target task as a dynamic comparison process between cluster centers regarding positional behavior, without relying on the complete clustering results and designing the complex validity index as before. Bipartite graph theory is then employed to efficiently model this process. Additionally, we find that different samples have different confidence levels and thereby actively remove low-confidence ones, which is, for the first time to our knowledge, considered in cluster number determination. CNMBI is robust and allows for more flexibility in the dimension and shape of the target data (e.g., CIFAR-10 and STL-10). Extensive comparison studies with state-of-the-art competitors on various challenging datasets demonstrate the superiority of our method.

Figures & tables

Panel of Figure 1 — Figure 1: Density center versus mean center for different cluster number settings.

Panel of Figure 2 — Figure 2: Synthetic dataset containing arbitrary-shaped clusters.

Panel of Figure 3 — Figure 3: Plots of $k$ and center pairwise loss on partial image data sets.

Methods	$S_{\mu}$	$S_{\gamma}$	${{\varphi}}$	MNIST	Pointing Data
Ours	$\checkmark$	$\checkmark$	$\checkmark$	NC: 10 ACC: 1	NC: 15 ACC: 1
Method-1	$\checkmark$	$\checkmark$	$\times$	NC: 10 ACC: 0.6	NC: 15 ACC: 0.2
Method-2	$\checkmark$	$\times$	$\times$	NC: 1 ACC: 0	NC: 1 ACC: 0
Method-3	$\times$	$\checkmark$	$\times$	NC: 10 ACC: 0.3	NC: 15 ACC: 0.1
Method-4	$\checkmark$	$\times$	$\checkmark$	NC: 1 ACC: 0	NC: 1 ACC: 0
Method-5	$\times$	$\checkmark$	$\checkmark$	NC: 10 ACC: 0.5	NC: 15 ACC: 0.4

Table 3: Ablation study of CNMBI and its degradation methods.

S_{\mu}

S_{\gamma}

and

{{\varphi}}

denote the Mean center, Denisty center, and boundary filtering, respectively.

Panel of Figure 4 — Figure 4: Three extreme scenarios in Robustness

Panel of Figure 5 — Figure 5: Boundary pattern information extraction.

Cluster Number Estimation

See all 13 papers

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis
Sep 15, 2026Savik Kinger, Luciano Dyballa, Steven W. ZuckerCluster Number Estimation Clustering
Department of Computer Science Yale University · School of Science & Technology IE University · Depts. of Computer Science and Biomedical Engineering Wu Tsai Institute Yale University
Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees
Apr 8, 2026Marek GagolewskiDensity-Based Clustering Clustering
Warsaw University of Technology, Faculty of Mathematics and Information Science, ul. Koszykowa 75, 00-662 Warsaw, Poland · Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447 Warsaw, Poland
Central Description Length (CDL) Clustering Validation Index
Jun 2, 2026Mahdi Shamsi, Soosan BeheshtiMinimum Description Length Clustering
Toronto Metropolitan University, 350 Victoria St., Toronto, Ontario M5B 2K3, Canada

Sep 15, 2026J/K move · Enter open · S save

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

Savik Kinger, Luciano Dyballa, Steven W. Zucker

Department of Computer Science Yale University · School of Science & Technology IE University · Depts. of Computer Science and Biomedical Engineering Wu Tsai Institute Yale University

Cluster Number Estimation Clustering Unsupervised Clustering Manifold Learning

Open paper AskPDF arXiv

The manifold hypothesis suggests a natural criterion for clustering: partition data according to the manifold component from which each point is drawn. Whether two components are separable depends on a geometric tradeoff: the ambient separation between components versus the largest gap in sampling. In practice, this tradeoff is rarely assessed explicitly, leading standard methods to over-commit to a single clustering assignment even when the data do not support a unique answer. We formalize this tradeoff by combining intrinsic manifold geometry (volume growth and reach) with sample-level quantities (fill distance and density), yielding a threshold phenomenon for mutual-

k

-nearest-neighbor graphs: when the offset-to-fill ratio exceeds a conservative upper threshold, component separation is preserved; below a lower threshold, components fuse. The gap between these thresholds defines a geometric uncertainty zone in which the number of clusters is not identifiable from the data. Nevertheless, conventional approaches still seek one: sweeping parameters (an engineering approach) or fitting a generative mixture model (a model-based approach). Rather than forcing a single estimate of the number of clusters, we propose Manifold-Based Clustering (MBC), which returns an explicit bracket interval to quantify the underlying data uncertainty. This bracket acts as an empirically calibrated diagnostic: it narrows when a single resolution is supported, widens when multiple resolutions coexist, and collapses to one when no separated structure is detectable. Empirically, we find that many real datasets lie within the uncertainty zone rather than admitting one clear answer. Our results suggest that ambiguity in cluster number is often intrinsic, and should be quantified rather than resolved.

Abstract

Cluster Number Estimation

Explore similar work

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees

Central Description Length (CDL) Clustering Validation Index