基于维度权重和遗传因子的萤火虫算法在聚类分析中的应用

邓青,朱晓军,杨宁

基于维度权重和遗传因子的萤火虫算法在聚类分析中的应用

邓青1,朱晓军2,杨宁3

1. 山西轻工职业技术学院信息工程系, 山西 太原 030013 2. 太原理工大学信息与计算机学院, 山西 太原 030600 3. 山西云时代技术有限公司, 山西 太原 030600

针对传统聚类算法对初始值敏感，易陷入局部最优的问题，本文提出一种基于维度权重和遗传因子的萤火虫算法（AWG-FA)。该算法引入遗传算法的交叉、变异思想，并通过计算维度权重，将群体中具有优良维度的个体遗传到下一代，保留种群的潜在最优解，并对余下个体进行自适应变异，提高了种群的多样性。在UCI数据集上进行仿真实验，结果表明该算法具有更好的聚类性能和鲁棒性。

萤火虫算法; 聚类分析

聚类分析是数据挖掘领域中的一个重要组成部分，它是根据数据之间的相关性，按照特定的准则，将物理或抽象的对象集合分成若干类的过程，使得相同类内的元素相似性较大，而不同类元素之间差异性较大[1]。对于研究对象特征数据的内在关系，是非常有效的。许多聚类算法，如经典的均值，虽然算法应用较广，但存在对初始值敏感、参数设置的问题，而且在算法迭代的后期往往无法获得最优解。智能算法在解决全局最优解问题上有着独特的优势，许多学者把智能算法与聚类算法进行融合，文献[2]提出一种自适应布谷鸟搜索的-均值聚类算法，文献[3]提出一种基于模糊C-均值的改进人工蜂群聚类算法。文献[4]和[5]将蚁群算法同聚类分析算法进行结合。文献[6]将粒子群和模拟退火算法的思想应用到聚类算法中，克服了初始化的敏感性，提高了聚类精度。

2008年英国学者模拟自然界萤火虫的发光行为，提出一种启发式智能优化算法——萤火虫算法，简称FA[1]。该算法具有良好的寻优和搜索性能，已经成功应用于多目标优化[7]、调度问题[8]、图像处理[9]及路径规划[10]等领域。但该算法和其他智能算法一样，也容易陷入局部极值点导致解的精度不高。本文在萤火虫算法中引入遗传算法的交叉变异，根据维度权重选择性保留较优个体，同时变异增加了种群的多样性。通过对多个UCI数据集进行仿真实验对比，结果证明该算法聚类精度高，且不易陷入局部最优。

1 萤火虫算法

萤火虫算法（Firefly Algorithm，简称FA）是模拟萤火虫表现出的社会行为而设计的生物进化算法。其原理是利用萤火虫的发光特性，在指定区域内搜索其他个体并向亮度较大的个体移动，从而实现位置的寻优[9]。萤火虫根据亮度和吸引度，这两个因素决定移动策略。亮度反映了萤火虫位置的优劣（和该位置的目标函数有关），亮度越大的萤火虫越能吸引其他萤火虫向它所处位置移动；吸引度同萤火虫之间的距离有关，同时影响萤火虫所要移动的距离。FA正是通过萤火虫的位置改变，来不断更新自身亮度和吸引度，一步步向区域内较优的位置移动，以此来实现目标优化。

一个处于位置的萤火虫，其亮度就是该位置的目标函数，的位置越好，它的亮度就越大。吸引度大小和亮度大小成正比，与二者之间距离成反比，同时还和介质的吸收因子有关。萤火虫算法的相关定义如下：

定义1 萤火虫相对亮度：一个萤火虫对相距其处的亮度()，可以用公式（1）表示：

其中，0表示萤火虫的最大亮度；d表示萤火虫和在空间上的距离；表示介质对荧光的吸收因子。

定义2 萤火虫的吸引度，0表示萤火虫的最大吸引度。用公式（2）表示：

定义3 萤火虫被萤火虫吸引的移动公式（3）为：

、为萤火虫和在进行第次迭代前的空间位置；为移动步长因子，且Î[0,1]；rand是取值在[0,1]上的随机数，可以影响萤火虫下一时刻位置的变化。萤火虫算法作为智能算法之一，拥有较好的寻优性能，但在多峰值寻优中，因步长设置不合理，往往会陷入局部最优，即便能跳出局部最优却也可能跳过精确解导致算法精度降低。

