# An efficient k-means-type algorithm for clustering datasets with incomplete records

arXiv: https://arxiv.org/abs/1802.08363 · HTML: https://mlsanity.com/paper/1802.08363/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Fast model-based clustering of partial records](https://mlsanity.com/paper/2103.16336/) (2021)
- [MNAR-k-means: A k-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability](https://mlsanity.com/paper/2606.31253/) (2026)
- [Statistical Properties of k-means Clustering for Data Missing Completely at Random](https://mlsanity.com/paper/2607.01945/) (2026)

## Abstract (arXiv)

The k-means algorithm is arguably the most popular nonparametric clustering method but cannot generally be applied to datasets with incomplete records. The usual practice then is to either impute missing values under an assumed missing-completely-at-random mechanism or to ignore the incomplete records, and apply the algorithm on the resulting dataset. We develop an efficient version of the k-means algorithm that allows for clustering in the presence of incomplete records. Our extension is called km-means and reduces to the k-means algorithm when all records are complete. We also provide initialization strategies for our algorithm and methods to estimate the number of groups in the dataset. Illustrations and simulations demonstrate the efficacy of our approach in a variety of settings and patterns of missing data. Our methods are also applied to the analysis of activation images obtained from a functional Magnetic Resonance Imaging experiment.