k-POD: A Method for k-Means Clustering of Missing Data

Abstract

The k-means algorithm is often used in clustering applications but its usage requires a complete data matrix. Missing data, however, are common in many applications. Mainstream approaches to clustering missing data reduce the missing data problem to a complete data formulation through either deletion or imputation but these solutions may incur significant costs. Our k-POD method presents a simple extension of k-means clustering for missing data that works even when the missingness mechanism is unknown, when external information is unavailable, and when there is significant missingness in the data.

[Received November 2014. Revised August 2015.]

• Clustering
• k-means
• Imputation
• Majorization-minimization
• Missing data.

Additional information

Notes on contributors

Jocelyn T. Chi

Jocelyn T. Chi is Ph.D. Student (E-mail: [email protected])

Eric C. Chi

and Eric C. Chi is Assistant Professor (E-mail: [email protected]), Department of Statistics, North Carolina State University, Raleigh, NC 27695.

Richard G. Baraniuk

Richard G. Baraniuk is Professor, Department of Electrical and Computer Engineering, Rice University, Houston TX 77005 (E-mail: [email protected]). This material is based upon work supported by, or in part by, the U. S. Army Research Laboratory and the U. S. Army Research Office under contract/grant number ARO MURI W911NF0910383.