一种基于萤火虫算法的模糊聚类方法

林睦纲，刘芳菊，童小娇

1.衡阳师范学院计算机科学系，湖南衡阳 421008

2.南华大学计算机科学与技术学院，湖南衡阳 421001

一种基于萤火虫算法的模糊聚类方法

林睦纲1，刘芳菊2，童小娇1

1.衡阳师范学院计算机科学系，湖南衡阳 421008

2.南华大学计算机科学与技术学院，湖南衡阳 421001

针对模糊C-均值聚类对初始值敏感、容易陷入局部最优的缺陷，提出了一种基于萤火虫算法的模糊聚类方法。该方法结合萤火虫算法良好的全局寻优能力和模糊C-均值算法的较强的局部搜索特性，用萤火虫算法优化搜索FCM的聚类中心，利用FCM进行聚类，有效地克服了模糊C-均值聚类的不足，同时增强了萤火虫算法的局部搜索能力。实验结果表明，该算法具有很好的全局寻优能力和较快的收敛速度，能有效地收敛于全局最优解，具有较好的聚类效果。

萤火虫算法；模糊聚类；模糊C-均值聚类

1 引言

聚类分析是指按照事物间的相似程度对事物进行区分和分类的过程，使得同一类簇的数据相似性尽量大，不同类簇之间的数据相似性尽量小。它是数据挖掘、模式识别和图像处理等研究的一种重要分析工具，已经广泛应用于数据分析、机器学习、图像分割、市场研究等领域中。聚类可分为硬聚类和模糊聚类，由于模糊聚类使用模糊隶属度来描述数据对象隶属各个类的不确定性，能够比较客观地反映现实世界；而且算法简便易行，具有较好聚类效果，因而在许多实际问题中获得广泛的运用。模糊C-均值聚类（Fuzzy C-Means clustering，FCM）算法是模糊聚类分析中非常有效的一种算法，算法简单，收敛速度快，局部搜索能力强。但它属于一种局部搜索算法，随机地选取聚类中心，以致其对初值和噪声较为敏感，容易陷入局部最优，而得不到全局最优解，从而限制了该算法应用[1]。近年来，随着各种群智能优化算法的提出和研究，许多学者运用蚁群算法[2-3]、微粒群算法[4-5]等来优化模糊聚类，克服FCM聚类算法的不足，取得较好的效果。

萤火虫算法（Firefly Algorithm，FA）是英国剑桥大学学者Yang Xin-she在2008年根据自然界中萤火虫通过发光吸引同伴的生物学特性行为而提出一种新的元启发式群智能算法[6-7]。算法有效地刻画了萤火虫发光亮度的变化和吸引度的大小，模拟了萤火虫根据同伴的亮度与吸引度大小进行搜索和移动、寻找同伴的原理，有效地实现了优化目标的目的。萤火虫算法自提出以来，已经受到越来越多学者的关注和研究，文献[7]利用萤火虫算法求解多模态优化问题，文献[8]应用萤火虫算法求解连续约束优化问题，文献[7-8]得出相同的结论：萤火虫算法在性能上优于遗传算法与粒子群算法。萤火虫算法不仅原理简单、参数少、易于实现；而且具有良好的全局寻优能力和一定的局部寻优能力，能快速地收敛于最优解的特点，目前已成功应用于路径规划[9]、工业优化[10-12]、经济调度[13-14]、图像处理[15]等领域。

本文尝试在模糊C-均值聚类算法中引入萤火虫算法，运用萤火虫算法优化搜索FCM算法的聚类中心，充分发挥萤火虫算法良好的全局寻优能力和模糊C-均值算法的较强的局部搜索特性，提出了一种基于萤火虫算法的模糊聚类算法。算法有效地克服了模糊C-均值聚类对初始值敏感、容易陷入局部最优的缺陷，同时也进一步增强了萤火虫算法的局部搜索能力。最后把新算法与传统的FCM算法和粒子群聚类算法通过数值实验进行比较，来验证算法的有效性。

