基于精英个体划分的变步长萤火虫算法的特征选择方法

刘 磊，罗 蓉，尹 胜

(重庆邮电大学 先进制造工程学院，重庆 400065)

0 引 言

特征选择(feature selection)是机器学习、数据挖掘任务中，对于高维或冗余特征数据集采取的一种数据预处理方法[1]。特征选择可以移除原数据集中冗余、不相关的噪音特征，从原数据集中获取一个最优的特征子集以提升机器学习模型的预测精度，同时最优特征子集相较于原特征集具有更少的特征数据，利用其进行机器学习模型的训练和预测可以极大地降低运行时间与数据存储方面的开销[2]。机器学习领域中主要有2类特征选择方式：过滤式(filter mode)和包装式(wrapper mode)[3]。包装式通常会取得比过滤式更好的特征选择结果，包装式比过滤式占用更长运算时间，在非海量数据规模且机器学习模型固定的情况下宜选用这种方式[4]。本文的特征选择方法为包装式的方法。特征选择算法像基于贪心或完备思想的算法[5]虽可在原始数据集上找到最优特征子集，但这些算法为找到全局最优解需要付出高昂的计算代价[6]。特征选择是一个0-1规划的组合优化问题[7]，被证明是NP(non-deterministic polynomial)难题[8]，而一些元启发式或生物启发式优化算法已在求解此类NP难组合优化问题中表现出了良好的性能[9]，其在解决特征选择问题方面的研究[10-12]，近年来受到学术界越来越多的关注[13]，遗传算法(simple genetic algorithm，SGA)[14-15]与离散粒子群优化(binary particle swarm optimization，BPSO)[16-17]等传统生物启发式算法已成功用于特征选择优化。

萤火虫算法(firefly algorithm，FA)是新型的生物启发式群智能优化算法[18]，FA因具有多目标优化能力[19]，使其被国内外学者应用于旅行商问题[20-21]、背包问题[22]、系统效能优化[23]、特征选择[24-27]等组合优化问题的研究中。标准FA设置参数少，算法步骤和公式较简单，然而其步长参数取值大小对其性能影响很大[22]，标准FA采用固定步长设置，这使FA在优化求解中全局最优解发现率低、算法搜索易陷入局部最优。对此，文献[27]提出一种随算法迭代次数增加而算法步长逐渐减小的改进策略，然而该步长调整方式忽视了FA种群中萤火虫个体在寻优过程中的差异性，无法使个体自适应调整寻优步长，且在算法迭代优化的后期寻优效率降低，这存在着寻优局限性。因此，本文充分考虑了FA在寻优过程中其种群内个体的差异性，在遵循标准FA算法机理的基础上，提出了基于精英个体划分的变步长FA(elite -individual -dipartition dynamic step firefly algorithm，EDSFA)，并将EDSFA进行离散化实现，提出EDSFA的相应离散化算法EDSBFA(elite -individual -dipartition dynamic step binary firefly algorithm，EDSBFA)用于机器学习任务中的特征选择优化，实验表明，在优化特征选择方面EDSBFA的总体性能优于固定步长BFA(binary firefly algorithm)、文献[27]所提变步长BFA以及传统启发式优化算法SGA和BPSO。

1 精英个体划分的变步长FA

1.1 标准FA

标准FA算法原理：萤火虫种群中的每只萤火虫个体的位置代表待求解问题的一个可行解，即整个种群为原问题的解空间，萤火虫自身亮度与待求解问题的目标函数值相关，即萤火虫亮度越强，对应可行解的目标函数值越佳。当FA算法运行时，荧光亮度较弱的萤火虫被荧光亮度较强的萤火虫吸引，并向其所处位置移动，随着算法的不断迭代，种群中原先亮度较弱的萤火虫持续不断地移向亮度较强个体所处位置，最终种群中大多数萤火虫将聚集在一个或多个亮度较强的萤火虫周围，当萤火虫间没有亮度差异时算法收敛，而最亮萤火虫所处位置代表问题的最优解[19]。

在标准FA中，萤火虫个体遵循以下3条规则：①所有个体无性别区分；②个体吸引力与自身亮度相关，较弱亮度的个体会被较强亮度的个体所吸引而向其移动，最强亮度的个体将在解空间中随机移动；③待求问题的可行解的目标函数值通常作为个体的亮度值。

