新的小生境萤火虫划分聚类算法

王 冲，雷秀娟

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

新的小生境萤火虫划分聚类算法

王 冲，雷秀娟

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

针对传统的划分聚类算法过度依赖初始聚类中心并容易陷入局部最优的问题，提出基于萤火虫算法的改进划分聚类算法。该算法将萤火虫个体对应于一组聚类中心的解，类簇的聚合度对应于萤火虫的亮度，通过萤火虫个体之间的相互吸引寻找聚类中心的最优解。在寻优过程中使用随机分布的萤火虫种群克服划分聚类过于依赖初始聚类中心的问题，采用自适应步长的策略加强算法寻找精确解的能力。为了避免在寻优过程中因为种群过于集中而导致算法陷入局部最优，引入小生境技术提高萤火虫的种群多样性。仿真实验结果表明，与传统聚类算法相比，该算法的聚类精度较高，稳定性较好。

划分聚类；聚类中心；局部最优；萤火虫算法；自适应步长；小生境

1 概述

随着信息社会的发展，社会各个领域的数据正在迅速膨胀并变大。数据挖掘作为大数据时代寻找数据背后有用信息的重要工具，越要越受到人们的重视。聚类分析[1-2]是数据挖掘中的一个重要课题，它是将物理或抽象的对象集合分成相似的类簇的过程。通过聚类描述事物间的相似性和差异，从而方便人们掌握事物的内部规律。

划分聚类是聚类算法中非常常用的聚类方法，因为其简单高效的优点，被人们广泛研究及应用到各领域，常见的有K-means[2]、K-medoids[3]以及一些改进算法等。这些启发式的聚类方法通常适合于发现数据库中的球状簇[4]，但为了对大规模的数据集聚类，需要对基于划分的算法做进一步扩展和改进。

群智能优化算法[5]通过模拟自然界中动物的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优的目的。萤火虫算法[6-7](Firefly Algorithm, FA)是一种新兴的群智能优化算法，是模拟自然界萤火虫的发光行为发展而来。该算法具有良好的寻优和搜索性能，目前已应用到很多优化问题中，如多目标优化问题[8]、TSP问题[9]、调度问题[10]及灾难挖掘方法[11]等。

针对传统划分聚类方法存在的问题，本文在萤火虫算法的基础上建立聚类模型并进行改进，对常用数据集进行实验验证。

2 相关算法及定义

2.1 划分方法的数学描述

对一个含有n个对象的数据集，指定类簇数为k，划分方法将这组数据集分成期望的k个类簇，k≤n ，每个类簇表示一个聚类。其中，这组类簇必须满足如下条件[12]：

(1)每个数据集中的个体必须属于且仅属于其中一个类簇。

(2)每个类簇必须至少包含一个对象。

对于期望的类簇数k，从初始的分类方法开始，不断地通过迭代改变分类情况，使得改变后的分类情况优于之前的分类。评价类簇的一般标准是：同一类簇间个体的距离尽可能小，而不同类簇间个体的距离尽可能大。但传统的划分聚类会存在一些缺点，以最常用K-means为例：(1)初始聚类中心选取的好坏会直接影响到整个聚类的效果；(2)算法的全局搜索性能不足从而导致陷入局部最优；(3)对孤立数据和噪声数据非常敏感，少量的该类数据会对聚类结果产生极大的影响。

2.2 萤火虫算法

自然中萤火虫会有节奏地发出短促的荧光，而不同的萤火虫有着不同的发光目的。一般认为是为了吸引异性或者捕食，还有的以此作为警戒信号。萤火虫算法通过模拟萤火虫的发光行为搜索领域内的伙伴，一步步朝着区域内较优的位置移动，从而实现状态的不断进化。

萤火虫算法的寻优要素主要是自身亮度和吸引度。亮度取决于当前位置的目标函数值，如果位置越好则亮度越高。同时亮度也影响萤火虫的吸引力，亮度高的萤火虫会拥有更强的吸引力，可以将视野内亮度较弱的伙伴吸引过来。同时随着距离的增加，传播媒介吸收荧光后亮度和吸引力都随之减弱。萤火虫算法的相关定义如下：

定义1 萤火虫的荧光亮度：

其中，L0是萤火虫的最强亮度，也就是r=0处的荧光值；rij是萤火虫i和j之间的距离，随着rij传播媒介距离的增加，荧光亮度L逐渐减弱；γ为传播媒介的光强吸收系数。

定义2 第i只萤火虫的位移公式：

其中，xnext是位移后的值；β为萤火虫i，j之间的吸引因子；step是步长因子；δ小于1大于0且服从均匀分布的随机数。

2.3 小生境技术

小生境技术[13-14]就是通过模仿自然界中相同种类生物一起生活，形成一个生活的小环境，从而分离不同种类个体。其中，基于排挤机制的选择策略步骤如下：

(1)设置一个排挤因子CF(一般取2或3)；

(2)从种群中随机选取1/CF个个体组成排挤成员；

(3)依据新个体与排挤成员的相似性排挤掉种群中相类似的个体。

小生境技术能够保持种群的多样性，避免种群陷入局部最优，从而得到更好的全局搜索能力。萤火虫算法虽然有较好的寻优能力，但是算法缺乏避免种群个体过于集中的能力，在算法后期容易导致局部最优。

本文将小生境技术用到萤火虫算法中，使算法在求解聚类问题过程中避免陷入局部极值从而得到更好的求解精度。

3 小生境萤火虫聚类模型定义

3.1 萤火虫编码

针对聚类问题，将一组聚类中心对应于一只萤火虫，每只萤火虫的状态就是问题的一个可行解。假设期待聚类个数为k，第i只萤火虫ffi的编码形式表示如下：

3.2 萤火虫自身亮度和吸引度

在划分聚类中，距离是用来评价任意2个个体相异度的标准，而对于一个类簇来说，它的类间距离的和反映了该类聚合程度的强弱，同时这也是聚类问题通常采用的准则函数，定义如下：

其中，D( ci)表示聚类中心ci对应的类间聚类的和。在本文中，使用D( ci)反映萤火虫个体的优劣，也就是说萤火虫的亮度L在r=0处的计算公式如下：

由式(1)和式(4)可以看到，D( ci)越小，则该类内部就聚集得越紧密，而萤火虫的亮度也就越高，周围领域的萤火虫聚集的机会也就越高。

3.3 目标函数

目标函数也就是适应度函数，是评价一个算法结果的标准。对聚类问题来说，需要使生成的结果簇尽可能地紧凑和独立。本文通过计算类簇集的内间距离的和，作为目标函数来评价全局聚类结果的好坏，定义如下：

3.4 萤火虫种群初始化

造成K-means过于依赖初始聚类中心缺陷的原因，很大程度上是由于一开始随机选取数据点作为初始聚类中心的方法。因为在没有先验知识的情况下，无法从一开始就估计聚类中心的位置，最坏的情况下就导致同一类簇中的个体作为不同的聚类中心划分出去。而对于萤火虫算法来说，多样性正是它的优势之一，为了避免K-means这样的缺点的产生，将萤火虫随机分布到空间坐标中，得到更加随机多样的初始种群分布。具体做法如下：

3.5 自适应的步长设置

萤火虫算法作为智能算法之一，拥有较好的寻优性能，但也同样拥有很多智能算法的缺陷，在多峰值的寻优过程中，如果步长设置得不合理就会导致算法陷入局部最优的问题。在步长step的设置中，虽然过高的步长能很快地跳出局部最优却可能因此而跳过精确解导致算法精度降低。为了解决这个问题，本文采用自适应的步长，在移动的过程中根据目标函数值fitness的变化自适应调整步长step。通过下式计算自适应的步长：

其中，step'为每一只萤火虫根据预先设置的step计算得到的自适应步长；fitnessnext为萤火虫移动后的目标函数值；fitness为移动前的目标函数值，由式(6)可以看出，使用自适应的方式，当目标函数快速收敛的时候，step较高，萤火虫个体会保持较快的寻优能力，而当fitness趋于稳定的时候，萤火虫个体则趋向于搜索自身周围领域的精确解。

3.6 小生境技术的引入

萤火虫算法通过相互吸引的行为达到寻优的目的，但是对于复杂问题特别是多峰优化问题来说却同样面临陷入局部最优的情况。为了提高种群的多样性和全局搜索能力，保持解的多样性，引入基于排挤策略的小生境技术。具体做法是，首先用统计学中的离散系数gather描述种群的聚集情况：

