A Novel Theoretical Analysis for Clustering Heteroscedastic Gaussian Data without Knowledge of the Number of Clusters

Dominique Pastor; Elsa Dupraz; Ismail Hbilou; Guillaume Ansel

stat.MLApr 2, 2026

A Novel Theoretical Analysis for Clustering Heteroscedastic Gaussian Data without Knowledge of the Number of Clusters

Authors: Dominique Pastor, Elsa Dupraz, Ismail Hbilou, Guillaume Ansel

Organizations: Lab-STICC, IMT Atlantique, 29238 Brest, France · OPTI’SEA 23 rue du Bourgneuf 29300 Quimperlé, France

Abstract

This paper addresses the problem of clustering measurement vectors that are heteroscedastic in that they can have different covariance matrices. From the assumption that the measurement vectors within a given cluster are Gaussian distributed with possibly different and unknown covariant matrices around the cluster centroid, we introduce a novel cost function to estimate the centroids. The zeros of the gradient of this cost function turn out to be the fixed-points of a certain function. As such, the approach generalizes the methodology employed to derive the existing Mean-Shift algorithm. But as a main and novel theoretical result compared to Mean-Shift, this paper shows that the sole fixed-points of the identified function tend to be the cluster centroids if both the number of measurements per cluster and the distances between centroids are large enough. As a second contribution, this paper introduces the Wald kernel for clustering. This kernel is defined as the p-value of the Wald hypothesis test for testing the mean of a Gaussian. As such, the Wald kernel measures the plausibility that a measurement vector belongs to a given cluster and it scales better with the dimension of the measurement vectors than the usual Gaussian kernel. Finally, the proposed theoretical framework allows us to derive a new clustering algorithm called CENTRE-X that works by estimating the fixed-points of the identified function. As Mean-Shift, CENTRE-X requires no prior knowledge of the number of clusters. It relies on a Wald hypothesis test to significantly reduce the number of fixed points to calculate compared to the Mean-Shift algorithm, thus resulting in a clear gain in complexity. Simulation results on synthetic and real data sets show that CENTRE-X has comparable or better performance than standard clustering algorithms K-means and Mean-Shift, even when the covariance matrices are not perfectly known.

Figures & tables

Figure 1: Centre-X applied on the 2D toy data sets provided in the scikit-learn documentation. The red dots are the centroids estimated by CENTREx.

Panel of Figure 2 — Figure 2: Clustering performance of CENTREx vs. K-means++, X-means and Mean-Shift with various kernels (flat, Gaussian, Wald). For all $n\in\llbracket 1,N\hskip 0.42677pt\rrbracket$ , $\bm{C}_{n}=\sigma^{2}\,\bm{I}_{{\mathrm{d}}}$ with known $\sigma$ : (a) Percentage of correctly retrieved number of clusters; (b) Silhouette; (c) Error rate; (d) Average estimated value of $K$ ; (e) Zoom on error rate.

Panel of Figure 3 — Figure 3: Clustering performance and robustness of CENTREx vs. K-means, X-means, and Mean-Shift. For all $n\!\in\!\llbracket 1,N\hskip 0.42677pt\rrbracket$ , $\bm{C}_{n}\!=\!\sigma^{2}\,\bm{I}_{{\mathrm{d}}}$ and $\sigma$ is estimated by MLE if unknown to CENTREx: (a) Percentage of correctly retrieved number of clusters; (b) Silhouette; (c) Error rate; (d) Average estimated value of $K$ ; (e) zoom on error rate.

Panel of Figure 4 — Figure 4: Clustering performance of CENTREx vs. K-means++ and X-means. For each $\sigma_{\text{min}}\!\in\![1,40]$ and for all $n\!\in\!\llbracket 1,N\hskip 0.42677pt\rrbracket$ , $\bm{C}_{n}$ is a diagonal matrix $\bm{\Delta}_{n}$ with random diagonal elements uniformly distributed in $[\sigma_{\text{min}},\sigma_{\text{max}}]$ with $\sigma_{\text{max}}=\sigma_{\text{min}}+4$ . CENTREx ( $\bm{\Delta}$ ) is CENTREx with perfect knowledge of $\bm{\Delta}_{1},\ldots,\bm{\Delta}_{N}$ and, for different $\widehat{\sigma}$ , CENTREx ( $\widehat{\sigma}^{2}\bm{I}_{{\mathrm{d}}}$ ) is CENTREx with $\bm{\Delta}_{n}=\widehat{\sigma}^{2}\bm{I}_{{\mathrm{d}}}$ for all $n\in\llbracket 1,N\hskip 0.42677pt\rrbracket$ : (a) Percentage of correctly retrieved number of clusters; (b) Silhouette; (c) Error rate; (d) Average estimated value of $K$ ; (e) zoom on error rate.

