A survey on theory and algorithms for bm$k$-means problems

Zhang Dong-mei, Zhenning Zhang, Min Li, Dachuan XuScientia 2020 · DOI

Abstract

The $k$-means problem is one of the classical problems in theoretical computer science and combinatorial optimization. Meanwhile, the corresponding Lloyd algorithm is one of the ten classical algorithms in data mining. It has been studied in various fields and has a lot of applications, especially on image processing and feature engineering. With the explosive growth of data diversity and quantity, the $k$-means clustering in practical applications are more complex and diversified. A variety of challenging research topics have emerged that need to be solved urgently. The $k$-means problem is theoretically NP-hard. In this paper, we introduce effective algorithms based on local search, linear programming rounding, primal-dual, dual-fitting, Lagrange relaxation and other techniques for the classical $k$-means problem and its variants. We begin with the review of improving approximation algorithms for the classical $k$-means problem. Then we introduce effective polynomial-time approximation scheme in the doubling metric space and polynomial solvability of stable instances. We further survey several important variants of $k$-means problems including $k$-median, spherical $k$-means, robust $k$-means, constrained $k$-means, privacy preserving $k$-means, etc. Finally, we discuss some open problems for $k$-means problems.

Introduction

Clustering is a cornerstone of unsupervised learning, and $k$-means is its most prominent representative. The objective is to partition $n$ points into $k$ clusters to minimize the sum of squared distances to the cluster centers. Despite its conceptual simplicity, the problem is computationally challenging. This survey bridges the gap between the heuristic Lloyd’s algorithm and modern theoretical breakthroughs, exploring state-of-the-art approximation algorithms, complexity bounds, and specialized variants designed for robustness and privacy.

The $k$-means problem is known to be NP-hard even in two-dimensional space. As shown in Figure 5, the complexity varies significantly depending on the constraints placed on the dimension $d$ and the number of clusters $k$.

Complexity and approximation difficulty of the k-means problem under various constraints on dimension d and cluster count k.

Algorithmic Frameworks and Techniques

While practitioners often rely on the iterative Lloyd’s algorithm, it lacks theoretical guarantees on solution quality. Theoretical research has focused on designing algorithms with provable approximation ratios.

Beyond random starts, strategies like $k$-means++ and $D^2$ sampling provide an $O(\log k)$ approximation guarantee. More sophisticated approaches utilize Local Search, Linear Programming (LP) Rounding, Primal-Dual methods, and Lagrange Relaxation to achieve constant-factor approximation ratios.

Dimensionality Reduction and Coresets

For high-dimensional data, the Johnson-Lindenstrauss (JL) Lemma allows for projecting data into lower dimensions while preserving cluster structures. For massive datasets, coresets—small, weighted subsets of the original data—serve as efficient proxies. Solving $k$-means on a coreset yields a solution nearly as good as the full dataset at a fraction of the computational cost.

Key Results and State-of-the-Art

The theoretical landscape of $k$-means has advanced significantly, providing a variety of algorithms with different performance trade-offs.

Comparison of approximation ratios and running times for prominent k-means algorithms and initialization strategies.
  • Classic $k$-means: Polynomial Time Approximation Schemes (PTAS) exist if the dimension $d$ or the number of clusters $k$ is fixed.
  • Stability: If a dataset is "stable" (the optimal clustering is well-separated), the problem becomes solvable in polynomial time.
  • Robustness and Privacy: Modern variants can ignore outliers or operate under Differential Privacy constraints, ensuring individual data points do not compromise privacy while maintaining clustering utility.
  • Spherical $k$-means: Used extensively in text mining, these variants have achieved approximation ratios around 2.675.

Discussion and Future Directions

Despite significant progress, several open problems remain:

  1. Closing the Approximation Gap: A gap persists between theoretical lower bounds and the best-known upper bounds for approximation ratios.
  2. Efficiency in Specialized Variants: Spherical $k$-means and constrained clustering (e.g., "must-link" constraints) require more efficient, theoretically-backed algorithms.
  3. Scalability: Balancing communication costs and accuracy in distributed "Big Data" environments continues to be an active research area.

This survey underscores the transition of $k$-means from a simple heuristic to a deeply understood optimization problem with robust theoretical foundations.

Summary updated

Abstract

The $k$-means problem is one of the classical problems in theoretical computerscience and combinatorial optimization.Meanwhile, the corresponding Lloyd algorithm is one of the ten classical algorithms in data mining.It has been studied in various fields and has a lot of applications,especially on image processing and feature engineering.With the explosive growth of data diversity and quantity,the $k$-means clustering in practical applications are more complex and diversified.A variety of challenging research topics have emerged that need to be solved urgently.The $k$-means problem is theoretically NP-hard.In this paper, we introduce effective algorithms based on local search, linear programming rounding, primal-dual, dual-fitting, Lagrange relaxation and other techniquesfor the classical $k$-means problem and its variants.We begin with the review of improving approximation algorithms forthe classical $k$-means problem.Then we introduce effective polynomial-time approximation scheme in the doubling metric spaceand polynomial solvability of stable instances.We further survey several important variants of $k$-means problems including$k$-median, spherical $k$-means, robust $k$-means, constrained $k$-means,privacy preserving $k$-means, etc.Finally, we discuss some open problems for $k$-means problems.
BibTeX
@inproceedings{dongmei2020survey,
  author = {Zhang Dong-mei and Zhenning Zhang and Min Li and Dachuan Xu},
  title = {{A survey on theory and algorithms for bm$k$-means problems}},
  booktitle = {Scientia},
  year = {2020},
  doi = {10.1360/ssm-2019-0280},
}
Figure