1)萤火虫的相对亮度为

Ι(γ)=Ι0e-γr2

(1)

(1)式中：r为萤火虫之间的距离；γ为光强吸收系数，考虑了光在传播过程中因空气等介质会有所损耗，可设为常数；I0为r=0时萤火虫的荧光亮度，即自身荧光亮度，其值与目标函数值有关，目标函数值越优，自身荧光亮度越强。

2)萤火虫的吸引力为

β(r)=β0e-γr2

(2)

(2)式中，β0为r=0时萤火虫的自身吸引力。

3)萤火虫之间的距离为

(3)

(3)式中：若两萤火虫个体i和j分别位于xi和xj，它们之间的距离可用欧式距离rij表示；D为问题的解空间维度；xik，xjk分别表示第i与j只萤火虫的位置向量xi,xj中第k维的分量。

萤火虫的位置移动为

xi(t+1)=xi(t)+β0*e-γrij2(xj(t)-

xi(t))+α*ε

(4)

发光亮度较弱的萤火虫i将移向发光亮度较强的萤火虫j，从而i的位置向量发生更新。

(4)式中，t指算法迭代计数。等号右端由3项因式构成：第1项xi(t)表示萤火虫i当前所在解空间位置；第2项表示萤火虫i向萤火虫j移动的距离；第3项α·ε为i向j移动的过程中伴有的随机扰动，避免萤火虫过早陷入局部最优，其中，α为随机移动步长，其取值为0～1，ε是由高斯分布、均匀分布或莱维飞行[28]所得到的随机数向量。

1.2 基于精英个体划分的变步长策略

标准FA中萤火虫位置移动方式如(4)式，其中，移动步长α的引入是为了扩大萤火虫的移动视野，提高萤火虫种群的多样性，避免算法早熟收敛。步长参数α取值大小应与具体解空间的搜索范围相关，在较小搜索范围内α取值过大可能导致算法无法收敛；取值过小，随机移动距离极小，无法增加种群多样性，不能起到扩大搜索范围或扩大萤火虫移动视野、避免算法过早收敛的作用[22]。在标准FA中所有萤火虫个体的步长取统一固定值，不能根据实际搜索情况进行调节，这具有很大的局限性。文献[27]提出一种步长α随算法迭代次数增加而动态减小的变步长FA，相比标准FA扩大了步长α的调节范围，在算法运行初始阶段能增强算法的随机搜索能力，跳出局部最优，算法迭代后期搜索的随机性减弱，促使算法逐步收敛。该变步长改进策略没有考虑萤火虫个体在寻优搜索中的差异性，在算法搜索中为所有个体设置一样的步长，在算法迭代后期由于步长值被减到很小，难以使已处在局部最优位置的大部分萤火虫更进一步扩大寻优视野，这极易使整个萤火虫种群的搜索陷入局部最优陷阱，另外算法跌代后期整个种群采取统一的小步长值也降低了算法收敛的效率。对所有萤火虫个体采取大步长，能增强FA对解空间的全局搜索能力，但易跳过全局最优而求解精度低；对所有个体采取小步长，能增强FA在局部解空间的探索能力，但易使萤火虫寻优陷入局部最优陷阱，且会降低算法求解效率。所以为每只萤火虫个体的移动单独设置动态变化的步长是必要的。本文从萤火虫种群的精英个体划分角度出发，提出一种变步长策略以提高FA的寻优能力。

为了兼顾算法在解空间的全局搜索和局部探索能力，同时充分考虑每只萤火虫的性能差异，本文提出如下的步长调整策略：对每轮次算法迭代中种群里性能较好的精英个体增大其步长，保持其全局移动视野以搜索更大区域，提高了种群的多样性，进而降低搜索陷入局部最优陷阱的风险；而对于当前迭代轮次中的非精英个体减小其步长，保持其在局部解空间的探索能力，小步长值对精确搜索有利，能提高算法求解精度和促使种群逐步收敛。基于精英个体划分的变步长设置具体表示为

αi(t+1)=

(5)

αi(t+1)=α0,αi(t)>1

(6)

