Open Access

ARTICLE

Coordinate Descent K-means Algorithm Based on Split-Merge

by Fuheng Qu¹, Yuhang Shi¹, Yong Yang^1,*, Yating Hu², Yuyao Liu¹

1 College of Computer Science and Technology, Changchun University of Science and Technology, Changchun, 130022, China
2 College of Computer Science and Technology, Jilin Agricultural University, Changchun, 130118, China

* Corresponding Author: Yong Yang. Email:

(This article belongs to the Special Issue: Artificial Intelligence Algorithms and Applications)

Computers, Materials & Continua 2024, 81(3), 4875-4893. https://doi.org/10.32604/cmc.2024.060090

Received 23 October 2024; Accepted 20 November 2024; Issue published 19 December 2024

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.

---

Keywords

---