Scalable K-Means++

Details Scalable K-Means++ Scalable K-Means++

2012-03-29

arxiv.org/abs/1203.6402v1

Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 7, pp. 622-633 (2012)

Computer Science

Databases

VLDB2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Scalable K-Means++ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scalable K-Means++, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable K-Means++ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56949