CONF Newling_FASTK-MEANSWITHACCURATEBOUNDS_2016/IDIAP Fast K-Means with Accurate Bounds Newling, James Fleuret, Francois http://publications.idiap.ch/index.php/publications/showcite/Newling_Idiap-RR-17-2016 Related documents Proceedings of the International Conference on Machine Learning (ICML) New York 2016 REPORT Newling_Idiap-RR-17-2016/IDIAP Fast K-Means with Accurate Bounds Newling, James Fleuret, Francois accelerated exact k-means Annulus clustering Elkan exact k-means Exponion Hamerly K-means Yinyany EXTERNAL http://publications.idiap.ch/attachments/reports/2015/Newling_Idiap-RR-17-2016.pdf PUBLIC Idiap-RR-17-2016 2016 Idiap June 2016 We propose a novel accelerated exact $k$-means algorithm, which outperforms the current state-of-the-art low-dimensional algorithm in 18 of 22 experiments, running up to 3$\times$ faster. We also propose a general improvement of existing state-of-the-art accelerated exact $k$-means algorithms through better estimates of the distance bounds used to reduce the number of distance calculations, obtaining speedups in 36 of 44 experiments, of up to 1.8$\times$. We have conducted experiments with our own implementations of existing methods to ensure homogeneous evaluation of performance, and we show that our implementations perform as well or better than existing available implementations. Finally, we propose simplified variants of standard approaches and show that they are faster than their fully-fledged counterparts in 59 of 62 experiments.