基于最优类中心扰动的萤火虫聚类算法*

赵 杰，雷秀娟，吴振强

(陕西师范大学计算机科学学院，陕西 西安 710062)

1 引言

聚类是一种常用的数据分析和数据挖掘方法。随着聚类分析在数据挖掘、模式识别、机器学习、统计学等领域应用的不断扩展，相关领域的学者越来越重视对聚类算法的研究。传统聚类算法大致可以分为以下几个类别：基于划分的方法和基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法[1,2]。群智能优化算法是近十几年发展起来的受动物群体智能启发的算法，由于具有简单性、分布式、鲁棒性、良好的可扩展性、广泛的适用性等特点[1]，受到越来越多学者的关注和研究，被广泛应用于聚类算法中，如遗传算法[3]、蚁群算法[4]、人工蜂群优化算法[5]、人工鱼群优化算法[6]、粒子群优化算法[7]，成为聚类的一类新兴方法。

萤火虫算法FA(Firefly Algorithm)是受自然界中萤火虫之间通过发光相互沟通、进行信息交流这种生物学特性的启发，由剑桥学者Yang Xin-she在2008年提出[8,9]，是比较新的一种群智能优化算法，已成功应用到优化问题[10,11]、图像处理[12,13]、路径规划[14]、旅行商问题[15]、聚类[16～18]等多个领域。

用FA聚类过程中，发现存在收敛速度较慢、容易在局部最优值或者全局最优值附近反复振荡的问题，据此，本文对萤火虫的移动方式和随机扰动方式做了改进，基于最优类中心扰动提出了一种改进萤火虫算法IFA(Improved Firefly Algorithm)的聚类算法，选择三个标准UCI数据集做聚类，验证了该算法的可行性及有效性。和K均值(K-means)、粒子群优化PSO(Particle Swarm Optimization)算法、FA聚类结果比较的结果表明，基于最优类中心扰动的萤火虫聚类算法能找到更好的解，有更好的收敛效果。

2 FA的基本理论

2.1 FA的仿生原理

萤火虫通过荧光素发生的复杂生化反应进行发光，借助发光捕食、求偶、警示以及相互交流等，萤火虫算法就是模拟萤火虫的发光行为提出的启发式随机优化算法。在该算法中，有两个重要的参数：萤火虫的亮度和吸引度。为了简易描述FA算法，通常遵循下面三个理想化的规则[8]：

(1) 萤火虫不分雌雄，它们之间相互吸引与性别无关；

(2) 吸引度与亮度成正比，亮度低的萤火虫被吸引向亮度高的萤火虫移动，亮度最大的萤火虫随机移动，吸引度和亮度与距离成反比，随着距离的增大吸引度和亮度减小；

(3) 萤火虫的亮度由具体的求解问题的目标函数值决定。

FA算法仿生原理是：用搜索空间中的点模拟萤火虫个体，将搜索和优化过程模拟成萤火虫个体之间相互吸引和移动的过程，用求解问题的目标函数值来衡量萤火虫所处位置的优劣，将个体的适者生存过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程[19]。

2.2 FA算法的描述

萤火虫的亮度和目标函数值相关，体现了萤火虫所处位置的优劣，位置越佳目标值越好，亮度越高，亮度高的萤火虫吸引亮度低的萤火虫向自己移动，移动的大小由吸引度来衡量，可见，亮度决定移动方向，吸引度决定移动大小。

在算法的实现过程有以下几个定义[8,11]：

定义1荧光亮度:

I∝f(xi), 1≤i≤n

(1)

I=I0×e-γ rij

(2)

其中，xi表示第i个萤火虫的位置，f(xi)代表具体问题的目标函数值；I0为萤火虫的最大荧光亮度，即自身(r=0处)的荧光亮度，与目标函数值相关；γ为光强吸收系数，因为荧光会随着距离的增加和传播媒介吸收逐渐减弱，所以设置光强吸收系数体现此特性，可设为常数，rij为萤火虫i和j之间的距离：

(3)

其中，d表示数据维度，xi,k表示萤火虫i的第k个数据分量。

定义2吸引度:

(4)

其中，β0为最大吸引度，即光源处(r=0)的吸引度；γ、rij意义同上。

定义3萤火虫i被吸引向萤火虫j移动的位置更新:

(5)

其中，xi、xj表示萤火虫i和j的位置；α为随机化参数，是[0,1]上的常数；εi是服从高斯分布或均匀分布的随机因子，通常简单地用rand-0.5来表示，rand为[0,1]上服从均匀分布的随机数；αεi是扰动项，避免算法过早陷入局部最优。目前最亮的萤火虫xbest，没有萤火虫能够吸引它，它的位置更新就变成了：

xbest=xbest+αεi

(6)

其中，xbest代表当前最亮的萤火虫所处位置，α含义同上。

文献[8]中详细描述了FA算法，算法伪代码描述如下：

初始化目标函数f(x),x=(x1,…,xd)T;

初始化萤火虫种群xi(i=1,2,…,n)，n为萤火虫种群数目;

萤火虫i在xi处的亮度Ii由f(xi)决定;

初始化算法其他参数：最大吸引度β0、光强吸收系数γ、步长因子α。

while(未到最大迭代次数)

for i=1:n

for j=1:n

if(Ii

萤火虫i按照式(5)向萤火虫j移动;

end if

按照式(4)更新吸引度，按照公式(2)更新亮度;

end for j

end for i

对萤火虫进行排序，找出当前全局最优解;

end while

结果处理;

3 基于最优类中心扰动的萤火虫聚类算法

3.1 基于最优类中心扰动的萤火虫聚类算法思想

本文对萤火虫的移动方式和随机扰动方式做了改进，提出了一种基于最优类中心扰动的萤火虫聚类算法，算法的基本思路是：用萤火虫的位置代表聚类中心，通过萤火虫之间的相互吸引和移动来寻找最优的聚类中心，从而找到最优的聚类，目标是使所有样本到相应聚类中心的距离之和最小，聚类准则函数[1]为：

(7)

其中，m为聚类数目，Zk代表第k个聚类的中心，d(Xi,Zk)为样本Xi到对应聚类中心的距离。

d(Xi,Zk)=‖Xi-Zk‖

(8)

萤火虫生物特性在改进FA聚类算法中所起作用的对应关系见表1。

Table 1 Corresponding relation of fireflies biologicalcharacteristics in improved FA clustering algorithm

3.2 基于最优类中心扰动的萤火虫聚类算法改进之处

改进1用聚类准则函数Jc的值代表萤火虫亮度I，即:

I=Jc

(9)

萤火虫的亮度和目标函数值相关，体现了萤火虫所处位置的优劣，位置越佳目标值越好，亮度越高[8,19]。式(2)能够满足上述条件，但计算量较大，因此本文提出的基于改进FA的聚类算法中直接用聚类准则函数Jc的值来代表亮度，满足条件的同时降低算法的复杂性。

改进2对萤火虫位置更新式(5)进行了改进：

α*rand*(cc-xi)

(10)

其中，cc为目前最优聚类的类中心，β0、γ、α、rand意义同公式(5)。

(11)

其中，ni是第Γi聚类中的数据个数，y代表数据数值。

在基本FA算法中，萤火虫被吸引向比较亮的萤火虫移动，扰动项α(rand-0.5)加大了算法搜索区域，避免过早陷入局部最优，增加了算法的局部寻优能力，但导致算法整体收敛速度较慢，稳定性比较差，当待处理问题目标函数值比较大的时候，扰动作用不明显，容易使算法在局部最优值附近波动。本文将扰动项改进为α*rand*(cc-xi)，基于最优类中心随机扰动。实验结果表明，改进之后，算法收敛速度和稳定性明显改善。

改进3最亮的萤火虫按照式(12)进行移动:

xbest=xbest+α*rand*(cc-xbest)

(12)

其中，xbest代表目前最亮的萤火虫所处位置，cc含义同上。

在FA算法中，最亮的萤火虫随机移动，容易导致算法在局部最优值或全局最优值附近反复振荡、收敛速度较慢、优化精度降低，按照式(12)改进之后，能有效地避免上述现象。

3.3 基于最优类中心扰动的萤火虫聚类算法步骤

步骤1设置算法参数：聚类个数C、萤火虫个数N、最大吸引度β0、光强吸收系数γ、步长因子α、最大迭代次数maxiter；

步骤2初始化萤火虫的位置(从数据集中随机选出C个作为初始萤火虫位置)，按照式(8)计算每个样本点到各个聚类中心的距离，依此将样本点划分到离它最近的那个聚类中心所在的类中；

步骤3根据步骤2初始聚类的结果，利用式(9)计算萤火虫的亮度，找出并记录最亮萤火虫的亮度、位置和聚类结果；

步骤4比较萤火虫的亮度，如果Ii>Ij，表示萤火虫j的聚类准则函数值较小，所处位置较好，吸引萤火虫i向自己移动，按照式(4)计算萤火虫j对萤火虫i的吸引度，按照式(10)和式(12)来更新萤火虫i的位置；

步骤5萤火虫位置更新完成后，重新进行聚类，并更新萤火虫的亮度，找出并记录最亮萤火虫的亮度、位置和聚类结果；

步骤6达到最大迭代次数则停止算法，否则转到步骤3；

步骤7输出结果。

4 仿真实验及评价

为检验上述算法的正确性和有效性，在Matlab平台上对其进行了仿真实验(Matlab 2011b、内存4 GB、CPU为3.10 GHz)。

4.1 参数设置

文献[10]对萤火虫算法中的参数做了实验对比，本文中β0、γ的取值采用文献[10]中的结果，即β0=1，γ=0.8；最大迭代次数maxiter=150。

对参数α的取值，文献[10]中的取值为0.01，在实验过程中发现，α=0.01时算法的收敛效果不是很好，找到的最优解不是很理想，因此，本文对α的取值重新做了实验比较，用IRIS数据集，运行20次取平均值，分析结果如图1所示。

Figure 1 Value of clustering criterion function for varying step factor图1 步长因子对应的聚类准则函数值

由图1可以看出，当α=0.06时，聚类准则函数的最小值和平均值均达到最优，因此在仿真实验过程中步长因子的取值为0.06。

4.2 收敛性分析

为了验证基于IFA的聚类算法的可行性、有效性和收敛性，把基于IFA的聚类算法和FA算法、K-means算法、PSO算法做了对比，图2、图3和图4分别显示了在IRIS数据集上四种方法聚类的收敛曲线、基于IFA和K-means算法聚类准则函数最优值比较以及基于IFA、FA聚类后IRIS数据集样本分布图。由图2可以看出，基于IFA的聚类算法收敛快而且比较平稳，求解出的聚类准则函数值明显优于FA和PSO聚类方法。K-means聚类算法[20～22]是一种比较经典的聚类算法，图2中IFA算法和K-means算法的收敛曲线比较接近，因此进一步比较了二者的最优值，使用IRIS数据集，程序运行20次，运行结果如图3所示；从图3a可以看出，K-means聚类算法由于对初始聚类中心比较敏感，导致其稳定性较差，求出的最优值波动比较明显，从图3b可以看出，基于IFA算法的聚类算法比较稳定，求得的最优值优于K-means聚类算法。

Figure 2 Convergence curve of clustering for IRIS data set图2 IRIS数据集聚类收敛曲线

Figure 3 Comparison of optimum values between IFA and K-means图3 IFA和K-means聚类准则函数最优值比较

为了更好地对比基于IFA的聚类算法和基于FA的聚类算法的聚类效果，绘制了基于IFA(图4a)、FA(图4b)聚类后IRIS数据集样本分布图。由于IRIS数据集样本具有四个属性，因此在绘图之前，先对IRIS数据集数据进行了PCA处理，提取两个主要成分进行绘图，效果如图4所示。由图4可以看出，改进之后，聚类错误个数明显减少，聚类效果优于改进之前。

Figure 4 Sample distribution of clustering for IRIS data set based on IFA and FA图4 基于IFA、FA聚类后IRIS数据集样本分布图

4.3 聚类结果分析

本文从UCI标准数据集中选出了三个数据集IRIS(表2)、SONAR(表3)、WINE(表4)做了实验。IRIS数据集包括三类共150个样本，每个样本有四个属性；SONAR数据集包括两类共208个样本，每个样本有60个属性；WINE数据集包括三类共178个样本，每个样本有13个属性。K-means和PSO的数据来自文献[17]，FA和IFA数据为程序运行20次的平均值。

Table 2 Comparison of clustering criterion function andclustering error between different methods for IRIS data set

Table 3 Comparison of clustering criterion function andclustering error between different methods for SONAR data set

Table 4 Comparison of clustering criterion function andclustering error between different methods for WINE data set

由表2～表4可以看出，基于IFA的聚类算法能够找到较好的聚类准则函数值，平均值和最优值相差比较小，说明算法比较稳定，错误率和K-means、PSO、FA三种方法相比也明显降低；K-means聚类算法由于对初始聚类中心比较敏感，导致算法不够稳定，最优值波动比较明显，其平均值和错误率普遍偏高；基本PSO算法和FA算法都属于群智能优化算法，具有群体智能和较好的全局寻优能力，求出的最优值和错误率也比K-means的要好，但是由于算法本身存在不足，导致求出的最优值和错误率比IFA算法要差。同时，从表中也可以看出，同一种聚类方法在不同的数据集上聚类产生的效果也不全相同，也就是说，聚类结果和数据类型及维度也存在一定的关系，因此，在进行聚类评价的时候要综合考虑聚类准则函数、错误率以及数据特点等各方面因素。

5 结束语

本文提出了基于最优类中心扰动的萤火虫聚类算法，有效地克服了FA算法收敛较慢、易于在局部最优值或全局最优值附近反复振动的缺陷，通过对三个标准数据集进行聚类以及和FA、K-means、基本PSO算法进行比较，仿真结果表明，基于最优类中心扰动的萤火虫聚类算法具有较好的收敛性和稳定性，聚类效果较好。但是，在实验中，光强吸收系数和步长因子都是设定的常数，把基于最优类中心扰动的萤火虫聚类算法应用到不同规模的问题中时，算法表现出的全局搜索能力和稳定性还有一定的差异，因此这两个系数的自适应特性还有待进一步研究。

[1] Lei Xiu-juan. Swarm intelligent optimization algorithms and their applications[M]. Beijing:Science Press, 2012. (in Chinese)

[2] Sun Ji-gui, Liu Jie, Zhao Lian-yu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61. (in Chinese)

[3] Maulik U, Bandyopadhyay S. Genetic algorithm-based clustering technique[J]. Pattern Recognition, 2000, 33(9):1455-1465.

[4] Kao Y, Cheng K. An ACO-based clustering algorithm[C]∥Proc of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, 2006:340-347.

[5] Karaboga D, Ozturk C. A novel clustering approach:Artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1):652-657.

[6] Yongming C, Mingyan J, Dongfeng Y. Novel clustering algorithms based on improved artificial fish swarm algorithm[C]∥Proc of the 6th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’09), 2009:141-145.

[7] Van Der Merwe D W, Engelbrecht A P. Data clustering using particle swarm optimization[C]∥Proc of 2003 Congress on Evolutionary Computation(CEC’03), 2003:215-220.

[8] Yang X S.Nature-inspired metaheuristic algorithms[M]. Beckington:Luniver Press, 2008.

[9] Zang H, Zhang S, Hapeshi K. A review of nature-inspired algorithms[J]. Journal of Bionic Engineering, 2010, Supplement:232-237.

[10] Lukasik S, Zak S. Firefly algorithm for continuous constrained optimization tasks[C]∥Proc of the 1st International Conference on Computational Collective Intelligence (ICCCI 2009), 2009:97-106.

[11] Tilahun S L,Ong H C.Modified firefly algorithm[J]. Journal of Applied Mathematics, 2012, 12:1-12,doi:10.1155/2012/467631.

[12] Hassanzadeh T, Vojodi H, Moghadam A M E. An image segmentation approach based on maximum variance intra-cluster method and firefly algorithm[C]∥Proc of the 7th International Conference on Natural Computation (ICNC), 2011:1817-1821.

[13] Horng M H. Vector quantization using the firefly algorithm for image compression[J]. Expert Systems with Applications, 2012, 39(1):1078-1091.

[14] Christensen A L, O'Grady R,Dorigo M.From fireflies to fault-tolerant swarms of robots[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(4):754-766.

[15] Jati G K, Suyanto. Evolutionary discrete firefly algorithm for travelling salesman problem[C]∥Proc of the 2nd International Conference on Adaptive and Intelligent Systems, 2011:393-403.

[16] Senthilnath J, Omkar S N, Mani V. Clustering using firefly algorithm:Performance study[J]. Swarm and Evolutionary Computation, 2011, 1(3):164-171.

[17] Hassanzadeh T, Meybodi M R. A new hybrid approach for data clustering using firefly algorithm andK-means[C]∥Proc of the 16th CSI International Symposium on Artificial Intelligence and Signal Processing (AISP2012), 2012:7-11.

[18] Abshouri A A, Bakhtiary. A new clustering method based on firefly and KHM[J]. Journal of Communication and Computer, 2012, 9(4):387-391.

[19] Liu Chang-ping, Ye Chun-ming. Novel bioinspired swarm intelligence optimization algorithm:Firefly algorithm [J].Application Research of Computers, 2011, 28(9):3295-3297. (in Chinese)

[20] Chen Su-rong, Zhu Xiao-hui. Research ofK-means algorithm by fuzzy logic[J]. Computer Engineering & Science, 2012, 34(12):155-159. (in Chinese)

[21] Jiang Sheng-yi, Li Qing-hua. An enhancedk-means clustering algorithm[J]. Computer Engineering & Science, 2006, 28(11):56-59. (in Chinese)

[22] Kanungo T, Mount D M, Netanyahu N S, et al. An efficientk-means clustering algorithm:Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(7):881-892.

附中文参考文献：

[1] 雷秀娟. 群智能优化算法及其应用[M].北京:科学出版社, 2012.

[2] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J].软件学报,2008,19(1):48-61.

[19] 刘长平, 叶春明. 一种新颖的仿生群智能优化算法:萤火虫算法[J].计算机应用研究,2011, 28(9):3295-3297.

[20] 陈苏蓉, 朱晓辉. 基于模糊逻辑的K-means算法研究[J].计算机工程与科学, 2012, 34(12):155-159.

[21] 蒋盛益, 李庆华. 一种增强的k-means聚类算法[J].计算机工程与科学, 2006, 28(11):56-59.