胡绍方，周凤

　　（贵州大学 计算机科学与技术学院，贵州 贵阳 550025）

　　摘要：针对FCM聚类算法对初始聚类中心敏感和易陷入局部最优解的缺点，提出一种基于细菌觅食的细菌觅食聚类算法。将细菌觅食算法与FCM算法相结合，并以反向学习来初始化细菌种群，增加种群的多样性和代表性，求得的最优解作为FCM算法的初始聚类中心，使FCM算法对初始聚类中心的依赖性降低，同时也降低了陷入局部最优解的可能性，提高了算法的稳定性。实验结果表明，该算法克服了FCM算法稳定性差的缺点，收敛速度更快，具有良好的性能和聚类效果。

　　关键词：细菌觅食优化算法；聚类；FCM

0引言

　　随着计算机技术的发展，信息量的倍增，数据挖掘技术是当前技术研究的重点，而聚类是数据挖掘技术中的一个重要分支，它是一种以相似性为基础的无监督的机器学习技术，其目的是将目标数据集分成若干个簇，使得同簇内的数据相似度尽可能高，不同簇的数据相似度尽可能低。聚类技术目前应用非常广泛，在机器学习、模式识别、Web挖掘［1］领域等都有很好的应用前景。

　　模糊C均值(Fuzzy C Means, FCM)是聚类技术的一个重要方法，它是1973年由DUNN J C［2］和BEZDEK J［3］提出的，属于基于目标函数的模糊聚类算法。FCM算法简单且快速，其应用非常广泛，目前已形成了庞大的体系。但是FCM算法也存在缺点，主要表现在［4］:

　　（1）初始聚类中心的数目必须提前给出，而且这个数目的取值至今没有规律可循；

　　（2）对于不规则簇和带状簇识别困难，而且对噪声敏感；

　　（3）初始聚类中心的选取是随机的，但不同的选取结果，对聚类结果有较大影响；

　　（4）算法运行过程中比较容易陷入局部极值点，从而得不到全局最优值。

　　针对FCM算法的这些缺点，本文把并行搜索能力强、易于跳出局部极值的细菌觅食算法引进到FCM算法，来改善传统FCM算法的弊端。最后，运用经典的UCI数据集和自构造数据集进行测试实验，结果表明这种改进算法是可行的并且提高了聚类的准确率。

1FCM算法　

　　FCM算法是通过不断的迭代逼近最优解的一种聚类算法。对于集合X={x1,x2,..,xj,..,xn},把这n个数据xj(j=1,2,...,n)分成C={c1,c2,..,ci,..cc}的c个簇，用隶属度来刻画数据xj属于某个类的程度，通常记为uij，取值范围为［0,1］且∑ci=1uij=1，计算每个分组的聚类中心，使目标函数（即非相似性指标的价值函数）达到最小。在聚类过程中，把聚类生成的类看成模糊集合，所以隶属矩阵U中的每个点的分量只能取值在0~1间的元素。

　　FCM算法的目标函数：

　　其中，m是一个加权指数，一般是大于1的数。

　　通过拉格朗日公式，要使式（1）达到最小，必须满足以下两个条件：

　　ci=∑nj=1umijxj∑nj=1umij(2)

　　uij=1∑ck=1ci－xjck－xj2/(m－1)(3)

　　根据上述两个条件公式，可以看出FCM算法其实是一个简单的迭代计算过程，其算法描述如下：

　　(1)设置初始化参数值，包含模糊加权参数值m和聚类数c，以及最大迭代的次数T和算法终止目标精度误差ε；

　　(2)随机选中初始化聚类中心C0；

　　(3)根据式（3）计算隶属度矩阵U(t)；

　　(4)根据式（2）迭代计算聚类中心Ct+1；

　　(5)如果J(t+1)－J(t)<ε或者t>T，则算法结束，否则返回步骤（3）。

　　近年来对FCM算法改进的研究也有很多，2005年周新华、黄道［5］提出了一种利用蚁群算法来改进模糊c均值聚类算法，同年郑岩［6］等人提出了一种利用遗传算法来实现动态模糊聚类的算法，施美珍［7］在2012年也提出了利用粒子群来改进模糊聚类的方法，2014年林睦纲［8］等人提出了基于萤火虫算法的模糊聚类。在FCM算法的步骤中，必须先选中初始化聚类中心，然后才执行迭代运算，而这种操作方式不能一次就得出最终想要的聚类结果，需要反复运行多次才能得到理想聚类效果。因为FCM算法对初始聚类中心具有很强的依赖性。所以，可以采用另外的算法预先寻找、确定初始聚类中心，然后根据这些初始聚类中心再执行FCM算法，这样不需多次运行FCM算法就可以得到相对准确的结果。

