基于超球和ASSRFOA的多生支持向量机.pdf
《基于超球和ASSRFOA的多生支持向量机.pdf》由会员分享,可在线阅读,更多相关《基于超球和ASSRFOA的多生支持向量机.pdf(10页珍藏版)》请在咨信网上搜索。
1、基于超球和 ASSRFOA 的多生支持向量机莫源乐,朱嘉静,刘勇国,张云,李巧勤(电子科技大学信息与软件工程学院中医知识与数据工程实验室,成都610054)通信作者:朱嘉静,E-mail:摘要:支持向量机(supportvectormachine,SVM)是一种基于结构风险最小化的机器学习方法,能够有效解决分类问题.但随着研究问题的复杂化,现实的分类问题往往是多分类问题,而 SVM 仅能用于处理二分类任务.针对这个问题,一对多策略的多生支持向量机(multiplebirthsupportvectormachine,MBSVM)能够以较低的复杂度实现多分类,但缺点在于分类精度较低.本文对 MBS
2、VM 进行改进,提出了一种新的 SVM 多分类算法:基于超球(hypersphere)和自适应缩小步长果蝇优化算法(fruitflyoptimizationalgorithmwithadaptivestepsizereduction,ASSRFOA)的MBSVM,简称 HA-MBSVM.通过拟合超球得到的信息,先进行类别划分再构建分类器,并引入约束距离调节因子来适当提高分类器的差异性,同时采用 ASSRFOA 求解二次规划问题,HA-MBSVM 可以更好地解决多分类问题.我们采用 6 个数据集评估 HA-MBSVM 的性能,实验结果表明 HA-MBSVM 的整体性能优于各对比算法.关键词:超球
3、;多生支持向量机;多分类;自适应缩小步长;果蝇优化算法引用格式:莫源乐,朱嘉静,刘勇国,张云,李巧勤.基于超球和 ASSRFOA 的多生支持向量机.计算机系统应用,2023,32(9):4352.http:/www.c-s- Birth Support Vector Machine Based on Hypersphere and ASSRFOAMOYuan-Le,ZHUJia-Jing,LIUYong-Guo,ZHANGYun,LIQiao-Qin(KnowledgeandDataEngineeringLaboratoryofChineseMedicine,SchoolofInformati
4、onandSoftwareEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China)Abstract:Supportvectormachine(SVM)isamachinelearningmethodbasedonstructuralriskminimizationandcansolveclassificationproblems.However,withthecomplexityofresearchproblems,therealclassificationproblemsareofte
5、nmulti-classificationones,whereasSVMcanonlybeadoptedtodealwithbinaryclassificationtasks.Tothisend,themultiplebirthsupportvectormachine(MBSVM)combinedwiththeone-against-allstrategycanrealizemulti-classificationwithlowcomplexity,buttheclassificationaccuracyislow.ThisstudyimprovesMBSVMandproposesanewSV
6、Mmulti-classificationalgorithmwhichisamultiplebirthsupportvectormachinebasedonthehypersphereandfruitflyoptimizationalgorithmwithadaptivestepsizereduction(ASSRFOA).ThealgorithmisreferredtoasHA-MBSVM.Throughtheinformationobtainedfromhyperspherefitting,firstlyallclassesaredividedintoseveralblocksandthe
7、nclassifiersareconstructedforeachclass.Theconstraintdistanceregulationfactorisintroducedtoproperlyimprovethedifferenceoftheclassifiers.Atthesametime,ASSRFOAisemployedtosolvethequadraticprogrammingproblemsandHA-MBSVMcanbettersolvethemulti-classificationproblems.Sixdatasetsareutilizedtoevaluatetheperf
8、ormanceofHA-MBSVM.TheexperimentalresultsshowthattheoverallperformanceofHA-MBSVMisbetterthanthatofthecomparisonalgorithms.Key words:hypersphere;multiplebirthsupportvectormachine(MBSVM);multi-classification;adaptivestepsizereduction;fruitflyoptimizationalgorithm(FOA)计算机系统应用ISSN1003-3254,CODENCSAOBNE-m
9、ail:ComputerSystems&Applications,2023,32(9):4352doi:10.15888/ki.csa.009216http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:国家自然科学基金(62202084);国家科技基础资源调查专项(2022FY102002);中国博士后科学基金(2021M690028);中央高校基本业务费(ZYGX2021YGLH012,ZYGX2021J020);四川省自然科学基金(2022NSFSC0883,2022NSFSC0958);四川省重点研发计划(2022YFS0059,202
10、3YFS0338)收稿时间:2023-02-13;修改时间:2023-03-14;采用时间:2023-03-30;csa 在线出版时间:2023-07-14CNKI 网络首发时间:2023-07-17SpecialIssue专论综述43SVM1是一种基于结构风险最小化的机器学习方法,在解决小样本、高维问题和非线性问题等方面表现出良好的泛化能力和预测性能,在生物医学25、故障分析69、图像识别1012等领域中被广泛应用,并具有可观的分类效果13,14.随着研究问题的复杂化,现实的分类问题不单纯是二分类任务,存在多分类的现象,而 SVM 仅能用于处理二分类任务.针对这个问题,现有的工作已做出重要的
11、贡献1519.其中一对一(one-against-one,OAO)策略、一对一对余(one-against-one-against-rest,OAOAR)策略、一对多(one-against-all,OAA)策略是 3 种最常用的间接求解多分类问题的分解策略20.对于一个具有 K 个类别的多分类问题,结合 OAO 策略的一对一支持向量机(one-against-onesupportvectormachine,OAOSVM)任选两个类别的样本,分别作为正反两类,构建 K(K1)/2 个 SVM 分类器.结合 OAOAR 策略的支持向量分类-回归机(supportvectorclassificat
12、ion-regressionmachineforK-classclassification,K-SVCR)21在正反两类的基础上,增加了其余类,减少了样本的误分.将孪生支持向量机(twinsupportvectormachine,TWSVM)22与 OAA 策略结合,Yang 等人提出了MBSVM23,通过将“最近”的决策方式转变为“最远”的决策方式,有效减少了约束条件,因而具有较低时间复杂度.MBSVM 虽然在算法效率上具有明显优势,但其分类精度不够高.主要原因有两点24,一是用超平面进行拟合的类别之间可能相距较远,很难使得超平面离它们同时都近;二是约束条件较少,二次规划问题(quadrat
13、icprogrammingproblem,QPP)的求解容易陷入局部最优.对于第 1 个问题,为达到更好的超平面拟合效果,我们希望根据不同类别之间的相似度将所有类别划分成若干块,块内类别的样本相似度相对较高,块间类别的样本相似度相对较低;对于第 2 个问题,应该采用全局性更好的求解算法.ASSRFOA 是一种新型的群智能优化算法,相比于其他算法,它继承了果蝇优化算法(fruitflyoptimizationalgorithm,FOA)优秀的全局寻优能力,同时通过改进候选解生成机制和搜索步长,并引入柯西变异,有效地改善了陷入局部最优的共性问题2527.本文将采用 ASSRFOA 作为 QPP 的
14、求解算法.基于以上讨论,本文从 MBSVM 存在的问题出发,提出一种新的 SVM 多分类算法:基于超球(hypersphere)28和 ASSRFOA 的 MBSVM,简称 HA-MBSVM.该算法框架如图 1 所示,首先通过拟合超球,获取各类样本对应超球的球心和半径.利用球心和半径,计算各类别之间的相似度判定值,然后将所有类别划分成若干块,块内类别样本相似度相对较高,块间类别样本相似度相对较低,最后再为各类别构建分类器并采用 ASSRFOA求解 QPP.我们还引入了约束距离调节因子用以进一步提升 HA-MBSVM 的性能.本文中的算法仅介绍使用了核方法的情形,核函数选择径向基核函数(radi
15、albasisfunction,RBF),规定矢量加粗表示,标量不加粗.拟合超球相似度较低类别划分分类器构建分类器计算相似度判定值相似度判定值球心和半径ASSRFOA约束距离调节因子相似度较高相似度较高图 1HA-MBSVM 算法框架综上所述,本文的主要贡献如下.(1)提出了一种新的 SVM 多分类算法.利用拟合超球所得信息完成类别划分,构建更准确的分类器.(2)将 ASSRFOA 应用于 QPP 的求解,ASSRFOA良好的全局性有利于提高 HA-MBSVM 的性能.(3)采用 6 个数据集对 HA-MBSVM 的性能进行评估.实验结果表明,HA-MBSVM 算法的性能优于常见的 SVM 多
16、分类算法以及 MBSVM.1相关工作本节将介绍与 HA-MBSVM 密切相关的 3 项工作.其中,第 1.1 节介绍 MBSVM23,这是本文算法的改进出发点;第 1.2 节介绍超球相关内容,HA-MBSVM 采用文献 28 中生成超球的方法为各类别的样本拟合超球,获取球心和半径用于后续的类别划分;第 1.3 节介绍的 ASSRFOA 算法25将用于求解 QPP.1.1 多生支持向量机为方便讨论,假定对于多分类问题,有训练集:T=(xi,y1),(xl,yl)(1)计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第9期44专论综述SpecialIssue(xi,yi)x
17、i Rnyi1,K其中,为第 i 个样本,为特征向量,为类别标签,l 是样本数,K 为类别数.Ak RlknBk=AT1,ATk1,ATk+1,ATKTk=1,K,lk对于训练集(1),假设第 k 类样本构成矩阵,训练集(1)中除去第 k 类样本的剩余样本构成矩阵,为第 k类样本的数量.MBSVM 每次选取一个类的样本作为负样本,其他类的所有样本作为正样本,寻找一个超平面,要求该超平面离正样本尽可能近,离负样本尽可能远,即获得式(2)22,29.K(x,E)vk+bk=0,k=1,K(2)vk RlbkE=AT1,ATKT,K(x,E)RlK(x,y)vkbk其中,和为模型参数,为由核函数产生
18、的行向量.为了计算和,需要解决如下 QPP 问题,如式(3)所示.minvk,bk,k12K(Bk,E)vk+ek1bk2+CkeTk2ks.t.K(Ak,E)vk+ek2bk ek2kk 0(3)k RlkAkCk 0ek1 Rllkek2 RlkK(Ak,E)K(Bk,E)K(x,y)lkl(llk)l其中,为中样本对应松弛变量的列向量,为惩罚参数,和为元素全是 1 的列向量,和分别为由核函数产生的和的矩阵.由拉格朗日优化方法可将式(3)转为对偶问题(4).maxkeTk2k12TkRk(STkSk)1RTkks.t.0 kCk(4)k RlkSk=K(Bk,E)ek1,Rk=K(Ak,E
19、)ek2STkSkI 0其中,为拉格朗日乘子的非负列向量,.为避免矩阵的病态化导致不可求逆,需要为对偶问题(4)添加一个正则化项,其中为一固定的小标量,I 为适当大小的单位矩阵,于是对偶问题(4)可写成22:maxkeTk2k12TkRk(STkSk+I)1RTkks.t.0 kCk(5)由各类别对应 QPP 求解得到的超平面,MBSVM的决策函数计算新样本到各超平面的距离,相距最远的超平面对应的类别即为新样本的预测类别标签.1.2 超球Aknkrk朱美琳等人提出的球结构支持向量机,通过为每个类别拟合超球来解决多分类问题28.对于训练集(1),当为拟合超球时,假定为最小超球的球心,为最Ak小超
20、球的半径,要求该最小超球尽可能包含中所有样本点,通过引入松弛变量,允许存在样本点位于超球外侧.于是,可得到如下优化问题(6).min(rk)2+Cklki=1kis.t.?xkink?2(rk)2+kiki 0,i=1,lk(6)xkiAkkixkiCk 0其中,为中第 i 个样本点的特征向量,为对应的松弛变量,为惩罚参数.引入核函数并利用拉格朗日优化方法,可将式(6)转为对偶问题(7).maxlki=1kiK(xki,xki)lki=1lkj=1kikjK(xki,xkj)s.t.lki=1ki=10 kiCk,i=1,lk(7)ki其中,为式(6)中第 i 个约束条件对应的拉格朗日乘子.通
21、过求解式(7),可以得到满足要求的拉格朗日乘子,进而得到超球的球心和半径.1.3 ASSRFOA 具体步骤Xaxis RD、Yaxis RD步骤 1.初始化最大迭代次数 Maxgen、果蝇种群规模 Sizepop、味道浓度方差阈值 和果蝇群体位置,D 为待求解未知量的个数.步骤 2.赋予果蝇个体随机的搜索方向和距离.Xi=Xaxis+RandYi=Yaxis+Rand(8)Rand RDXiYii=1,Sizepop其中,其元素均为 1,1 之间的随机数,和为各果蝇个体基于群体位置随机分散后所处的位置,.Xi=(pi,pD),Yi=(q1,qD),Disti RDSDi RD步骤 3.设利用式
22、(9)计算果蝇个体到原点的间距,再利用式(10)计算味道浓度判定值.Disti=(p21+q21,p2D+q2D)(9)SDi=sign(Rand)p21+q21,sign(Rand)p2D+q2D(10)Rand 其中,随机数1,1,sign 函数如式(11)所示30.2023年第32卷第9期http:/www.c-s-计 算 机 系 统 应 用SpecialIssue专论综述45sign(x)=1,x 00,x=01,x 0(11)SDismelli步骤 4.把代入到味道浓度判定函数 Fitness(即目标函数),计算出味道浓度值.smelli=Fitness(SDi)(12)步骤 5.找
23、出果蝇种群中味道浓度值最优的果蝇,并记录此果蝇的位置信息和相应的味道浓度值.Currentbest,bestindex=max(Smell)(13)bestindex 1,SizepopSmell=(smelli,smellSizepop)其中,Currentbest 为最优味道浓度值,为最优味道浓度值对应下标,.2步骤 6.计算味道浓度方差值,且当迭代次数不为 0 时,转至步骤 7,否则转至步骤 8.2=1SizepopSizepopi=1smelliSizepopi=1smelliSizepop2(14)步骤 7.判断 Currentbest 是否优于历史最优味道浓度值 Globalbes
24、t,是则通过式(15)和式(16)保留 Current-best 并更新果蝇群体位置,然后转至步骤 8,否则直接转至步骤 8.Globalbest=Currentbest(15)Xaxis=XbestindexYaxis=Ybestindex(16)2 步骤 8.判断是否陷入局部最优,若,则转至步骤 9,否则转至步骤 10.步骤 9.利用式(17)对果蝇个体位置进行柯西变异,然后转至步骤 11.Xi=Xi+XiC(0,1)Yi=Yi+YiC(0,1)(17)其中,C(0,1)为标准柯西分布.步骤 10.根据式(18)更新果蝇个体位置,然后转至步骤 11.Xi=Xaxis+e(g)MaxgenR
25、andYi=Yaxis+e(g)MaxgenRand(18)e(g)Maxgen其中,为搜索步长,为步长调控因子,为指数调节因子,g 为当前迭代次数.步骤 11.当前迭代次数不大于 Maxgen,执行步骤3 至步骤 10,否则执行步骤 12.步骤 12.输出全局最优解.2HA-MBSVM 2.1 类别划分在 MBSVM 中,被作为正类的样本间可能相距较远,很难构建一个超平面离它们同时都近.于是我们尝试先将所有类别根据彼此间的相似度和给定阈值划分成若干块,块内类别样本相似度相对较高,块间类别样本相似度相对较低,之后再分别以各块的样本作为约束条件来构建多个超平面,从而避免因单个超平面难以同时有效地
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 ASSRFOA 支持 向量
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。