arXiv:2607.01945stat.MLcs.LG2026-07

揭示缺失数据下k均值聚类的统计性质,给出理论保证。

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

  • 分析缺失数据中k均值的渐近行为,建立风险界与一致性。
  • 在完全随机缺失下,估计中心达到√n收敛速度并服从渐近正态。
  • 指出高维下需各簇中心每维都不同,否则无法收敛到真中心。

经典k均值聚类无法直接用于不完整数据,现有方法多关注实际精度提升,缺乏渐近理论保障。本文研究缺失数据下的k均值聚类统计性质,首先在一般缺失机制下建立√n阶过风险界,并证明估计簇中心的一致性;针对完全随机缺失(MCAR)机制,进一步推导出估计中心的√n收敛速率和渐近正态性。我们还研究了不完整数据估计的簇中心何时收敛到原始完整数据的真实簇中心,给出了缺失概率与真实簇间分离度之间的充分条件。结果为缺失数据k均值提供了理论支持。值得注意的是,在MCAR机制下,要同时实现√n速率和收敛到真实中心,要求所有真实中心在每一维度上均不相同,凸显了高维应用的重大挑战。最后通过合成数据集的数值模拟验证了理论分析。

原文摘要 · Abstract (English)

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.

聚类缺失数据统计理论k均值

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。