@article{Qu2024, 
author = {Fuheng Qu and Yuhang Shi and Yong Yang and Yating Hu and Yuyao Liu},
title = {Coordinate Descent K-means Algorithm Based on Split-Merge},
year = {2024},
journal = {Computers, Materials & Continua},
volume = {81},
number = {3},
pages = {4875-4893},
keywords = {Cluster analysis, K-means, coordinate descent K-means, split-merge},
url = {https://www.sciopen.com/article/10.32604/cmc.2024.060090},
doi = {10.32604/cmc.2024.060090},
abstract = {The Coordinate Descent Method for K-means (CDKM) is an improved algorithm of K-means. It identifies better locally optimal solutions than the original K-means algorithm. That is, it achieves solutions that yield smaller objective function values than the K-means algorithm. However, CDKM is sensitive to initialization, which makes the K-means objective function values not small enough. Since selecting suitable initial centers is not always possible, this paper proposes a novel algorithm by modifying the process of CDKM. The proposed algorithm first obtains the partition matrix by CDKM and then optimizes the partition matrix by designing the split-merge criterion to reduce the objective function value further. The split-merge criterion can minimize the objective function value as much as possible while ensuring that the number of clusters remains unchanged. The algorithm avoids the distance calculation in the traditional K-means algorithm because all the operations are completed only using the partition matrix. Experiments on ten UCI datasets show that the solution accuracy of the proposed algorithm, measured by the E value, is improved by 11.29% compared with CDKM and retains its efficiency advantage for the high dimensional datasets. The proposed algorithm can find a better locally optimal solution in comparison to other tested K-means improved algorithms in less run time.}
}