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$.
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.
Initialization and Local Search
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.
- 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:
- Closing the Approximation Gap: A gap persists between theoretical lower bounds and the best-known upper bounds for approximation ratios.
- Efficiency in Specialized Variants: Spherical $k$-means and constrained clustering (e.g., "must-link" constraints) require more efficient, theoretically-backed algorithms.
- 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