PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable K-Means++

Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii

arXiv:1203.6402v1cs.DB

TL;DR

The paper addresses the sequential, k-pass bottleneck of k-means++ initialization for massive datasets. It introduces k-means||, which samples multiple centers in parallel rounds and reclusters them before Lloyd’s iteration. The method has a constant-factor approximation guarantee and performs well empirically, with a constant number of rounds often sufficient.

  • Problem

    k-means++ provides strong initialization but is inherently sequential and requires k passes, limiting its use on massive datasets.

  • Method

    k-means|| samples O(k) points per round for approximately O(log n) rounds, then reclusters the selected O(k log n) points into k initial centers.

  • Results

    k-means|| achieves a constant-factor approximation and, after as few as five rounds, is consistently as good as or better than other evaluated methods while running much faster in parallel.

  • Takeaways & Limitations

    Parallel initialization can retain k-means++-style quality while substantially reducing the passes needed for large-scale k-means.

  • Takeaways & Limitations

    The paper leaves efficient parallelization of application-specific modifications to k-means as an open question.

Abstract

from arXiv · show

Over half a century old and showing no signs of aging, k-means remains one of the most popular data processing algorithms. As is well-known, a proper initialization of k-means is crucial for obtaining a good final solution. The recently proposed k-means++ initialization algorithm achieves this, obtaining an initial set of centers that is provably close to the optimum solution. A major downside of the k-means++ is its inherent sequential nature, which limits its applicability to massive data: one must make k passes over the data to find a good initial set of centers. In this work we show how to drastically reduce the number of passes needed to obtain, in parallel, a good initialization. This is unlike prevailing efforts on parallelizing k-means that have mostly focused on the post-initialization phases of k-means. We prove that our proposed initialization algorithm k-means|| obtains a nearly optimal solution after a logarithmic number of passes, and then show that in practice a constant number of passes suffices. Experimental evaluation on real-world large-scale data demonstrates that k-means|| outperforms k-means++ in both sequential and parallel settings.

1. INTRODUCTION

K-means remains popular, but solution quality depends strongly on initialization. The paper introduces k-means||, a parallel alternative to sequential k-means++ that achieves strong quality with far fewer passes.

  • Motivation: K-means is popular and scales relatively easily because assignments and centroid averaging can be performed independently across points.Its iterative Lloyd’s procedure repeatedly assigns points to their nearest centers and recomputes centers.
  • Motivation: Initialization substantially affects k-means solution quality and Lloyd’s convergence, motivating improved initialization procedures.Even locally optimal k-means solutions can be far from globally optimal, while better starting points improve practical performance.
  • Motivation: k-means++ provides strong approximation guarantees, but its sequential center selection requires k passes over the data.Each selection depends on the previously selected centers, preventing straightforward parallelization.
  • Motivation: Massive-data settings amplify k-means++’s slowdown, especially when clustering millions of points with large k values.The need for efficient initialization is particularly important when Lloyd’s iterations themselves run in parallel environments such as MapReduce.
  • Our contributions: k-means|| samples O(k) points per round for approximately O(log n) rounds, then reclusters O(k log n) points into k initial centers.This design is intended to preserve approximation quality while enabling parallel implementation.
  • Our contributions: After as few as five rounds, k-means|| is consistently as good as or better than other evaluated methods, while its parallel implementation is much faster.It also yields the smallest number of Lloyd’s iterations until convergence among the reported initialization methods.

2. RELATED WORK

Related work spans scalable database, parallel, streaming, and theoretical approaches to clustering. This paper builds on approximation-oriented initialization, especially k-means++, while targeting parallel scalability.

  • Database and scalable methods: Prior database research addressed disk-based, SQL, compressed, and single-pass implementations of k-means for scalable data processing.These efforts adapted k-means to relational systems or reduced data-processing requirements.
  • Parallel methods: Parallel k-means research studied message-passing implementations, speedup, scalability, and MapReduce techniques for related clustering procedures.The literature also includes work on outliers and EM, a generalization of k-means, in distributed settings.
  • Theoretical methods: Theoretical approaches include local-search algorithms with constant-factor approximations and methods with near-optimal approximation but exponential dependence on parameters.Some theoretically strong methods exhibit slow practical convergence or unfavorable worst-case complexity.
  • Initialization and streaming: k-means++ achieves an O(log k)-approximation without assumptions on the data, while related work obtains O(1)-approximations under additional conditions.Streaming extensions select O(k log k) points in one pass and achieve a constant-factor approximation in expectation.
  • Parallel model: MapReduce became a standard large-data analysis model, and the paper uses it to demonstrate k-means|| while requiring only primitive parallel operations.The stated implementation model is not the only setting in which the algorithm can be realized.

3. THE ALGORITHM

k-means|| parallelizes k-means++ by oversampling multiple centers per round, then reclustering them into k centers for Lloyd’s iteration. Its analysis gives approximation guarantees after logarithmically many rounds, while practice needs only a few rounds.

  • Background: k-means++ sequentially selects centers one at a time, making each selection depend on previous centers and requiring k data passes.This dependence limits direct parallelization.
  • k-means||: k-means|| samples O(k) points per round for approximately O(log n) rounds, producing O(k log n) candidate centers before reclustering.The candidate set is then reduced to k initial centers for Lloyd’s iteration.
  • k-means||: The algorithm uses an oversampling factor ℓ = Ω(k), samples points independently according to their squared distance from the current centers, and assigns weights before reclustering.The expected number of sampled points per iteration is ℓ.
  • Guarantees: If Step 8 uses an α-approximation algorithm, k-means|| obtains an O(α)-approximation to k-means.Using k-means++ for reclustering therefore yields an O(log k)-approximation.
  • Analysis: Each round removes a fraction of every optimal cluster’s current cost, so O(log ψ) rounds yield a constant-factor approximation with O(ℓ log ψ) centers.In practice, experimental results show that only a few rounds suffice.
  • Implementation: The MapReduce implementation assumes the center set C is small enough to fit in memory or be distributed among the mappers.The paper notes that this assumption covers nearly all practical settings and describes a possible implementation without it.

4. EXPERIMENTAL SETUP

The evaluation compares k-means|| with k-means++, Random, and Partition across synthetic and real-world datasets in sequential and parallel settings. It varies cluster counts and k-means|| parameters, using Lloyd’s iterations after initialization and reporting seed and final costs.

  • Experimental setup: The parallel experiments run on a Hadoop cluster of 1968 nodes, while sequential algorithms run on a quad-core workstation with 16GB of memory.The setup is designed to compare sequential and parallel implementations.
  • Datasets: The evaluation uses GaussMixture, Spam, and KDDCup1999, including a 4.8M-point dataset for large-scale parallel testing.GaussMixture is synthetic with n = 10,000; Spam has 4,601 points in 58 dimensions.
  • Datasets: GaussMixture and Spam use k ∈ {20, 50, 100}, while KDDCup1999 uses k ∈ {500, 1000}.The first two datasets use the sequential implementation, whereas KDDCup1999 uses Hadoop in parallel.
  • Baselines: The baselines are k-means++, Random, and Partition, with k-means++ treated as the true baseline because k-means|| is its natural parallelization.Partition is a one-pass streaming algorithm with performance guarantees and parallelizability.
  • Parameters: k-means|| is tested with ℓ ∈ {0.1k, 0.5k, k, 2k, 10k}, using 15 rounds for ℓ = 0.1k and 5 rounds otherwise.These settings produce an expected intermediate set between 1.5k and 40k points.
  • Metrics: Table 1 reports median GaussMixture costs over 11 runs, separately for initialization seeds and final solutions after Lloyd’s iterations.Costs are scaled down by 10^4.
  • Results: The initialization cost of k-means|| is typically lower than that of k-means++, and its running time improves linearly with the number of available machines.The intermediate set returned by k-means|| is smaller by three orders of magnitude in Table 5.

5. EXPERIMENTAL RESULTS

Experiments show that k-means|| achieves clustering quality comparable to k-means++ while reducing parallel running time through fewer rounds and fewer intermediate centers. It also typically accelerates Lloyd’s convergence, with a practical quality–rounds trade-off.

  • Clustering cost: k-means|| achieves clustering costs on par with k-means++ and outperforms Random by orders of magnitude on KDDCup1999.For larger ℓ, its overall cost surpasses Partition when ℓ > k.
  • Running time: k-means|| runs much faster than Random and Partition across the tested parallel settings.Its initialization time depends on both data passes and intermediate-solution size.
  • Running time: 10–40% as many intermediate centers as Partition typically suffices for k-means||, directly translating into faster running time without sacrificing solution quality.Table 5 compares the number of centers selected before reclustering on KDDCup1999.
  • Running time: k-means|| typically requires fewer Lloyd’s iterations than k-means++ and both converge significantly faster than Random.The comparison measures iterations required to reach a local optimum.
  • Trading-off quality with running time: r ≈ 8 is the experimentally observed sweet spot, while oversampling is beneficial for r ≤ 8.With ℓ = k, final clustering cost decreases monotonically as the number of rounds increases; larger ℓ improves solutions, but the benefit diminishes with more rounds.
  • Trading-off quality with running time: When r·ℓ ≥ k, k-means|| finds an initial set as good as k-means++ on GaussMixture and Spam; below that threshold, quality is substantially worse.At least k/ℓ rounds are needed to avoid risking fewer than k initial centers.

6. ANALYSIS

The analysis proves that each round significantly reduces the current cost, establishing the key step toward k-means||'s approximation guarantee. Experiments examine how initialization rounds and sampling affect final clustering cost.

  • Theoretical analysis: Each round reduces the current solution cost by a constant factor plus O(φ*).The paper identifies this per-round decrease as the key technical step in the analysis.
  • Empirical evaluation: The experiments vary ℓ and the number of rounds r, measuring final cost on a 10% sample of KDDCup1999.Each plotted data point is the median of 11 algorithm runs.
  • Empirical evaluation: When r·ℓ < k, the final solution is substantially worse than k-means++; when r·ℓ ≥ k, initialization is comparably good.This comparison is reported for GaussMixture and Spam as the number of initialization rounds changes.
  • Theoretical analysis: The proof analyzes the expected cost of an optimal cluster after one sampling round.The analysis introduces an LP and its dual to upper-bound this expected potential.
  • Theoretical analysis: The dual analysis uses the increasing sequence of sampling-related values to characterize an optimal dual solution.Specifically, the dual variables satisfy α_t = s_{t+1} − s_t.

7. CONCLUSIONS

The paper presents k-means|| as an efficient parallel version of k-means++, with a constant-factor approximation and scalability demonstrated on large real-world datasets. It also identifies parallelizing application-specific k-means modifications as an open direction.

  • Conclusions: k-means|| is an efficient parallel version of the inherently sequential k-means++ initialization algorithm.The algorithm is described as simple, embarrassingly parallel, and realizable in any parallel computational model.
  • Conclusions: k-means|| achieves a constant-factor approximation to the optimum.The conclusion presents this guarantee alongside the algorithm's parallel design.
  • Conclusions: Parallelizing modifications of basic k-means for specific applications remains an open direction.The paper states that it would be interesting to determine whether these modifications can also be efficiently parallelized.
Loading 1203.6402v1…