2 聚类问题

其中X表示第个样本，c表示第个聚类中心，ǁX-cǁ表示X和聚类中心c的距离。目标函数值越小，表明类内个体具有越高的相似度，聚类效果越好。

3 基于维度权重和遗传因子的萤火虫算法（AWG-FA）

3.1 萤火虫编码方式

萤火虫算法应用于聚类问题，可以这样抽象：用空间中一只萤火虫代表解决问题的一组解，对应就是一组聚类中心。假设为聚类个数，样本维度为，第只萤火虫的位置可以编码为X=[c1,c2,…,c]，c表示第类样本的中心，每类样本中心都是一个维向量。

3.2 算法原理及关键操作

在萤火虫算法中，每个萤火虫个体都是一个维向量，它们根据自身的亮度和吸引度，按照一定的规则向最优解的位置和方向移动，寻找最优解。某只萤火虫在某次迭代中某一维找到了最优值，而该位置其他维的值可能不是最优，受目标函数影响，这一维的最优值也将被舍去。受遗传算法[13]原理的启发，对每次萤火虫算法寻优中获得的较优解和较差解进行交叉、变异、选择操作。有利于保留较优个体，同时可以扩大解的搜索空间，获取全局最优解或近似最优解。

3.2.1 改进的交叉方式交叉互换过程可以产生不同于父类的个体，提高种群的多样性。当交叉率比较高时，个体更新快，可达到较大的解空间，但会破坏已有的潜在最优解。当交叉率比较低时，搜索空间较小，很容易陷入局部最优。为了克服这些弊端，本文提出利用维度权重来决定交叉率的方法。维度权重的计算公式如(5)所示：

W表示某个体第维的权重。维度权重标识某一维对目标函数的贡献程度，值越大，这一维成为最优解的概率越大。为了将这些潜在的较优维度的值继承下来，同时达到更大的解空间，将维度权重低于平均值的个体对应位置进行交叉操作。

3.2.2 自适应的变异操作为提高种群多样性，对当前种群中余下的个体进行变异操作。为了克服变异的盲目性，本文采用文献[13]的变异策略：若当前个体的适应度大于群体平均适应度，则以小概率变异，反之，以较大概率变异。变异概率设定在[0.001，0.1]。

最后对所有个体采用精英策略进行选择，淘汰一定数目的个体，控制种群的过度膨胀，完成种群的更新。

图1 AWG-FA算法流程图

3.3 算法流程 见图1。

4 结果与分析

本实验选取机器学习库UCI中常用三个数据集Iris、Glass、Wine，分别进行对比实验。这三组数据集描述如表1所示。

表1 三组数据集描述

4.1 实验环境及参数设置

4.1.1 实验环境及参数设置算法通过Matlab R2017a编程实现，实验机器配置为：处理器：intel core i7-5500U，主频：2.4GHz，内存：8G，操作系统Windows764位。

设置三组数据集的聚类个数分别为3，3，6。

设置萤火虫的步长因子=0.5，最大吸引度0=1，最小吸引度min=0.18，介质吸收因子=1，变异概率=0.1，算法终止条件为最大迭代次数100次。

4.1.2 实验设计分别采用-means、FA算法和AWG-FA算法对三组实验数据集分别进行50次独立实验，求得多次实验中的最优值、最差值和平均值，以及平均运行时间，记录在表2中，进行对比。图2到图4表示三种数据集下，几种算法在收敛效果方面的对照。

4.2 实验结果

表2为不同算法的聚类性能比较。从表2的数据统计结果可以看出，AWG-FA算法在三组测试数据集中，整体来看目标函数值均低于其他算法，说明聚类效果更好一些。在算法的运行时间上，AWG-FA算法比其他的两种算法运行时间稍长，主要原因在于交叉、变异过程耗时方面。但交叉、变异操作使得AWG-FA在全局最优解的搜索过程中表现的更好，特别是算法后期收敛速度加快，能找到的解更好。多次实验发现，AWG-FA聚类后得到的目标函数最优值、最差值、平均值几乎都是三种算法中最小的，说明AWG-FA的聚类效果三者中最好，聚类的稳定性高。

