烟花搜索导向的多路启发式聚类算法
|
摘要
启发式聚类算法具有收敛速度快、易实现等优点,但初始解敏感,严重影响了聚类算法的质量。针对这一问题,提出了一种烟花搜索导向的多路启发式聚类算法。该算法通过多次调用经典启发式聚类算法,产生多个局部最优解;在搜索空间中以多个局部最优解为搜索起点,采用烟花搜索进行多路搜索;基于信息熵浓度设计烟花选择算子确定搜索方向;再经过变异、映射、偏移算子变换局部最优中心点,以发现质量更好的搜索起点;直至算法收敛获得新的搜索起点;最终以新的搜索起点调用经典启发式聚类算法获得高质量聚类结果。实验结果表明,烟花搜索导向的多路启发式聚类算法在不同数据集上的聚类质量明显高于对比其他聚类算法的聚类质量。
Heuristic clustering algorithm has the advantages of fast convergence and easy implementation, but the initial solution is sensitive, which seriously affects the quality of clustering algorithm. In order to solve this problem, this paper proposes a multi-channel heuristic clustering algorithm for fireworks search guidance. The classical heuristic clustering algorithm is called many times to generate several local optimal solutions. In the search space, multiple local optimal solutions are used as the starting point, and fireworks search is used for multi-path search. Design fireworks selection operator based on information entropy concentration to determine the search direction; Then the local optimal center point is transformed by mutation, mapping and migration operator to find a better search starting point. Until the algorithm converges to obtain a new search starting point; Finally, the classical heuristic clustering algorithm is used to obtain high quality clustering results. Experimental results show that the clustering quality of FSG_MHC algorithm on different data sets is obviously higher than that of the contrast clustering algorithm.
Heuristic clustering algorithm has the advantages of fast convergence and easy implementation, but the initial solution is sensitive, which seriously affects the quality of clustering algorithm. In order to solve this problem, this paper proposes a multi-channel heuristic clustering algorithm for fireworks search guidance. The classical heuristic clustering algorithm is called many times to generate several local optimal solutions. In the search space, multiple local optimal solutions are used as the starting point, and fireworks search is used for multi-path search. Design fireworks selection operator based on information entropy concentration to determine the search direction; Then the local optimal center point is transformed by mutation, mapping and migration operator to find a better search starting point. Until the algorithm converges to obtain a new search starting point; Finally, the classical heuristic clustering algorithm is used to obtain high quality clustering results. Experimental results show that the clustering quality of FSG_MHC algorithm on different data sets is obviously higher than that of the contrast clustering algorithm.
引文
[1] YIN Hong-zhi,HU Zhi-ting,ZHOU Xiao-fang,et al.Discovering interpretable geo-social communities for user behavior prediction[C]// 32nd International Conference on Data Engineering(ICDE).IEEE,2016.
[2] COOPER C,FRANKLIN D,ROS M,et al.A Comparative Survey of VANET Clustering Techniques[J].IEEE Communications Surveys & Tutorials,2016,99:1.
[3] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[4] 周东华.数据挖掘中聚类分析的研究与应用[D].天津:天津大学,2006.
[5] 宗瑜.聚类质量改进方法的研究[D].大连:大连理工大学,2010.
[6] 宗瑜,李明楚,江贺.近似骨架导向的归约聚类算法[J].电子与信息学报,2009,31(12):2953-2957.
[7] DRINEAS P,FRIEZE A,KANNAN R,et al.Clustering Large Graphs via the Singular Value Decomposition[J].Machine Learning,2004,56(1-3):9-33.
[8] 吴文亮.聚类分析中K-均值与K-中心点算法的研究[D].广州:华南理工大学,2011.
[9] 周涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,48(12):100-111.
[10] 金萍,陈家俊,徐华丽.一种基于变邻域搜索的启发式聚类算法[J].皖西学院学报,2015,31(5):74-77.
[11] 宗瑜,江贺,张宪超,等.空间平滑搜索CLARANS算法[J].小型微型计算机系统,2008(4):667-671.
[12] ZHANG Tong,WANG Dong,CHEN Hao-nan.Balanced COD-CLARANS:A Constrained Clustering Algorithm to Optimize Logistics Distribution Network[A].Proceedings of 2016 2nd International Conference on Artificial Intelligence and Industrial Engineering [C].Science and Engineering Research Center,2016:5.
[13] DING C,HE Xiao-feng.K-nearest-neighbor consistency in data clustering:incorporating local information into global optimization[C]//Acm Symposium on Applied Computing.DBLP,2004.
[14] 李洁,高新波,焦李成.基于特征加权的模糊聚类新算法[J].电子学报,2006(1):89-92.
[15] GU J,HUANG X.Efficient local search with search space smoothing:a case study of the traveling salesman problem (TSP)[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(5):728-735.
[16] 赵东东,宗瑜,江贺,等.一种多空间聚类算法[J].小型微型计算机系统,2006(12):2297-2300.
[17] JIN Ping,QU Shi-chao,ZONG Yu,et al.CUDAP:A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone[J].JSW,2014,732-737.
[18] 金萍,宗瑜,屈世超,等.面向不确定数据的近似骨架启发式聚类算法[J].南京大学学报(自然科学),2015,51(1):197-205.
[19] TAN Y.Fireworks Algorithm:A Novel Swarm Intelligence Optimization Method[M].Springer Publishing Company,Incorporated,2015.
[20] ZHENG S,LI J,JANECEK A,et al.A Cooperative Framework for Fireworks Algorithm[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2015:1.
[21] 陈小雪,尉永清,任敏,等.基于萤火虫优化的加权K-means算法[J].计算机应用研究,2018,35(2):466-470.
[22] RAO Qi,YANG Yan,JIANG Yong-quan.Condition Recognition of High-Speed Train Bogie Based on Multi-View Kernel FCM[J].Big Data Mining and Analytics,2019,2(1):1-11.
[23] ZHANG Jian,YU Hui-long,QIN Cui,et al.Ray Tracing Dynamic Scenes Using Multiple Kd-trees[A].Proceedings of 2018 2nd International Conference on Applied Mathematics,Modeling and Simulation [C].Science and Engineering Research Center,2018:8.
[2] COOPER C,FRANKLIN D,ROS M,et al.A Comparative Survey of VANET Clustering Techniques[J].IEEE Communications Surveys & Tutorials,2016,99:1.
[3] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[4] 周东华.数据挖掘中聚类分析的研究与应用[D].天津:天津大学,2006.
[5] 宗瑜.聚类质量改进方法的研究[D].大连:大连理工大学,2010.
[6] 宗瑜,李明楚,江贺.近似骨架导向的归约聚类算法[J].电子与信息学报,2009,31(12):2953-2957.
[7] DRINEAS P,FRIEZE A,KANNAN R,et al.Clustering Large Graphs via the Singular Value Decomposition[J].Machine Learning,2004,56(1-3):9-33.
[8] 吴文亮.聚类分析中K-均值与K-中心点算法的研究[D].广州:华南理工大学,2011.
[9] 周涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,48(12):100-111.
[10] 金萍,陈家俊,徐华丽.一种基于变邻域搜索的启发式聚类算法[J].皖西学院学报,2015,31(5):74-77.
[11] 宗瑜,江贺,张宪超,等.空间平滑搜索CLARANS算法[J].小型微型计算机系统,2008(4):667-671.
[12] ZHANG Tong,WANG Dong,CHEN Hao-nan.Balanced COD-CLARANS:A Constrained Clustering Algorithm to Optimize Logistics Distribution Network[A].Proceedings of 2016 2nd International Conference on Artificial Intelligence and Industrial Engineering [C].Science and Engineering Research Center,2016:5.
[13] DING C,HE Xiao-feng.K-nearest-neighbor consistency in data clustering:incorporating local information into global optimization[C]//Acm Symposium on Applied Computing.DBLP,2004.
[14] 李洁,高新波,焦李成.基于特征加权的模糊聚类新算法[J].电子学报,2006(1):89-92.
[15] GU J,HUANG X.Efficient local search with search space smoothing:a case study of the traveling salesman problem (TSP)[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(5):728-735.
[16] 赵东东,宗瑜,江贺,等.一种多空间聚类算法[J].小型微型计算机系统,2006(12):2297-2300.
[17] JIN Ping,QU Shi-chao,ZONG Yu,et al.CUDAP:A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone[J].JSW,2014,732-737.
[18] 金萍,宗瑜,屈世超,等.面向不确定数据的近似骨架启发式聚类算法[J].南京大学学报(自然科学),2015,51(1):197-205.
[19] TAN Y.Fireworks Algorithm:A Novel Swarm Intelligence Optimization Method[M].Springer Publishing Company,Incorporated,2015.
[20] ZHENG S,LI J,JANECEK A,et al.A Cooperative Framework for Fireworks Algorithm[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2015:1.
[21] 陈小雪,尉永清,任敏,等.基于萤火虫优化的加权K-means算法[J].计算机应用研究,2018,35(2):466-470.
[22] RAO Qi,YANG Yan,JIANG Yong-quan.Condition Recognition of High-Speed Train Bogie Based on Multi-View Kernel FCM[J].Big Data Mining and Analytics,2019,2(1):1-11.
[23] ZHANG Jian,YU Hui-long,QIN Cui,et al.Ray Tracing Dynamic Scenes Using Multiple Kd-trees[A].Proceedings of 2018 2nd International Conference on Applied Mathematics,Modeling and Simulation [C].Science and Engineering Research Center,2018:8.