Panel of Figure 5 — Figure 5: Performance of CENTREx vs. K-means++ and X-means. Given $\sigma_{\text{min}}\!\in\![1,40]$ and cluster # $k$ , we equiprobably choose $I_{0}\!=\![\sigma_{\text{min}},\sigma_{\text{min}}\!+\!1]$ or $I_{1}\!=\![\sigma_{\text{max}}\!-\!1,\sigma_{\text{max}}]$ with $\sigma_{\text{max}}\!=\!\sigma_{\text{min}}\!+\!4$ . The covariance matrix of each $\bm{Y}_{n}$ in cluster # $k$ is a diagonal matrix $\bm{\Delta}_{n}$ with random diagonal elements uniformly distributed in the drawn interval. CENTREx ( $\bm{\Delta}$ ) is CENTREx with ${{\bm{C}^{\prime}}}_{\!\!n}\!=\!\bm{\Delta}_{n}$ for all $n$ , CENTREx ( $\widehat{\bm{\Delta}}$ ) is CENTREx with the ${{\bm{C}^{\prime}}}_{\!\!n}$ equal to estimates $\widehat{\bm{\Delta}}_{n}$ of the $\bm{\Delta}_{n}$ and, for different $\widehat{\sigma}$ , CENTREx ( $\widehat{\sigma}^{2}\bm{I}_{{\mathrm{d}}}$ ) is CENTREx with all the ${{\bm{C}^{\prime}}}_{\!\!n}$ equal to $\widehat{\sigma}^{2}\bm{I}_{{\mathrm{d}}}$ : (a) Percentage of correctly retrieved number of clusters; (b) Silhouette; (c) Error rate; (d) Average estimated value of $K$ ; (e) zoom on error rate.

Panel of Figure 6 — Figure 6: Clustering with CENTREx on (a) Ruspini, (b) IRIS ( $2$ nd and $4$ th dimensions). The red dots are the estimated centroids.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Oct 12, 2026

Selective Inference for Clustering Under Unknown Covariance

Unsupervised clustering is widely used to discover underlying group structure, after which researchers often seek to validate these groups via post-hoc hypothesis testing on the population means. However, using the same data both to form clusters and to test for a difference in means inflates the Type I error rate. Recent work in selective inference has proposed solutions when the underlying data are drawn from a multivariate Gaussian distribution with a known covariance matrix or an unknown isotropic covariance matrix. We propose a new selective test for the difference in means between two clusters that provably controls the Type I error rate under an arbitrary unknown covariance matrix. Our test statistic does not require estimating the feature covariance matrix; instead, it leverages a Monte Carlo sampling procedure over the set of orthogonal matrices. We show that this new selective test can be computed efficiently, and we derive closed-form solutions when clusters are formed using k-means or hierarchical clustering. In simulations, we demonstrate that our proposed p-value controls the selective Type I error rate and achieves substantial power, and we illustrate its application on gene expression and drug review data sets.

Yiqun T. Chen, Lucy L. Gao

Departments of Biostatistics and Computer Science, Johns Hopkins University · Department of Statistics and Actuarial Science, University of Waterloo

Selective Inference Statistical Hypothesis Testing Clustering

Ask PDF

Jul 2, 2026

Statistical Properties of $k$ -means Clustering for Data Missing Completely at Random

The classical

k

-means clustering cannot be directly used to incomplete data, and existing

k

-means-based clustering for missing data primarily focus on improving the practical accuracy of clustering, whereas most of them lack theoretical guarantees in the asymptotic sense. In this paper, we investigate the statistical properties of

k

-means clustering in the presence of missing data. We first establish the

\sqrt{n}

-excess risk bound and prove the consistency of the estimated cluster centers under general missing mechanisms. For the Missing Completely at Random (MCAR) mechanism, we further derive the

\sqrt{n}

-convergence rate and asymptotic normality of the estimated cluster centers. Moreover, we study in what cases the cluster centers estimated by incomplete data converge to the true cluster centers of original fully observed data, and give a sufficient condition about the missing probability and the separation among true clusters. These results provide a theoretical guarantee for missing-data-

k

-means. Notably, our analysis reveal that under MCAR mechanism, both achieving the

\sqrt{n}

-rate and converging to the true cluster centers require

k

true centers to be distinct in every dimension, highlighting the significant challenges of application in high-dimensional regimes. Finally, we conduct numerical simulations on synthetic incomplete datasets to support our theoretical analysis results.

Xin Guan

Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan

Clustering Unsupervised Clustering Statistical Learning Theory

Ask PDF

Apr 13, 2026

Distributionally Robust K-Means Clustering

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 Distribution Shift Robustness Wasserstein Distributionally Robust Optimization

Ask PDF

Abstract

Clustering

Explore similar work

Selective Inference for Clustering Under Unknown Covariance

Statistical Properties of kkk-means Clustering for Data Missing Completely at Random

Distributionally Robust K-Means Clustering

Statistical Properties of $k$ -means Clustering for Data Missing Completely at Random