第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dee.2015 D0:10.11992.tis.201505043 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.006.html 融合并行混沌萤火虫算法的K-调和均值聚类 朱书伟，周治平，张道文 (江南大学物联网工程学院，江苏无锡214122) 摘要：针对K-调和均值算法易陷于局部最优的缺点，提出一种基于改进萤火虫算法(firefly algorithm,FA)的K-调 和均值聚类算法。将基于FA的粗搜索与基于并行混沌优化FA的精细搜索相结合，其中精细搜索部分首先通过FA 搜索到当前最优解及次优解，然后通过改进的1 ogistic映射与并行混沌优化策略产生混沌序列在其附近直接搜索，以 增强算法的寻优性能。最终，将这种改进的FA用于K调和均值算法聚类中心的优化。实验结果表明：该算法不但 对几种测试函数具有更高的搜索精度，而且对6种数据集的聚类结果均有一定的改善，有效地抑制了K-调和均值算 法陷于局部最优的问题，提高了聚类准确性和稳定性。 关键词：K调和均值：局部最优：莹火虫算法；聚类：并行混沌优化：混沌局部搜索：映射模型：种群多样性 中图分类号：TP18文献标志码：A文章编号：1673-4785(2015)06-0872-09 中文引用格式：朱书伟，周治平，张道文.融合并行混沌萤火虫算法的K-调和均值聚类[J].智能系统学报，2015,10(6)：872-880. 英文引用格式：ZHU Shuwei,ZHOU Zhiping,ZHANG Daowen.K-harmonic means clustering merged with parallel chaotic firefly algorithm[J].CAAI Transactions on Intelligent Systems,2015,10(6):872-880. K-harmonic means clustering merged with parallel chaotic firefly algorithm ZHU Shuwei,ZHOU Zhiping,ZHANG Daowen (School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China) Abstract:The K-harmonic means algorithm (KHM)has the disadvantage of easily falling into a local optimum.To solve this problem,we propose a hybrid KHM based on an improved firefly algorithm(FA).In this paper,we com- bined raw FA-based searching with parallel chaotic FA-based elaborate searching.In the elaborate searching,we found the current best and second-best solutions using the FA,then we used an improved logistic map model com- bined with parallel chaotic optimization to search this area in order to enhance the searching ability of the algorithm. Finally,we used the improved FA to optimize the cluster centers obtained by the KHM.Experimental results dem- onstrate that the proposed algorithm not only had higher search precision for several test functions,but also im- proved the clustering accuracy and stability of six datasets,effectively avoiding being trapped into a local optimum. Keywords:K-harmonic means;local optimum;firefly algorithm;clustering;parallel chaotic optimization;chaotic local search;map model;diversity of population 聚类分析是一种广泛使用的数据分析方法，一 最经典且使用最为广泛的聚类算法，其过程简单快 直被应用于多个领域，特别是在数据挖掘、模式识 捷，容易实现。为了克服K-means对初始聚类中心 别、图像处理等领域应用十分广泛。K-meanst是 敏感的缺陷，Zhang等)于1999年提出一种K-调和 均值(K-harmonic means,KHM)算法，具有较高的稳 收稿日期：2015-05-27.网络出版日期：2015-11-10. 定性、收敛速度快，但由于其与K-means同样基于划 基金项目：江苏省产学研联合创新资金-前瞻性联合研究基金资助项目 (BY2013015-33). 分的原理，仍存在易陷于局部最优的问题。 通信作者：朱书伟.E-mail:6131905056@ip-jiangnan.cdu.cm 目前，对于KHM算法的研究主要是结合智能第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１５０５０４３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１０．１３５４．００６．ｈｔｍｌ 融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 朱书伟，周治平，张道文 （江南大学 物联网工程学院，江苏 无锡 ２１４１２２） 摘 要：针对 Ｋ⁃调和均值算法易陷于局部最优的缺点，提出一种基于改进萤火虫算法（ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＦＡ）的 Ｋ⁃调 和均值聚类算法。 将基于 ＦＡ 的粗搜索与基于并行混沌优化 ＦＡ 的精细搜索相结合，其中精细搜索部分首先通过 ＦＡ 搜索到当前最优解及次优解，然后通过改进的 ｌｏｇｉｓｔｉｃ 映射与并行混沌优化策略产生混沌序列在其附近直接搜索，以 增强算法的寻优性能。 最终，将这种改进的 ＦＡ 用于 Ｋ⁃调和均值算法聚类中心的优化。 实验结果表明：该算法不但 对几种测试函数具有更高的搜索精度，而且对 ６ 种数据集的聚类结果均有一定的改善，有效地抑制了 Ｋ⁃调和均值算 法陷于局部最优的问题，提高了聚类准确性和稳定性。 关键词：Ｋ⁃调和均值；局部最优；萤火虫算法；聚类；并行混沌优化；混沌局部搜索；映射模型；种群多样性 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０８７２⁃０９ 中文引用格式：朱书伟，周治平， 张道文． 融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类［Ｊ］． 智能系统学报， ２０１５， １０（６）： ８７２⁃８８０． 英文引用格式：ＺＨＵ Ｓｈｕｗｅｉ， ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＺＨＡＮＧ Ｄａｏｗｅｎ． Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｒｇｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ８７２⁃８８０． Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｒｇｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ ＺＨＵ Ｓｈｕｗｅｉ， ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＺＨＡＮＧ Ｄａｏｗｅｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ （ＫＨＭ） ｈａｓ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅ ｏｆ ｅａｓｉｌｙ ｆａｌｌｉｎｇ ｉｎｔｏ ａ ｌｏｃａｌ ｏｐｔｉｍｕｍ． Ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ， ｗｅ ｐｒｏｐｏｓｅ ａ ｈｙｂｒｉｄ ＫＨＭ ｂａｓｅｄ ｏｎ ａｎ ｉｍｐｒｏｖｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ （ＦＡ）． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｃｏｍ⁃ ｂｉｎｅｄ ｒａｗ ＦＡ⁃ｂａｓｅｄ ｓｅａｒｃｈｉｎｇ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ＦＡ⁃ｂａｓｅｄ ｅｌａｂｏｒａｔｅ ｓｅａｒｃｈｉｎｇ． Ｉｎ ｔｈｅ ｅｌａｂｏｒａｔｅ ｓｅａｒｃｈｉｎｇ， ｗｅ ｆｏｕｎｄ ｔｈｅ ｃｕｒｒｅｎｔ ｂｅｓｔ ａｎｄ ｓｅｃｏｎｄ⁃ｂｅｓｔ ｓｏｌｕｔｉｏｎｓ ｕｓｉｎｇ ｔｈｅ ＦＡ， ｔｈｅｎ ｗｅ ｕｓｅｄ ａｎ ｉｍｐｒｏｖｅｄ ｌｏｇｉｓｔｉｃ ｍａｐ ｍｏｄｅｌ ｃｏｍ⁃ ｂｉｎｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｏ ｓｅａｒｃｈ ｔｈｉｓ ａｒｅａ ｉｎ ｏｒｄｅｒ ｔｏ ｅｎｈａｎｃｅ ｔｈｅ ｓｅａｒｃｈｉｎｇ ａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｆｉｎａｌｌｙ， ｗｅ ｕｓｅｄ ｔｈｅ ｉｍｐｒｏｖｅｄ ＦＡ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｏｂｔａｉｎｅｄ ｂｙ ｔｈｅ ＫＨＭ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍ⁃ ｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｎｏｔ ｏｎｌｙ ｈａｄ ｈｉｇｈｅｒ ｓｅａｒｃｈ ｐｒｅｃｉｓｉｏｎ ｆｏｒ ｓｅｖｅｒａｌ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ， ｂｕｔ ａｌｓｏ ｉｍ⁃ ｐｒｏｖｅｄ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｃｃｕｒａｃｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ｓｉｘ ｄａｔａｓｅｔｓ， ｅｆｆｅｃｔｉｖｅｌｙ ａｖｏｉｄｉｎｇ ｂｅｉｎｇ ｔｒａｐｐｅｄ ｉｎｔｏ ａ ｌｏｃａｌ ｏｐｔｉｍｕｍ． Ｋｅｙｗｏｒｄｓ： Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ； ｌｏｃａｌ ｏｐｔｉｍｕｍ； ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ； ｃｌｕｓｔｅｒｉｎｇ； ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ； ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ； ｍａｐ ｍｏｄｅｌ； ｄｉｖｅｒｓｉｔｙ ｏｆ ｐｏｐｕｌａｔｉｏｎ 收稿日期：２０１５⁃０５⁃２７． 网络出版日期：２０１５⁃１１⁃１０． 基金项目：江苏省产学研联合创新资金－前瞻性联合研究基金资助项目 （ＢＹ２０１３０１５⁃３３）． 通信作者：朱书伟． Ｅ⁃ｍａｉｌ：６１３１９０５０５６＠ ｖｉｐ．ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ． 聚类分析是一种广泛使用的数据分析方法，一 直被应用于多个领域，特别是在数据挖掘、模式识 别、图像处理等领域应用十分广泛。 Ｋ⁃ｍｅａｎｓ ［１］ 是 最经典且使用最为广泛的聚类算法，其过程简单快 捷，容易实现。 为了克服 Ｋ⁃ｍｅａｎｓ 对初始聚类中心 敏感的缺陷，Ｚｈａｎｇ 等［２］于 １９９９ 年提出一种 Ｋ⁃调和 均值（Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ， ＫＨＭ）算法，具有较高的稳 定性、收敛速度快，但由于其与 Ｋ⁃ｍｅａｎｓ 同样基于划 分的原理，仍存在易陷于局部最优的问题。 目前，对于 ＫＨＭ 算法的研究主要是结合智能