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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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 Yi1,3, YANG Hang2, LYU Ze-hua1, CHEN Chuan-bo1, ZOU Xiao-wei1   

  1. 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)

摘要: 模糊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

中图分类号: