Modified K-means Algorithm with Local Optimality Guarantees

2 Huawei Noah's Ark Lab 3 RIKEN AIP Summary & Contribution ▶ K-means is a classic, widely used clustering algorithm. ▶ We show by counterexample that K-means does not necessarily converge to a locally optimal solution, let alone a global one. LO-K-means (Our Algorithm) ▶ A simple modification to the K-means algorithm that ensures local optimality with no additional complexity. ▶ Analysis of two local-optimality criteria-continuous (C-local) and discrete (D-local)-shows experimentally that LO-K-means consistently improves clustering quality.