Improved k-means clustering algorithm and its applications

被引：2

作者：

Qi H. ^{[1
,2
]}

Li J. ^{[2
]}

Di X. ^{[1
,2
]}

Ren W. ^{[1
,2
]}

Zhang F. ^{[3
]}

机构：

[1] National and Local Joint Engineering Research Center of Space and Optoelectronics Technology, Changchun University of Science and Technology, Changchun

[2] School of Computer Science and Technology, Changchun University of Science and Technology, Changchun

[3] Northeast Normal University, Changchun

来源：

Recent Patents on Engineering | 2019年 / 13卷 / 04期

基金：

中国国家社会科学基金;

关键词：

Algorithm; Applications; Clustering; GPS; K-means; Network attack detection;

D O I：

10.2174/1872212113666181203110611

中图分类号：

学科分类号：

摘要：

Background: K-means algorithm is implemented through two steps: initialization and subsequent iterations. Initialization is to select the initial cluster center, while subsequent iterations are to continuously change the cluster center until it won't change any more or the number of iterations reaches its maximum. K-means algorithm is so sensitive to the cluster center selected during initialization that the selection of a different initial cluster center will influence the algorithm performance. Therefore, improving the initialization process has become an important means of K-means performance improvement. Methods: This paper uses a new strategy to select the initial cluster center. It first calculates the minimum and maximum values of the data in a certain index (For lower-dimensional data, such as two-dimensional data, features with larger variance, or the distance to the origin can be selected; for higher-dimensional data, PCA can be used to select the principal component with the largest vari-ance), and then divides the range into equally-sized sub-ranges. Next adjust the sub-ranges based on the data distribution so that each sub-range contains as much data as possible. Finally, the mean value of the data in each sub-range is calculated and used as the initial clustering center. Results: The theoretical analysis shows that although the time complexity of the initialization process is linear, the algorithm has the characteristics of the superlinear initialization method. This algorithm is applied to two-dimensional GPS data analysis and high-dimensional network attack detection. Experimental results show that this algorithm achieves high clustering performance and clustering speed. Conclusion: This paper reduces the subsequent iterations of K-means algorithm without compromising the clustering performance, which makes it suitable for large-scale data clustering. This algorithm can not only be applied to low-dimensional data clustering, but also suitable for high-dimensional data. © 2019 Bentham Science Publishers.

引用

页码：403 / 409

页数：6

共 19 条

[1]

Aloise D., Deshpande A., Hansen P., Popat P., NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn, 75, pp. 245-248, (2009)

[2]

Mahajan M., Nimbhorkar P., Varadarajan K., The planar-means problem is NP-hard, Theoretical Comp. Sci, 442, pp. 13-21, (2012)

[3]

Qi H., Liu Y., Wei D., GPS-Based vehicle moving state recognition method and its applications on dynamic in-car navigation systems, 2014 IEEE 12Th International Conference on Dependable, Autonomic and Secure Computing, pp. 354-360, (2014)

[4]

Celebi M.E., Kingravi H.A., Vela P.A., A comparative study of efficient initialization methods for the k-means clustering algo-rithm, Expert Sys. App, 40, pp. 200-210, (2013)

[5]

Celebi M.E., Improving the performance of k-means for color quantization, Image Vision Comput, 29, pp. 260-271, (2011)

[6]

Arthur D., Vassilvitskii S., K-means++: The advantages of careful seeding, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027-1035, (2007)

[7]

Al-Daoud M.B., A new algorithm for cluster initialization, Inter. J. Comp. Cont. Quant. Info. Eng, 1, pp. 1016-1018, (2007)

[8]

Redmond S.J., Heneghan C., A method for initialising the K-rmeans clustering algorithm using kd-trees, Pattern Recogn., Letters, 28, pp. 965-973, (2007)

[9]

Hasan M.A., Chaoji V., Salem S., Zaki M.J., Robust partition-al clustering by outlier and density insensitive seeding, Pattern Recogn. Lett, 30, pp. 994-1002, (2009)

[10]

Nazeer K.A.A., Sebastian M.P., Improving the accuracy and efficiency of the k-means clustering algorithm, World Congress on Engineering, pp. 308-312, (2009)

← 1 2 →