本文摘要：摘要：基于元启发式算法乌鸦搜索算法(CrSA)，提出一种改进的基于乌鸦搜索算法的特征选择算法(IFSCrSA)，以解决目前特征选择问题中存在的不足.通过与传统的机器学习特征选择算法和基于进化计算的特征选择算法进行比较，结果表明，IFSCrSA能在数据集中选择辨识
摘要：基于元启发式算法———乌鸦搜索算法(CrSA)，提出一种改进的基于乌鸦搜索算法的特征选择算法(IFSCrSA)，以解决目前特征选择问题中存在的不足.通过与传统的机器学习特征选择算法和基于进化计算的特征选择算法进行比较，结果表明，IFSCrSA能在数据集中选择辨识度较强的特征，不仅大幅度降低了特征子集的规模，而且提高了分类准确率.
关键词：元启发式算法,乌鸦搜索算法,特征选择,分类准确率
特征选择是从原始数据集中选择出最优特征子集的过程，其通过降低数据集维度提高学习算法的性能，是机器学习过程中关键的数据预处理步骤.使用特征选择方法删除数据集中不相关和冗余的特征，解决了数据集中特征数量庞大、特征之间相互作用复杂的问题[1]，从而降低了后续机器学习任务的难度.但随着数据集规模的不断增大，优化效率也不断降低，因此，设计并改进特征选择算法已成为特征选择问题求解的关键.
为了解决该难题，一些研究者将元启发式搜索应用到特征选择[2]寻找近似最优解.元启发式算法解决了大规模组合优化问题，在一定程度上提高了特征选择的优化效率.根据元启发式算法解的数量可将其分为基于单一解的算法和基于种群策略的算法[3].
其中基于单一解的算法在迭代过程中只有一个解，例如SFS(sequentialforwardselection)算法和SBS(sequentialbackwardselection)算法[4]，将其应用到特征选择时，对于解决中等维度的特征选择问题具有简单、快速的优点，但容易陷入局部最优，且由于算法具有单向性，对已选择的特征不能更改，从而导致特征冗余.
为克服算法的缺点，Pudil等[5]提出了SFFS(sequentialforwardfloatingselection)算法和SBFS(sequentialbackwardfloatingselection)算法，这些算法可在局部搜索过程中回溯之前遍历的特征，但每次渐进搜索还是集中在与当前最优点最近的一些组合上，不利于全局搜索.另一类是基于种群策略的算法，在每轮迭代过程中均产生多个并行计算的个体，通过模拟生物种群之间的合作解决特征选择问题.
例如，UFSACO算法[6]模拟了巢穴和食物来源之间真实蚂蚁的行为，PSO(particleswarmoptimization)算法[7]模拟了鸟群或鱼群的群体行为，ABC(artificialbeecolony)算法[8]是受蜜蜂群体行为的启发.AC-ABC算法[9]是ACO(antcolonyoptimization)算法和ABC算法的混合算法;FS-NEIR算法[10]结合了遗传算法和局部搜索方法;HGAFS算法[11]是基于互信息的混合遗传算法.
CrSA[12]是一种新的元启发式算法，适用于求解连续搜索空间问题.通过分析和改进CrSA，本文提出一种基于乌鸦搜索算法的特征选择算法(IFSCrSA)来解决特征选择问题.在IFSCrSA中，使用包含“0”和“1”的字符串初始化种群，为了在算法开始时提高算法的效率，加入了初始化学习策略，从而获得更好的原始种群.引入Lévy飞行搜索策略平衡全局搜索与局部搜索.在乌鸦飞行寻找目标过程中，使用Sigmoid转换函数保持种群位置值始终为二进制.同时还提出了基于贪婪策略的更新机制，以进一步提高IFSCrSA的收敛速度.
1乌鸦搜索算法
乌鸦搜索算法是基于乌鸦觅食过程提出的一种智能算法.乌鸦是一种聪明且贪婪的鸟类[12]，它可以识别同伴的脸，用不同方式与同伴进行交流，为了获得更多的食物，它会偷偷地跟踪其他乌鸦，发现它们存储食物的地点，并偷取食物.如果乌鸦发现被其他乌鸦跟踪，则该乌鸦将随机飞行，从而迷惑跟踪它的乌鸦.在优化理论中，乌鸦是搜寻者，周围环境是搜索空间，随机存储食物的位置是可行解.
在所有食物位置中，存放最多食物的位置被认为是全局最优解，目标(适应度)函数是食物量.模拟乌鸦的智能行为，乌鸦搜索算法试图找到各种优化问题的最优解.假设乌鸦i随机选择一只乌鸦j进行跟踪，则在跟踪过程中会出现以下两种情况：1)乌鸦j未发现乌鸦i跟踪，结果i到达j隐藏食物的位置偷取了食物;2)乌鸦j发现乌鸦i跟踪，则其将随机飞行，迷惑跟踪乌鸦，使其食物避免被偷.
2基于乌鸦搜索算法的改进特征选择算法
2.1基于反向搜索策略的初始化方法
初始解的分布直接影响特征选择算法的收敛速度和解的质量.为了获得更好的初始解，本文引入基于反向学习的概念[13]，即算法在初始化期间同时搜索解和与之对应的相反解，选择更好的解作为初始位置.通过使用反向搜索策略，可使算法在后续搜索过程中加速收敛[14].
基于反向搜索的初始化：设X=(x1，x2，…，xD)为D维空间中的一个点(即候选解)，其中xi∈{0，1｝，i∈{1，2，…，D｝.ˇX=(ˇx1，ˇx2，…，ˇxD)是X的相反解，其中ˇxi=1-xi.假设f(·)是一个适应度函数，用于衡量候选解的适应度.如果f(ˇX)≥f(X)，则可用点ˇX替换点X作为候选解;否则保持X作为候选解.
2.2基于Lévy飞行的搜索策略
在连续搜索空间中，如果乌鸦发现被其他乌鸦跟踪，则将通过随机飞行来保护食物.在IFSCrSA中，引入Lévy飞行[15]改变随机算法，从而平衡全局搜索与局部搜索.假设有N只乌鸦在D维搜索空间中，任意一只乌鸦(乌鸦i)在任意时刻(迭代iter)可用包含“0”和“1”的字符串表示为Xi，iter=(xi，iter1，xi，iter2，…，xi，iterD)(i=1，2，…，N;iter=1，2，…，itermax).使用记忆位置(Mi，iter)表示乌鸦记忆中藏食物最多的位置.字符串中的“1”表示对应特征被选中，“0”表示特征未被选中.在离散空间中，乌鸦的飞行过程可表示为：
2.4改进算法设计
算法1IFSCrSA的伪代码.算法开始：步骤1)根据反向搜索策略初始化乌鸦种群当前位置和记忆位置;步骤2)whileiter
根据贪婪搜索策略判断是否更新乌鸦i的记忆位置;步骤8)endfor步骤9)计算种群记忆位置的评估值并排序，评估值最大的记忆位置即为最优特征子集;算法结束.在算法1中，首先根据反向搜索策略进行种群初始化，将乌鸦种群的当前位置(Xi)和记忆位置(Mi)离散化.
在每轮迭代过程中，当乌鸦i选择跟踪目标(乌鸦j)时使用贪婪搜索策略，以保证跟踪的有效性.乌鸦i选定跟踪目标(乌鸦j)后，根据式(1)对自己当前位置进行更新.该过程引入Lévy飞行，从而平衡算法的全局搜索和局部搜索.然后使用Sigmoid转换函数将更新后的位置转换为仅包含“0”和“1”的字符串，保持算法的离散性.最后使用式(4)更新乌鸦i的记忆位置.算法1中步骤4)～7)确保每只乌鸦在一轮迭代后的记忆位置是保存食物最多的位置.在迭代结束后，通过评估函数计算乌鸦种群记忆位置的评估值.评估值最大的记忆位置即为最优特征子集.
3实验
实验环境为Python3.6.1，使用公开的scikit-learn包，计算机为DELLIntelCorei7CPU(3.60GHz)，4GB内存.实验对比算法包括FSFOA[16]，UFSACO，SFS，SBS，SFFS，FS-NEIR，HGAFS，PSO和NSM[4].IFSCrSA使用KNN(K=1，3，5)、SVM和J48分类器指导学习过程.
3.1数据集
将IFSCrSA在11个数据集上进行实验验证，其中有10个数据集来自UCI机器学习库(http：//www.ics.uci.edu/mlearn/MLRepository.html)，包括Heart-statlog，Vehicle，Cleveland，Dermatology，Ionosphere，Sonar，Glass，Wine，Arcene和Segmentation数据集，有1个数据集(SRBCT)来自微阵列数据集.数据集的特征数(#Feature)、实例数(#Instance)以及分类数(#Class)等信息.
3.2IFSCrSA实验参数设置
IFSCrSA参数设置如下：在所有参数中，种群大小N、意识概率AP、飞行距离fl和最大迭代次数itermax与数据集无关，所以本文设置参数为N=50，AP=0.1，fl=2，itermax=10.
3.3评价函数
实验中，采用分类准确率(CA)[17]和维度缩减(DR)[18]作为IFSCrSA的评价函数.分类准确率是验证特征选择的有效方式[19]，计算公式为CA=N_CC/N_AS×100%，(5)其中：N_CC表示正确分类的实例数;N_AS表示数据集的整体实例数.维度缩减公式为DR=[1-(N_SF/N_AF)]×100%，(6)其中：N_SF表示选择特征的数量;N_AF表示数据集上所有特征的数量[19].
3.4实验结果分析
针对不同的数据集，IFSCrSA和其他对比算法的CA和DR结果.实验所有数据均为经过10次单独运行结果求平均值后得到的.由于数据集采用不同的百分数划分训练和测试数据集时可能会影响算法运行的结果，特别是数据集中实例数很小的情况下，所以在本文实验中，采用不同方法对数据集进行划分，包括10-折交叉验证、2-折交叉验证、70%用于训练集30%用于预测集(记为70%/30%).
IFSCrSA在数据集为Heart-statlog，Glass，Dermatology，Cleveland，Segmentation，Arcene和SRBCT的分类准确率明显高于其他算法，同时在维度缩减方面普遍有较大改善.数据集SRBCT和Arcene的特征数远超过实例数，通常情况下很难选择合适的特征进行预测，但IFSCrSA的分类准确率仍高于其他算法.
IFSCrSA对于数据集Sonar，Wine和Ionosphere的分类准确率虽然不总是最好，但维度缩减明显，并且分类准确率也较好.例如数据集Wine，在分类器是1NN和5NN时，IFSCrSA的分类准确率略低于其他算法，但维度缩减则高于其他算法;在分类器是3NN和J48时，IFSCrSA的分类准确率达100%，同时维度缩减也明显高于其他对比算法.
分析表明，由于KNN算法在对数据进行分类时只依据最邻近的一个或者几个特征的类别，所以可能对实验结果产生一定影响.对于数据集Vehicle，IFSCrSA的分类准确率不太理想，但维度缩减明显高于其他算法.例如在分类器为SVM时，IFSCrSA的分类准确率为63.59%，维度缩减为77.78%，HGAFS算法的分类准确率为76.36%，但维度缩减仅为38.99%.
这可能是因为IFSCrSA删除了过多的特征，使分类器在很小特征子集情形下，降低了分类准确率所致.综上所述，本文采用乌鸦搜索算法的思想，基于反向的初始学习策略、Lévy飞行和贪婪搜索策略，提出了使用IFSCrSA解决特征选择问题，通过引入基于对立的初始化学习策略获得了更好的原始种群，使用Lévy飞行搜索策略平衡全局搜索与局部搜索，使用基于贪婪搜索策略的更新机制进一步提高了收敛速度.实验结果表明，IFSCrSA性能优于传统算法.
参考文献
[1]周志华.机器学习[M].北京：清华大学出版社，2016：247-261.(ZHOUZhihua.MachineLearning[M].Beijing：TsinghuaUniversityPress，2016：247-261.)
[2]YANGXin.Nature-InspiredMetaheuristicAlgorithms[M].[S.l.]：LuniverPress，2010：1-5.
[3]AFFENZELLERM，BEHAMA，KOFLERM，etal.MetaheuristicOptimization[C]//HagenbergReseach.Berlin：Springer，2009：103-155.
相关刊物推荐：《密码学报》(双月刊)创刊于2013年，是国家新闻出版广电总局批准创办《密码学报》。是中国密码学会主办的唯一学术期刊。
转载请注明来自发表学术论文网：http://www.fbxslw.com/dzlw/20325.html
