基于PSO算法的SVM参数优化方法研究.pdf
- 文档编号:3438077
- 上传时间:2023-05-05
- 格式:PDF
- 页数:8
- 大小:792.54KB
基于PSO算法的SVM参数优化方法研究.pdf
《基于PSO算法的SVM参数优化方法研究.pdf》由会员分享,可在线阅读,更多相关《基于PSO算法的SVM参数优化方法研究.pdf(8页珍藏版)》请在冰点文库上搜索。
-9-www.ivypub.org/cstTransactionsonComputerScienceandTechnologyMarch2013,Volume2,Issue1,PP.9-16MethodofParametersOptimizationinSVMbasedonPSOJianLiu1,2,ZhongLiu1,YingXiong21ElectricalEngineeringCollege,NavalUniversityofEngineering,Wuhan430033China;2NavalArchitecture&PowerEngineeringCollege,NavalUniversityofEngineering,Wuhan430033ChinaAbstractToovercometheuncertaintyandtoresolvetheproblemofparametersoptimizationinkernelfunctionofsupportvectormachine(SVM),particleswarmoptimization(PSO)method,whichwasoriginatedformartificiallifeandevolutionarycomputation,isappliedtoSVMsparametersselectionandoptimizationinthepaper.TheimprovedPSOalgorithmofincreasingconvergencerateisproposedbasedontheanalyzingprincipleofbasicPSO.Thereupon,theimprovedPSOalgorithmhasself-adaptiveabilitythatcanbefastersearchinginearlyphaseandmorecarefullysearchinginlatterphaseratherthanbasicPSO,andcanbemeetingtherequestsofdiversificationandintensification.Thesimulationexperimentresultsdemonstratethat,theselectedkernelparametersbythenewPSOalgorithmcanimprovetheoverallperformanceoftheSVMclassifierandhavenewapplicationdomain.Keywords:
SupportVectorMachines(SVM);ParticleSwarmOptimization(PSO);ParametersOptimization;Self-adaptive基于PSO算法的SVM参数优化方法研究刘健1,2,刘忠1,熊鹰21海军工程大学电子工程学院,湖北武汉,4300332海军工程大学船舶与动力学院,湖北武汉,430033摘要:
为了克服支持向量机中核函数参数的不确定性及解决核参数的最优选择问题,本文将起源于人工生命和演化计算理论的粒子群优化算法运用到支持向量机的参数选择中。
在对基本粒子群优化算法工作原理分析的基础上,对基本算法的收敛速度进行了适度改进,使其具有自适应能力,即在初期进行快速搜索,而在末期进行精细搜索,从而扩大参数搜索的宽度和深度,满足多样化和集中化的特点。
仿真实验表明,通过该方法选择出来的核参数能够提高分类及预测精度,具有实用性。
关键词:
支持向量机;粒子群优化;参数优化;自适应引言统计学习理论(StatisticalLearningTheory,STL)1是一种专门的小样本统计理论,为研究有限样本情况下的统计模式识别和更广泛的机器学习(MachineLearning,ML)问题建立了一个较好的理论框架,同时也发展了一种模式识别方法支持向量机(SupportVectorMachine,SVM),在解决小样本、非线形及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其它机器学习问题中。
目前,STL和SVM已经成为国际上机器学习领域新的研究热点并已被应用于人脸识别、文本识别、手写体识别等领域。
SVM是Vapnik于1995年提出的一种新的机器学习方法2,由于具有好的泛化能力,已成为当前ML领域的热点。
SVM是基于核的学习,算法关键是引入了核函数,因此核函数具有重要的地位,其中核参数的选取直接影响到核函数的推广能力。
常用的核函数有:
线性核函数;多项式核函数;径向基核(RBF)函数基金项目:
受中国博士后科学基金(20080431383);海军工程大学自然科学基金(HGDJJ2008029);湖北省自然科学基金(2012FFC129)支持资助-10-www.ivypub.org/cst等,具体可参见文献3。
SVM核函数及核参数的选择是SVM发展过程中亟待完善的问题之一,其本质是一个优化搜索过程,并直接影响模型的推广能力。
对于同一个分类问题,选择不同的核函数或相同的核函数不同的核参数,都会有不同的分类结果。
究竟用哪一种核函数取决对数据处理的要求,大多数情况下可使用RBF核函数,主要理由参见文献4。
由于缺乏理论指导,传统的核参数选择大多通过反复实验,人工选取令人满意的解。
推广能力估计是机器学习中的另一个重要问题,也是参数选择的基础,常用的方法有k-fold交叉验证法、留一法(LOO)、支持向量率法、Jaakkola-Haussler法、Opper-Winther法、V-C法等等。
其中,LOO法是kfold交叉验证法的特例,要求k等于样本的个数。
目前应用最广的SVM参数优化方法是参数空间穷尽搜索法(又称枚举法),即在一定的参数范围内,对每个参数按照一定的间隔取值,每个取值称为一个水平,每个参数不同的水平组合就构成了多组备选的参数组合,然后选择使得期望风险上界最小的一组水平组合作为最优参数值。
鉴于k重交叉验证5是对SVM期望风险上界最准确的估计,目前最常用的就是把k重交叉验证估计和枚举法相结合来选择SVM参数,但这种方法存在以下缺点6:
(1)该优化方法相当耗时,对于大规模数据或者当参数个数超过2个的时候,这种方法几乎是不可能的。
(2)这种方法很难精确地找到最优参数,因为它首先确定了一个合理的参数范围,若是参数范围选择不准确则得不到最优的结果。
对于一个实际问题,很难实现指导最优参数所在的范围;同时这种方法对于参数空间的划分是有限的,它只能在有限点上寻找最优参数,是一种“有级”的寻优方法,如果最优参数组合不包括在测试点中,则枚举算法也不可能达到最优解。
鉴于上述原因,寻找更高效、合理的参数优化方法一直是支持向量机的一个重要研究方向。
粒子群优化算法(ParticleSwarmOptimization,PSO)是由Kennedy和Eberhart于1995年提出的一种智能优化算法7,模拟鸟群飞行迷失的行为,通过鸟之间的集体协作使得群体达到寻优目的。
由于其容易理解、易于实现、可调参数少,在很多优化问题中得到了成功的应用,并且在一些情况下优于常用的智能算法(如ANN、GA等)。
本文将粒子群优化算法应用于支持向量机的参数优化问题,并对算法的具体运用提出了改进建议,为解决支持向量机的参数选择问题提供了一条有效的方法和途径。
1算法原理1.1SVM算法原理SVM是一种建立在统计学习理论基础上的分类方法。
它主要基于以下三种考虑:
(1)基于结构风险最小化,通过最小化函数集的VC维来控制学习机器的结构风险,使其具有较强的推广能力。
(2)通过最大化分类间隔(寻找最优分类超平面)来实现对VC维的控制。
(3)SVM在技术上采用核化技术,根据泛函中的Mercer定理,寻找一个核函数将样本空间中内积对应于变换空间中的内积,即避免求非线形映射而求内积8。
SVM通过事先选择的非线形映射将输入向量x映射到一个高维特征空间,在这个空间构造最优分类超平面,即存在一个超平面满足对样本正确划分的条件。
而且,在这个超平面两侧的与这个超平面距离最近的两个点之间的距离最大,这样,在原始空间中非线性可分问题就转化为高维空间中线性可分问题。
如图1所示。
图1输入空间到特征空间的映射-11-www.ivypub.org/cst设线性可分样本集为(,)iixy,1,ildixR;1,1y为类别标志,d为空间维数。
最优分类面问题可以表示成如下优化问题,即在约束条件:
()10,1,iiyxbil
(1)下求函数211()()22的极小值。
为此,可以定义如下的Lagrange函数:
11(,)()()12liiiiLyxbb
(2)其中:
为机器学习的权值,b为机器学习的阈值,0为Lagrange系数。
此时目标函数的对偶问题为:
最大化的二次规划问题。
1,11()()2lliijijijiijWyyxx(3)约束条件为:
10,1,0iliiiily(4)这是一个不等式约束下的二次函数极值问题,且存在唯一解。
根据Kuhn-Tucker条件,这个优化问题的解必须满足:
()10,1,iiiyxbil(5)因此多数样本对应的i将为0,将只有一部分(通常是少部分)i不为零,对应的样本就是支持向量。
而相应的分类函数也变为:
()sgn()iiiifxyxxb(6)此函数值的输出即是分类的结果。
通过以上分析,可将支持向量机的基本思想概括为:
在进行分类时,对于线性不可分的样本首先通过一个非线性映射将原空间的样本映射到一个高维的特征空间(核空间),使得在核空间中变得线性可分或近似线性可分,然后在核空间中进行线性分类,从而实现相对于原空间的非线性算法。
1.2PSO算法原理PSO的思想来源于人工生命和演化计算理论。
假设在一个n维的目标搜索空间中,有m个粒子组成一个种群,其中第i个粒子表示为一个n维的空间向量12(,)iiiiknxxxx,其中1,2,im,即第i个粒子在n维搜索空间中的位置是ikx,每个粒子的位置就是一个潜在的解。
将ikx代入一个目标函数()ifx可以计算出其适应值ikf,根据适应值ikf的大小衡量ikx的优劣。
第i个粒子的飞行速度是一个n维的向量,记为12(,)iiiiknvvvv,第i个粒子目前搜索到的最优位置为12(,)iiiiknpppp,整个粒子群目前搜索到的最优位置为12(,)ggggknpppp。
基本的PSO算法运行过程中,随机产生一个初始种群并赋予每个粒子一个随机速度,并采用下列公式对粒子的速度和位置进行操作:
11122()()iiiigikkkkkkkccvwvpxpx(7)11iiikkkxxv(8)其中:
kw为惯性因子,为非负数;ikv为第k次迭代粒子i飞行速度矢量;1c、2c为学习因子,通常取122cc;1、2为介于0,1之间的随机数;ikp为第k次迭代后粒子i的最好位置;ikx为第k次迭代后粒子i的位置矢量;gkp为第k次迭代后群体的最好位置。
粒子群优化算法的运行流程如图2所示。
基本PSO的流程可以描述为:
Step.1初始化:
初始搜索点的位置0ix及其速度0iv通常是在允许的范围内随机产生的,每个粒子的Pbest坐-12-www.ivypub.org/cst标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将Gbest设置为该最好粒子的当前位置。
Step.2评价每一个粒子:
计算粒子的适应度值,如果好于该粒子当前的个体极值,则将Pbest设置为该粒子的位置,且更新个体极值。
如果所有粒子的个体极值中最好的好于当前的全局极值,则将Gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。
Step.3粒子的更新:
用式(7)和式(8)对每一个粒子的速度和位置进行更新。
Step.4检验是否符合结束条件:
如果当前的迭代次数达到了预先设定的最大次数(或达到最小错误要求),则停止迭代,输出最优解,否则转到Step2。
PSO算法具有以下特点:
(1)可以处理连续优化问题;
(2)多点搜索;(3)式(7)中的第一项对应多样化(diversification)的特点,第二、三项对应搜索过程的集中化(intensification)特点,因此这种方法在多样化和集中化之间建立均衡9。
开始初始化评价粒子更新粒子满足停止条件结束YN图2PSO算法运行流程图1.3PSO收敛速度的改进PSO收敛快,尤其是在算法的早期,但也存在着精度较低,易发散等缺点。
若加速系数、最大速度等参数太大,粒子群可能错过最优解,算法不收敛;而在收敛的情况下,由于所有的粒子都向最优解的方向飞去,所以粒子趋向同一化(失去了多样性),使得后期收敛速度明显变慢,同时算法收敛到一定精度时,无法继续优化,所能达到的精度也比GA低10,因此很多学者都致力于提高PSO算法的性能。
文献11提出了惯性权重的方法。
惯性权重w是与前一次速度有关的比例因子。
用惯性权重来控制前面的速度对当前速度的影响,较大的w可以加强PSO的全局搜索能力,而较小的w能加强局部搜索能力。
基本的PSO可以看作w=1,因此在迭代后期缺少局部搜索能力。
实验结果表明,w在0.8,1.2之间PSO有更快的收敛速度。
文献中试验了将w设置为从0.9到0.4的线性下降,使得PSO在开始时探索较大的区域,较快地定位最优解的大致位置,随着w逐渐减小,粒子速度减慢,开始精细的局部搜索。
在运用算法时,迭代过程中使w进行线性递减:
00()()/wtwwwtk(9)式中,0w为初始惯性因子,w为终止惯性因子,k为一个与迭代次数有关的常数,其值为迭代次数乘以递减系数S的积。
该方法加快了收敛速度,提高了PSO算法的性能。
当待解问题很复杂时,该法使得PSO在迭代后期全局搜索能力不足,导致不能找到要求的最优解,因此可以用自适应改变惯性权重来加以克服。
2算法仿真及分析为了验证文中所提出PSO-SVM算法的性能,进行了三组仿真实验。
-13-www.ivypub.org/cst2.1考察Schaffe提出的实例根据文献7所提出的实例对改进算法性能进行对比分析。
2221222212sin0.5min(),10010.001()ixxfxxxx(10)已知全局最优点是(0,0),()fx为-0.5。
由于其强烈的振荡性以及全局最优点被无数个局部最优点包围的特性,一般优化算法很难找到它的全局最优值。
网格法参数的搜索范围是110,110ee。
采用改进的PSO算法只需迭代760次,即可找到最优值,且耗时只有93ms。
本文改进算法与传统算法的对比结果见表1,其运行过程结果如图3所示。
表1实验1对比结果项标准PSO算法文献6算法本文改进算法1x-3.416583e-5-5.412430e-51.0727e-92x-2.828398e-6-2.138258e-71.5688e-9()fx-0.5-0.5-0.5图3PSO算法运行过程示意图该实验的仿真表明,用基本PSO很难得到的仿真结果,运用所采用的两种改进方法都可以快速得到较满意的结果,并且本文的改进方案更为简单、有效。
本文改进算法与文献7相比较,最优值的选取有数量级上的提高,这与采用的算法体系不同有很大关系,但对于比较算法的改进效果仍具有一定的参考意义。
本文利用了PSOt,一种基于Matlab的算法工具箱12,并在收敛速度的惯性权重上依据1.3节内容进行了改进。
2.2高斯分布样本点分类实验依据前面所述SVM分类原理、PSO运行步骤及改进的粒子更新算法,终止条件为30代内性能无改善。
基于PSO的SVM参数优化方法的具体工作流程如图4所示。
随机产生了2类三维样本的数据点13,每类样本数目1,000点,满足多元正态分布,分布参数见表2。
实验时,每一类别选择500点作为训练样本,500点作为待识别样本。
实验中采用C-SVC分类类型,RBF核函数,网格法参数的搜索范围是14,12ee,考虑PSO算法的随机性,对其进行5次运算后取最优值作为最终结果。
最优结果采用5-折交叉验证法。
对比实验结果见表3。
-14-www.ivypub.org/cst开始初始化PSO运行参数生成随机粒子读取训练数据读取测试数据SVM分类分类算法评估(交叉验证)更新粒子(改进算法)满足停止条件结束设定SVM参数搜索范围更新最优结果YN图4基于PSO的SVM参数优化算法运行流程图表2合成样本点参数分布类别均值1均值2均值3方差10.21.01.5121.01.60.41表3实验2对比结果分类及参数优选方法c=100g=0.5Libsvm最优参数c=3.125e-2g=0.125PSO最优参数c=0.001000g=5.250054交叉验证(%)78.779.379.1#iter7742484500BSV数目4439641000SV数目4679641000训练时间(s)0.1870.2340.188决策时间(s)0.3900.5930.656分类率(%)77.377.878.3图5试验2LIBSVM的寻优结果图-15-www.ivypub.org/cst其中,LIBSVM最优参数是采用LIBSVM软件14自带选优工具的结果。
其寻优结果如图5所示。
2.3UCI数据分类实验采用UCI公共测试数据库提供的数据集a1a15作分类实验,其训练样本数据文件为a1a,样本数为1,605个,每个样本含123维特征;待识别样本数据文件为a1a.t,样本数为30,956个。
实验中采用C-SVC分类类型,RBF核函数,网格法参数的搜索范围是13,13ee,最优结果采用5-折交叉验证法。
对比实验结果见表4,LIBSVM寻优结果如图6所示。
从上面的对比实验可以看出,文中提出的基于PSO的支持向量机优化算法无论对于高斯分布合成数据还是UCI真实数据,其性能都明显优于普通的参数选择算法,在分类精度上都有较明显地提高;同时,改进的PSO算法在运算时间上也比基本PSO算法快。
表4实验3对比结果分类及参数优选方法c=10g=0.8Libsvm最优参数c=8.0g=7.8125e-3PSO最优参数c=8.702666g=1.0000e-2交叉验证(%)79.6383.4982.74#iter290813171362BSV数目24577566SV数目1574649648训练时间(s)1.2190.6410.672决策时间(s)38.73417.82918.156分类率(%)77.461684.416684.4392图6试验3LIBSVM的寻优结果图3结论本文提出了一种改进的基于PSO的SVM参数优化算法,即采用自适应的收敛速度因子,在早期进行快速搜索,而在晚期进行精细搜索,从而满足了多样化和集中化的要求。
通过三组仿真实验,其结果也显示PSO-SVM是一种有效的参数优化方法,能对SVM的参数进行快速、准确地选择,使SVM具有更高的分类准确率。
下一步的工作是如何将SVM和PSO有机融合在一起,使算法在参数优化的同时进行分类或拟合,减少计算次数,加快运行速度,满足实时运算需求。
-16-www.ivypub.org/cstREFERENCES1V.N.Vapnik.StatisticalLearningTheoryM.BEIJING,PublishingHouseofElectronicsIndustry,2009.2VladimirN.Vapnik.TheNatureofStatisticalLearningTheoryM.NY:
SpringerVerlag,1995.3NelloCristianini,JohnShawe-Taylor.Anintroductiontosupportvectormachinesandotherkernel-basedlearningmethodsM.BEIJING,ChinaMachinePress,2005.4邵信光,杨惠中,陈刚.基于粒子群优化算法的支持向量机参数选择及其应用J.控制理论与应用,2006,23(5):
740-743.5SHAOXin-guang.ParametersselectionandapplicationofsupportvectormachinesbasedonparticleswarmoptimizationalgorithmJ.ControlTheory&Applications.2006,23(5):
740-743.6Chih-WeiHSU,Chih-ChungChang,Chih-JenLin.APracticalGuidetoSupportVectorClassificationEB/OL.2009-07-20.http:
/www.csie.ntu.edu.tw/cjlin.7袁小艳,刘爱伦.基于PSO算法的支持向量机核参数选择问题研究J.自动化技术与应用,2007,26(5):
5-8.8YUANXiao-yan.KernelparameterselectionofsupportvectormachinebasedonparticleswarmoptimizationJ.Automatictechnique&Applications.2007,26(5):
5-8.9杨维,李歧强.粒子群优化算法综述J.中国工程科学,2004,6(5):
87-94.10YANGWei.SurveyonParticleSwarmOptimizationAlgorithmJ.EngineeringScience.2004,6(5):
87-9411张学工关于统计学习理论与支持向量机J自动化学报,2000,26
(1):
32-42.12ZHANGXuegong.IntroductiontostatisticallearningtheoryandsupportvectormachinesJ.ACTAAUTOMATICASINICA.2000,26
(1):
32-42.13FukuyamaY.FundamentalsofparticleswarmtechniquesA.LeeKY,El-SharkawiMA.ModernHeuristicOptimizationTechniqueswithApplicationstoPowerSystemsM.IEEEPowerEngineeringSociety,2002,45-51.14徐海,刘石,马勇,等基于改进粒子群游优化的模糊逻辑系统自学习算法J.计算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 PSO 算法 SVM 参数 优化 方法 研究
![提示](https://static.bingdoc.com/images/bang_tan.gif)