MNAR-$k$-means: A $k$-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability

• URL: http://arxiv.org/abs/2606.31253v1
• Date: Tue, 30 Jun 2026 07:31:22 GMT
• Title: MNAR-$k$-means: A $k$-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability
• Abstract summary: 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.
• Score: 7.3226942109207895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical $k$-means clustering, based on distances computed from all data features, cannot be directly applied to incomplete data with missing values. A natural extension of $k$-means to missing data is to involve only the observed positions in clustering, which is equivalent to imputing missing values by corresponding cluster means. However, for data missing not at random (MNAR), since missingness is related to data values, such a mean-imputation-based method may lead to the distortion of estimated cluster centers, resulting in a poor clustering result. Since MNAR mechanisms are very common in reality, it is necessary to improve the performance of $k$-means-based clustering methods for such data. In this paper, we focus on a magnitude-decaying MNAR scenario where data is more likely to be missing at positions with smaller absolute values, and we propose a novel $k$-means clustering method based on the constraint of the size of imputation values, which enjoys a good mathematical interpretation. Moreover, we establish the statistical consistency of the estimated cluster centers of the proposed method to the true cluster centers of fully observed data, and solve the optimization of the proposed loss function via an alternative minimization algorithm. Simulation experiments verify the effect of the proposed method in improving clustering results and reducing the bias of estimated cluster centers. Applications to real-world missing data further show the utility of the proposed method.

Related papers

• Statistical Properties of $k$-means Clustering for Data Missing Completely at Random [7.3226942109207895]
  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.
  arXiv  Detail & Related papers  (2026-07-02T09:34:44Z)
• 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)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-means is a novel clustering algorithm that eliminates the need to set k or any other parameters.<n>It uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters.<n>We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown.
  arXiv  Detail & Related papers  (2025-05-17T08:41:07Z)
• 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 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)
• Dirichlet Process-based Robust Clustering using the Median-of-Means Estimator [16.774378814288806]
  We propose an efficient and automatic clustering technique by integrating the strengths of model-based and centroid-based methodologies.<n>Our method mitigates the effect of noise on the quality of clustering; while at the same time, estimates the number of clusters.
  arXiv  Detail & Related papers  (2023-11-26T19:01:15Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• 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)
• 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)
• Too Much Information Kills Information: A Clustering Perspective [6.375668163098171]
  We propose a simple, but novel approach for variance-based k-clustering tasks, including in which is the widely known k-means clustering. The proposed approach picks a sampling subset from the given dataset and makes decisions based on the data information in the subset only. With certain assumptions, the resulting clustering is provably good to estimate the optimum of the variance-based objective with high probability.
  arXiv  Detail & Related papers  (2020-09-16T01:54:26Z)
• Decorrelated Clustering with Data Selection Bias [55.91842043124102]
  We propose a novel Decorrelation regularized K-Means algorithm (DCKM) for clustering with data selection bias. Our DCKM algorithm achieves significant performance gains, indicating the necessity of removing unexpected feature correlations induced by selection bias.
  arXiv  Detail & Related papers  (2020-06-29T08:55:50Z)

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.