{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:42:20Z","timestamp":1723016540428},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2022\/429","type":"proceedings-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T22:55:56Z","timestamp":1657925756000},"page":"3092-3098","source":"Crossref","is-referenced-by-count":0,"title":["FLS: A New Local Search Algorithm for K-means with Smaller Search Space"],"prefix":"10.24963","author":[{"given":"Junyu","family":"Huang","sequence":"first","affiliation":[{"name":"Central South University"}]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[{"name":"Central South University"}]},{"given":"Ziyun","family":"Huang","sequence":"additional","affiliation":[{"name":"Penn State Erie"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[{"name":"SUNY Buffalo"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"Central South University"},{"name":"The Hunan Provincial Key Lab of Bioinformatics"}]}],"member":"10584","event":{"number":"31","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2022","name":"Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}","start":{"date-parts":[[2022,7,23]]},"theme":"Artificial Intelligence","location":"Vienna, Austria","end":{"date-parts":[[2022,7,29]]}},"container-title":["Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T07:09:40Z","timestamp":1658128180000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2022\/429"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2022\/429","relation":{},"subject":[],"published":{"date-parts":[[2022,7]]}}}