2细菌觅食算法

　　细菌觅食算法(Bacterial Foraging Optimization, BFO)是PASSINO K M［9］于2002年提出的一种新型仿生类群体智能算法。它主要通过趋化、繁殖、迁徙三种算子进行位置更新和最优解搜索，进而实现种群的进化。该算法的优点［10］在于并行搜索、易跳出局部极值等。

　　在细菌的这三种算子中，细菌向食物源区域靠拢的行为被称为趋化算子。在趋化算子中，细菌的运动行为有两种：一种是细菌向随机方向前进单位步长，把其定义为翻转算子，另外一种是如果细菌执行翻转算子一次后，其适应度值得到改善，则细菌沿同一方向继续移动，直到细菌的适应度值不再改善或达到最大的移动步数，把其定义为前进算子。细菌达到最大趋化算子次数后，将执行繁殖算子，细菌的繁殖行为同样遵循自然界的“优胜劣汰，适者生存”的原则。细菌生活的区域可能突然会发生剧烈变化，这样可能导致生活在这个区域的细菌种群死亡或迁徙到一个新的适合的生活区域，在该算法中把这种现象描述成为迁徙算子。在这三种算子中，趋化算子为算法的核心部分，它可以提高细菌的局部搜索精度，繁殖算子可以增加细菌的快速收敛性能，而迁徙算子的存在则有利于趋化算子跳出局部极值进而寻找全局最佳值，三种算子相互配合以达到快速准确地寻找全局最优解。

　　假设Xi(j,k,l)表示细菌个体i的位置，其中j表示j代趋化算子，k表示细菌k代繁殖算子，l表示l代迁徙算子。

　　细菌的位置按照下式进行调整更新：

　　Xi(j+1,k,l)=Xi(j,k,l)+rand()*step*φ(i)(4)

　　φ(i)=Xi(j,k,l)－Xrand(j,k,l)Xi(j,k,l)－Xrand(j,k,l)(5)

　　其中，step是每一步前进的步长，φ(i)表示细菌随机翻滚的方向，Xrand(j,k,l)表示当前个体Xi(j,k,l)邻域内的一个随机位置。如果翻转后适应度值得到改善，则继续沿着翻转的方向前进，细菌个体i的适应度值用fiti来表示：

　　其中Jc为总的类内离散度。

3基于细菌觅食的FCM聚类算法

　　对数据的聚类实际上就是对函数进行优化的过程，通过对此迭代搜寻目标函数的最优解，直到得到最佳的聚类效果。繁殖算子的“优胜劣汰”原则可以保留优秀的初始聚类中心，迁徙算子可以有效地帮助跳出局部最优解，体现了算法的全局搜索性能。

　　基于细菌觅食的FCM聚类算法（Bateria Foraging Optimization Fuzzy C Means,BFFM)的思想：首先利用BFO算法的并行搜索等优点求得群体最优解，以这些最优解作为FCM算法的初始聚类中心，然后利用FCM算法对初始聚类中心进行进一步优化计算，最后求得聚类结果。此算法克服了FCM算法对随机选择的初始聚类中心的敏感，提高了算法的稳定性，提升了算法的收敛速度。

　　3.1基于反方向学习的初始化

　　初始种群是算法进行搜索的起点，而初始种群的分布状况以及好坏在一定程度上会影响算法的求解效率和最终结果。细菌觅食算法采用的是随机产生初始群体的初始化方式，这种方式不能保证所产生的初始群体的均匀分布。基于反向学习［11］的群体初始化方法，不仅提升了初始种群的多样性，同时也可以使初始群体比较均匀地分布在解空间内，提高算法的运行效率。具体步骤为:

　　（1)初始化种群，按照种群规模数目N初始化，并指定聚类数目c，然后再将每个细菌随机地指派为某一类，把其最初的聚类划分，作为细菌i的位置编码，同时计算各类的聚类中心，随机生成的初始解每一维分量都满足Xid∈［ad,bd］(d∈(1,2,...,D)，D为维数，a、b分别为样本数据中对应维的上、下限。

　　（2)为每一个上一步产生的初始解生成其相应的反向解，它在每个维度的分量按下式计算：

　　vid=ad+bd－Xid,d∈D（7）

　　(3)把上面两步产生的解合并，计算它们的适应度值并排序，选出前N个适应度较高的解作为初始种群。

　　3.2算法的实现步骤

　　(1)参数、种群的初始化。设定迁移次数Ned、繁殖次数Nre、趋化次数Nc、基本迁移概率Ped、细菌规模数S和游动次数Ns的初始值。

