Speeding up k-means by approximating Euclidean distances via block vectors

Thomas Bottesch, Thomas Bühler, Markus Kächele
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2578-2586, 2016.

Abstract

This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-bottesch16, title = {Speeding up k-means by approximating Euclidean distances via block vectors}, author = {Bottesch, Thomas and Bühler, Thomas and Kächele, Markus}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2578--2586}, 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/bottesch16.pdf}, url = {https://proceedings.mlr.press/v48/bottesch16.html}, abstract = {This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems.} }
Endnote
%0 Conference Paper %T Speeding up k-means by approximating Euclidean distances via block vectors %A Thomas Bottesch %A Thomas Bühler %A Markus Kächele %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-bottesch16 %I PMLR %P 2578--2586 %U https://proceedings.mlr.press/v48/bottesch16.html %V 48 %X This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems.
RIS
TY - CPAPER TI - Speeding up k-means by approximating Euclidean distances via block vectors AU - Thomas Bottesch AU - Thomas Bühler AU - Markus Kächele 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-bottesch16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2578 EP - 2586 L1 - http://proceedings.mlr.press/v48/bottesch16.pdf UR - https://proceedings.mlr.press/v48/bottesch16.html AB - This paper introduces a new method to approximate Euclidean distances between points using block vectors in combination with the Hölder inequality. By defining lower bounds based on the proposed approximation, cluster algorithms can be considerably accelerated without loss of quality. In extensive experiments, we show a considerable reduction in terms of computational time in comparison to standard methods and the recently proposed Yinyang k-means. Additionally we show that the memory consumption of the presented clustering algorithm does not depend on the number of clusters, which makes the approach suitable for large scale problems. ER -
APA
Bottesch, T., Bühler, T. & Kächele, M.. (2016). Speeding up k-means by approximating Euclidean distances via block vectors. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2578-2586 Available from https://proceedings.mlr.press/v48/bottesch16.html.

Related Material