一种基于禁忌搜索的全局最优化模糊聚类算法

doi:10.3969/j.issn.0372-2112.2019.02.005

电子学报 ›› 2019, Vol. 47 ›› Issue (2): 289-295.DOI: 10.3969/j.issn.0372-2112.2019.02.005

一种基于禁忌搜索的全局最优化模糊聚类算法

朱毅^1,3, 杨航², 吕泽华¹, 陈传波¹, 邹小威¹

1. 华中科技大学软件学院, 湖北武汉 430079;
2. 深圳市腾讯计算机系统有限公司, 广东深圳 518000;
3. 武汉华中时讯科技有限责任公司, 湖北武汉 430079

收稿日期:2017-05-26 修回日期:2018-10-26 出版日期:2019-02-25
- 通讯作者:
- 吕泽华
- 作者简介:
- 朱毅男,1987年出生,浙江温州人,2013年毕业于华中科技大学获得硕士学位,现为2013级华中科技大学软件学院博士生,主要从事大数据、深度学习等方面的研究;杨航男,1995生,河南安阳人,2017年毕业于华中科技大学软件学院,主要从事聚类分析,图像处理等方面的研究.
- 基金资助:
- 中央高校基本科研业务费资助 (No.HUST：2017KFYXJJ226）

A Global Optimization Fuzzy Clustering Algorithm Based on Tabu Search

ZHU Yi^1,3, YANG Hang², LYU Ze-hua¹, CHEN Chuan-bo¹, ZOU Xiao-wei¹

1. Huazhong University of Science & Technology, Wuhan, Hubei 430079, China;
2. Shenzhen Tencent Computer Systems Company Limited, Shenzhen, Guangdong 518000, China;
3. Sencent Technology(Wuhan) Co., Ltd. Wuhan, Hubei 430079, China

Received:2017-05-26 Revised:2018-10-26 Online:2019-02-25 Published:2019-02-25
- Supported by:
- supported by Fundamental Research Funds for the Central Universities (No.HUST：2017KFYXJJ226)

摘要/Abstract

摘要： 模糊C均值（FCM）算法是一种基于贪心思想的迭代算法，算法沿迭代序列收敛到一个极小值，但存在搜索能力弱、易陷入局部最优的缺点.本文提出了一种基于禁忌搜索的模糊聚类算法，该算法在一个解的邻域内使用禁忌搜索，并采用了基于FCM局部收敛性质的长期表禁忌策略，保证在不断移动搜索起点的同时避免重复搜索；其次使用混沌优化思想与动态步长策略来提升算法的全局搜索能力，以达到获取全局最优解的目的.实验结果表明，改进算法极大地提高了聚类准确率，并具有良好的稳定性，与群智算法和遗传算法的优化相比也具有一定的优势.

关键词: 模糊C均值(FCM)算法, 禁忌搜索, 全局最优

Abstract: 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.

Key words: fuzzy c-means, tabu search, global minimum

中图分类号:

TP319

朱毅, 杨航, 吕泽华, 等. 一种基于禁忌搜索的全局最优化模糊聚类算法[J]. 电子学报, 2019, 47(2): 289-295.

ZHU Yi, YANG Hang, LYU Ze-hua, et al. A Global Optimization Fuzzy Clustering Algorithm Based on Tabu Search[J]. Acta Electronica Sinica, 2019, 47(2): 289-295.

参考文献

[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 ISODATA clustering algorithms[J].IEEE Trans.Pattern Anal.Mach.Intell.(USA),1980,PAMI-2(1):1-8.
[3] 李凯,曹喆.一种基于神经网络的广义熵模糊聚类算法[J].电子学报,2016,44(8):1881-1886. Li Kai,Cao Zhe.A fuzzy clustering algorithm with generalized entropy based on neural network[J].Acta Electronica Sinica,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 and features selection[J].Journal of Computer Research and Development,2015,52(3):718-728.(in Chinese)
[5] Katayoon Ahmadi,Abbas Karimi,Babak Fouladi Nia,Thomas Desaive.Newtechnique for automatic segmentation of blood vessels in CT scan images of liver based on optimized fuzzy c-means method[J].Computational and Mathematical Methods in Medicine,2016,2016:1-8.
[6] 周双,冯勇,吴文渊.一种识别关联维数无标度区间的新方法[J].物理学报,2015,64(13):36-41. Zhou Shuang,Feng Yong,Wu Wen-Yuan.A novel method to 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 intuitionistic fuzzy kernel clustering algorithm[J].Journal on Communications,2015,36(5):78-84.(in Chinese)
[8] Zhongxing Zhang.Intrusion detection network based on fuzzy c-means and particle swarm optimization[A].IEEE Beijing Section.Proceedings of 2014 International Conference on Industrial Engineering and Information Technology[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 based fuzzy clustering algorithm[J].Computer Science,2016,43(8):267-272.(in Chinese)
[10] David Gabriel de Barros Franco,Maria Teresinha Arns Steiner.Clustering of solar energy facilities using a hybrid fuzzy 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 and retrieval inspired by fish swarm[J].Journal of Computer-Aided Design & Computer Graphics,2016,28(8):1373-1382+1392.(in Chinese)
[12] TRAN Dang Cong,WU Zhijian,WANG Zelin,DENG Changshou.A novel hybrid data clustering algorithm based 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 and links to artificial intelligence[J].Computers and Operations Research,1986,13(5):533-549.
[14] Fred Glover.Tabu search-part1[J].ORSA Journal on Computing,1989,1(2):190-206.
[15] Fred Glover.Tabu search-part2[J].ORSA Journal on Computing,1990,2(1):4-32.
[16] 朱喜华,李颖晖,李宁,范炳奎.基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J].通信学报,2014,35(2):182-189. Zhu Xihua,Li Yinghui,Li Ning,Fan Bingkui.Improved PSO algorithm based on swarm prematurely degree and nonlinear periodic oscillating strategy[J].Journal on Communications,2014,35(2):182-189.(in Chinese)
[17] Bezdek J.C.Convergence theory for fuzzy c-means:counterexamples and repairs[J],IEEE Trans Syst Man Cybern.1987,SMC-17:873-877.
[18] Hathaway R.J.Local convergence of the fuzzy c-means algorithm[J].Pattern Recognition,1986,6:477-480.

一种基于禁忌搜索的全局最优化模糊聚类算法

A Global Optimization Fuzzy Clustering Algorithm Based on Tabu Search

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	刘浩阳, 林耀进, 刘景华, 吴镒潾, 毛煜, 李绍滋. 由粗到细的分层特征选择[J]. 电子学报, 2022, 50(11): 2778-2789.
[2]	周果清, 王庆. 针对摄像机矩阵估计的增强连续禁忌搜索方法[J]. 电子学报, 2014, 42(12): 2422-2428.
[3]	闫峰, 刘淑芬, 冷煌. 基于转换的攻击图分析方法研究[J]. 电子学报, 2014, 42(12): 2477-2480.
[4]	钱洁, 郑建国. 引入逆学习的量子自适应禁忌搜索算法[J]. 电子学报, 2013, 41(6): 1069-1075.
[5]	陈晓峰, 姜慧研. 量子禁忌搜索算法的研究[J]. 电子学报, 2013, 41(11): 2161-2166.
[6]	许鹏飞, 苗启广, 李伟生, 张军英. 基于函数复杂度的自适应模拟退火和禁忌搜索新算法[J]. 电子学报, 2012, 40(6): 1218-1222.
[7]	王文彬;孙其博;赵新超;杨放春. 基于非均衡变异离散粒子群算法的QoS 全局最优Web服务选择方法[J]. 电子学报, 2010, 38(12): 2774-2779.
[8]	张昊;陶然;李志勇;蔡镇河. 基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究[J]. 电子学报, 2009, 37(7): 1628-1632.
[9]	王烨;李乐民;王晟. 考虑链路负载均衡和容量限制的WDM光传送网保护设计[J]. 电子学报, 2001, 29(10): 1319-1322.
[10]	陆明珠;万明习;施雨. 基于遗传算法的热疗温度场重构参数辨识方法[J]. 电子学报, 2000, 28(6): 131-134.