Authors: Tom Trigano, Yann Sepulcre, Itshak Lapidot
Organizations: Shamoon College of Engineering, Department of Electrical Engineering, Ashdod, Israel · Sapir Academic College, Department of Engineering, Sderot, Israel · Afeka Tel-Aviv Academic College of Engineering, School of Electrical Engineering, Israel · Avignon University, LIA, France
Standard Mean-Shift algorithms are notoriously sensitive to the bandwidth hyperparameter, particularly in data-scarce regimes where fixed-scale density estimation leads to fragmentation and spurious modes. In this paper, we propose Doubly Stochastic Mean-Shift (DSMS), a novel extension that introduces randomness not only in the trajectory updates but also in the kernel bandwidth itself. By drawing both the data samples and the radius from a continuous uniform distribution at each iteration, DSMS effectively performs a better exploration of the density landscape. We show that this randomized bandwidth policy acts as an implicit regularization mechanism, and provide convergence theoretical results. Comparative experiments on synthetic Gaussian mixtures reveal that DSMS significantly outperforms standard and stochastic Mean-Shift baselines, exhibiting remarkable stability and preventing over-segmentation in sparse clustering scenarios without other performance degradation.
Figures & tables
List of Algorithms 0.1 Stochastic and Doubly Stochastic mean-shifts.
Cluster ID
Parameters
Cluster 1
Cluster 2
Cluster 3
Mean Vector
[11]
[−1−1]
[1−1]
Covariance matrix
0.65I2
0.65I2
0.65I2
Points per Cluster ( N )
N∈[10;200]
N∈[10;200]
N∈[10;200]
Table 2: Data generation hyperparameters for the 3-Gaussian Mixture Model. The values for Mean, Standard Deviation, and Sample Size are detailed for each Cluster ID.
Parameter
MS
BMS
SMS
DSMS
Common Parameters
Max Iterations
107
Convergence Threshold
10−6
Algorithm-Specific Parameters
Bandwidth ( h )
0.6
0.6
0.6
Variable
Bandwidth Range [hmin,hmax]
N/A
N/A
N/A
[0.2,1.6]
Table 3: Hyperparameter settings for Mean-Shift (MS), Blurring Mean-Shift (BMS), Stochastic Mean-Shift (SMS), and Dynamic Stochastic Mean-Shift (DSMS).
Figure 1: Average number of clusters with 90% confidence intervals for the different algorithms, as a function of the number of samples per cluster. The true number of clusters (3) is represented by the thin dotted line.
Figure 2: K as a function of the class imbalance ratio as defined in [ 11 ]
Figure 3: K as a function of the number of clusters
Figure 4: K as a function of the bandwidth range hmax−hmin
Figure 5: ACP and ALP as a function of hmax−hmin
K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.
Vikrant Malik, Taylan Kargin, Babak Hassibi
Department of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125 USA. · California Institute of Technology, Pasadena, CA 91125 USA · Massachusetts Institute of Technology, Cambridge, MA 02139 USA.
Clustering is a cornerstone of modern data analysis. Detecting clusters in exploratory data analyses (EDA) requires algorithms that make few assumptions about the data. Density-based clustering algorithms are particularly well-suited for EDA because they describe high-density regions, assuming only that a density exists. Applying density-based clustering algorithms in practice, however, requires selecting appropriate hyperparameters, which is difficult without prior knowledge of the data distribution. For example, DBSCAN requires selecting a density threshold, and HDBSCAN* relies on a minimum cluster size parameter. In this work, we propose Persistent Leaves Spatial Clustering for Applications with Noise (PLSCAN), a multiscale density-based clustering algorithm that replaces HDBSCAN*'s fixed minimum cluster size pruning of a mutual-reachability linkage hierarchy with a persistence-based cluster selection procedure. Effectively, PLSCAN identifies all minimum cluster sizes for which HDBSCAN* produces stable (leaf) clusters. In concept, PLSCAN applies scale-space clustering principles and is equivalent to persistent homology on a novel metric space. We compare its performance to HDBSCAN* on several real-world datasets, demonstrating that it achieves a higher median ARI, is less sensitive to changes in the number of mutual reachability neighbours, and has higher stability under resampling. Additionally, we compare PLSCAN's computational costs to k-Means++, demonstrating competitive run-times on low-dimensional datasets. At higher dimensions, run times scale more similarly to HDBSCAN*.
Daniël Bot, Leland McInnes, Jan Aerts
1UHasselt, Data Science Institute (DSI) · 2Tutte Institute for Mathematics and Computing · 3KU Leuven, Augmented Intelligence for Data Analytics Lab, Department of Biosystems
The Subspace Constrained Mean Shift (SCMS) algorithm is a popular nonparametric method for extracting density ridges, which serve as a low-dimensional representation of high-dimensional data. It is a widely held belief in the literature that SCMS trajectories converge to the classical density ridge, which we call the "static ridge", defined via the density gradient and the eigenvalues and eigenvectors of the density's Hessian. In this paper, we demonstrate that this assumption does not hold in general, as the static definition fails to account for the rotation of the trailing eigenspace along the continuous flow of the algorithm's underlying vector field. To resolve this, we propose a paradigm shift by introducing the "stable ridge", a novel geometric structure defined through the lens of dynamical systems and the Jacobian of the projected density gradient. We prove that this stable ridge is the true theoretical target of the SCMS algorithm. Building upon this foundation, we develop a generalized SCMS framework utilizing a constant step size, establishing its uniform R-linear convergence and topological surjectivity onto the stable ridge. We further derive the rates of convergence for estimating the stable ridge in terms of the Hausdorff distance. Finally, we expose that the original SCMS algorithm suffers from polynomial-time computational complexity, which is caused by implicitly coupling the step size to the smoothing bandwidth via the Mean Shift operator, and demonstrate how our generalized framework provides a statistically consistent and more efficient solution.