(5)—(6)式中：αi(t+1)表示第i只萤火虫个体在第t+1次算法迭代时的步长；MaxGen指设置的算法最大迭代次数；α0表示初始统一步长值；a为步长增大的随机加速度；a取值为[1,MaxGen/2]的随机整数；Ii为个体i的荧光亮度；Ibest为当前种群中最佳个体的荧光亮度；θ为用于划分精英个体的阈值，θ为[0.85,0.95]的常数值，由(5)式知当个体i的亮度大于当前种群中最佳个体亮度值的θ倍时，便视其为精英萤火虫个体，增大其步长值，否则线性减小其步长值，如果i的步长经过增大调整后已大于1，则按(6)式所示将其步长重置为初始步长值。对于(5)式中步长增大的随机加速度a的引入可使萤火虫个体间步长的扩大趋于多样化、随机性，这也促进了种群的多样性变化，避免了种群的早熟收敛，另外a可结合具体解空间的搜索范围进行滑动窗口取值，使步长调节更具灵活性。

2 基于EDSBFA的特征选择方法

2.1 萤火虫位置向量编码

特征选择实际上是从原始数据集的M个数据特征中选择N个特征后组成一个特征子集(M>N)，进而用该特征子集中的特征优化后续的数据分析处理，对于每个待选特征而言只存在“入选”或“落选”2种状态，因此，可将萤火虫个体的位置向量每一维的索引序号对应于原数据集各维特征的索引序号，并将个体向量编码为每一维元素仅为‘0’或‘1’的二元离散向量，其中，元素为0表示落选，元素为1表示入选，向量维度等于原数据集特征维度。例如萤火虫i当前位置向量为Xi=[0,1,0,1,0,1,0,1,1,0]，其向量维度为10，表示原数据集的10个数据特征中入选特征的索引序号分别为“2,4,6,8,9”，该索引序号所对应特征即被选择。

2.2 目标函数定义

特征选择的目标是从原始数据集选择一个特征数量较少的特征子集，利用该特征子集中的特征做数据挖掘，使机器学习模型获取更好的预测准确率。目标函数应考虑选择的特征数量和预测准确率这2个因素，当所选特征数量越少和模型预测准确率越高时，目标函数值越优，本文中萤火虫的自身亮度等于萤火虫位置向量的目标函数值，所以目标函数值越优，萤火虫的亮度越强。目标函数定义为

f(accu,num|Xi)=

(7)

(7)式中：Xi为萤火虫个体i的位置向量；accu为个体向量对应特征子集的预测准确率；num为该特征子集中入选特征的数量；k为特征数量num的权重，本文实验中k=0.5。

2.3 EDSFA离散化为EDSBFA

由于特征选择问题是组合优化问题，属于离散优化范畴，本文萤火虫的位置向量编码是0，1二元离散编码，标准FA中对萤火虫的距离、位置移动的定义只适用于连续优化领域而不适用于离散优化，故须对萤火虫的距离、位置移动做适用于离散化操作的重新定义。对于提出的基于精英个体划分的变步长萤火虫算法(EDSFA)，本文采用了与文献[27]一样的萤火虫算法离散化方式，将EDSFA离散化为EDSBFA。

定义1 萤火虫i与j之间的距离。由于本文萤火虫位置向量被编码为0，1二元离散向量，所以2个萤火虫之间的距离或差距使用汉明距离描述比使用原FA中的欧式距离更适合，汉明距离准确刻画了2个向量的差异性，比欧式距离的计算开销少，提高了算法运行效率。两萤火虫个体间的归一化汉明距离定义为

(8)

(8)式中：⨁指XOR异或操作；d为个体向量的维度。萤火虫之间的吸引力β通过(2)式计算，其中距离r使用上述定义的归一化汉明距离。

定义2 萤火虫的离散化移动。当萤火虫i向亮度更强更有吸引力的萤火虫j移动时，个体i的位置向量每一维元素值将做决策是否发生改变，本文将个体位置向量中每一维元素值的改变分2步进行：①吸引移动，如(9)式，对应于(4)式右端第2项因式所作操作；②随机游走，如(10)式，对应于(4)式右端第3项因式所作操作。其中，rand(0,1)指0～1的随机数,αi为个体i的当前步长,vik是个体i的位置向量的第k维分量在“吸引移动”后的中间变量。

