Improved smoothed analysis of the -means method
Manthey, Bodo and Röglin, Heiko (2009) Improved smoothed analysis of the -means method. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, 4-6 Jan 2009, New York, NY, USA (pp. pp. 461-470).
|Abstract:||The -means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii aimed at closing this gap, and they proved a bound of poly() on the smoothed runningtime of the -means method, where is the number of data points and is the standard deviation of the Gaussian perturbation. This bound, though better than the worstcase bound, is still much larger than the running-time observed in practice.
We improve the smoothed analysis of the -means method by showing two upper bounds on the expected running-time of -means. First, we prove that the expected running-time is bounded by a polynomial in and Second, we prove an upper bound of poly(), where is the dimension of the data space. The polynomial is independent of and , and we obtain a polynomial bound for the expected running-time for
Finally, we show that -means runs in smoothed polynomial time for one-dimensional instances.
|Item Type:||Conference or Workshop Item|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/68852|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page