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

• URL: http://arxiv.org/abs/2607.01945v1
• Date: Thu, 02 Jul 2026 09:34:44 GMT
• Title: Statistical Properties of $k$-means Clustering for Data Missing Completely at Random
• Abstract summary: We investigate the statistical properties of $k$-means clustering in the presence of missing data.<n>For the Missing Completely at Random (MCAR) mechanism, we derive the $sqrtn$-convergence rate and normality of the estimated cluster centers.<n>These results provide a theoretical guarantee for missing-data-$k$-means.
• Score: 7.3226942109207895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• MNAR-$k$-means: A $k$-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability [7.3226942109207895]
  We propose a novel $k$-means clustering method based on the constraint of the size of imputation values.<n>We establish the statistical consistency of the estimated cluster centers of the proposed method to the true cluster centers of fully observed data.
  arXiv  Detail & Related papers  (2026-06-30T07:31:22Z)
• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  We introduce a new data selection framework based on low-rank approximation and residual-based sampling.<n>We show that it is possible to select a weighted subset of $tildeOleft(k + frac1varepsilon2right)$ data points whose average loss approximates the average loss over the full dataset.
  arXiv  Detail & Related papers  (2026-06-14T22:29:59Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  This paper focuses on generalization error, excess risk and consistency in ensemble clustering.<n>By assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation.<n>We instantiate our theory to develop a new ensemble clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-01T09:34:52Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
  We develop a family of distributed center-based clustering algorithms that work over networks of users. Our framework allows for a broad class of smooth convex loss functions, including popular clustering losses like $K$-means and Huber loss. For the special case of Bregman losses, we show that our fixed points converge to the set of Lloyd points.
  arXiv  Detail & Related papers  (2024-02-02T10:44:42Z)
• A provable initialization and robust clustering method for general mixture models [6.806940901668607]
  Clustering is a fundamental tool in statistical machine learning in the presence of heterogeneous data. Most recent results focus on optimal mislabeling guarantees when data are distributed around centroids with sub-Gaussian errors.
  arXiv  Detail & Related papers  (2024-01-10T22:56:44Z)
• Wasserstein $K$-means for clustering probability distributions [16.153709556346417]
  In the Euclidean space, centroid-based and distance-based formulations of the $K$-means are equivalent. In modern machine learning applications, data often arise as probability distributions and a natural generalization to handle measure-valued data is to use the optimal transport metric. We show that the SDP relaxed Wasserstein $K$-means can achieve exact recovery given the clusters are well-separated under the $2$-Wasserstein metric.
  arXiv  Detail & Related papers  (2022-09-14T23:43:16Z)
• No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds [17.226362076527764]
  Centroid based clustering methods such as k-means, k-medoids and k-centers are heavily applied as a go-to tool in exploratory data analysis. In many cases, those methods are used to obtain representative centroids of the data manifold for visualization or summarization of a dataset. We propose to remedy such a scenario by introducing a maximal radius constraint $r$ on the clusters formed by centroids.
  arXiv  Detail & Related papers  (2022-03-04T18:59:02Z)
• Distribution free optimality intervals for clustering [1.7513645771137178]
  Given data $mathcalD$ and a partition $mathcalC$ of these data into $K$ clusters, when can we say that the clusters obtained are correct or meaningful for the data? This paper introduces a paradigm in which a clustering $mathcalC$ is considered meaningful if it is good with respect to a loss function such as the K-means distortion, and stable, i.e. the only good clustering up to small perturbations.
  arXiv  Detail & Related papers  (2021-07-30T06:13:56Z)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  We show a continuous version of sum-of-norms clustering, where the dataset is replaced by a general measure. We state and prove a local-global characterization of the clustering that seems to be new even in the case of discrete datapoints.
  arXiv  Detail & Related papers  (2021-04-28T13:35:17Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.