融合粒子群和蛙跳算法的模糊C-均值聚类算法研究
|
摘要
随着数据库技术的飞速发展,数据以惊人的速度膨胀,面多如此海量的数据,为了从中提取有效的信息,数据挖掘技术孕育而生。
聚类分析是数据挖掘的一个重要部分,聚类分析就是把数据对象集合中的不同数据对象划分成不同的类的过程,同一个类里的数据对象彼此相似,不同的类之间数据对象彼此相异。聚类分析中的有许多复杂组合的优化问题,智能优化算法能为之提供有效的帮助。
本文深入研究了群智能算法中混合蛙跳算法和粒子群算法与聚类分析中模糊C-均值聚类算法,并将三者融合在一起。主要工作包括:
(1)深入分析了混合蛙跳算法的求解过程、参数设定和优缺点,针对算法易陷入局部最优的问题,引进了混沌映射系统和高斯分布改进了算法中的更新步骤。通过实验仿真,验证算法的可行性,并做了相关分析。
(2)研究了粒子群算法的特点,为克服模糊C-均值聚类算法的不足,通过设计一个参数,有机地将改进的混合蛙跳算法和粒子群算法融合到模糊C-均值聚类算法中。使算法能够较好地跳出局部最优解,收敛于全局最优,同时也保证了收敛速度。最后通过实验仿真,验证了算法的有效性。
Along with the high speed development of database technology, data is inflating in an astonishing speed. And to confront such mass data and to extract effective information, data mining technology emerges.
Clustering is an important part of data mining, that to divide objects of a dataset into different classes, in which, objects in the same class resemble to each other and objects belongs to different classes differ from each other. In clustering, there are lots of complex combinational optimization problems, intelligence optimization algorithms makes great contribution.
This paper researches fuzzy C-mean clustering algorithm and two swarm intelligence optimization algorithms, namely the shuffled frog leaping algorithm(SFLA) and the Particle Swarm Optimization(PSO) algorithm, and the two algorithms is integrated into the former. The work mainly includes:
(1)To deeply analyze the solution procedure, the parameters and the merits and demerits of SFLA. And chaos mapping system and Gaussian distribution is imported to improve the upgrade procedure aiming to the problem of easy trapped by local optimum. Simulation experiments are taken for feasibility and other analysis.
(2)To deeply analyze the PSO algorithm. A new parameter, that is designed to improve the disadvantage of the C-means Clustering, integrates the PSO algorithm and SFLA into the C-means Clustering, that could convergence to global optimum against of original local optimum at an equal convergence speed. Simulation experiments are taken for validation.
聚类分析是数据挖掘的一个重要部分,聚类分析就是把数据对象集合中的不同数据对象划分成不同的类的过程,同一个类里的数据对象彼此相似,不同的类之间数据对象彼此相异。聚类分析中的有许多复杂组合的优化问题,智能优化算法能为之提供有效的帮助。
本文深入研究了群智能算法中混合蛙跳算法和粒子群算法与聚类分析中模糊C-均值聚类算法,并将三者融合在一起。主要工作包括:
(1)深入分析了混合蛙跳算法的求解过程、参数设定和优缺点,针对算法易陷入局部最优的问题,引进了混沌映射系统和高斯分布改进了算法中的更新步骤。通过实验仿真,验证算法的可行性,并做了相关分析。
(2)研究了粒子群算法的特点,为克服模糊C-均值聚类算法的不足,通过设计一个参数,有机地将改进的混合蛙跳算法和粒子群算法融合到模糊C-均值聚类算法中。使算法能够较好地跳出局部最优解,收敛于全局最优,同时也保证了收敛速度。最后通过实验仿真,验证了算法的有效性。
Along with the high speed development of database technology, data is inflating in an astonishing speed. And to confront such mass data and to extract effective information, data mining technology emerges.
Clustering is an important part of data mining, that to divide objects of a dataset into different classes, in which, objects in the same class resemble to each other and objects belongs to different classes differ from each other. In clustering, there are lots of complex combinational optimization problems, intelligence optimization algorithms makes great contribution.
This paper researches fuzzy C-mean clustering algorithm and two swarm intelligence optimization algorithms, namely the shuffled frog leaping algorithm(SFLA) and the Particle Swarm Optimization(PSO) algorithm, and the two algorithms is integrated into the former. The work mainly includes:
(1)To deeply analyze the solution procedure, the parameters and the merits and demerits of SFLA. And chaos mapping system and Gaussian distribution is imported to improve the upgrade procedure aiming to the problem of easy trapped by local optimum. Simulation experiments are taken for feasibility and other analysis.
(2)To deeply analyze the PSO algorithm. A new parameter, that is designed to improve the disadvantage of the C-means Clustering, integrates the PSO algorithm and SFLA into the C-means Clustering, that could convergence to global optimum against of original local optimum at an equal convergence speed. Simulation experiments are taken for validation.
引文
[1] Han Jiawei,Kamber M.数据挖掘-概念与技术[M].北京:机械工业出版社,2005.
[2]郑岩.数据仓库与数据挖掘原理及应用[M].北京:机械工业出版社,2011.
[3]梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006.
[4]毛国君.数据挖掘原理与算法[M].北京:清华大学出版社,2005.
[5] George M.Marakas.数据仓库、挖掘和可视化:核心概念[M].北京:清华大学出版社,2004.
[6] W.H.Inmon.数据仓库[M].北京:机械工业出版社,2003.
[7] Witold Pedrycz.基于知识的聚类:从数据到信息粒[M] .北京:北京师范大学出版社: 2008.
[8]梁艳春,吴春国,时小虎.群智能优化算法理论与应用[M] .北京:科学出版社,2009.
[9] Rodríguez-Díaz, F.J.; García-Martínez, C.; Lozano, M.A GA-based multiple simulated annealing [C]//IEEE International Conference on Evolutionary Computation , Barcelona, 2010,7:18-23.
[10]苏清华,胡中波,熊一能.聚类问题的自适应杂交差分演化模拟退火算法[J].计算机工程与应用, 2010, 46(23): 41-43.
[11] Qi Ji-Yang. Application of improved simulated annealing algorithm in facility layout design [C].Control Conference , Beijing, 2010:7:29-31.
[12] Qingping Fu. An improved ant swarm algorithm for clustering analysis of data mining[C].ICTM '09 International Conference on Hong Kong, 2009; VOL (2): 347
[13] Ling Chen,Xiaohua,XuYixin Chen,Yixin Chen.Ping He. A novel ant clustering algorithm based on cellular automata[C]. IEEE/WIC/ACM International Conference on Intelligent Agent Technology,2004:148.
[14] Zhou Shu-jing,Li Yan-cang, Li Hui-min. A self-adaptive Ant Algorithm with changing index[C]. ICMSE 2008. 15th Annual Conference Proceedings., International Conference on Management Science and Engineering, Long Beach, CA , 2008:225.
[15]张丽,刘希玉,李章泉.基于蚁群算法的聚类优化[J].计算机工程, 2010,36 (9): 190-191.
[16] Dortgo M,Maniezzo V .Ant System:Optimization by A Colony Cooperating Agents[J].IEEE Trans on System Man and Cybernetics,2006,26(1):29-41.
[17]周丽娟,石倩,葛学彬等.基于聚类的模糊遗传挖掘算法的研究[M].计算机工程与应用,2010,46(13): 118-121.
[18]董红斌,陈佳,吴斌.数据立方体选择的改进遗传算法[M],计算机科学,2010, 37 (11):152-155.
[19] Meng, Q.C, Feng, T.J, Chen, Z,Zhou, C.J,Bo, J.H. Genetic algorithms encoding study and a sufficient convergence condition of GAs [C]. IEEE International Conference on Systems, Man, and Cybernetics, Tokyo, 1999,1: 649.
[20] Bagheri, Deldari, H. Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C]. IEEE Symposium on Computers and Communications, University of New Bruswick, Canada,2006: 675.
[21]蒋盛益.基于聚类的入侵检测算法研究[M].北京:科学出版社,2008.
[22]王翠娥,于晓明.网格和密度聚类算法在入侵检测中的应用[M].计算机应用, 2010,11: 3051-3052,3061.
[23]韩毅,蔡建湖,周根贵等.随机蛙跳算法的研究进展[J].计算机科学,2010,37(7): 16-19.
[24] M.Eusuff,K.Lansey, F.Pasha.Shuffled frog leaping algorithm:a memetic metaheuristic for discrete optimization.Engineering Optimization,2005,38(3):129-154
[25] Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved Shuffled Frog Leaping Algorithm for Continuous optimization problem [C]//IEEE Congress on Evolutionary Computation, Trondheim, 2009,5:2992-2995.
[26] Luo Xue-hui, Yang Ye, Li Xia. Solving TSP with Shuffled Frog-Leaping Algorithm [C] Eighth International Conference on Intelligent Systems Design and Applications, Kaohsiung, 2008 , VOL(3): 228-232.
[27] Eusuff M M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm [J]. Journal of Water Sources Planning and Management, 2003,129(3):210-225.
[28] E.Elbeltagi,T.Hegazy,D.Grierson.Comparison among five evolutionary based optimization algorithms[J].Aavanced Engineering Informatics,2005,19(1):43-53
[29] Thai-Hoang Huynh.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllersp[C]// IEEE International Conference on Industrial Technology , Chengdu,2008 , 1-6.
[30] Acampora. G, Cadenas. J.M, Loia. V, Mu?oz.E. Achieving memetic adaptability by means of fuzzy decision trees [C]// IEEE International Conference on Fuzzy Systems , Barcelona, 2010: 1– 8.
[31] Nguyen. Q.H,Ong. Y.S, Krasnogor.N. A study on the design issues of Memetic Algorithm [C]// IEEE International Conference on Evolutionary Computation, Singapore, 2009: 519– 524.
[32]郭秀萍,杨根科,吴智铭.一种混合自适应多目标Memetic算法[M].控制与决策,2006, 21(11):1234-1238.
[33]于万波.混沌的计算实验与分析[M].北京:科学出版社,2008.
[34]刘道华,原思聪,兰洋,马新建.混沌映射的粒子群优化方法[J].西安电子科技大学学报,2010,37(4):764-769.
[35]陈希孺,倪国熙,陈长顺.数理统计学教程[M].合肥:中国科学技术大学出版社,2009.
[36]赵鹏军.一种新的仿生优化算法及其改进[J].商洛学院学报:2009,23(2):19-21.
[37]况夯,罗军.基于遗传FCM算法的文本聚类[J].计算机应用,2009,29(2):558-560.
[38]杜长海,黄席樾,杨祖元等.改进的FCM聚类在交通时段自动划分中的应用[J].计算机工程与应用,2009,45(24):190-193.
[39]李春芳,庞雅静,钱丽璞等.半监督FCM聚类算法目标函数研究[J].计算机工程与应用,2009, 45(14): 128-132,135.
[40]李丽丽,刘希玉,庄波.基于模拟退火粒子群算法的FCM聚类方法[J].计算机应用,2008, 44 (30): 170-172.
[41]宋娇,葛临东.一种遗传模糊聚类算法及其应用[J].计算机应用,2008,28 (5):1197-1199.
[42] GAP Xin—bo,XIE Wei-xin.Advances in theory and applieations of fuzzy clustering [J].Chinese Science Bulletin,2000,45(11):950-972.
[43] Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M]. New York :Plenum Press,1981.
[44] Kennedy J, Eberhert R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks, 1995:1942-1948.8.
[45] Shi Y, Eberhart R. A modified particle swarm optimizer [C]// IEEE International Conference on Evolutionary Computation, Anch- orage, 1998,5:69- 73.
[46] Kennedy J, Eberhart R C, Shi Y. Swarm intelligence [M].SanFranciSco:Morgan Kaufman Publisher,2001.
[47] Shi Y, Eberhart R C.Particle Swarm Optimization: developments, applications and resources [C] //IEEE International Conference on Evolutionary Computation 2001 NJ: Piscataway, IEEE Press, 2001:81-86,101-106.
[48] Tang Hai-yan, Ding Bao, Qi Wei-gui. Research on traffic mode of elevator applied fuzzy C-mean clustering algorithm based on PSO [C]//IEEE International Conference on Measuring Technolo- gy and Mechatronics Automation, Zhangjiajie, Hunan,2009, 582– 585.
[49] Wei Jing, Hai Zhao, Chunhe Song, Dan Liu. A optimized particle filter based on PSO algorithm [C]// IEEE International Conferen- ce on BioMedical Information Engineering ,Future, 2009, 122-125.
[50]寇保华,杨涛,张晓今等.基于交叉变异的混合粒子群优化算法[J].计算机工程与应用,2007,43(17):85-88.
[51]宋书强,叶春明.一种新的自适应小生境粒子群优化算法[J].计算机仿真,2010,10:175-178,258.
[52]李丽丽,刘希玉,刘涛等.一种基于粒子群优化的FCM聚类方法[J].计算机应用技术,2008,1:89-92.
[53] Hsiang-Chuan Liu, Jeng-Ming Yih, Der-Bang Wu, Shin-Wu Liu. Fuzzy C-Mean Clustering Algorithms Based on Picard Iteration and Particle Swarm Optimization [C]//IEEE International Confer- ence on Education Technology and Training,Shanghai,2008, 2: 838– 842.
[54] Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved Shuffled Frog Leaping Algorithm for Continuous optimization problem [C]//IEEE Congress on Evolutionary Computation, Trondheim, 2009,5:2992-2995.
[55]刘向东,沙秋夫,刘勇奎.基于粒子群算法的聚类分析[J].计算机工程,2006,32 (6):201-202.
[2]郑岩.数据仓库与数据挖掘原理及应用[M].北京:机械工业出版社,2011.
[3]梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006.
[4]毛国君.数据挖掘原理与算法[M].北京:清华大学出版社,2005.
[5] George M.Marakas.数据仓库、挖掘和可视化:核心概念[M].北京:清华大学出版社,2004.
[6] W.H.Inmon.数据仓库[M].北京:机械工业出版社,2003.
[7] Witold Pedrycz.基于知识的聚类:从数据到信息粒[M] .北京:北京师范大学出版社: 2008.
[8]梁艳春,吴春国,时小虎.群智能优化算法理论与应用[M] .北京:科学出版社,2009.
[9] Rodríguez-Díaz, F.J.; García-Martínez, C.; Lozano, M.A GA-based multiple simulated annealing [C]//IEEE International Conference on Evolutionary Computation , Barcelona, 2010,7:18-23.
[10]苏清华,胡中波,熊一能.聚类问题的自适应杂交差分演化模拟退火算法[J].计算机工程与应用, 2010, 46(23): 41-43.
[11] Qi Ji-Yang. Application of improved simulated annealing algorithm in facility layout design [C].Control Conference , Beijing, 2010:7:29-31.
[12] Qingping Fu. An improved ant swarm algorithm for clustering analysis of data mining[C].ICTM '09 International Conference on Hong Kong, 2009; VOL (2): 347
[13] Ling Chen,Xiaohua,XuYixin Chen,Yixin Chen.Ping He. A novel ant clustering algorithm based on cellular automata[C]. IEEE/WIC/ACM International Conference on Intelligent Agent Technology,2004:148.
[14] Zhou Shu-jing,Li Yan-cang, Li Hui-min. A self-adaptive Ant Algorithm with changing index[C]. ICMSE 2008. 15th Annual Conference Proceedings., International Conference on Management Science and Engineering, Long Beach, CA , 2008:225.
[15]张丽,刘希玉,李章泉.基于蚁群算法的聚类优化[J].计算机工程, 2010,36 (9): 190-191.
[16] Dortgo M,Maniezzo V .Ant System:Optimization by A Colony Cooperating Agents[J].IEEE Trans on System Man and Cybernetics,2006,26(1):29-41.
[17]周丽娟,石倩,葛学彬等.基于聚类的模糊遗传挖掘算法的研究[M].计算机工程与应用,2010,46(13): 118-121.
[18]董红斌,陈佳,吴斌.数据立方体选择的改进遗传算法[M],计算机科学,2010, 37 (11):152-155.
[19] Meng, Q.C, Feng, T.J, Chen, Z,Zhou, C.J,Bo, J.H. Genetic algorithms encoding study and a sufficient convergence condition of GAs [C]. IEEE International Conference on Systems, Man, and Cybernetics, Tokyo, 1999,1: 649.
[20] Bagheri, Deldari, H. Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C]. IEEE Symposium on Computers and Communications, University of New Bruswick, Canada,2006: 675.
[21]蒋盛益.基于聚类的入侵检测算法研究[M].北京:科学出版社,2008.
[22]王翠娥,于晓明.网格和密度聚类算法在入侵检测中的应用[M].计算机应用, 2010,11: 3051-3052,3061.
[23]韩毅,蔡建湖,周根贵等.随机蛙跳算法的研究进展[J].计算机科学,2010,37(7): 16-19.
[24] M.Eusuff,K.Lansey, F.Pasha.Shuffled frog leaping algorithm:a memetic metaheuristic for discrete optimization.Engineering Optimization,2005,38(3):129-154
[25] Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved Shuffled Frog Leaping Algorithm for Continuous optimization problem [C]//IEEE Congress on Evolutionary Computation, Trondheim, 2009,5:2992-2995.
[26] Luo Xue-hui, Yang Ye, Li Xia. Solving TSP with Shuffled Frog-Leaping Algorithm [C] Eighth International Conference on Intelligent Systems Design and Applications, Kaohsiung, 2008 , VOL(3): 228-232.
[27] Eusuff M M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm [J]. Journal of Water Sources Planning and Management, 2003,129(3):210-225.
[28] E.Elbeltagi,T.Hegazy,D.Grierson.Comparison among five evolutionary based optimization algorithms[J].Aavanced Engineering Informatics,2005,19(1):43-53
[29] Thai-Hoang Huynh.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllersp[C]// IEEE International Conference on Industrial Technology , Chengdu,2008 , 1-6.
[30] Acampora. G, Cadenas. J.M, Loia. V, Mu?oz.E. Achieving memetic adaptability by means of fuzzy decision trees [C]// IEEE International Conference on Fuzzy Systems , Barcelona, 2010: 1– 8.
[31] Nguyen. Q.H,Ong. Y.S, Krasnogor.N. A study on the design issues of Memetic Algorithm [C]// IEEE International Conference on Evolutionary Computation, Singapore, 2009: 519– 524.
[32]郭秀萍,杨根科,吴智铭.一种混合自适应多目标Memetic算法[M].控制与决策,2006, 21(11):1234-1238.
[33]于万波.混沌的计算实验与分析[M].北京:科学出版社,2008.
[34]刘道华,原思聪,兰洋,马新建.混沌映射的粒子群优化方法[J].西安电子科技大学学报,2010,37(4):764-769.
[35]陈希孺,倪国熙,陈长顺.数理统计学教程[M].合肥:中国科学技术大学出版社,2009.
[36]赵鹏军.一种新的仿生优化算法及其改进[J].商洛学院学报:2009,23(2):19-21.
[37]况夯,罗军.基于遗传FCM算法的文本聚类[J].计算机应用,2009,29(2):558-560.
[38]杜长海,黄席樾,杨祖元等.改进的FCM聚类在交通时段自动划分中的应用[J].计算机工程与应用,2009,45(24):190-193.
[39]李春芳,庞雅静,钱丽璞等.半监督FCM聚类算法目标函数研究[J].计算机工程与应用,2009, 45(14): 128-132,135.
[40]李丽丽,刘希玉,庄波.基于模拟退火粒子群算法的FCM聚类方法[J].计算机应用,2008, 44 (30): 170-172.
[41]宋娇,葛临东.一种遗传模糊聚类算法及其应用[J].计算机应用,2008,28 (5):1197-1199.
[42] GAP Xin—bo,XIE Wei-xin.Advances in theory and applieations of fuzzy clustering [J].Chinese Science Bulletin,2000,45(11):950-972.
[43] Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M]. New York :Plenum Press,1981.
[44] Kennedy J, Eberhert R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks, 1995:1942-1948.8.
[45] Shi Y, Eberhart R. A modified particle swarm optimizer [C]// IEEE International Conference on Evolutionary Computation, Anch- orage, 1998,5:69- 73.
[46] Kennedy J, Eberhart R C, Shi Y. Swarm intelligence [M].SanFranciSco:Morgan Kaufman Publisher,2001.
[47] Shi Y, Eberhart R C.Particle Swarm Optimization: developments, applications and resources [C] //IEEE International Conference on Evolutionary Computation 2001 NJ: Piscataway, IEEE Press, 2001:81-86,101-106.
[48] Tang Hai-yan, Ding Bao, Qi Wei-gui. Research on traffic mode of elevator applied fuzzy C-mean clustering algorithm based on PSO [C]//IEEE International Conference on Measuring Technolo- gy and Mechatronics Automation, Zhangjiajie, Hunan,2009, 582– 585.
[49] Wei Jing, Hai Zhao, Chunhe Song, Dan Liu. A optimized particle filter based on PSO algorithm [C]// IEEE International Conferen- ce on BioMedical Information Engineering ,Future, 2009, 122-125.
[50]寇保华,杨涛,张晓今等.基于交叉变异的混合粒子群优化算法[J].计算机工程与应用,2007,43(17):85-88.
[51]宋书强,叶春明.一种新的自适应小生境粒子群优化算法[J].计算机仿真,2010,10:175-178,258.
[52]李丽丽,刘希玉,刘涛等.一种基于粒子群优化的FCM聚类方法[J].计算机应用技术,2008,1:89-92.
[53] Hsiang-Chuan Liu, Jeng-Ming Yih, Der-Bang Wu, Shin-Wu Liu. Fuzzy C-Mean Clustering Algorithms Based on Picard Iteration and Particle Swarm Optimization [C]//IEEE International Confer- ence on Education Technology and Training,Shanghai,2008, 2: 838– 842.
[54] Ziyang Zhen, Daobo Wang, Yuanyuan Liu. Improved Shuffled Frog Leaping Algorithm for Continuous optimization problem [C]//IEEE Congress on Evolutionary Computation, Trondheim, 2009,5:2992-2995.
[55]刘向东,沙秋夫,刘勇奎.基于粒子群算法的聚类分析[J].计算机工程,2006,32 (6):201-202.