We develop a geometric framework that links objective accuracy to structural recovery in prototype-based clustering. The analysis is algorithm-agnostic and applies to a broad class of admissible loss functions. We define a clustering condition number that compares within-cluster scale to the minimum loss increase required to move a point across a cluster boundary. When this quantity is small, any solution with a small suboptimality gap must also have a small misclassification error relative to a benchmark partition. The framework also clarifies a fundamental trade-off between robustness and sensitivity to cluster imbalance, leading to sharp phase transitions for exact recovery under different objectives. The guarantees are deterministic and non-asymptotic, and they separate the role of algorithmic accuracy from the intrinsic geometric difficulty of the instance. We further show that errors concentrate near cluster boundaries and that sufficiently deep cluster cores are recovered exactly under strengthened local margins. Together, these results provide a geometric principle for interpreting low objective values as reliable evidence of meaningful clustering structure.
Figures & tables
Figure 1: Geometric interpretation of the loss increment. A point xi in cluster j lies at distance r≤Deff from its anchor θj∗ . Any reassignment to another prototype θℓ∗ increases the distance by at least γ , so that d(xi,θℓ∗)≥r+γ . This distance gap induces a minimum loss increase of Δg(γ;Deff) .
Figure 2: Condition number κ as a function of the relative margin γ/Deff . Huber loss (shown with markers, τ/Deff∈{0.5,1,2} ) interpolates between the quadratic scaling of k -means and the linear scaling of k -medoids, providing a tunable trade-off between stability and robustness. The k -means curve coincides with the Huber curve when τ/Deff=2 .
Figure 3: Two-cluster phase diagram in the geometric two-ball model. Curves show the sufficient exact-recovery boundaries from Theorem 4.1 . Regions to the right of each curve correspond to parameter values for which the benchmark partition is guaranteed to be the unique minimizer of the profiled objective C↦minθLn(C,θ) , up to label swapping.
Figure 4: Core–Belt decomposition. Shaded disks represent cluster cores ( d(x,θj∗)≤Deff−s ), while dashed rings indicate the boundary belt where misclassifications may occur. Points on the right side of Cluster 1 lie closer to the competing prototype θ2∗ and are therefore more susceptible to reassignment.
This paper develops a unified theoretical framework showing that a broad family of clustering methods, including k-means, fuzzy c-means, kernel k-means, kernel FCM, and spectral clustering, can all be expressed as structured low-rank projectors acting on a signal-derived matrix. By formulating each method as an instance of min over B in C of ||M - M P_B||_F^2, with different constraint sets C, we establish a common optimization template that clarifies the algebraic links among hard, fuzzy, kernel-induced, and orthonormal projections. Within this framework, we derive non-trivial theoretical results, including geodesic convexity properties on the projection manifold, perturbation bounds quantifying stability to matrix noise, and exact recovery guarantees under ideal block-model conditions. The analysis further explains when different clustering families collapse to the same optimal subspace and how deviations arise under small inter-cluster leakage. Overall, the work provides a coherent, theory-first foundation for understanding clustering through structured projectors.
Angshul Majumdar
Indraprastha Institute of Information Technology Delhi New Delhi 110020, India
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.
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
Determining the number of clusters is a central challenge in unsupervised learning, where ground-truth labels are unavailable. The Silhouette coefficient is a widely used internal validation metric for this task, yet its standard micro-averaged form tends to favor larger clusters under size imbalance. Macro-averaging mitigates this bias by weighting clusters equally, but may overemphasize noise from under-represented groups. We introduce Composite Silhouette, an internal criterion for cluster-count selection that aggregates evidence across repeated subsampled clusterings rather than relying on a single partition. For each subsample, micro- and macro-averaged Silhouette scores are combined through an adaptive convex weight determined by their normalized discrepancy and smoothed by a bounded nonlinearity; the final score is then obtained by averaging these subsample-level composites. We establish key properties of the criterion and derive finite-sample concentration guarantees for its subsampling estimate. Experiments on synthetic and real-world datasets show that Composite Silhouette effectively reconciles the strengths of micro- and macro-averaging, yielding more accurate recovery of the ground-truth number of clusters.
Aggelos Semoglou, Aristidis Likas, John Pavlopoulos
Athens University of Economics and Business, Greece. · Archimedes, Athena Research Center, Greece. · University of Ioannina, Greece.