Fast k-means with accurate bounds

James Newling, Francois Fleuret
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:936-944, 2016.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-newling16, title = {Fast k-means with accurate bounds}, author = {Newling, James and Fleuret, Francois}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {936--944}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/newling16.pdf}, url = {https://proceedings.mlr.press/v48/newling16.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Fast k-means with accurate bounds %A James Newling %A Francois Fleuret %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-newling16 %I PMLR %P 936--944 %U https://proceedings.mlr.press/v48/newling16.html %V 48 %X 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.
RIS
TY - CPAPER TI - Fast k-means with accurate bounds AU - James Newling AU - Francois Fleuret BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-newling16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 936 EP - 944 L1 - http://proceedings.mlr.press/v48/newling16.pdf UR - https://proceedings.mlr.press/v48/newling16.html AB - 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. ER -
APA
Newling, J. & Fleuret, F.. (2016). Fast k-means with accurate bounds. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:936-944 Available from https://proceedings.mlr.press/v48/newling16.html.

Related Material