2 FCM聚类分析

给定数据集X={x1，x2，…，xn}，其中xi是包含d个属性的数据对象（元素）(1≤i≤n)。聚类的目的就是将这n个对象划分为c个以V=(v1，v2，…，vc)为聚类中心的模糊聚类簇(2≤c≤n-1)。uij表示数据对象xi隶属于以vj为中心的类簇的隶属度，模糊聚类问题的目标函数[16]可表示为：

式中uij∈[0，1]；i=1，2，…，n；j=1，2，…，c，U=(uij)为隶属度矩阵，m是模糊权重系数，用来控制分类矩阵的模糊程度，一般取m≥1。

对于式（1）的优化问题结合式（2）的约束条件，应用Lagrange乘数法求解，可以得到uij和vj的取值公式为：

FCM算法就是求出使目标函数Jm(U，V)达到最小值的(U，V)。其基本思想是通过迭代更新(U，V)，使得目标函数最小。FCM算法的基本步骤可以描述如下：

步骤1设置参数与初始化，给定聚类数c和模糊权重系数m，设定迭代停止阈值ε，初始化聚类中心V。

步骤2根据式（3）计算隶属度U。

步骤3根据式（4）更新聚类中心V。

步骤4如更新后的聚类中心与原聚类中心距离小于或等于设定的迭代停止阈值ε，则算法停止并输出隶属度U和聚类中心V，否则，转向步骤2。

模糊C-均值算法是一种无监督的聚类方法，它通过在迭代过程中，不断使目标函数减少来达到最优的，迭代过程在本质上是用梯度下降的方法搜索最优解，它在很大的程度上依赖聚类中心的初始值，如果初始值选择不好，算法可能陷入局部最优解。因此它是一种局部搜索算法，存在对初始值和干扰敏感，易陷入局部最优等缺点。

3 萤火虫算法

自然界中，萤火虫利用其物种特有的闪光信号来定位并吸引异性，实现求偶交配和繁殖的目的。Yang Xin-she在文献[6]中根据萤火虫这种发光行为首次提出了一种随机优化的萤火虫算法，算法舍弃了萤火虫发光的一些生物学意义，基于下面三个理想的规则[6-7]：

（1）所有的萤火虫都是单性的，所以萤火虫吸引同伴，与性别无关。

（2）吸引力的大小跟发光的亮度成正比，对于任意两只萤火虫，亮度小的萤火虫被亮度大的萤火虫吸引而向亮度大的萤火虫方向移动。亮度和吸引度与萤火虫之间的距离成反比，随着距离的增加而减小。在一群萤火虫中，没有别的萤火虫的亮度比其明亮时，则该萤火虫将随机移动。

（3）萤火虫的亮度由给定问题的目标函数决定。

在萤火虫算法中，亮度和吸引度是两个关键要素。对于最大优化问题，最简单的情况下，特定位置s的萤火虫的亮度I(s)与目标函数f(s)成正比；对于最小化问题，亮度函数I(s)可取与遗传算法中适应度函数的方式相同。萤火虫的吸引度是相对的，它随着萤火虫i与萤火虫j的距离的变化而变化，同时吸引度也与吸收因子有关，由于光传输媒介对光的吸收，因而光的亮度随着与光源的距离增大而变小。吸引度β可定义为：

式中β0是最大吸引度，即r=0时的吸引度，γ是光的吸收因子。

萤火虫i被比其明亮的萤火虫j的吸引移动，其移动的位置由下式决定：

式中，si、sj为萤火虫i和j在解空间的位置；α为步长因子，它是区间[0，1]上的常数；rand为随机因子，它在区间[0，1]上服从均匀分布。式（6）右边的第一部分表示萤火虫当前位置，第二部分表示由于受其他萤火虫吸引而引起的位置变化量，体现了算法的全局寻优能力，第三部分表示萤火虫的局部随机搜索移动，体现了算法的局部寻优能力，因此萤火虫算法既具有较好的全局寻优能力，又具有一定的局部寻优能力。

萤火虫算法基本过程为：首先萤火虫群体随机分布在问题的解空间，每只萤火虫代表问题的一个可行解，萤火虫的亮度决定了解的优劣，萤火虫间的相对吸引度决定了萤火虫的移动方向和更新。比较萤火虫的亮度，亮度小的萤火虫被亮度大的萤火虫吸引，而向亮度大的萤火虫移动，按式（6）更新自己的位置，这样不断循环，寻找更优解，从而达到目标最优。

4 基于萤火虫算法的模糊聚类方法

由于FCM聚类算法采用的梯度下降的方法寻找目标函数的最优解，如果算法的初始值选择不当，算法会陷入局部最优，而不能逃离局部最优点。针对模糊C-均值聚类算法对初始值和干扰敏感，易陷入局部最优等不足，结合萤火虫算法良好的全局寻优能力和较强的局部寻优能力，收敛速度较快等优点。为此，本文把萤火虫算法与模糊C-均值聚类方法结合起来，提出了一种基于萤火虫算法的模糊聚类方法（FAFCM）。该算法的思路是：利用萤火虫算法寻找聚类中心，然后根据聚类中心进行模糊聚类，从而克服传统FCM算法对初始值敏感，易于陷入局部最优等缺陷。

在基于萤火虫算法的模糊聚类方法中，每一只萤火虫的位置用聚类中心表示，其位置为向量V=(v1，v2，…，vc)，其中vi为第i个类簇中心。萤火虫的亮度由模糊聚类的目标函数决定，根据萤火虫算法的特点，可定义萤火虫的亮度函数为：

式中xi(1≤i≤n)是数据集X={x1，x2，…，xn}的第i个的数据对象。

基于萤火虫算法的模糊聚类算法的基本步骤如下：

步骤1设置算法参数及初始化萤火虫群，设置萤火虫群的规模即萤火虫群中萤火虫数目N，最大吸引度β0，光的吸收因子γ，步长因子α，聚类簇数c，最大迭代次数maxT，以及k，m；初始化群中萤火虫的位置V1，V2，…，VN。

步骤2对于每个Vi根据式（3）计算隶属度矩阵Ui，然后根据亮度函数式（7）计算群中每只萤火虫的亮度I(Vi)；并根据亮度对群中的萤火虫进行升序排序。

步骤4输出最优解。

5 数值实验与分析

为了验证与分析本文算法（FAFCM）的有效性与可行性，选取UCI标准数据库中IRIS、Glass Identification两个数据集对算法进行测试，并且把实验结果与标准FCM算法、基于粒子群算法的模糊聚类（PSOFCM）进行比较。Iris数据集包括3类样本，共150个样本组成，每个样本包含4个属性，每类样本均为50个。Glass数据集包括6类样本，共214个样本组成，每个样本包含9个属性。文献[5]经过1 000次实验发现，IRIS数据集聚类问题目标函数是单极值的，而Glass数据集聚类问题目标函数有两个极值，是多极值的，因而选择这两个数据集进行数值实验具有代表性。在实验时，为避免每维数据幅值对聚类结果的影响，对这两个数据集的数据进行线性归一化预处理，使每一维数据的范围为[0，1]。

为了衡量聚类结果，在实验中主要比较下面三个指标：

（1）模糊聚类的目标函数

对模糊聚类来说，目标函数越小越好，聚类越精确，误差越小；划分系数和划分熵是常用的衡量聚类有效性函数，划分系数越大，聚类结果越好；划分熵越小，聚类效果越好。

在Matlab2011b平台下实现运行算法，算法的参数设置如下：模糊权重系数m=2，ISIR数据集聚类数为3类，最大迭代次数maxT=50，Glass数据集聚类数为6类，最大迭代次数maxT=300；对于FAFCM算法β0=1.0，γ=0.9，α=0.1，k=2。对于PSOFCM算法，惯性权重w=0.2，学习因子c1=c2=2.0。在测试中，FCM算法、PSOFCM算法与FAFCM算法分别运行30次最好的结果，实验结果如表1所示，迭代过程如图1，2所示。

表1 三种算法聚类有效性比较结果

图1 三种算法对IRIS数据集的聚类迭代过程

图2 三种算法对Glass数据集的聚类迭代过程

三种算法对每个数据集取不同的初始聚类中心分别运行30次，结果如表1所示，对于IRIS数据集，三种算法均能达到相同的结果；但对于Glass数据集，FCM算法选择不同的初始聚类中心，得到不同的目标函数值，而另外两种算法均得到相同的结果。从图1，2可以发现，FCM算法具有较快的收敛速度，FAFCM算法在收敛速度上比FCM算法略慢，但比PSOFCM算法要快很多。分析其原因是因为FAFCM算法和PSOFCM算法是一种随机搜索算法，具有较好的全局搜索能力，其能逃离局部极值而达到全局最优；而FCM算法用最速梯度下降的方法搜索，局部搜索能力较好，全局搜索能力较差，具有较快收敛速度。对于多极值问题，一旦陷入局部极值点，就无法跳出局部极值，而陷入局部最优。对于IRIS数据集聚类是单极值的，FCM算法不存在陷入局部收敛的情况，三种算法都能收敛到全局最优；而对于Glass数据集，FCM算法易陷入局部最优。FAFCM算法与PSOFCM算法比较，由于在萤火虫算法中，每个萤火虫几乎是相互独立的，而粒子群算法中的粒子之间有一定的依赖性，因此在最优解附近，萤火虫算法仍然有较好的寻优能力。综上所述，FAFCM算法不仅有较强的全局搜索能力，而且有较快的收敛速度，具有较好的综合性能。

6 结束语

本文结合萤火虫算法具有较好的全局搜索能力，较快的收敛速度等优点，提出基于萤火虫算法的模糊聚类算法。算法用萤火虫算法迭代搜索聚类中心进行模糊聚类，有效地克服了FCM算法对初始值敏感，易于陷入局部最优的缺陷。通过对具体标准数据集进行测试以及与标准FCM算法、PSO-FCM算法的比较，实验结果表明，基于萤火虫算法的模糊聚类算法能有效地收敛于全局最优解，具有较好的聚类效果，算法有效可行。但在实验中，也发现在设置萤火虫算法的步长因子、吸收因子和最大吸引度等参数时，由于设置为固定的常数，对算法全局搜索能力与局部搜索能力的平衡有一定影响，因此萤火虫算法参数自适应调整还有待进一步研究。

[1]Peng J M，Xia Y.A new theoretical framework for K-means clustering[C]//Chu Wesley，Lin TsauYoung.Foundation and Recent Advances in Data Mining.Berlin：Springer-Verlag，2005：79-96.

[2]Fei Wang，Dexian Zhang，Na Bao.Fuzzy document clustering based on ant colony algorithm[C]//Proceedings of the 6th International Symposium on Neural Networks：Advances in Neural Networks-Part II，2009：709-716.

[3]Runkler T A.Ant colony optimization of clustering moels[J]. International Journal of Intelligent Systems，2005，20（12）：1233-1261.

[4]Izakian H，Abraham A.Fuzzy C-means and fuzzy swarm for fuzzy clustering problem[J].Expert Systems with Applications，2011，38（3）：1835-1838.

[5]Li Chaoshun，Zhou Jianzhong，Kou Pangao，et al.A novel chaotic particle swarm optimization based fuzzy clustering algorithm[J].Neurocomputing，2012，83（4）：98-109.

[6]Yang Xinshe.Nature-inspired metaheuristic algorithms[M]. [S.l.]：Luniver Press，2008：83-96.