表2 三种数据集上不同算法聚类性能对比

图2到图4显示三种算法分别在三个数据集上的收敛效果，可以看出-means的收敛速度最快，但是寻优能力最差，很快就陷入局部最优解；FA的收敛速度和AWG-FA相近，得到的最优值介于-means和AWG-FA之间；AWG-FA的收敛速度稍慢，但是得到的最优值最好。从收敛效果上，再次验证AWG-FA算法跳出局部最优解，逼近全局最优解的收敛过程。AWG-FA相比较其他算法来说，在合理的迭代次数下能够找到较好的目标函数值。

图2 Iris数据集的收敛对比

图3 Wine数据集的收敛对比

图4 Glass数据集的收敛对比

5 结论

本文提出一种新颖的萤火虫算法，对基本的萤火虫算法进行了如下改进：（1）计算维度权重并保留优势属性的个体；（2）对位置不好的个体引入遗传算法中的杂交、变异算子，增强种群多样性。将改进的萤火虫算法（AWG-FA）同经典的-means算法、FA在UCI数据上进行聚类，并在聚类准确性、收敛速度及稳定性方面作出比较，实验结果证明改进算法的寻优能力远优于其他两种算法，稳定性方面更好。

[1] 莫愿斌,马彦追,郑巧燕.一种协作的萤火虫算法在聚类问题上的应用[J].化工自动化及仪表,2014,41(3):238-242

[2] 杨辉华,王克.基于自适应布谷鸟搜索算法的-means聚类算法及其应用[J].计算机应用,2016,36(8):2066-2070

[3] 何嘉婧,王晋东,于智勇.基于模糊C-均值的改进人工蜂群聚类算法[J].计算机应用研究,2015,33(5):1342-1345

[4] 鲍义东,周改云,赵伟艇.自适应蚁群和模糊聚类的SAR图像分割[J].测绘科学,2016,41(8):121-124

[5] 李振,贾瑞玉.一种改进的-means蚁群聚类算法[J].计算机技术与发展,2015,25(12):34-37

[6] 蒋君,徐蔚鸿,潘楚.基于粒计算和模拟退火的-medoids聚类算法[J].计算机仿真,2015,32(12):214-217

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

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

[9] 周晨航,田力威,赵宏伟.基于改进萤火虫算法的二维Otsu图像分割法[J].沈阳大学学报:自然科学版,2016,28(1):45-50

[10] 徐晓光,胡楠,徐禹翔,等.改进萤火虫算法在路径规划中的应用[J].电子测量与仪器学报,2016,30(11):1735-1742

[11] 程美英,倪志伟,朱旭辉.萤火虫优化算法理论研究综述[J].计算机科学,2015,42(4):19-24

[12] 王琦,朴燕.基于改进遗传算法的深度图像获取技术[J].激光与光电子学进展,2018,55(2):170-176

[13] 陈闯,Ryad Chellali,邢尹.改进遗传算法优化BP神经网络的语音情感识别[J].计算机应用研究,2019(2):1-5

Application of Firefly Algorithm Based on Attribute Weights and Genetic Factors in Clustering Analysis

DENG Qing1, ZHU Xiao-jun2, YANG Ning3

1.030013,2.030600,3.030600,

Aiming at the problem that the traditional clustering algorithm is sensitive to the initial value and easily falls into the local optimum, a firefly algorithm (AWG-FA) based on attribute weights and genetic factors is proposed. This algorithm introduces the crossover and mutation ideas of genetic algorithm, and calculates the attribute weights, then it inherits the individuals with excellent attributes from the population to the next generation, and mutates the poor individuals, which improves the diversity of the population. Simulation experiments on UCI datasets show that the algorithm has better clustering performance and robustness.

Firefly algorithm; cluster analysis

TP301.6

A

1000-2324(2019)05-0889-04

10.3969/j.issn.1000-2324.2019.05.034

2018-04-22

2018-05-26

基于新型素数筛法的素性检测和素数生成机制研究(201701D11100202)

邓青(1983-),女,硕士,主要从事网络技术、大数据方向研究. E-mail:yndengqing@126.com