LSDS++ : Dual Sampling for Accelerated k-means++

Chenglin Fan, Ping Li, Xiaoyun Li
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:9640-9649, 2023.

Abstract

k-means clustering is an important problem in machine learning and statistics. The k-means++ initialization algorithm has driven new acceleration strategies and theoretical analysis for solving the k-means clustering problem. The state-of-the-art variant, called LocalSearch++, adds extra local search steps upon k-means++ to achieve constant approximation error in expectation. In this paper, we propose a new variant named LSDS++, which improves the sampling efficiency of LocalSearch++ via a strategy called dual sampling. By defining a new capture graph based on the concept of coreset, we show that the proposed LSDS++ is able to achieve the same expected constant error with reduced complexity. Experiments are conducted to justify the benefit of LSDS++ in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-fan23c, title = {{LSDS}++ : Dual Sampling for Accelerated k-means++}, author = {Fan, Chenglin and Li, Ping and Li, Xiaoyun}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {9640--9649}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/fan23c/fan23c.pdf}, url = {https://proceedings.mlr.press/v202/fan23c.html}, abstract = {k-means clustering is an important problem in machine learning and statistics. The k-means++ initialization algorithm has driven new acceleration strategies and theoretical analysis for solving the k-means clustering problem. The state-of-the-art variant, called LocalSearch++, adds extra local search steps upon k-means++ to achieve constant approximation error in expectation. In this paper, we propose a new variant named LSDS++, which improves the sampling efficiency of LocalSearch++ via a strategy called dual sampling. By defining a new capture graph based on the concept of coreset, we show that the proposed LSDS++ is able to achieve the same expected constant error with reduced complexity. Experiments are conducted to justify the benefit of LSDS++ in practice.} }
Endnote
%0 Conference Paper %T LSDS++ : Dual Sampling for Accelerated k-means++ %A Chenglin Fan %A Ping Li %A Xiaoyun Li %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-fan23c %I PMLR %P 9640--9649 %U https://proceedings.mlr.press/v202/fan23c.html %V 202 %X k-means clustering is an important problem in machine learning and statistics. The k-means++ initialization algorithm has driven new acceleration strategies and theoretical analysis for solving the k-means clustering problem. The state-of-the-art variant, called LocalSearch++, adds extra local search steps upon k-means++ to achieve constant approximation error in expectation. In this paper, we propose a new variant named LSDS++, which improves the sampling efficiency of LocalSearch++ via a strategy called dual sampling. By defining a new capture graph based on the concept of coreset, we show that the proposed LSDS++ is able to achieve the same expected constant error with reduced complexity. Experiments are conducted to justify the benefit of LSDS++ in practice.
APA
Fan, C., Li, P. & Li, X.. (2023). LSDS++ : Dual Sampling for Accelerated k-means++. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:9640-9649 Available from https://proceedings.mlr.press/v202/fan23c.html.

Related Material