FLS: A New Local Search Algorithm for K-Means with Smaller Search Space
Abstract
The k-means problem is an extensively studied unsupervised learning problem with various applications in decision making and data mining. In this paper, we propose a fast and practical local search algorithm for the k-means problem. Our method reduces the search space of swap pairs from O(nk) to O(k^2), and applies random mutations to find potentially better solutions when local search falls into poor local optimum. With the assumption of data distribution that each optimal cluster has "average" size of \Omega(n/k), which is common in many datasets and k-means benchmarks, we prove that our proposed algorithm gives a (100+\epsilon)-approximate solution in expectation. Empirical experiments show that our algorithm achieves better performance compared to existing state-of-the-art local search methods on k-means benchmarks and large datasets.
Cite
Text
Huang et al. "FLS: A New Local Search Algorithm for K-Means with Smaller Search Space." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/429Markdown
[Huang et al. "FLS: A New Local Search Algorithm for K-Means with Smaller Search Space." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/huang2022ijcai-fls/) doi:10.24963/IJCAI.2022/429BibTeX
@inproceedings{huang2022ijcai-fls,
title = {{FLS: A New Local Search Algorithm for K-Means with Smaller Search Space}},
author = {Huang, Junyu and Feng, Qilong and Huang, Ziyun and Xu, Jinhui and Wang, Jianxin},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {3092-3098},
doi = {10.24963/IJCAI.2022/429},
url = {https://mlanthology.org/ijcai/2022/huang2022ijcai-fls/}
}