(9)

(10)

2.4 基于EDSBFA的包装式特征选择方法流程

包装式特征选择，使用优化算法从原始数据集中选择特征，产生一系列待评价特征子集，将各个特征子集对应的特征数据送入机器学习分类器进行分类器的训练，并用训练好的分类器做分类预测，经过数次迭代优化，最终将能使分类器获得最好精度和泛化能力的特征子集输出。基于精英个体划分的变步长离散FA(EDSBFA)的包装式特征选择方法流程如图1。

3 实验与分析

3.1 实验设置

使用python3编程语言分别实现了本文提出的基于精英个体划分的变步长离散萤火虫算法EDSBFA、固定步长离散萤火虫算法BFA、文献[27]中所提变步长离散萤火虫算法IBFA，EDSBFA中除精英个体划分阈值θ和步长增大的随机加速度a之外，初始步长值α0、其他参数设置和BFA一样均同IBFA[27]一致，如表1。表1中，所有算法的最大迭代次数MaxGen=100,t为当前迭代计数，Randint表示随机整数。

实验所用机器学习分类器与文献[14，16]一致，为k-近邻算法(k-nearest neighbor,KNN)分类器，其中，K=1,将python的Sklearn库中KNN应用接口与EDSBFA，BFA，IBFA的算法代码进行包装融合，分别开发了基于EDSBFA，BFA，IBFA的包装式特征选择程序EDSBFA-KNN，BFA-KNN，IBFA-KNN，并使用文献[14，16]中测试所用到的7个UCI分类数据集对所开发的特征选择程序进行了实验测试，为了保证测试结果的客观准确，由萤火虫算法产生的特征子集使用KNN分类器的10折交叉验证方式进行评价，且特征选择程序在每个数据集上单独运行各30次，实验所得平均分类准确率、选择特征的平均数量与文献[14]中基于遗传算法(simple genetic algorithm,SGA)和文献[16]中基于离散粒子群算法(binary particle swarm optimization,BPSO)优化特征选择所得KNN分类结果以及与单一KNN分类结果进行了对比分析。此外，在UCI高维度数据集LSVT(LSVT为医疗语音数据集，共126个分类样本，每个样本多达309个特征)上进一步测试了EDSBFA，BFA，IBFA的性能，每个算法程序单独运行20次。实验环境为Win10系统 ，Inter (R) Core (TM) i3-3120 CPU 2.50 GHz, 8.0 GB内存的PC机。

表1 参数设置Tab.1 Parameter setting

3.2 结果分析

在7个UCI分类数据集上，包装式特征选择方法EDSBFA-KNN，IBFA-KNN，BFA-KNN，SGA-KNN[14]，BPSO-KNN[16]和单一KNN取得的平均分类预测准确率与特征数量如表2，其中，D为数据集特征维度；N为各方法选择的平均特征数量；A为各方法获得的平均分类准确率，最少的特征数量与最高的分类准确率为加粗显示的数值。由表2可知，除SGA-KNN在数据集Segmentation，WDBC上取得的分类准确率比使用单一KNN的分类结果差之外，SGA-KNN在其他5个数据集上的分类准确率比单一KNN要高，而BPSO-KNN，BFA-KNN，IBFA-KNN，EDSBFA-KNN在全部数据集上均取得了比单一KNN更高的分类准确率，说明了基于优化算法(SGA，BPSO，BFA，IBFA，EDSBFA)构造最优特征子集，KNN(K=1)利用最优特征子集的特征数据进行分类预测可以显著改善其在数据集上的预测精度。Vowel数据集的特征维度较小(D=10)，数据集较简单，SGA-KNN，BPSO-KNN，BFA-KNN，IBFA-KNN，EDSBFA-KNN均取得了99%以上的分类精度，而IBFA-KNN，EDSBFA-KNN在Wine数据集上的分类准确率和选择的特征数量相同且比其他方法取得的结果要优，此外EDSBFA-KNN在Vehicle，Segmentation，WDBC，Ionosphere，Sonar数据集上均取得了最高的分类准确率，且其在大多数的数据集上选择的特征数量偏少。综合结果表明本文所提算法EDSBFA优化特征选择的能力要强于其他对比算法。

