Proceedings

Exact Acceleration of K-Means++ and K-Means||

Edward Raff

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2928-2935.

https://doi.org/10.24963/ijcai.2021/403

Keywords

  • Data Mining: Clustering
  • Machine Learning: Clustering
  • Machine Learning Applications: Big data; Scalability

Abstract

K-Means++ and its distributed variant K-Means|| have become de facto tools for selecting the initial seeds of K-means. While alternatives have been developed, the effectiveness, ease of implementation,and theoretical grounding of the K-means++ and || methods have made them difficult to "best" from a holistic perspective. We focus on using triangle inequality based pruning methods to accelerate both of these algorithms to yield comparable or better run-time without sacrificing any of the benefits of these approaches. For both algorithms we are able to reduce distance computations by over 500×. For K-means++ this results in up to a 17×speedup in run-time and a551×speedup for K-means||. We achieve this with simple, but carefully chosen, modifications to known techniques which makes it easy to integrate our approach into existing implementations of these algorithms.

Edward Raff. 2021. Exact Acceleration of K-Means++ and K-Means||. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2928–2935. https://doi.org/10.24963/ijcai.2021/403
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards