K-means clustering algorithm based on adaptive cuckoo search and its application

doi:10.11772/j.issn.1001-9081.2016.08.2066

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (8): 2066-2070.DOI: 10.11772/j.issn.1001-9081.2016.08.2066

Previous Articles Next Articles

K-means clustering algorithm based on adaptive cuckoo search and its application

YANG Huihua^1,2, WANG Ke¹, LI Lingqiao¹, WEI Wen¹, HE Shengtao³

1. Guangxi Experiment Center of Information Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
2. Automation School, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3. Guilin Intelligent Metric Information Technology Company Limited, Guilin Guangxi 541004, China

Received:2016-03-01 Revised:2016-05-16 Online:2016-08-10 Published:2016-08-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (21365008, 61562013), the Guangxi Natural Science Foundation (2013GXNSFBA019279), the Innovation Project of Graduate Education of Guilin University of Electronic Technology (GDYCSZ201478, GDYCSZ201474).

基于自适应布谷鸟搜索算法的K-means聚类算法及其应用

杨辉华^1,2, 王克¹, 李灵巧¹, 魏文¹, 何胜韬³

1. 桂林电子科技大学广西信息科学实验中心, 广西桂林 541004;
2. 北京邮电大学自动化学院, 北京 100876;
3. 桂林市智度信息科技有限公司, 广西桂林 541004

通讯作者: 杨辉华
作者简介:杨辉华(1972-),男,湖南常德人,教授,博士生导师,博士,主要研究方向:机器学习、人工智能、最优化;王克(1988-),男,安徽淮北人,硕士研究生,主要研究方向:数据挖掘、分布式计算;李灵巧(1986-),男,四川达州人,博士研究生,主要研究方向:智能信息处理、机器学习;魏文(1989-),男,山东日照人,硕士研究生,主要研究方向:模式识别、机器学习;何胜韬(1985-),男,广西玉林人,硕士,主要研究方向:软件工程。
基金资助:
国家自然科学基金资助项目（21365008,61562013）；广西自然科学基金资助项目（2013GXNSFBA019279）；桂林电子科技大学研究生创新项目（GDYCSZ201478,GDYCSZ201474）。

Abstract

Abstract: The original K-means clustering algorithm is seriously affected by initial centroids of clustering and easy to fall into local optima. To solve this problem, an improved K-means clustering algorithm based on Adaptive Cuckoo Search (ACS), namely ACS-K-means, was proposed, in which the search step of cuckoo was adjusted adaptively so as to improve the quality of solution and boost speed of convergence. The performance of ACS-K-means clustering was firstly evaluated on UCI dataset, and the results demonstrated that it surpassed K-means, GA-K-means (K-means based on Genetic Algorithm), CS-K-means (K-means based on Cuckoo Search) and PSO-K-means (K-means based on Particle Swarm Optimization) in clustering quality and convergence rate. Finally, the ACS-K-means clustering algorithm was applied to the development of heat map of urban management cases of Qingxiu district of Nanning city, the results also showed that the proposed method had better quality of clustering and faster speed of convergence.

Key words: data mining, K-means clustering, Cuckoo Search (CS)algorithm, digital urban management, heat map

摘要： 针对原始K-means聚类算法受初始聚类中心影响过大以及容易陷入局部最优的不足，提出一种基于改进布谷鸟搜索（CS）的K-means聚类算法（ACS-K-means）。其中，自适应CS（ACS）算法在标准CS算法的基础上引入步长自适应调整，以提高搜索精度和收敛速度。在UCI标准数据集上，ACS-K-means算法可得到比K-means、基于遗传算法的K-means（GA-K-means）、基于布谷鸟搜索的K-means（CS-K-means）和基于粒子群优化的K-means（PSO-K-means）算法更优的聚类质量和更高的收敛速度。将ACS-K-means聚类算法应用到南宁市青秀区“城管通”系统的城管案件热图的开发中，在地图上对案件地理坐标进行聚类并显示，应用结果表明，聚类效果良好，算法收敛速度快。

关键词: 数据挖掘, K-means聚类, 布谷鸟搜索算法, 数字城管, 热图

CLC Number:

TP391
TP183

YANG Huihua, WANG Ke, LI Lingqiao, WEI Wen, HE Shengtao. K-means clustering algorithm based on adaptive cuckoo search and its application[J]. Journal of Computer Applications, 2016, 36(8): 2066-2070.

杨辉华, 王克, 李灵巧, 魏文, 何胜韬. 基于自适应布谷鸟搜索算法的K-means聚类算法及其应用[J]. 计算机应用, 2016, 36(8): 2066-2070.

References

[1] FONG S,DEB S,YANG X-S,et al.Towards enhancement of performance of K-means clustering using nature-inspired optimization algorithms[J].The Scientific World Journal,2014,2014:564829.
[2] YANG X-S,DEB S.Cuckoo search via Lévy flights[C]//NaBIC 2009:Proceedings of the 2009 World Congress on Nature&Biologically Inspired Computing.Piscataway,NJ:2009:210-214.
[3] FISTER I,Jr.,YANG X-S,FISTER D,et al.Cuckoo search:a brief literature review[M]//Cuckoo Search and Firefly Algorithm,Volume 516 of the Series Studies in Computational Intelligence.Berlin:Springer-Verlag,2013:49-62.
[4] YANG X-S,DEB S.Cuckoo search:recent advances and applications[J].Neural Computing and Applications,2014,24(1):169-174.
[5] SRIVASTAVA P R,KHANDELWAL R,KHANDELWAL S,et al.Automated test data generation using cuckoo search and tabu search (CSTS) algorithm[J].Journal of Intelligent Systems,2012,21(2):195-224.
[6] BEZDELC J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].Berlin:Springer-Verlag,1981:46-52.
[7] LI X,WANG J,YIN M.Enhancing the performance of cuckoo search algorithm using orthogonal learning method[J].Neural Computing and Applications,2014,24(6):1233-1247.
[8] ONG P.Adaptive cuckoo search algorithm for unconstrained optimization[J].Scientific World Journal,2014,2014:943403.
[9] 张永韡,汪镭,吴启迪.动态适应布谷鸟搜索算法[J].控制与决策,2014,29(4):617-622.(ZHANG Y W,WANG L,WU Q D.Dynamic adaptation cuckoo search algorithm[J].Control and Decision,2014,29(4):617-622.)
[10] 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法[J].软件学报,2013(11):2687-2698.(WANG L J,YIN Y L,ZHONG Y W.Cuckoo search algorithm with dimension by dimension improvement[J].Journal of Software,2013,24(11):2687-2698.)
[11] 胡欣欣,尹义龙.求解连续函数优化问题的合作协同进化布谷鸟搜索算法[J].模式识别与人工智能,2013,26(11):1041-1049.(HU X X,YIN Y L.Cooperative co-evolutionary cuckoo search algorithm for continuous function optimization problems[J].Pattern Recognition and Artificial Intelligence,2013,26(11):1041-1049.)
[12] 吴希玉.深化城管改革建设宜居南宁[N].广西日报,2015-12-30(7).(WU X Y.Deepen the reform of urban construction of livable Nanning[N].Guangxi Daily,2015-12-30(7).)
[13] 向志强,朱丽莉."互联网+城管"的"青秀探索"[N].新华每日电讯,2016-02-03(7).(XIANG Z Q,ZHU L L.The exploration of Qingxiu based on Internet and urban management[N].Xinhuashenet,2016-02-03(7).)
[14] BAGHERI E,DELDARI H.Dejong function optimization by means of a parallel approach to fuzzified genetic algorithm[C]//ISCC'06:Proceedings of the 11th IEEE Symposium on Computers and Communications.Washington,DC:IEEE Computer Society,2006:675-680.
[15] HALL L O,OZYURT I B,BEZDEK J C.Clustering with a genetically optimized approach[J].IEEE Transactions on Evolutionary Computation,1999,3(2):103-112.
[16] 陆林花,王波.一种改进的遗传聚类算法[J].计算机工程与应用,2007,43(21):170-172.(LU L H,WANG B.Improved genetic algorithm-based clustering approach[J].Computer Engineering and Applications,2007,43(21):170-172.)
[17] 傅景广,许刚,王裕国.基于遗传算法的聚类分析[J].计算机工程,2004,30(4):122-124.(FU J G,XU G,WANG Y G.Clustering based on genetic algorithm[J].Computer Engineering,2004,30(4):122-124.)
[18] AHMADYFARD A,MODARES H.Combining PSO and k-means to enhance data clustering[C]//IST 2008:Proceedings of the 2008 International Symposium on Telecommunications.Piscataway,NJ:IEEE,2008:688-691.
[19] 陈小全,张继红.基于改进粒子群算法的聚类算法[J].计算机研究与发展,2012,49(增刊):287-291.(CHEN X Q,ZHANG J H.Clustering algorithm based on improved particle swarm optimization[J].Journal of Computer Research and Development,2012,49(Suppl.):287-291.)

K-means clustering algorithm based on adaptive cuckoo search and its application

基于自适应布谷鸟搜索算法的K-means聚类算法及其应用

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LIU Shize, QIN Yanjun, WANG Chenxing, SU Lin, KE Qixue, LUO Haiyong, SUN Yi, WANG Baohui. Traffic flow prediction algorithm based on deep residual long short-term memory network [J]. Journal of Computer Applications, 2021, 41(6): 1566-1572.
[2]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[3]	CHEN Kai, YU Yanwei, ZHAO Jindong, SONG Peng. Work location inference method with big data of urban traffic surveillance [J]. Journal of Computer Applications, 2021, 41(1): 177-184.
[4]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[5]	DU Xusheng, YU Jiong, YE Lele, CHEN Jiaying. Outlier detection algorithm based on graph random walk [J]. Journal of Computer Applications, 2020, 40(5): 1322-1328.
[6]	XU Zhoubo, YANG Jian, LIU Huadong, HUANG Wenwen. Protein complex identification algorithm based on XGboost and topological structural information [J]. Journal of Computer Applications, 2020, 40(5): 1510-1514.
[7]	CHEN Xi, MEI Guang, ZHANG Jinjin, XU Weisheng. Student grade prediction method based on knowledge graph and collaborative filtering [J]. Journal of Computer Applications, 2020, 40(2): 595-601.
[8]	MA Dong, CHEN Hongmei, WANG Lizhen, XIAO Qing. Dominant feature mining of spatial sub-prevalent co-location patterns [J]. Journal of Computer Applications, 2020, 40(2): 465-472.
[9]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[10]	SUN Heli, ZHANG Youyou, YANG Zhou, HE Liang, JIA Xiaolin. Urban reachable region search based on time segment tree [J]. Journal of Computer Applications, 2020, 40(10): 2936-2941.
[11]	ZHAO Ruixiang, HOU Honghua, ZHANG Pengcheng, LIU Yi, TIAN Zhu, GUI Zhiguo. Welding ball edge bubble segmentation for ball grid array based on full convolutional network and K-means clustering [J]. Journal of Computer Applications, 2019, 39(9): 2580-2585.
[12]	REN Jie, MIN Fan, WANG Min. Cost-sensitive active learning through farthest distance sum sampling [J]. Journal of Computer Applications, 2019, 39(9): 2499-2504.
[13]	LI Bo, ZHANG Xiao, YAN Jingyi, LI Kewei, LI Heng, LING Yulong, ZHANG Yong. Application of KNN algorithm based on value difference metric and clustering optimization in bank customer behavior prediction [J]. Journal of Computer Applications, 2019, 39(9): 2784-2788.
[14]	LI He, JIANG Dengying, HUANG Zhangcan, WANG Zhanzhan. Method for solving color images quantization problem of color images [J]. Journal of Computer Applications, 2019, 39(9): 2646-2651.
[15]	JI Lina, CHEN Kai, YU Yanwei, SONG Peng, WANG Shuying, WANG Chenrui. Vehicle type mining and application analysis based on urban traffic big data [J]. Journal of Computer Applications, 2019, 39(5): 1343-1350.