CONF
Newling_FASTK-MEANSWITHACCURATEBOUNDS_2016/IDIAP
Fast K-Means with Accurate Bounds
Newling, James
Fleuret, Francois
https://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
https://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.