在许多领域中，聚类是重要分析技术之一，如数据挖掘、模式识别和图像分析。针对K-means算法过度依赖初始聚类中心的选择而陷入局部最优的问题，提出了基于自适应步长的萤火虫划分聚类算法（ASFA）。利用萤火虫算法的随机性和全局搜索性找到指定数量的初始簇中心，进一步利用K-means得到精确的簇划分。在萤火虫聚类优化算法中，采用自适应步长代替原有的固定步长，从而避免算法陷入局部最优，且能获得精度更高的解。为了提高算法性能，将改进的新算法用于不同规模大小的标准数据集中，实验结果表明，ASFA与K-means、GAK、PSOK对比显示了更好的聚类性能和更好的稳定性及鲁棒性，与其他文献中算法相比，ASFA在寻优精度方面能取得更好的效果。
3578· 计算机应用研究 第34卷 随机扰动,更新萤火虫的位置和吸引度 数为d维,每只萤火虫个体是由k个聚类中心组成的向量,则 d)解码最优适应度值的个体得到聚类中心值,该聚类中第讠只萤火虫编码形式为Z=(C1,Ca,…,C),其中C; 心为K- means算法的初始中心 (1,X2,…,X)表示第i个类簇的聚类中心,所以每只萤火虫 (e)执行K- means算法; 的位置编码为hxd维向量 〔f)计算试图替换后的日标函数值,最终替換为更小的日2.2.4种群的初始化 标函数值 由于K- means算法对初始中心随机选取,导致这个解可能 输出结果。 是仝局最优,也可能是局部最优。对于需要仝局优化难以进行 ASA的时间复杂度为O(n2),n是蛋火虫数目。 解析处理的冋題,FA中的随机过程使得对解空间史广泛的搜 2.2基于自适应步长策略的萤火虫聚类算法 索成为可能,多样性正是它的优势之·。FA根据当前解和 对于不同的优化问题,一个算法并不能解决所有问题,囚 些随机信息来产生新解,可以克服 K-means对初始聚类中心的 此需要作相应算法混合并且改进。本文将FA与K- means结依颧。 合应用到聚类问题,为消除萤火虫聚类算法的弱点和改善萤火 对于每只萤火虫Z的位置编码为k×d维问量,各个维值 虫的集体运动,从而寻找到更好的聚类中心,提出了自适应步是从数据集中随机选取。将生成的萤火虫再随机分布到空间 长策略的萤火虫聚类算法(ASFA)。 坐标中,得钊初始科群 自适应步长策略 2.2.5适应度函效 步长是决定算法运行速度和精度的重要因素之一。针对 适应度函数是目标函数,也称误差函数,是评价个算法 萤火虫算法中乐有的固定步长&在搜索解的过程中算法精度对全局聚类结果好坏的标准。在迭代过程中,使得目标函数 低,易陷入局部最优解的问题8,提出自适应步长策略思想 的值逐渐减小,簇问相互独立,簇内足够紧凑,最终收敛至一个 采用自适应移动步长a代替原有的固定步长a。通过萤火虫固定的值,目标函数值越小,表示聚类效果越好。定义如下 种群的聚合程度动态调整步长,随着萤火虫之间的距离变小, llness=tin∑∑dis(x-e2) 令步长变化呈减小的趋势。寻优初期因为萤火虫位置更新变其中sdit(x-c1)2是样本x到对应聚类中心的距离。 化较大,步长改变大,令萤火虫个体保持较快寻优能力,提髙收 敛速度;寻优后期趋于稳定时,步长白动减小,令萤火虫个体在3实验结果与分析 白身周围进行精度解的寻优,逐渐逼近最优解,可以防止在最 优值附近发生振荡现象。通过下式计算白适应的步长 3.1实验相关设置 D(c) 本文选用UCI作为数据库,C语言编程环境实现算法,并 (6 D(c1) 且采用了三个不同数据规模的数据集来验证改进后算法的有 其中:a'为萤火虫每代的自适应步长因子,D(e)为萤火效性。测试集信息如表1所示。 虫种群移动后的簇间距离和。 表1数据集信息统计表 在划分聚类中,对于一个类簇米说,它的簇问距离和反映 数据集样本数(准聚类数)屈性数类别数 了该簇的聚合程度。定义如下 150(50,50,50) )(c1)=∑cdst(x-c1)2 glas214(70,17,76,13,9,29)9 其中:D(c)是聚类中心c:对应的簇间距离和,c巾聚类中心 178(59,71,48 13 点转换为萤火虫和群中相对亮度最大的萤火虫 在自适应步长萤火虫聚类优化算法(ASFA)中,实验参数 2.2.2萤火虫的位置更新 设置γ=1,B=1,βB=0.2,=0.5,和群规模N=20,最大迭代 对萤火虫位置史新式(5)进行」改进,公式为 次数T执行150次,每种算法独立运行20次,分别记录下聚 x+1=x2+B(x2-x)+a'(rnd-12) (8)类结果最优伍和平均值。错误概率偏差计算公式如下: 其中:β为吸引度,α'为萤火虫每一代的日适应步长囚子。新 (if( class(i)=cluster( i))then O else 1))100 的吸引度公式如下: B=Bmn+(B0-Bmine ys 其中:n是数据集的样本数,eror是每一次实验聚类结果的错 其中:是萤火虫对距离其r=0处的最大吸引度,Bm.是最小误率,clas(i)是标准数据集的聚类结果集, cluster()是实验结 吸引度。吸引度决定萤火虫距离移动的多少,新的吸引度与白果数据集。 适应步长策略结合将优化的过程分为两个阶段。前一阶段有 鲁棒性指标可直接用多次实验结果的均方差米参考,计算 利于扩大搜索范围,后一阶段有利于提高算法的收敛速度。而公式如下: 参数的选择依赖于多次尝试,调整到最佳的优化性能 E=nean-R 2.2.3编码方式 ×100% (12) 根据划分聚类问题的特点董火虫的位置编码采用基于聚其中men为算法多次运行得到的半均值R是该间题的真实 类中心的实数编码方式。实数编码方法采用决策变量的真实最优值;E越小,鲁棒性越高 值,个体串长度等于其决策变量的个数,这样做无须转换数制32实验结果与分析 和数据类型。对于一些多维、髙精度优化问题,其具有实数示 ASFA与K- means、GAK(GA- Kmeans)、KOK( PSO-Kmeans)、 数范围大且表小精度高,不仅节省了操作时间、也便于与其他FAK( FA-Kmeans进行比较。其中K- means、PsOK的数据来源 搜索技术结合等优点。假设要求把数据样本分为k类,数据维于文献[20],则不同算法的聚类性能结果如表2~4所示。 第12期 潘晓莫,等:基于自适应步长的萤火虫划分聚类算法 3579 表2ris数据集实验结果 收敛早期根据种群最优的萤火虫吸引所有萤火虫个体仝局寻 算法最优值平均值失误率 优且保持一个高的收敛速度;ASA还保持上A原有的特点,并 102.5716.05±10.10 能利用步长收缩跳出局部最优,弥补∫FA的不足,整体表现 着较快的收敛速度及较髙的收敛精度,算法性能最优 FAK 96.4932110.6628.22±3.72 means虽然寻优速度最快,但随着数据复杂程度的增加,寻优 ASFA 95.32129732427.46±1.43 效果表现得差强人意。如表5所示鲁棒性指标 3Clas数据集实验结果 表5鲁棒性指标 算法 最优值平均值失误率 算法 K 13.2347.80±1.98 GAK 8.2 FAK 210.993237.91247.11±3.33 OK 7.61 ASFA 208.678232.4804.67+2.24 AsFA 8.14 l6.24 表4Wine数据集实验结果 从表5可以看出,ASHA的鲁棒性更好。通过对三个UCI 算法 最优值平均值失误率 数据集的仿真实验可以看出,本文算法是可行的。 K-means 16555.6817662.7334.38±6.80 结束语 FAK16218.6716388.7628.71±2.23 文中针对聚类问题结合萤火虫算法,利用萤火虫算法较强 ASH 16201630828.06±0.88 的鲁棒性和随机拽索性,解决∫K- means对初始中心的依赖 由表2~4可知,对于三种数据集,K- means由于过度依赖顿提高了算法稳定的寻优能力。通过在算法中加入自适应步长 初始中心,随着数据复杂程度增长,导致算法稳定性差,最终算策略,有效防止了算法陷入局部最优值,提高了捕获到全局最 法溎确度大幅下降。评价聚类方法好坏的—个最重要的特点优值的可能性,并提高了算法的求解精度。因此,改进后的算 是聚类误差的能力。一种适当的聚类方法,应该能够减少聚类法更有效。但是关于改进后的算法仅仅釆用了计算机仿真研 误差,并分配到准确的聚类数据向量。 究方法,相关改进思路没有作进一步的收敛轨迹的理论分析 表2~4中已经表明 K-means、POK、FAK、ASFA聚类误等。对于算法的其他应用需要深入饼究,也是下步将要做的 差,所得到的结果让明了所提出方法的准确性和效率。本文方作 法可以减少在所有情况下,与其他方法相比的聚类误差。加入参考文献: 自适应步长后的FA,在准确率上得到提高;错误率范围最小,[1周涛,陆惠玲.救据挖掘中聚类算法研究进辰J计算机工程与 表明了本文算法的稳定性明显优于 K-means同时由表1~4 应用,2012,48(12):100-111 可以看岀聚类结果的准确度也受数据类型和维数变化的影12戴红,常子冠,于宁数据挖据导论LⅥ」.北京:清华大学出版社 响ε可以看出,iris数据集的聚类效果最好,而 glass数据集本 2014 身的数据属性较为复杂,数据间的差异度大,所以得到的聚类3彭丽数据挖掘中几种划分巢类笄法的比较及改进1].大连:大 结果准确度低。同一算法优化不同的效据集,整体来说ASFA 迕理工大学,2008 的聚类结果最为满意,比 K-means、CA、PSOK和上AK有更好14.孙吉贵,刘杰,赵连宇聚类算法研究J」软件学报,2008,19 的效率。 (1):48-61 为了直观地看到不同算法的收敛速度和种群进化,比较[5] Maulik l, Bandyopadhyay S. Genetic algorithm-hased clustering lechluyue[J. Pattern Recognition, 2000, 33(9): 1455-1465 K- means、FAK和ASFA,表明ASFA聚类效果史好,绘制出寻优 [6 Pei Zhenkui, Hua Xia, Han Jinfeng. The clustering algorithm based 过程,如图2~4所小。 on particle swarm optimization algorithm[(]//Pror of International 130 300 90 Cunlerenee on Intelligent Coinpulalion Techology and AulonaLiun 120 新238 本文算注 Washington DC: IEEE Computer Society, 2008: 148-151 110 套250 [7] Jafar ()A M, Sivakumar R. A study on fuzzy and particle swarm op 100 tnizzlioll algorithms and their applicaliunIs lu clustering problem L C// Proc of IEEE International Conference on Advanced Communi 101 101 迭代次数 迭代次数 cation Control and Computing Technologies. 2012: 462-466 图2Iri数据集寻优曲线 图3Gas数据集寻优曲线 [8 De Oc M AM, SlLilzle T, Birallari M, et al. Frunkenslein's PSO: il algorithm[J. IEEE Trans on ary Computation 2009, 13(5): 1 120-11 17500 17000 spired algorilhms[ J] Journal of Bionic Engineering, 2010, 7(3) 迭代次数 「10]许茂增,余国印.基于云自适应遗传算法的 聚类分析 图4 Wine数据集寻优出线 [J.数学的实践与认识,2015,45(17):48-55 巾图2~4的适应度进化曲线可以看出,本文的ASA在 (下转第3602页) 3602· 计算机应用研究 第34卷 更高。对于 Rastrigin和〔 riewvank函数,IPSO都能准确找到最调整惯性权重系数,来平衡算法的仝局搜索能力和局部开发能 优值,而其他两种算法对 Griewank函数均未获得最优值。 力,通过对四个标准测试西数实验分析表明,TPSO算法非常有 b)算法收敛速度分析。根据3.2节參数设置,在同等条件效地提高了算法的速度和精度以及全局收敛能力,并且算法计 下对三种优化算法收敛速度进行统计,分别统计了爷算法10算简单,效率高。 次迭代过程中收敛到1e-2时,算法所需要的平均迭代次数参考文献 (AT)(若不能达到收敛条件,则记该次迭代为最大迭代次1 Kenned1, erhart R O. Particle swarm optimization C,Pme 数)、最少迭代次数(BT)以及满足收敛判据的次数占总实验次 IEEE International Conference on Neural Networks. 1995: 1942-1948 数的比值(SR)。从表3可以看出,IPSO算法的AT和BT值明[2王东风,孟丽.粒子群优佗算法的性能分析和参散选择[J.自动 显低于IDWⅨO和WPO算法,可见使用IPSO算法进行优化 化学报,2016,42(10):1552-1561 所需平均时间较少,表明算法具有较高计算效率,总之,mPS0[3MhiM, Behnam m I, Reza d b,eal. Solution of optimal reactive 算法在成功率和计算效率方面都优于另外两种算法。 power dispatch ul power systems using hybrid particle swarm optimiz 图5~8为三种粒子群优化算法对应的四个标准测试两数 Lion and imperialisT competiTive algorithms[ J]. Electrical Power and 中屮均适应值变化曲线。 Energy Systems, 2016, 83: 104-116 扬进,高飞,马良,基于改进并行粒子群算法的彩色图像匹配[J]」 计算机应月研究,2016,33(8):2543-2546 在10 [5 Ma gang, Zhou Wei, Chang Xiaolin. A novel particle swarm optimi 10 怛10… zation algorithm haser on particle migration[J. Applied Mathema s& compl 12,218(11):6620 L6李盂山,黄兴元,柳和生,等,基于混沌自造应粒子群人工神经网 10 0200400600800100004008001200 2000 络的气伓在聚合物中的溶解模型J.化学学报,2013,71(7) 迭代次数 迭代次数 图5 Spheres应值而线图图6 Rosenbrock适应值曲线图 1053-1058 「7徐文星,耿忐强,朱群雄,等.基于S局部搜索的混沌粒子群优 化算法[J.控制与决策,2012,27(4):557-561 [8ˉ李悛,汪冲,李波,等.基于扰动的精英反向学习粒子群优化算法 10 炽 [J].计算机应用研究,2016,33(9):2584-2587,2591 」谭跃,潭冠政,邓曙光.基于遗传交叉和多混沌策略改进的粒子群 伉化算法J.计算机应用研究,2016,33(12):3643-3647 4o08012010020000200060080100 [10 Wang Hui, Sun Hui, Li Changhe, et al. Diversity enhanced particle 迭代次数 迭代次数 swarm optimization with neighborhood search[J. Information Scien- 图7 Raslrigin适应值曲线图图8 Griewank适应值曲线图 ces,2013,223(2):119-135 从图5~8可以看出,IPSO算法相比于 LDWPSO和WPSO[1] Ii Yuhua,han/ Chibu, I in Shujin,etm!.( Competitive and coopera 算法在收敛精度和收敛时间上都有了极大提升,这对实际优化 tive partic ization with information sharing mechanism 问题能否求出最优值增大了几率 for global optimization problems [J]. Information Sciences, 2015 293(3):370-382 4结束语 [12 Liu Yu, Qin Zheng, Shi Zhewen, et al. Center particle swarm opti- 针对PSO算法前期搜素肓目,后期搜索速度慢且容易陷 mization[J]. Neurocomputing, 2007, 70(4-6): 672-679 [13]汤可宗,柳炳徉,杨静宇,等.双中心粒子群优化算法[J].计算机 入局部最优等问题,提出·种基于引导策略的自适应粒子群算 研究和发展,2012,49(5):1086-1094 法TpO算法,算法采用四种混合粒子构成种群在迭代过14」陈动责,李智欢,孙永发,等,电力系无功化的 LRS-PSO算法 程中用中心粒子、协同粒子和混沌粒子中的较好粒子更换主体 LJ.电力系统及其自动化学报,2008,20(4):92-97 粒了中的较差粒了,明显提八了收敛速度,同时也增强了算法15」任子晖,王坚一种动态改变惯性权貢的自适应粒子群算法J」 的全局搜索能力。此外采用基于聚焦距离变化率的大小动态 计算机科学,2009),36(2):227-229,256 (上接第3579页) J].计算机工程与应用,2011,47(11):123-127 [ll] Christensen a l,o' Grady r, Dorigo y. Frun fireflies lo laultlole-[16]莫愿斌,马彦追,郑巧燕.一种协作的萤火虫算法在聚类问题上的 rant swarms of robots[J. IEEE Trans on Evolutionary Computa- 应用J.亿工自动化及仪表,2014,41(3):238-242 tion,2009,13(4):754-766 [17]刘长平,叶春明一种新颖的仿生群智能优化算法:萤火虫算法 [12]Horng M H. Vetlor quanlizulion usiny the firefly algurithm for image 丁」.计算机应用研究,2011,28(9):3295-3297 J. Expert Systems with Applications, 2012, 39(1) [18]赵杰,需雷旁娟,吴振强.基于晸优类中心扰动的萤火虫聚类算法 1078-1091 J].计算机工栏与科学,2015,37(2):342-347 L19」王冲,雷秀娟,新的小生境火虫划分聚类算法LJ」.计算机 rithm: performance study [J. Swarm Evolutionary Computa 程,20)14,40(5):173-177 tion,2011,1(3):164-171 20」H deh T, Meybodi M R. A new hybrid ch for data clu 14]赵杰.群智能优化算法在聚类分析中的应用研究[D.西安:陕西 Bering usiny firefly algorith ll ant! K-means[C]//Proe of CSI TnlerTHd 师范大学,2015. Artificial Intelli d signal pr [15]张雪凤,张杜珍,刘鵾.基于聚关准则函数的改选K-meas算法 2012:7-11