Improved smoothed analysis of the k-means method

ABSTRACT

The k-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 [3] aimed at closing this gap, and they proved a bound of poly(n^k, σ⁻¹) on the smoothed running-time of the k-means method, where n is the number of data points and σ is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice.

We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in n^√k and σ⁻¹. Second, we prove an upper bound of k^kd·poly(n, σ⁻¹), where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for k, d ∈ O(√logn/log logn).

Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.

REFERENCES

• 1: David Arthur. Smoothed analysis of the k-means method. Manuscript, 2008.
• 2: David Arthur , Sergei Vassilvitskii, How slow is the k-means method?, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137880]
• 3: David Arthur , Sergei Vassilvitskii, Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.153-164, October 21-24, 2006 [doi>10.1109/FOCS.2006.79]
• 4: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 5: Pavel Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, USA, 2002.
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: Sariel Har-Peled , Bardia Sadri, How Fast Is the k-Means Method?, Algorithmica, v.41 n.3, p.185-202, January 2005 [doi>10.1007/s00453-004-1127-9]
• 8: Mary Inaba, Naoki Katoh, and Hiroshi Imai. Variance-based k-clustering algorithms by Voronoi diagrams and randomization. IEICE Transactions on Information and Systems, E83-D(6):1199--1206, 2000.
• 9: Amit Kumar , Yogish Sabharwal , Sandeep Sen, A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 10: Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129--137, 1982.
• 11: Jiří Matoušek. On approximate geometric k-clustering. Discrete and Computational Geometry, 24(1):61--84, 2000.
• 12: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
• 13: Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms and heuristics: Progress and open questions. In Luis M. Pardo, Allan Pinkus, Endre Süli, and Michael J. Todd, editors, Foundations of Computational Mathematics, Santander 2005, pages 274--342. Cambridge University Press, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms