MNAR-k-means: New clustering method tackles missing data bias with magnitude-decaying probability
A novel algorithm that corrects cluster center distortion when data is missing not at random.
Xin Guan's new paper presents MNAR-k-means, a novel clustering algorithm tailored for datasets where missingness correlates with data values—a scenario known as Missing Not at Random (MNAR). Classical k-means fails on incomplete data, and even natural extensions using mean imputation produce biased cluster centers when missing patterns depend on the actual values. The new method addresses this by assuming a magnitude-decaying MNAR mechanism: smaller absolute values are more likely to be missing. It introduces a constraint that caps imputation magnitudes, preventing the distortion seen in mean-based approaches.
Guan proves statistical consistency: as sample size grows, the estimated cluster centers converge to the true centers of fully observed data. Optimization is handled via an alternating minimization algorithm. Experiments on both synthetic and real-world missing datasets show that MNAR-k-means outperforms standard imputation-based clustering by reducing bias and improving cluster purity. This work is especially relevant for fields like healthcare, finance, and survey analysis, where missing data often follows MNAR patterns and accurate clustering is critical for downstream decisions.
- Addresses MNAR (Missing Not at Random) data where missingness depends on data values, unlike standard k-means extensions.
- Uses magnitude-decaying probability assumption: smaller absolute values are more likely missing, preventing cluster center distortion.
- Proves statistical consistency of cluster centers and reduces bias; validated with simulations and real-world datasets.
Why It Matters
Enables accurate clustering in real-world incomplete datasets where missingness is not random, improving ML pipelines in critical domains.