k-Means has Polynomial Smoothed Complexity

Details k-Means has Polynomial Smoothed Complexity k-Means has Polynomial Smoothed Complexity

2009-04-07

arxiv.org/abs/0904.1113v2

Computer Science

Data Structures and Algorithms

Full version of FOCS 2009 paper. The argument has been improved and the restriction to at least three dimensions could be drop

Scientific paper

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/\sigma, where \sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

Affiliated with

Also associated with

No associations

Rating

k-Means has Polynomial Smoothed Complexity 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 k-Means has Polynomial Smoothed Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-Means has Polynomial Smoothed Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-314049