A fast k-means implementation using coresets

ABSTRACT

In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004 [doi>10.1145/1008731.1008736]
• 2: P. Agarwal, S. Har-Peled, and K. Varadarajan. Geometric Approximation via Coresets. Survey available at http://valis.cs.uiuc.edu/sariel/research/papers/04/survey/survey.pdf
• 3: K. Alsabti, S. Ranka, and V. Singh. An Efficient k-Means Clustering Algorithm. Proceedings of the first Workshop on High Performance Data Mining, 1998.
• 4: Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: 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]
• 6: P. Berkhin. Survey of Clustering Data Mining Techniques. Available at ..., 2002.
• 7: Timothy M. Chan, Faster core-set constructions and data stream algorithms in fixed dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997843]
• 8: A.Czumaj and C. Sohler. Sublinear-Time Approximation for Clustering via Random Sampling. Proceedings of the 31st Annual International Colloquium on Autonate, Languages and Programming (ICALP'04), pp. 396--407, 2004.
• 9: W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780550]
• 10: E. Forgey. Cluster Analysis of Multivariate Data: Efficiency vs. Interpretability of Classification. Biometrics, 21:768, 1965.
• 11: Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060622]
• 12: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 13: Sariel Har-Peled, Clustering Motion, Discrete & Computational Geometry, v.31 n.4, p.545-565, March 2004 [doi>10.1007/s00454-004-2822-7]
• 14: Sariel Har-Peled , Akash Kushal, Smaller coresets for k-median and k-means clustering, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064114]
• 15: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 16: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 17: Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
• 18: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 19: Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002 [doi>10.1109/TPAMI.2002.1017616]
• 20: Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, A local search approximation algorithm for k-means clustering, Proceedings of the eighteenth annual symposium on Computational geometry, p.10-18, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513402]
• 21: D. Knuth. The Art of Computer Programming: Sorting and Searching, Vol. 3, Addison-Wesley, 1973.
• 22: 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 (FOCS'04), p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 23: S. Lloyd. Least Squares Quantization in PCM. IEEE Transactions on Information Theory, 28: 129--137, 1982.
• 24: J. Matoušek. On approximate geometric k-clustering. Discrete & Computational Geometry, 24(1): 61--84, 2000.
• 25: J. MacQueen. Some Methods for Classification and Analysis of Multivariate Observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pp. 281--296, 1967.
• 26: Ramgopal R. Mettu , C. Greg Plaxton, Optimal Time Bounds for Approximate Clustering, Machine Learning, v.56 n.1-3, p.35-60 [doi>10.1023/B:MACH.0000033114.18632.e0]
• 27: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
• 28: D. Mount. KMlocal: A Testbed for k-means Clustering Algorithms. Available at http://www.cs.umd.edu/ mount/Projects/KMeans/km-localdoc.pdf
• 29: Dan Pelleg , Andrew Moore, Accelerating exact k-means algorithms with geometric reasoning, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.277-281, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312248]
• 30: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 31: Steven J. Phillips, Acceleration of K-Means and Related Clustering Algorithms, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.166-177, January 04-05, 2002
• 32: S. Selim and M. Ismail. k-Means-Type Algorithms: A Generalized Convergence Theorem and Characterizations of Local Optimality. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6::81--87, 1984.
• 33: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: A New Data Clustering Algorithm and Its Applications, Data Mining and Knowledge Discovery, v.1 n.2, p.141-182, 1997 [doi>10.1023/A:1009783824328]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
Lloyds algorithm, clustering, coresets, k-means