贾鹤鸣,姜子超,李 瑶,孙康健
(1.三明学院信息工程学院,福建三明 365004;2.东北林业大学机电工程学院,哈尔滨 150040)
(*通信作者电子邮箱jiaheminglucky99@126.com)
随着各领域的信息计算需求不断增加,数据挖掘技术发展日新月异,人类进入大数据时代[1]。海量的数据不仅给人们带来繁重的处理工作,也无法准确地从中提取有效信息,机器学习的出现提升了数据处理的效果与能力。作为数据挖掘技术的一个分支,数据分类是一项重要的基础工作,而数据中冗余、不相关的特征或噪声属性常常会影响分类的性能。特征选择是重要的数据预处理环节,其基于某种评价标准从原特征空间中选择特征子集,通过消除数据中的冗余和不相关特征来减少计算时间,提升学习准确率[2],故所选特征子集比原特征集具有更优秀的分类效果,从而显著改善数据挖掘的能力。特征选择依据其与学习器结合的方式不同可分为过滤式、封装式、嵌入式与集成式四种[3],本文主要研究的是封装式特征选择方法,对于分类问题而言,其核心研究内容为如何利用搜索策略与学习算法在高分类准确率上获取最优特征子集,两者矛盾是特征选择的主要挑战。
因特征选择可视为最优化问题,为提高传统封装式特征选择所得最优特征子集的分类准确性,故诸多学者采取元启发式优化算法作为搜索策略对其进行研究。在K最近邻学习算法中,Jia 等[4]针对封装式特征选择分类性能差设计了一种混合海鸥优化算法,通过引入热交换原理来增强海鸥算法的局部搜索能力,有效提高了数据分类准确率并减少计算时间;张翠军等[5]提出一种多目标骨架粒子群优化的封装式特征选择算法,该方法显著改善了数据分类的性能与效率;Mafarja等[6]提出了一种基于鲸鱼优化的封装式特征选择方法,利用二进制鲸鱼优化算法来搜索最优特征子集完成分类任务,效果良好;张霞等[7]提出一种增强蜂群算法优化的封装式特征选择方法,极大地提高了数据分类的准确率。在支持向量机(Support Vector Machine,SVM)的学习算法[8]中,通过引用核函数技术生成精确模型,提高了计算效率与准确率,但其惩罚因子与核函数参数的选取会影响算法的泛化学习能力,而参数的调整与选择亦可视为优化问题来研究。庄严等[9]将蚁群优化算法引入SVM 参数的调整选择中,效果良好但未对原优化算法做出特征选择的应用研究;Huang 等[10]将遗传算法用于同步优化支持向量机的参数调整与特征选择,改善了SVM分类的效果,虽克服了对其单独优化的缺陷,但未对遗传算法做出改进研究;张进等[11]提出了一种基于改进粒子群优化的SVM 特征选择与参数联合优化方法,有效提高了特征选择的性能,但所选优化算法较为陈旧,优化性能有待进一步提升。上述研究所采取的元启发式优化算法均体现出一定优势,但在特征选择及SVM 参数同步优化的实际应用中,待优化目标体现出的复杂性与多样性使得部分优化算法在搜索计算时表现不佳,因此对优化机制新颖、求解精准、综合计算能力强的优化算法探究仍是封装式特征选择的重要研究方向之一,本文针对SVM 参数调整与特征选择联合同步优化效果做出深入研究,使得SVM 学习算法获取更精确的分类模型,降低单独优化的时间成本,同时改善封装式特征选择的性能。
受生物行为与自然现象启示的元启发式优化算法已有二十余年的研究,其主要包括进化类与群智能类。以遗传算法(Genetic Algorithm,GA)[10]为主的进化类包括:差分进化(Differential Evolution,DE)[12]算法、生物地理学优化(Biogeography Based Optimizer,BBO)[13]等;以粒子群优化(Particle Swarm Optimization,PSO)[14]算法为主的群智能类包括:布谷鸟搜索(Cuckoo Search,CS)[15]算法、灰狼优化(Grey Wolf Optimizer,GWO)[16]算 法、鲸鱼优化算法(Whale Optimization Algorithm,WOA)[17]等。尽管两类算法优化机制不同,但优化目标均为求解某一范围内的最优值。上述优化算法在现实的复杂工程问题中得到了有效的应用,但No-Free-Lunch 定理[18]表明没有一种算法能解决所有优化问题,因此对更优秀的优化算法的探索仍具有较高的研究价值。Dhiman 等[19]提出的斑点鬣狗优化(Spotted Hyena Optimizer,SHO)算法在诸多工程优化中效果良好,其与GWO 等均为群智能类优化算法,因此近年来诸多学者对其优化能力进行了相关研究。Kumar 等[20]基于SHO 设计了其二进制版本算法(Binary Spotted Hyena Optimizer,BSHO),将其离散化处理后应用于封装式特征选择中,通过数据集的特征选择实验仿真验证了二进制的斑点鬣狗优化算法在特征选择领域中的优越性与可行性;Jia 等[21]针对SHO 算法的局部优化效果不佳,混入模拟退火算法来增强搜索能力,提出斑点鬣狗模拟退火(Spotted Hyena Optimizer Simulated Annealing,SHOSA)算法,结合K 最近邻学习算法应用于封装式的特征选择中,提高了分类精度与特征选择性能。综上所述,SHO 算法在封装式特征选择的应用中表现良好、效果显著,与其他群智能优化算法相比具有一定的竞争性,故本文采用该算法进行封装式特征选择方面的研究。
本文主要研究内容如下:首先在DE算法中引入自适应控制参数[22],增强原算法搜索能力,提出自适应差分进化(Adaptive Differential Evolution,ADE)算法;其次用混沌初始化[23]、锦标赛选择策略[24]与ADE 算法对标准SHO 算法进行改进,增强原算法的局部搜索能力,提高其寻优效率与求解精度;随后利用改进算法优化支持向量机学习器,将这种模型用于封装式的特征选择中,同步处理特征子集选取与支持向量机参数调节;最后利用标准数据集进行测试仿真实验,对比分析评价指标,证明本文所提算法能够避免局部最优,提高全局搜索精度,在解决封装式特征选择问题时效果显著。
标准斑点鬣狗优化算法源于非洲斑点鬣狗的种群狩猎觅食机制,主要包括对猎物的搜索、包围、狩猎和攻击过程[19]。
1)包围过程。
斑点鬣狗首先会寻找猎物,依靠视觉来判断猎物的位置。将此刻与猎物距离最近的那只斑点鬣狗视为当前最优解,随后其他斑点鬣狗的位置将依据最优解进行更新,从而获得全局最优解。数学模型的描述如式(1)和(2)所示:
式中:Dh定义为斑点鬣狗与猎物间的距离;x为当前迭代数;P是斑点鬣狗位置;Pp代表猎物位置;B和E分别为摇摆因子和收敛因子,具体定义如下:
式中,rd1与rd2为[0,1]区间随机值;h为控制因子,迭代过程中从5 线性递减到0;iter=1,2,…,Maxiter,Maxiter为最大迭代次数。
2)狩猎过程。
斑点鬣狗依靠信任等级制度来进行分组捕杀。在种群中定义最佳搜索个体,其他斑点鬣狗搜索个体将朝着最佳搜索个体聚集,并组成最佳搜索组。因此该行为具体定义为:
式中:Ph为第一个最佳搜索个体位置;其他个体位置定义为Pk;Ch为最佳搜索组位置;N为斑点鬣狗数量,定义如下所示:
式中:M为一个[0.5,1]的随机向量,nos表示所有可行解的数量。该过程与在给定搜索空间中寻找最优解类似。
3)攻击过程(局部搜索)。
在此阶段斑点鬣狗将继续更新自己的位置,最终对猎物发动攻击。控制因子将随着迭代次数增加从5线性减小到0,同时收敛因子E也逐渐减小。当|E|<1 时,斑点鬣狗将发动攻击。攻击猎物的数学公式如下所示:
式中P(x+1)为当前最优解集的平均值。
4)搜索过程(全局探索)。
多数斑点鬣狗根据最佳搜索组Ch中的斑点鬣狗的位置来搜索猎物,然而当收敛因子|E|>1 时,斑点鬣狗会彼此远离,再次寻找和攻击猎物,从而进行全局搜索。
Storn 等[12]提出的差分进化算法与遗传算法类似,包括变异、交叉和选择操作。该算法从初始种群开始,把两个随机个体的向量差与第三个个体求和来得到变异个体,然后将变异个体与父代种群中相应的个体按一定规则交叉产生新个体。通过进化,优胜劣汰,保留优良个体,向最优解进行搜索。算法中“变异”“交叉”和“选择”算子如下所示。
1)变异算子。
DE算法的变异操作定义为:
2)交叉算子。
其中:rand是[0,1]的随机数;CR表示交叉概率。
3)选择算子。
式中f为适应度函数。
标准斑点鬣狗算法参数设置简单、结构清晰,同时全局搜索能力较强,但该算法尚处于研究初级阶段,仍存在一些缺陷,如局部搜索能力弱、后期收敛速度慢等。因此,本文将使用混沌初始化策略[23]、锦标赛选择策略[24]和ADE 算法对其进行改进,提出一种自适应差分进化斑点鬣狗优化(Adaptive Differential Evolution Spotted Hyena Optimizer,ADESHO)算法来改善其优化复杂性问题时的不足。
据差分进化算法表达式可知,SF和CR是DE 算法中的两个重要参数,该参数的选择会影响优化效果。但在DE 算法中,其值均为常数,不足以适应各类问题,特别是复杂的求解问题,因此引入可自适应控制参数[22]改进DE 算法,即ADE 算法。自适应控制参数SF和CR分别表示为:
式中:rand1~rand4均为0~1 的随机数;τ1和τ2表示转换概率;SFl和SFu为边界缩放因子。在本文中,τ1与τ2为0.1;SF及CR的初始值[22]分别为0.5与0.9。ADE算法流程如图1所示。
图1 ADE算法流程Fig.1 Flowchart of ADE algorithm
ADE 与GA 类似,虽均包括变异、交叉、选择操作,但ADE算法源于DE,仍与GA 有一定的区别。从优化机制上来看,GA[10]模拟基因重组与进化的自然过程,把待解决优化问题的参数编成二进制或十进制码等的基因,若干基因组成一个染色体(个体),而染色体进化类似于自然选择、配对交叉和变异的运算,经过多次重复迭代(即世代遗传)直到获得最终优化结果,其较容易陷入局部最优,存在一定的早熟现象;而ADE算法则是基于种群随机选择个体向量,将差分向量赋予权值后与第3 个随机选择的个体向量叠加,产生新的变异个体,在原DE[12]算法的基础上进行自适应参数运算,与预先确定的父代个体向量交叉产生实验向量,在不断的进化下评价种群,保留优秀个体,引导搜索过程向最优解逼近,改善优化效果。综上,ADE 算法在DE 算法中引入自适应参数,主要是利用差分的机制平衡启发式算法的探索与利用水平,而GA 则是通过原始种群间的基本遗传变异、进化操作进行算法在解空间的探索与利用,因此基于以上两者区别,本文选择优势较强的ADE算法进行相关混合优化研究。
Lin 等[22]提出混合免疫算法和自适应差分进化算法增强了免疫算法的收敛速度和种群多样性;Elaziz等[25]提出混合飞蛾搜索差分进化算法(Moth Search and Differential Evolution Algorithm,MSDEA),增强了飞蛾搜索算法的局部搜索能力,在云计算任务调度问题上效果显著。在上述混合算法应用启发下,为避免算法陷入局部最优,本文将ADE 算法与SHO 算法混合优化,以提高SHO的求解精度和稳定性。
在群智能算法中,种群初始化方法决定了全局搜索的质量和效率。初始种群的多样性可以提高搜索的效率,增强算法的计算能力。标准SHO 算法采用随机初始化策略,具有一定概率的重复性,可能不会遍历搜索空间,未能最大限度发挥SHO算法的优化能力。
混沌理论有强大的随机性、遍历性、敏感性和非重复性。作为一种优化策略,该理论已经被有效地应用于粒子群算法和人工蜂群算法等群智能算法中产生初始种群[23]。因此,利用混沌理论可增强初始种群的多样性,使算法以更高的效率对搜索空间进行寻优。目前群智能算法多采用Logistic 映射进行混沌初始化,但均匀性较差。相对于Logistic 映射,Tent映射具有结构简单,遍历均匀性更好的优点,因此,本文选择Tent 映射产生的混沌序列对斑点鬣狗种群进行混沌初始化。Tent 映射产生的种群会更均匀地分布在搜索空间,减小陷入局部最优的概率,间接增强全局搜索能力,提高求解质量和效率[23]。Tent映射的表达式如下:
经伯努利位移变换后可得:
锦标赛选择策略是一个类似于比赛选拔的机制,随机选取适应度值优秀的个体,不需要对所有的适应度值进行排序处理。这种策略不仅简单易行,而且计算复杂度低,可并行化处理,不易陷入局部最优,具体选择策略过程如图2所示。
图2 锦标赛选择策略的选择Fig.2 Selection of tournament selection strategy
由图2 可知,锦标赛选择策略简单直观,它先从总体(种群个数为10)中随机挑选一部分个体(挑选的个体数设置为5),使其进行适应度值的比较,选取其中最好的个体(F=3)进入子代种群。反复进行这个操作,直到子代种群的数量达到原来种群的数量,选择结束[24]。本文利用该策略对斑点鬣狗种群个体适应度值进行选择,具体步骤如下:
步骤1 首先确定每次选择的斑点鬣狗个体数量。
步骤2 其次从种群中随机选择个体(每个个体入选概率相同)构成组,根据每个个体的适应度值,选择组中适应度值最好的斑点鬣狗个体进入子代种群。
步骤3 重复步骤2,直到子代种群的数量达到原来种群的数量,得到的个体构成新一代斑点鬣狗种群为止。
本文所提的ADESHO 算法首先进行斑点鬣狗种群的混沌初始化,选择种群的初始参数;其次计算斑点鬣狗种群每个个体的适应度值,将斑点鬣狗种群进行锦标赛选择;随后依据收敛因子E的值判断算法进行全局搜索还是局部搜索。若|E|<1,则使用ADE 算法进行局部搜索,首先更新自适应控制参数SF和CR,随后进行变异、交叉和选择操作,计算每个新个体的适应度。此时,若没有达到算法终止条件,则继续进行锦标赛选择来产生下一代个体,判断下一步进行全局搜索还是局部搜索。若达到算法终止条件,则输出最优解,算法结束。若|E|>1,则算法进行全局搜索,按照式(8)、(9)来搜索斑点鬣狗新的组解,计算每个个体的适应度值,判断算法是否到达终止条件,输出保留的最优解,结束算法。ADESHO 算法的具体流程如图3所示。
图3 ADESHO算法流程Fig.3 Flowchart of ADESHO algorithm
自适应差分进化斑点鬣狗优化算法可以解决离散化问题,对于特征选择组合优化类问题时,需要将数据集中的特征改为二进制字符串进行实验。本文首先对特征进行二进制编码,得到一个二进制字符串,如果某一特征被选中,则对应的二进制位为“1”;否则对应的二进制位为“0”。在算法输出结束时通过二进制转换机制进行解码输出特征数目,实现SHO算法在特征组合优化类问题中的有效应用。
支持向量机在构建分类模型的时候,需要确定核函数参数γ和惩罚因子C。若依照所有特征训练模型,进行参数优化,再进行特征选择的流程,支持向量机所采用的关键特征在特征选择中没有被选择,则训练模型结果不够精确;若先进行特征选择,然后进行参数挑选,训练模型的时间成本过大。鉴于以上两种单独计算优化的不足,本文提出将SVM 的参数优化和特征选择同步进行的方法,提高分类模型的精确性并极大降低时间计算的成本。每一个搜索个体搜索的维度包括两部分:前部分为γ和C;后部分代表数据集特征的二进制字符串,n为数据集中的特征个数[26]。粒子设计示意图如图4所示。
图4 搜索粒子设计示意图Fig.4 Schematic diagram of search particle design
特征选择可视为多个目标优化问题,主要包括两个相互矛盾目标:分类准确率与所选特征的个数。当分类结果中分类准确率较高,选择特征个数较少时说明所得分类效果优秀。在算法迭代过程中,本文采用适应度函数来评估每个解的质量。ADESHO 算法与SVM 可平衡分类准确率和所选特征个数这两个指标,因此,根据SVM 分类器所得到的解的分类准确率与所选特征个数的关系[26],设计适应度函数如下:
式中:accuracy是指分类结果的正确率;R表示所选择的特征个数;N表示该数据集拥有的总特征数;α与β分别表示分类精确性与所选特征的重要性[27],且α+β=1,α属于(0,1),本文α取0.99。
机器学习中通常将数据集分为训练集和测试集来检验模型的能力,但这可能会导致训练出的模型效果差、泛化能力较弱等问题,交叉验证法可以解决上述问题[28]。K折交叉验证是将原始数据分为K份子集,其中K-1 份子集作为训练集,余下一份为测试集,重复此过程K次,得到K个结果,取其平均值作为模型的性能指标。该方法可有效利用样本数据,所得结果客观、准确,故本文利用K折交叉验证来保证模型的泛化能力(K=10)[28]。
基于以上两处设计,本文所提ADESHO 算法同步优化SVM与特征选择的方法流程如下。
步骤1 预处理数据,LIBSVM函数输入样本数据集。
步骤2 将样本数据每一个特征进行二进制编码(数据归一化后与0.5比较,若大于则记为1;否则记为0)。
步骤3 产生混沌初始化的斑点鬣狗种群;选择初始化所需的参数(包括种群大小、搜索维度、最大迭代数目、随机向量M、控制因子h、常值比例因子SF、交叉概率CR等)。
步骤4 初始化SVM 核参数γ及惩罚因子C,使用ADESHO算法对γ、C和二进制编码特征同时进行搜索。
该客户端主要针对消费者进行开发,主要实现农产品从生产到销售各个阶段的实时溯源信息的查询和展示工作,通过扫码进行信息的自动查询。主要的界面如下图所示:
步骤5 将搜索后的样本二进制特征进行解码,二进制码为“1”的特征从数据集中挑选出来。
步骤6 将数据集中选出的特征和γ、C一起输入SVM 分类器中进行分类测试,交叉拆分样本集,采用10 折交叉验证方法训练SVM 分类器来计算适应度值(式(18)),若有比当前最优解更好的解,则更新最优解。
步骤7 判断是否满足终止条件,若满足则停止优化并保存当前最优解,否则返回步骤5。
步骤8 输出并保存最优解(γ、C、最优特征子集及分类准确率),结束算法流程。
为了验证ADESHO 算法优化SVM 与特征选择的有效性,本文采用UCI[29]数据库中经典数据集进行仿真实验。实验共分3 部分:第1 部分为本文算法与标准SHO、传统SVM 算法[26]进行特征选择对比实验;第2 部分为本文算法与其他四种元启发式优化算法[14-17]的特征选择对比实验;第3部分为本文算法与同类改进算法研究的横向对比实验。实验所涉及8 个数据集信息列于表1,所有对比算法参数列于表2,其来源于文献[14-17]、[19]、[21]及[25]。
表1 UCI数据集的详细信息Tab.1 Details of UCI datasets
表2 所有对比算法实验参数Tab.2 Experimental parameters of all comparison algorithms
在原始数据集中,数据类型及大小参差不齐会影响SVM的分类效果,因此在进行特征选择仿真实验之前,数据集需预处理。本文首先将字符串类型的特征转化为数值型特征,其次为平衡所有特征属性的选择可能,利用数值归一化[26]公式将所有数值均归一化到[0,1]内,如下所示:
式中:X表示原始数据,Xnorm表示归一化后的数据,Xmin和Xmax分别代表此特征取值范围的最小值和最大值。
实验仿真环境为Windows 7 系统,微处理器主频为3.30 GHz,仿真软件为Matlab 2016a,采用LIBSVM 工具箱。种群大小与最大迭代数设为30 与100,每种算法在每个数据集上进行30次实验,取平均值作为最终结果。
为验证优化算法性能,本文选取如下几种性能指标[21]进行评估(指标公式中M均为算法运行次数):
式中:TP(True Positive)表示分类结果为真阳性;FP(False Positive)代表分类结果为假阳性;FN(False Negative)表示分类结果为假阴性。
平均分类准确率 是运行M次算法后所得分类结果的平均正确率,公式如下:
式中Accuracy(i)为算法第i次运行后的分类正确率。
平均选择特征个数 指M次算法运行后所选择特征个数的平均值,计算如下:
式中Size(i)为算法第i次运行后所选择特征的个数。
适应度值 表示分类准确率和选择特征数目的综合评价指标,也是训练特征选择模型时的标准,计算公式与式(18)相同,取其平均值与标准差来评价算法性能,如下:
式中fitness(i)为算法第i次运行中的适应度值。
平均运行时间M次算法运行所需的平均时间,如下:
式中Runtime(i)为算法第i次运行所需时间。
4.2.1 标准SHO、传统SVM与本文算法的特征选择对比
为验证本文算法在特征选择中的有效性,本节将本文算法与标准SHO、传统SVM 算法作为选择特征子集的方法,进行特征选择的实验对比。传统SVM 算法对数据分类使用的是网格搜索法[26],寻找最优的核参数和惩罚因子,然后进行特征选择。
图5 为本文算法与原SHO、传统SVM 算法在二分类数据集中特征选择所获得的F1值,结果表明ADESHO 算法的搜索效果良好,改进有效。
图5 本文算法与原算法特征选择后的F1值对比Fig.5 Comparison of F1-score between the proposed and original algorithms after feature selection
表3为本文算法、标准SHO、传统SVM 算法特征选择后的平均分类准确率与所选特征平均数,在平均分类准确率上,本文算法在全部数据集中均具有最高分类准确率,证明本文算法能够更准确地对数据进行分类;在所选特征平均数上,ADESHO 算法能够在多数数据集中选取更少的特征,较标准SHO与传统SVM的网格搜索算法更适合特征选择。
表3 本文算法与原算法的平均分类准确率和所选特征平均数测试结果Tab.3 Test results of average classification accuracy and average number of selected features of the proposed and original algorithms
基于本文算法与标准SHO、传统SVM 算法特征选择的适应度值与平均运行时间如表4 所示。从适应度值上可知,虽部分数据特征选择不够稳定,但在平均适应度值中,本文算法效果良好,相对稳定,证明本文改进方法有效;在算法的平均运行时间上,本文所提算法计算效率一般,不及标准SHO 算法,但却优于传统网格搜索SVM 最优参数后特征选择的方法,故本文改进依旧有效。综上所述,在特征选择问题上,ADESHO 的同步优化方法在各方面均优于标准SHO、传统优化SVM 的网格搜索算法,故本文后续将使用ADESHO 方法与其他优化算法进行特征选择对比实验。
表4 本文算法与原算法的适应度值和平均运行时间测试结果Tab.4 Test results of fitness value and average running time of the proposed and original algorithms
4.2.2 本文算法与其他算法的特征选择对比
前一节已证明本文算法特征选择效果显著优于标准SHO与传统SVM 算法,为进一步证明本文算法在特征选择中的优越性,本节将所提算法与其他四种元启发式优化算法进行特征选择实验对比。图6展示了ADESHO 算法与其他四种优化算法在4 个二分类数据集中的F1值,虽未在全部数据集中效果最佳,但本文算法仍在空间搜索与优化中表现良好;基于本文所提算法与其他四种优化算法在平均分类准确率和所选特征平均数上的仿真测试结果如图7~8所示,实验结果表明:在平均分类准确率上,本文算法在6 个数据集中平均分类准确率均最高,平均提高了3 个百分点,数据分类效果优于其他四种算法;在所选特征的平均数上,本文算法在6 个数据集中所选特征子集数目平均值均最少,平均减少了2.7 个特征,相较于其他算法,本文算法有效地降低了数据维度。
图6 本文算法与其他优化算法的F1值对比Fig.6 Comparison of F1-score between the proposed and other optimization algorithms
图7 本文算法与其他优化算法的平均分类准确率对比Fig.7 Comparison of average classification accuracy between the proposed and other optimization algorithms
基于本文算法与其他四种算法特征选择时的适应度值如表5 所示,在适应度平均值上,ADESHO 算法未在全部数据集中表现最优,但与其他算法对比,本文所提算法在多数数据集中表现良好;在适应度标准差上,GWO 算法具有一定的竞争性,但本文算法仍在半数数据集中具有相对稳定的优化性能,因此,从适应度值上来看,本文算法在特征选择中更好地平衡了准确率与特征数目两者的矛盾,同时具有良好的稳定性。
表5 ADESHO与其他优化算法的适应度值测试结果Tab.5 Test results of fitness value of ADESHO and other optimization algorithms
图8 本文算法与其他优化算法的所选特征平均数对比Fig.8 Comparison of average number of selected features between the proposed and other optimization algorithms
图9 为本文算法与其他四种算法特征选择的平均运行时间,测试结果表明:GWO 算法用时较少,而本文算法用于特征选择时计算效率一般,无明显优势,仍需加以改进。综上所述,本文所提出的ADESHO 算法具有优秀的搜索能力与求解精度,尤其在特征选择中表现出明显的优势。
图9 本文算法与其他优化算法的平均运行时间对比Fig.9 Comparison of average running time between the proposed and other optimization algorithms
4.2.3 本文算法与同类改进算法的特征选择对比
为全面综合验证本文算法在特征选择应用中的有效性与优越性,本节对同类混合改进优化算法SHOSA 算法与MSDEA 进行横向对比的特征选择实验研究。在图10 中,展示了本文算法与其他两种同类改进算法在4 个二分类数据集中的F1值结果。数据表明,本文算法较其他同类改进算法特征选择时具有更好的分类效果;图11~12 分别为ADESHO 与SHOSA、MSDEA 特征选择平均分类准确率与所选特征平均数,数据结果表明ADESHO 算法在多数数据集中可以准确分类并有效降低子集特征数目,优化特征选择的能力仍优于其他同类改进算法。
图10 ADESHO算法与其他同类改进算法的F1值对比Fig.10 Comparison of F1-score between ADESHO algorithm and other similar improved algorithms
图11 ADESHO与同类改进算法的平均分类准确率对比Fig.11 Comparison of average classification accuracy between ADESHO and similar improved algorithms
表6 为本文算法与SHOSA、MSDEA 在适应度值及平均运行时间上的对比结果,从表中可以看出,虽然MSDEA 的适应度标准差与SHOSA 的适用度平均值部分表现优于本文方法,但整体上ADESHO 仍较其他两种改进算法在特征选择中效果显著。而对于平均运行时间而言,本文算法与另外两种改进的混合算法表现均不够良好,因将两种算法进行混合操作,在每个粒子进行搜索计算最优解时,时间复杂度随着两种算法的迭代次数与搜索维度增加而变高,因此将两种算法进行混合优化时会产生时间复杂度变高的弊端,如何能够在混合优化能力增强的同时降低算法的时间复杂度将是未来混合优化中一项极具挑战的研究工作。
表6 ADESHO与同类改进算法适应度值及平均运行时间的测试结果Tab.6 Test results of fitness value and average running time between ADESHO and similar improved algorithms
图12 ADESHO与同类改进算法的所选特征平均数对比Fig.12 Comparison of average number of selected features between ADESHO and similar improved algorithms
针对机器学习中封装式特征选择的分类问题,本文提出一种自适应差分进化斑点鬣狗优化算法,并将其应用于特征选择与SVM 参数选取的同步优化中。通过UCI中8个数据集的分类仿真实验来评估本文算法的优化性能,与标准SHO、传统SVM 网格搜索寻优、PSO、CS、GWO、WOA 及同类改进混合SHOSA、MSDEA 进行对比分析,实验结果表明,ADESHO 算法能够有效降低所选特征数目并提高数据分类准确率,优于原算法与其他优化算法的特征选择能力,同时本文算法具有更好、更稳定的适应度值,证明了ADESHO 算法适合解决封装式特征选择问题。在运行时间上,本文算法改善效果不够显著,因此在未来的研究中仍需做进一步的改进。