Distributed random swap: An efficient algorithm for minimum sum-of-squares clustering
Kozbagarov O. Mussabayev R.
October 2024Elsevier Inc.
Information Sciences
2024#681
The clustering model known as Minimum Sum-of-Squares Clustering (MSSC) is widely used, with the popular k-means algorithm serving as its local minimizer. It is well-known that solutions of k-means can result in substantial deviations from the true global optimum of MSSC. While numerous heuristics and metaheuristics have been proposed to overcome this limitation, none have gained dominant acceptance in academic literature. This is likely related to challenges such as intricate implementations and a multitude of tunable parameters. In this paper, we dispute the belief that simplifying an algorithm for MSSC inherently means sacrificing quality. We present the Distributed Random Swap (DRS-means) algorithm, which is designed to enhance clustering performance for the MSSC problem. This algorithm can be interpreted as an iterative method that refines the solution generated by the k-means algorithm during each iteration. The enhancement is achieved by selecting points based on specific probability distributions. These distributions are carefully designed to improve and speed up the exploration phase. The proposed algorithm is straightforward to implement. DRS-means offers a user-friendly solution with state-of-the-art results, making it suitable for a wide range of research fields.
Clustering algorithm , Global optimization , k-Means , Local search , MSSC , Random swap , State-of-the-art
Text of the article Перейти на текст статьи
AI Research Lab, Satbayev University, Satbaev str., 22, Almaty, 050043, Kazakhstan
Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Pushkin str., 125, Almaty, 050010, Kazakhstan
AI Research Lab
Laboratory for Analysis and Modeling of Information Processes
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026