[7]Yang Xinshe.Firefly algorithms for multimodal optimization[C]//Proc of the 5th International Conference on Stochastic Algorithms：Foundations and Applications.Berlin：Springer-Verlag，2009：169-178.

[8]Łukasik S，Żak S.Firefly algorithm for continuous constrained optimization tasks[M]//Computational Collective Intelligence,Semantic Web，Social Networks and Multiagent Systems.Berlin Heidelberg：Springer，2009：97-106.

[9]刘鹏，刘弘，郑向伟，等.基于改进萤火虫算法的动态自动聚集路径规划方法[J].计算机应用研究，2011，28（11）：4146-4149.

[10]刘长平，叶春明.一种新颖的仿生群智能优化算法：萤火虫算法[J].计算机应用研究，2011，28（9）：3295-3297.

[11]Aungkulanon P，Chaiead N，Luangpaiboon P.Simulated manufacturing process improvement via particle swarm optimization and firefly algorithms[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists，Hong Kong，2011：1123-1128.

[12]Yousif A，Abdullanh A H，Nor S M，et al.Scheduling jobs on grid computing using firefly algorithm[J].Journal of Theoretical and Applied Information Technology，2011，33（2）：155-164.

[13]杨娇，叶春明.应用新型萤火虫算法求解Job-shop调度问题[J].计算机工程与应用，2013，49（11）：213-215.

[14]Apostolopoulos T，Vlachos A.Application of the firefly algorithm for solving the economic emissions load dispatch problem[J].International Journal of Combinatorics，2010，2011（9）：1-23.

[15]Tahereh H，Hakimeh V，Fariborz M.Non-linear grayscale image enhancement based on firefly algorithm[C]//Bijaya P，Swagatam D.Swarm，Evolutionary，and Memetic Computing.Berlin：Springer，2011：174-178.

[16]Bezdeck J C，Ehrlich R，Full W.FCM：the Fuzzy C-Means clustering algorithm[J].Computers and Geoscience，1984，23（2）：16-20.

LIN Mugang1,LIU Fangju2,TONG Xiaojiao1

1.Department of Computer Science,Hengyang Normal University,Hengyang,Hunan 421008,China
2.School of Computer Science and Technology,University of South China,Hengyang,Hunan 421001,China

For local optimum and initial sensitive problems with fuzzy C-means clustering,a new fuzzy clustering algorithm based on firefly algorithm is proposed.By incorporating the capacities of local and global search of firefly algorithm and FCM,taking the optimal clustering center of firefly algorithm as the initialized value of the FCM,and then clustering analysis is processed by FCM.The new algorithm overcomes FCM trapped local optimum and being sensitive to initial value effectively,and enhances the capacity of local search of firefly algorithm.The experimental results show that the new algorithm not only has better global search capacity and faster convergence speed but also has better clustering efficiency.

firefly algorithm;fuzzy clustering;fuzzy C-means clustering

A

TP391

10.3778/j.issn.1002-8331.1212-0004

LIN Mugang,LIU Fangju,TONG Xiaojiao.Fuzzy clustering algorithm based on firefly algorithm.Computer Engineering and Applications,2014,50（21）：35-38.

国家自然科学基金（No.11171095）；湖南省自然科学衡阳联合基金项目（No.10JJ8008）；湖南省科技计划项目（No.2010FJ4077）；湖南省重点学科建设项目（运筹学与控制论）；湖南省衡阳市科技发展计划项目（No.2014KJ21）。

林睦纲（1972—），男，博士研究生，讲师，CCF学生会员，研究方向为智能计算，计算机算法；刘芳菊（1974—），女，讲师，研究方向为智能计算，网络安全；童小娇（1962—），女，博士，教授，博士生导师，研究方向为最优化理论与计算方法，电力市场。E-mail：linmu710@163.com

2012-12-03

2013-03-11

1002-8331（2014）21-0035-04

CNKI出版日期：2013-03-19，http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.005.html