A Better k-means++ Algorithm via Local Search

Silvio Lattanzi, Christian SohlerICML 2019 · OpenReview

Overview

This paper introduces LS++, a simple yet powerful refinement to the industry-standard $k$-means++ seeding algorithm. By adding a local search phase—where cluster centers are iteratively swapped with new points sampled from the data—the authors prove the algorithm achieves a constant approximation guarantee in expectation. This overcomes the theoretical $O(\log k)$ limitation of standard $k$-means++ while remaining fast and practical for real-world applications.

The Challenge of Initialization in $k$-means

Clustering is a fundamental task in unsupervised learning, and the $k$-means problem is its most famous formulation. While the goal is simple—minimize the sum of squared distances between points and their nearest centers—the problem is NP-hard.

In practice, most practitioners rely on Lloyd’s algorithm, which starts with an initial set of centers and iteratively refines them. However, Lloyd’s algorithm is notoriously sensitive to its starting point. To address this, researchers developed $k$-means++, a "seeding" method that chooses initial centers one by one using a specific probability distribution ($D^2$ sampling).

While $k$-means++ is widely used and performs well empirically, it only guarantees a solution within an $O(\log k)$ factor of the optimum. Theoretical "constant factor" algorithms exist, but they are often too slow or complex for real-world use. The authors sought a method that is as simple and fast as $k$-means++ but backed by the theoretical rigor of a constant approximation.

The LS++ Algorithm

The authors propose a two-stage algorithm called LS++ (Local Search++):

  1. Standard Seeding: Run the classic $k$-means++ algorithm to select an initial set of $k$ centers.
  2. Local Search Phase: Perform $O(k \log \log k)$ additional rounds of refinement. In each round:
  3. Sample a new candidate point $p$ from the dataset with probability proportional to its current contribution to the total cost (the same $D^2$ sampling used in $k$-means++).
  4. Check if swapping $p$ with any of the $k$ existing centers reduces the total clustering cost.
  5. If a swap exists that improves the cost, perform the swap that yields the largest reduction. Otherwise, discard $p$ and keep the current centers.

The "magic" of LS++ lies in the combination of $D^2$ sampling with local search. Standard local search often struggles because it is computationally expensive to find the "right" point to swap in. By using $D^2$ sampling, the algorithm naturally picks candidate points from regions that are currently poorly served by the existing centers.

Empirical Evaluation and Results

The researchers evaluated their algorithm on three large-scale, high-dimensional datasets where efficient clustering is critical:

  • RNA: 488,565 samples with 8 features (biological sequence data).
  • KDD-BIO: 145,751 samples with 74 features (protein matching data).
  • KDD-PHY: 100,000 samples with 78 features (quantum physics task data).
Relative cost of LS++ vs. standard k-means++ over 25 iterations across multiple datasets and k values.

The empirical results strongly support the theoretical claims:

  • Empirical Quality: Compared to standard $k$-means++ seeding, LS++ reduced the clustering cost by 8% to 35%.
  • Post-Lloyd's Performance: Even when both algorithms were followed by 10 steps of Lloyd’s algorithm (the standard industry practice), the LS++ starting points still led to final solutions that were 1% to 18% better than those initialized with standard $k$-means++.
  • Stability: As shown in the figure above, the performance gains were consistent across different values of $k$ (tested at $k=25$ and $k=50$) and across all three diverse datasets.

Key Insights

  • Bridging Theory and Practice: The most significant insight is that a very small amount of local search—specifically $O(k \log \log k)$ rounds—is sufficient to jump from a logarithmic approximation to a constant one.
  • The Power of $D^2$ Sampling for Swaps: Traditional local search algorithms for $k$-means are notoriously slow because they might need to check many potential swaps. By using the $k$-means++ sampling distribution, the algorithm "guesses" better candidate points, drastically reducing the number of iterations needed.
  • Efficiency: The authors note that running 25 iterations of their local search is actually faster than a single iteration of Lloyd’s algorithm, making it a computationally "cheap" way to secure a vastly superior starting point.

Limitations and Future Directions

The primary limitation acknowledged by the authors is the theoretical constant. To formally prove the guarantee, the math requires $100,000k \log \log k$ iterations. However, in practice, the authors observed significant improvements after just a few dozen iterations, suggesting the theoretical bound is highly pessimistic.

Future work includes:

  • Tightening the Analysis: Can the field prove a constant approximation with only $O(k)$ steps?
  • Parallelization: Exploring how this local search strategy could be adapted for parallel settings, such as $k$-means||.
  • Dimensionality: While the algorithm is efficient, the cost of calculating swaps still scales with the number of centers and dimensions. Further optimizations for extremely high-dimensional data remain an open area for exploration.

Summary updated

Abstract

In this paper, we develop a new variant of k-means++ seeding that in expectation achieves a constant approximation guarantee. We obtain this result by a simple combination of k-means++ sampling wit...
BibTeX
@inproceedings{lattanzi2019better,
  author = {Silvio Lattanzi and Christian Sohler},
  title = {{A Better k-means++ Algorithm via Local Search}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=rybCEh-_Wr},
}
Figure