　　(2)种群初始化。本文采用基于反向学习的方法产生初始种群，并随机选取c个细菌作为初始聚类中心。

　　(3)执行趋向行为。细菌i在执行趋向行为过程中主要进行翻转行为和游动行为。此过程中按照式(4)和式(5)更新细菌的位置。

　　(4)执行复制行为。在复制之前，先按照细菌种群的适应度的大小降序排列，保留前一半适应度值较大的个体，去除掉另外一半适应度值小的个体，并对保留的这些个体进行一分为二的分裂复制，这样不但完成了单次复制，而且保证了细菌种群规模不变。若满足复制操作的终止条件，则进行迁徙操作，否则返回步骤（2）。

　　（5）以设定的概率Ped执行迁徙行为。大于迁徙概率就执行迁徙行为，即此细菌将消失，并随机在一个新的位置生成一个新的细菌，否则细菌将维持原来的位置不动。如果迁徙行为达到设置的最大迭代次数，则进入聚类过程，否则返回（2）。

　　（6）执行FCM聚类过程。将细菌寻优结束时最终的位置作为FCM算法的初始聚类中心，开始执行FCM算法聚类过程进行聚类。

4实验及结果

　　为了验证BFFM算法的可行性和有效性，使用数据集进行试验测试，分别使用公用的UCI数据集Iris 、Wine和自构造数据集Dataset0。Iris数据集包含3类且每类均有50个数据对象，每个数据包含花瓣长度和宽度、尊片长度和宽度4个属性。Wine是以葡萄酒的成分分析为数据来源，它包含178个数据，将其划分为3类，其中每类包含数据数目为59个、71个、48个。自构造数据集Dataset0是以等概率生成的4组2维数据点组成，该数据集包含160个数据点，以高斯分布分配到4个组，每组均包含40个数据对象，并且满足球形分布，如图1所示。

　　分别用FCM算法和BFFM算法对UCI数据集中的Iris、Wine和自构造数据集Dataset0进行聚类分析，算法中设定最大误差ε=10－3，模糊加权指数取2，BFFM算法种群规模为S=50，趋化次数Nc=5，迁徙次数Ns=3，繁殖次数为Nre=2，繁殖比例为0.5，迁移次数Ned=2，迁移概率为0.25，移动最大步长为0.05。两种算法各自运行30次。用式（8）评判聚类准确率：

　　precision=dD×100%(8)

　　其中，d代表正确地分配到某个类中数据的个数，D表示该类中所包含的总的数据个数。实验结果如表1~表3所示。 

　　由实验结果可以看出，BFFM算法相对于传统的FCM算法来说性能更加优越，提高了聚类的准确度，同时它也增加了算法的收敛速度。当然BFFM算法本身也存在缺陷，该算法所用的时间要比FCM算法稍长些，但整体来说，经过改进后算法的性能更加完善。

5结论

　　本文提出的BFFM算法将细菌觅食算法与FCM算法相结合来改进FCM算法，并以反向学习的思想来生成初始种群，增加种群的多样性和代表性，从而使BFFM算法不但克服了传统FCM算法对初始聚类中心的依赖性、易陷入局部极值等缺点，同时也提高了聚类的精准度，使聚类的收敛速度更快，聚类结果更完善。

参考文献

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

　　［2］ DUNN J C.A Fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster［J］.J Cybernet,1974(3):3257.

　　［3］ BEZDEK J. Pattern recognition with Fuzzy objective function algorithms［M］.New York: Plenum, 1981.

　　［4］ 丁旭晨,林锦贤.改进的高效模糊C均值聚类算法［J］.微型机与应用,2013,32(23):7476,79.

　　［5］ 周新华,黄道.一种基于蚁群算法的模糊c均值聚类［J］.控制工程,2005,12(2)：132134.

　　［6］ 郑岩,黄荣怀,战晓苏，等.基于遗传算法的动态模糊聚类［J］.北京邮电大学学报,2005,28(1):7578.

　　［7］ 施美珍.基于粒子群优化算法的模糊聚类分析及其应用［D］.广州：华南理工大学,2012.

　　［8］ 林睦纲,刘芳菊,童小娇.一种基于萤火虫算法的模糊聚类方法［J］.计算机工程与应用,2014,50(21):3538,73.

　　［9］ PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control［J］.Control System Magazine, 2002, 22(3): 5267.

　　［10］ 周雅兰.细菌觅食优化算法的研究与应用［J］.计算机工程与应用,2010, 46 (20):1621.

　　［11］ 王晖.基于一般反向学习的群体随机搜索算法框架［J］.南昌工程学院学报,2012，31（3）:16.