Adaptive Initialization Method for K-Means Algorithm

Yang，Jie1; Wang，Yu Kai1; Yao，Xin2,3; Lin，Chin Teng1

2021-11-25

10.3389/frai.2021.740817

Frontiers in Artificial Intelligence   影响因子和分区

2624-8212

The K-means algorithm is a widely used clustering algorithm that offers simplicity and efficiency. However, the traditional K-means algorithm uses a random method to determine the initial cluster centers, which make clustering results prone to local optima and then result in worse clustering performance. In this research, we propose an adaptive initialization method for the K-means algorithm (AIMK) which can adapt to the various characteristics in different datasets and obtain better clustering performance with stable results. For larger or higher-dimensional datasets, we even leverage random sampling in AIMK (name as AIMK-RS) to reduce the time complexity. 22 real-world datasets were applied for performance comparisons. The experimental results show AIMK and AIMK-RS outperform the current initialization methods and several well-known clustering algorithms. Specifically, AIMK-RS can significantly reduce the time complexity to O (n). Moreover, we exploit AIMK to initialize K-medoids and spectral clustering, and better performance is also explored. The above results demonstrate superior performance and good scalability by AIMK or AIMK-RS. In the future, we would like to apply AIMK to more partition-based clustering algorithms to solve real-life practical problems.

adaptive clustering initial cluster centers initialization method k-means

ESCI

英语

其他

Australian Research Council (ARC)["DP180100656","DP210101093"] ; Australia Defence Innovation Hub[P18-650825] ; US Office of Naval Research Global[ONRG-NICOP-N62909-19-1-2058] ; AFOSR - DST Australian Autonomy Initiative[10134] ; NSW Defence Innovation Network["DINPP2019 S1-03/09","PP21-22.03.02"] ; NSW State Government of Australia["DINPP2019 S1-03/09","PP21-22.03.02"]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems

WOS:000751704800155

FRONTIERS MEDIA SA

2-s2.0-85120959965

Scopus

1.Computational Intelligence and Brain Computer Interface Lab,Australian Artificial Intelligence Institute,FEIT,University of Technology Sydney,Sydney,Australia
2.Shenzhen Key Laboratory of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China
3.CERCIA,School of Computer Science,University of Birmingham,Birmingham,United Kingdom

Yang，Jie,Wang，Yu Kai,Yao，Xin,et al. Adaptive Initialization Method for K-Means Algorithm[J]. Frontiers in Artificial Intelligence,2021,4.

Yang，Jie,Wang，Yu Kai,Yao，Xin,&Lin，Chin Teng.(2021).Adaptive Initialization Method for K-Means Algorithm.Frontiers in Artificial Intelligence,4.

Yang，Jie,et al."Adaptive Initialization Method for K-Means Algorithm".Frontiers in Artificial Intelligence 4(2021).