表2 各方法在数据集上的平均分类准确率与平均选择特征数量Tab.2 Average values of classification accuracy and number of selected features through each method

表3 EDSBFA，IBFA，BFA在 LSVT上的测试结果Tab.3 Test results of EDSBFA, IBFA, BFA for LSVT

在拥有高维度特征的LSVT数据集上进一步测试了EDSBFA，IBFA，BFA的性能，实验结果如表3，其中，D，N，A的含义同表2，T指算法程序运行时间，单位为s。由于LSVT的候选特征空间相比前7个测试数据集大得多，搜索算法早熟收敛的风险相对较小，故EDSBFA的步长增大的幅度不宜过大，其随机加速度a应取偏小值，其取值为[1,10]的随机整数。由表3中T列数据知，EDSBFA-KNN比BFA-KNN、IBFA-KNN要省分别近21%和58%的时间开销，由表3中A列(括号内为取得的最高分类准确率)数据知，BFA-KNN的分类精度远不如IBFA-KNN，EDSBFA-KNN的分类精度，其最高分类准确率没有达到90%以上，而IBFA-KNN，EDSBFA-KNN的平均分类准确率都已达到了95%以上，且IBFA-KNN的最高分类准确率大于EDSBFA-KNN的最高分类准确率，但EDSBFA-KNN的平均分类准确率要高于IBFA-KNN的平均分类准确率，且EDSBFA-KNN选择的最优特征数量最少，以上表明在高维度数据集上基于EDSBFA优化特征选择的精度要比基于BFA，IBFA的更优、更稳定，且EDSBFA算法运行效率更高。图2～图7分别是LSVT测试中BFA，IBFA，EDSBFA的目标函数值(荧光亮度)、分类准确率、选择的特征数量在100次算法迭代搜索过程中的变化情况。如图2，BFA在迭代中步长固定，无法自适应调节，导致搜索趋于随机化，整个种群难以持续获得更好的解，而使算法陷入局部最优或是无法收敛。图3中，IBFA在迭代中整个种群虽能朝着优化方向进行搜索，可IBFA 未区分精英与非精英萤火虫个体，这使萤火虫个体在解空间中无法根据自身状况进行差异化搜索，这使找到更好解的效率变低。从图4可知，EDSBFA在迭代过程中最佳萤火虫个体的目标函数值(荧光亮度)和整个萤火虫种群的平均目标函数值都在持续平稳地获得提升，在迭代25次左右就取得比BFA，IBFA迭代100次时更高的目标值，且随着迭代优化的继续呈现出算法收敛趋势(最优值等于平均值时算法收敛)，EDSBFA的收敛速度快于BFA，IBFA,且最终获得更优的解。

从图5～图7可知，BFA在迭代的后期由于算法陷入局部最优或是搜索偏向随机化导致难以取得更优的分类准确率和特征子集。IBFA在迭代中可持续获得更高的分类准确率，但过程较缓慢，且选择的最优特征数量波动性大。EDSBFA随着迭代能持续且快速地获得更高的分类准确率和含更少数量特征的特征子集，直至算法收敛，其总体性能明显优于BFA，IBFA。

4 结束语

本文提出一种新的改进型萤火虫算法EDSFA，并通过重新定义萤火虫距离和移动方式，给出了改进算法的离散化实现EDSBFA，以适用解决特征选择问题，将EDSBFA与KNN分类器结合以包装式实现了特征选择优化，在UCI数据集上的实验表明，本文所提算法EDSBFA在优化特征选择效果和运行效率上性能优越，所提改进萤火虫算法使用基于精英个体划分的变步长策略，考虑了萤火虫个体差异性而进行自适应寻优，算法兼顾了解空间的全局搜索和局部探索，降低算法陷入局部最优的风险，同时使算法朝着种群优化的方向搜索，保证了算法的快速收敛。本文算法改进没有使用交叉、变异等复杂手段，但取得了理想效果。萤火虫算法的参数取值大小对算法的性能影响很大，不宜使用固定值，未来在本文变步长改进策略的基础上，将对FA的光强吸收系数γ进行自适应改进。另外基于启发式算法的包装式特征选择优化方法运行效率低、耗时，未来可研究基于算法并行化的改进方法以提升效率。