一种基于禁忌搜索的全局最优化模糊聚类算法
|
摘要
模糊C均值(FCM)算法是一种基于贪心思想的迭代算法,算法沿迭代序列收敛到一个极小值,但存在搜索能力弱、易陷入局部最优的缺点.本文提出了一种基于禁忌搜索的模糊聚类算法,该算法在一个解的邻域内使用禁忌搜索,并采用了基于FCM局部收敛性质的长期表禁忌策略,保证在不断移动搜索起点的同时避免重复搜索;其次使用混沌优化思想与动态步长策略来提升算法的全局搜索能力,以达到获取全局最优解的目的.实验结果表明,改进算法极大地提高了聚类准确率,并具有良好的稳定性,与群智算法和遗传算法的优化相比也具有一定的优势.
The fuzzy c-Means algorithm is a kind of iterative algorithms based on greedy algorithms. It converges to a local minimum value along the iteration sequence,yet it has the insufficient searching ability and can easily fall into local optimum solution. This paper,based on tabu search, introduces a fuzzy clustering algorithm. It uses tabu search in a solution's neighborhood and adopts the tabu strategy of long-term tabu lists based on the local convergence of FCM,which guarantees to move the search starting point constantly and avoids repeated searching. In addition, chaos optimization and dynamic step strategies are utilized to strengthen its global search ability in order to achieve global optimal solution. Experimental results show that this algorithm improves the accuracy of clustering considerably and has great stability. Compared with group-wise algorithm and genetic algorithm, this algorithm also has some advantages.
The fuzzy c-Means algorithm is a kind of iterative algorithms based on greedy algorithms. It converges to a local minimum value along the iteration sequence,yet it has the insufficient searching ability and can easily fall into local optimum solution. This paper,based on tabu search, introduces a fuzzy clustering algorithm. It uses tabu search in a solution's neighborhood and adopts the tabu strategy of long-term tabu lists based on the local convergence of FCM,which guarantees to move the search starting point constantly and avoids repeated searching. In addition, chaos optimization and dynamic step strategies are utilized to strengthen its global search ability in order to achieve global optimal solution. Experimental results show that this algorithm improves the accuracy of clustering considerably and has great stability. Compared with group-wise algorithm and genetic algorithm, this algorithm also has some advantages.
引文
[1] Zadeh L A. Similarity relations and fuzzy orderings[J].Inf. Sci.,1971,3(2):177-200.
[2]Bezdek J. C. Aconvergence theorem for the fuzzy ISODA-TA clustering algorithms[J]. IEEE Trans. Pattern Anal.M ach. Intell.(USA),1980,PAM I-2(1):1-8.
[3]李凯,曹喆.一种基于神经网络的广义熵模糊聚类算法[J].电子学报,2016,44(8):1881-1886.Li Kai,Cao Zhe. A fuzzy clustering algorithm w ith general-ized entropy based on neural netw ork[J]. Acta ElectronicaSinica,2016,44(8):1881-1886.(in Chinese)
[4]唐成华,刘鹏程,汤申生,谢逸.基于特征选择的模糊聚类异常入侵行为检测[J].计算机研究与发展,2015,52(3):718-728.Tang Chenghua,Liu Pengcheng,Tang Shensheng,Xie Yi.Anomaly intrusion behavior based on fuzzy clustering andfeatures selection[J]. Journal of Computer Research andDevelopment,2015,52(3):718-728.(in Chinese)
[5] Katayoon Ahmadi,Abbas Karimi,Babak Fouladi Nia,Thomas Desaive. New technique for automatic segmenta-tion of blood vessels in CT scan images of liver based onoptimized fuzzy c-means method[J]. Computational andM athematical M ethods in M edicine,2016,2016:1-8.
[6]周双,冯勇,吴文渊.一种识别关联维数无标度区间的新方法[J].物理学报,2015,64(13):36-41.Zhou Shuang,Feng Yong,Wu Wen-Yuan. A novel methodto identify the scaling region of correlation dimension[J].Acta Physica Sinica,2015,64(13):36-41.(in Chinese)
[7]余晓东,等.基于粒子群优化的直觉模糊核聚类算法研究[J].通信学报,2015,36(5):78-84.Yu Xiaodong,et al. Research on PSO-based intuitionisticfuzzy kernel clustering algorithm[J]. Journal on Communi-cations,2015,36(5):78-84.(in Chinese)
[8] Zhongxing Zhang. Intrusion detection network based onfuzzy c-means and particle sw arm optimization[A]. IEEEBeijing Section. Proceedings of 2014 International Confer-ence on Industrial Engineering and Information Technolo-gy[C]. IEEE Beijing Section,2014. 4.
[9]耿宗科,等.基于模糊c-means与自适应粒子群优化的模糊聚类算法[J].计算机科学,2016,43(8):267-272.Geng Zongke,et al. Fuzzy c-means and adaptive PSO basedfuzzy clustering algorithm[J]. Computer Science,2016,43(8):267-272.(in Chinese)
[10] David Gabriel de Barros Franco,Maria Teresinha ArnsSteiner. Clustering of solar energy facilities using a hybridfuzzy c-means algorithm initialized by metaheuristics[J]. Journal of Cleaner Production,2018,191:445-457.
[11]皇甫中民,等.鱼群启发的三维CAD模型聚类与检索[J].计算机辅助设计与图形学学报,2016,28(8):1373-1382+1392.Huangfu Zhongmin,et al. 3D CAD model clustering andretrieval inspired by fish sw arm[J]. Journal of Computer-Aided Design&Computer Graphics,2016,28(8):1373-1382+1392.(in Chinese)
[12] TRAN Dang Cong,WU Zhijian,WANG Zelin,DENGChangshou. A novel hybrid data clustering algorithmbased on artificial bee colony algorithm and k-means[J].Chinese Journal of Electronics,2015,24(4):694-701.
[13] Fred Glover. Future paths for integer programming andlinks to artificial intelligence[J]. Computers and Opera-tions Research,1986,13(5):533-549.
[14] Fred Glover. Tabu search-part1[J]. ORSA Journal onComputing,1989,1(2):190-206.
[15] Fred Glover. Tabu search-part2[J]. ORSA Journal onComputing,1990,2(1):4-32.
[16]朱喜华,李颖晖,李宁,范炳奎.基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J].通信学报,2014,35(2):182-189.Zhu Xihua,Li Yinghui,Li Ning,Fan Bingkui. ImprovedPSO algorithm based on sw arm prematurely degree andnonlinear periodic oscillating strategy[J]. Journal onCommunications,2014,35(2):182-189.(in Chinese)
[17]Bezdek J. C. Convergence theory for fuzzy c-means:coun-terexamples and repairs[J],IEEE Trans Syst M an Cy-bern. 1987,SM C-17:873-877.
[18]Hathaway R. J. Local convergence of the fuzzy c-meansalgorithm[J]. Pattern Recognition,1986,6:477-480.
[2]Bezdek J. C. Aconvergence theorem for the fuzzy ISODA-TA clustering algorithms[J]. IEEE Trans. Pattern Anal.M ach. Intell.(USA),1980,PAM I-2(1):1-8.
[3]李凯,曹喆.一种基于神经网络的广义熵模糊聚类算法[J].电子学报,2016,44(8):1881-1886.Li Kai,Cao Zhe. A fuzzy clustering algorithm w ith general-ized entropy based on neural netw ork[J]. Acta ElectronicaSinica,2016,44(8):1881-1886.(in Chinese)
[4]唐成华,刘鹏程,汤申生,谢逸.基于特征选择的模糊聚类异常入侵行为检测[J].计算机研究与发展,2015,52(3):718-728.Tang Chenghua,Liu Pengcheng,Tang Shensheng,Xie Yi.Anomaly intrusion behavior based on fuzzy clustering andfeatures selection[J]. Journal of Computer Research andDevelopment,2015,52(3):718-728.(in Chinese)
[5] Katayoon Ahmadi,Abbas Karimi,Babak Fouladi Nia,Thomas Desaive. New technique for automatic segmenta-tion of blood vessels in CT scan images of liver based onoptimized fuzzy c-means method[J]. Computational andM athematical M ethods in M edicine,2016,2016:1-8.
[6]周双,冯勇,吴文渊.一种识别关联维数无标度区间的新方法[J].物理学报,2015,64(13):36-41.Zhou Shuang,Feng Yong,Wu Wen-Yuan. A novel methodto identify the scaling region of correlation dimension[J].Acta Physica Sinica,2015,64(13):36-41.(in Chinese)
[7]余晓东,等.基于粒子群优化的直觉模糊核聚类算法研究[J].通信学报,2015,36(5):78-84.Yu Xiaodong,et al. Research on PSO-based intuitionisticfuzzy kernel clustering algorithm[J]. Journal on Communi-cations,2015,36(5):78-84.(in Chinese)
[8] Zhongxing Zhang. Intrusion detection network based onfuzzy c-means and particle sw arm optimization[A]. IEEEBeijing Section. Proceedings of 2014 International Confer-ence on Industrial Engineering and Information Technolo-gy[C]. IEEE Beijing Section,2014. 4.
[9]耿宗科,等.基于模糊c-means与自适应粒子群优化的模糊聚类算法[J].计算机科学,2016,43(8):267-272.Geng Zongke,et al. Fuzzy c-means and adaptive PSO basedfuzzy clustering algorithm[J]. Computer Science,2016,43(8):267-272.(in Chinese)
[10] David Gabriel de Barros Franco,Maria Teresinha ArnsSteiner. Clustering of solar energy facilities using a hybridfuzzy c-means algorithm initialized by metaheuristics[J]. Journal of Cleaner Production,2018,191:445-457.
[11]皇甫中民,等.鱼群启发的三维CAD模型聚类与检索[J].计算机辅助设计与图形学学报,2016,28(8):1373-1382+1392.Huangfu Zhongmin,et al. 3D CAD model clustering andretrieval inspired by fish sw arm[J]. Journal of Computer-Aided Design&Computer Graphics,2016,28(8):1373-1382+1392.(in Chinese)
[12] TRAN Dang Cong,WU Zhijian,WANG Zelin,DENGChangshou. A novel hybrid data clustering algorithmbased on artificial bee colony algorithm and k-means[J].Chinese Journal of Electronics,2015,24(4):694-701.
[13] Fred Glover. Future paths for integer programming andlinks to artificial intelligence[J]. Computers and Opera-tions Research,1986,13(5):533-549.
[14] Fred Glover. Tabu search-part1[J]. ORSA Journal onComputing,1989,1(2):190-206.
[15] Fred Glover. Tabu search-part2[J]. ORSA Journal onComputing,1990,2(1):4-32.
[16]朱喜华,李颖晖,李宁,范炳奎.基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J].通信学报,2014,35(2):182-189.Zhu Xihua,Li Yinghui,Li Ning,Fan Bingkui. ImprovedPSO algorithm based on sw arm prematurely degree andnonlinear periodic oscillating strategy[J]. Journal onCommunications,2014,35(2):182-189.(in Chinese)
[17]Bezdek J. C. Convergence theory for fuzzy c-means:coun-terexamples and repairs[J],IEEE Trans Syst M an Cy-bern. 1987,SM C-17:873-877.
[18]Hathaway R. J. Local convergence of the fuzzy c-meansalgorithm[J]. Pattern Recognition,1986,6:477-480.