An Extensive Empirical Comparison of k-means Initialization Algorithms

The k-means clustering algorithm, whilst widely popular, is not without its drawbacks. In this paper, we focus on the sensitivity of k-means to its initial set of centroids. Since the cluster recovery performance of k-means can be improved by better initialisation, numerous algorithms have been proposed aiming at producing good initial centroids. However, it is still unclear which algorithm should be used in any particular clustering scenario. With this in mind, we compare 17 such algorithms on 6,000 synthetic and 28 real-world data sets. The synthetic data sets were produced under different configurations, allowing us to show which algorithm excels in each scenario. Hence, the results of our experiments can be particularly useful for those considering k-means for a non-trivial clustering scenario.

Automated summary

This paper compares the performance of 17 different algorithms on 6,000 synthetic and 28 real-world data sets to investigate the sensitivity of k-means to its initial centroids. The results show that different algorithms may excel in different clustering scenarios, providing valuable insights for those considering k-means for complex clustering tasks.