其中，fiti表示当前第i只萤火虫的适应度函数值；fitavg是当前的萤火虫种群适应度平均值。离散系数可以用来反映数据集内个体间的离散程度，对于本文算法来说，由于萤火虫之间相互吸引会不断聚集到一起，适应度值也会逐渐趋于一致，gather值也越来越小，说明此时种群也越来越集中，离散程度越来越低。极限情况下，当gather值等于0时，种群的离散程度为0，整个种群完全重合到同一位置，此时算法要么是达到全局最优，要么是早熟收敛于局部最优，因此通过gather值可以判断当前种群的收敛情况。为了加强算法跳出局部最优的能力，再设置一个阈值δ，根据实际问题的不同，给δ设置一个较小的值，通常可以取δ值为0～0.3之间。当gather＜δ时，认为萤火虫种群已经过于集中，此时引入小生境机制，从萤火虫群体的取值空间中随机产生1/3的个体cj组成排挤成员，然后对行动后的萤火虫种群与排挤成员cj比较相似度并进行排挤操作，排挤掉相似度高的个体，从而保持萤火虫种群的多样性，避免陷入局部最优。

4 算法描述

算法步骤如下：

步骤1输入数据集，为了评价方便对数据进行归一化处理。确定萤火虫种群规模N、迭代次数iterNum以及期待的类簇数k，按照3.4节所示将聚类中心随机分布到数据空间从而完成萤火虫种群初始化。

步骤2根据式(4)计算每只萤火虫各自的亮度，将目标函数最优的萤火虫个体状态赋值给公告板。其中，公告板是一个d+1维的全局变量，前d维用于保存当前最优的萤火虫个体状态，第d+1维保存其对应的全局最优适应度值。然后判断是否已达到算法终止条件，达到则输出结果后退出，否则继续执行步骤3。

步骤3搜索视野内的萤火虫状态及亮度，选择亮度最强的萤火虫所在位置作为移动的方向，根据3.5节所示的方法设置自适应的步长step，模拟萤火虫的相互吸引行为。如果追逐后状态比先前状态更优，则执行吸引行为，否则重新选择下一个次优的萤火虫个体进行追逐，若得到更优的状态则移动。如果在tryNum次数内都无法完成追逐操作，则默认执行随机行为。假如行动后的萤火虫个体超出边界则执行如下操作：

步骤4依次计算萤火虫种群目标函数值与公告板值，如果得到了更优的适应度值，则更新公告板。完成该轮萤火虫种群寻优行为后，判断种群是否过于集中，如果是则执行小生境算法，否则进入步骤5。

步骤5判断算法是否已到终止条件，若达到则输出结果，否则转到步骤3，iter=iter+1。

5 仿真实验及分析

本文分别进行了2组实验，以分析和比较本文算法的效果。实验平台均为Matlab7.0。

实验1 为了更加直观地了解本文算法的寻优过程，先以一组随机产生的二维数据集为例。分别以(3,7)，(2,2)，(7,8) 及(6,4)为中心，随机产生3个类，每个类分别有150个数据点且服从高斯分布。最大种群寻优次数为150代，种群大小50，默认step为1，用Matlab绘制出大致的寻优图像如图1～图9所示。

图1 第1代聚类结果

图2 第1代种群分布

图3 第25代聚类结果

图4 第25代种群分布

图5 第50代聚类结果

图6 第50代种群分布

图8 第100代种群分布

图9 目标函数曲线

通过图1～图9可以看到，本文算法在初始化聚类中心时将萤火虫种群随机分布到了取值空间内，使算法具有更好的全局搜索条件。由于引入了小生境机制，使种群不会完全集中到一点，得到了更多样性的解和萤火虫个体，自适应的步长使算法在收敛后期能够逐步求得精确解。

实验2 通过对UCI数据集中的Iris数据集和Cancer数据集进行实验比较本文算法的性能，主要与K-means算法、PSO算法[15]和改进前的萤火虫算法进行比较，每种算法分别运行20次，分别取聚类结果的最低、最高精度和平均精度。精度的计算公式如下[16]：

其中，S表示标准数据集中的聚类结果集；R表示实验结果数据集；precision反映了聚类算法实验结果的正确率。

由表1、表2可以看到，对于K-means算法，由于过度依赖初始聚类中心，导致平均精度较低而且算法稳定性较差，而融入小生境机制的NFA算法聚类不但在精度方面有所提高，而且在鲁棒性方面也得到了增强。

表1 I ris数据集上的聚类结果比较 %

表2 Can cer数据集上的聚类结果比较 %

6 结束语

本文通过分析划分聚类方法的特性，在基本萤火虫算法的基础上，针对聚类问题做出一系列改进：为了提高聚类寻优的精确性使用自适应步长，避免了固定步长所带来的算法鲁棒性不高的问题，在聚类过程中引入小生境技术，提高了萤火虫算法种群的多样性，加强算法避免陷入局部最优的能力。虽然本文对于萤火虫算法应用于聚类问题提出了一些改进方法，但萤火虫算法作为一种新颖的智能算法，需继续改进。

[1] Jain A K, Murty M N, Flynn P J. Data Clustering: A Review[J]. ACM Computing Surveys, 1999, 31(3): 264-323.

[2] Ding C, Li Tao. Adaptive Dimension Reduction Using Discriminate A nalysis and K-means Clustering[C]//Proc. of the 24th International Conference on Machine Learning. New York, USA: ACM Press, 2007: 521-528.

[3] Chen Xinq uan, P eng Hong, Hu Jing-song. K-medoids Substitution C lustering Method and a New C lustering Validity Index Method[C]//Proc. of the 6th World Congress on Intelligent Control and Automati on. [S. l.]: IEEE Press, 2006: 5896-5900.

[4] Han Jiawei, Kamber M, Jian Pei. Data Mining Concepts and Techniques[M]. 2nd ed. [S. l.]: Morgan Kaufmann Publishers, 2006.

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

[6] Y ang Xinshe. Nature-inspired Metaheuristic Algorithms[M]. [S. l.]: Luniver Press, 2008.

[7] Yang Xinshe. Firefly Algorithms for Multimodal Optimization[C]//Proc. of the 5th International Conference on Stochastic Algorithms: Foundations and Applications. Berlin, Germany: Springer-Verlag, 2009: 169-178.

[8] 袁际军. 基于多目标萤火虫算法的可调节产品族优化设计[J]. 计算机集成制造系统, 2012, 18(8): 1801-1809.

[9] 周永权, 黄正新. 求解TSP的人工萤火虫群优化算法[J].控制与决策, 2012, 27(12): 1816-1821.

[10] 郭丽萍, 李向涛, 谷文祥, 等. 改进的萤火虫算法求解阻塞流水线调度问题[J]. 智能系统学报, 2013, 8(1): 1-7.

[11] 胡明生, 贾志娟, 吉晓宇, 等. 基于改进萤火虫群的区域灾害链挖掘方法[J]. 计算机应用与软件, 2012, 29(11): 29-31.

[12] Dunham M H. 数据挖掘教程[M]. 郭崇慧, 田凤占, 靳晓明, 等, 译. 北京: 清华大学出版社, 2005.

[13] Z hang J un, Huang Deshuang, Lo k T M, et a l. A No vel Adaptive Sequential Niche T echnique for Multimodal Function Optimization[J]. Neurocomputing, 2006, 69(16/18): 2396-2401.

[14] 喻寿益, 郭观七. 一种改善遗传算法全局搜索性能的小生境技术[J]. 信息与控制, 2001, 30(6): 526-530.

[15] 刘靖明, 韩丽川. 粒子群优化k均值的混合聚类算法研究[J]. 中国管理科学, 2004, 12(10): 96-99.

[16] Zhang Aidong. Protein Interaction Networks[M]. New York, USA: Cambridge University Press, 2009.

编辑 顾逸斐

New Partition Clustering Algorithm of Niching Firefly

WANG Chong, LEI Xiu-juan

(School of Computer Science, Shaanxi Normal University, Xi’an 710062, China)

Traditional partition clustering method has the problem of over-reliance on the initial cluster centers and the method is prone to fall into local optimum. So an improved partition clustering algorithm based on the firefly algorithm is proposed. The algorithm considers a firefly as a set of cluster centers and class cohesion is rega rded as brightness of the fi refly. Then find the optimal cluste ring center by the fireflies attracting each other. In the process of opt imization, randomly distributed fi refly population is used to overco me the problem of over-reliance on the initial cluster centers and adaptive step st rategy is adopted to st rengthen the ability to find the exa ct solution of the algorithm. In order to prevent the algorithm from local optimum for population concentration, the niche technology is introduced to improve the diversity of the fireflies’ population. Experimental results indicate that the algorithm is improved in clustering precisio n and stability compared with traditional clustering algorithm.

partition clustering; clustering center; local optimum; firefly algorithm; adaptive step; niche

10.3969/j.issn.1000-3428.2014.05.036

国家自然科学青年基金资助项目(61100164, 61 173190)；中央高校基本科研业务费专项基金资助项目(GK201302025)；教育部留学回国人员科研启动基金资助项目(教外司留[2012]1707号)；陕西省2010年自然科学基础研究计划青年基金资助项目(2010JQ 8034)。

王 冲(1985－)，男，硕士研究生，主研方向：数据挖掘，智能计算；雷秀娟，教授、博士、CCF会员。

2013-04-07

2013-05-16E-mail：alaso2009@126.com

1000-3428(2014)05-0173-05

A

TP391.4