Search papers, labs, and topics across Lattice.
This paper investigates the statistical properties of $k$-means clustering when applied to datasets with missing values, specifically under the Missing Completely at Random (MCAR) mechanism. The authors establish a $\sqrt{n}$-excess risk bound and prove the consistency of estimated cluster centers, providing a theoretical foundation for the method's performance in the presence of missing data. Key findings indicate that achieving the $\sqrt{n}$-rate and convergence to true cluster centers requires distinct true centers across all dimensions, underscoring the challenges in high-dimensional contexts.
Under the MCAR mechanism, $k$-means clustering can achieve theoretical guarantees, but only if true centers are distinct in every dimension鈥攁 significant hurdle in high-dimensional data.
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.
