FLS: A New Local Search Algorithm for K-means with Smaller Search Space

Junyu Huang, Qilong Feng, Ziyun Huang, Jinhui Xu, Jianxin Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(k2), 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 Ω(nk), which is common in many datasets and k-means benchmarks, we prove that our proposed algorithm gives a (100 + ε)- 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
EditorsLuc De Raedt, Luc De Raedt
PublisherInternational Joint Conferences on Artificial Intelligence
Pages3092-3098
Number of pages7
ISBN (Electronic)9781956792003
StatePublished - 2022
Event31st International Joint Conference on Artificial Intelligence, IJCAI 2022 - Vienna, Austria
Duration: Jul 23 2022Jul 29 2022

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Country/TerritoryAustria
CityVienna
Period7/23/227/29/22

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'FLS: A New Local Search Algorithm for K-means with Smaller Search Space'. Together they form a unique fingerprint.

Cite this