SVM参数优化的AFMC算法

CN 43- 1258/TP计算机工程与科学第37卷第7期2015年7月ISSN 1007- 130XComputer Engineering &. ScienceVol. 37 ,No.7,Jul. 2015文章编号:1007-130X(2015)07-1304-07SVM参数优化的AFMC算法高雷阜,赵世杰,于冬梅,徒君(辽宁工程技术大学优化与决策研究所,辽宁阜新123000)摘要:支持向量机的参数选择仍未有系统的理论指导,其优化选择一直是支持向量机的一个重要研究方向。考虑到人工鱼群算法优化支持向量机参数往往易陷入最优参数组合微小邻域的问题,构造了用于支持向量机参数优化的AFMC算法。该算法前期利用鱼群算法较好的并行寻优性能，能快速寻得问题.的近似最优解,而后利用MonteCarlo法进行局部寻优，以实现快速、有效地获取强近优解。数值实验结果表明，该算法具有较好的分类性能和较快的寻优速度,验证了在支持向量机参数寻优中的有效性和可行生。关键词:支持向量机;参数优化;人工鱼群算法;蒙特卡罗法;近似最优解中图分类号:TP18文献标志码:Adoi:10. 3969/j. issn. 1007- 130X.2015. 07.013AFMC algorithm for SV M parameter optimizationGAO Leifu,ZHAO Shirjie, YU Dong -mei,TU Jun(Institute of Optimization and Decision, Liaoning Technical University , Fuxin 123000)Abstract : Support vector machine (SVM) parameter optimization selection is an important researchdirection, but there is still no systematic theory to guide the selection of the SVM parameters. Since op-timizing the SVM parameters by the artificial fish-swarm algorithm tends to fall into the small neighbor-hood of the approximate optimal solution, we design the AFMC algorithm for the SVM parameter opti-mization. At the early stage,we use the better parallel optimization performance of the fish-swarm algo-rithm to quickly gain the approximate optimal solution. Then we use the MonteCarlo algorithm for localsearching to achieve a quick and effective strong approximate optimal solution. The numerical experi-ments show that the proposed algorithm has better classification performance and faster searching speed,and it is effective and feasible in the SVM parameter optimization.Key words: support vector machine (SVM) ; parameter optimization; artificial fish algorithm; Monte-Carlo algorithm ;approximate optimal solution本集的容错性能和核思想实现对线性和非线性问1引言题的适用性;在处理小样本、非线性和高维数据中表现出许多特有优势,有效地克服了神经网络等算支持向量机SVM ( Support Vector Ma-法中存在的“过学习”、“维数灾难”等问题而得到广chine)1是Vapnik V等人根据统计学习理论，以泛的应用。作为一种新兴的机器学习方法,SVM结构风险最小化和VC( Vapnik-Chervonenkis)维仍有较多有待研究和完善的方面,主要有:SVM性为基础发展起来的一种新的机器学习方法，以最优.质分析和理论基础研究[2]、实现算法和方法的提出超平面技术实现推广性能的控制、软间隔实现对样和改进[3~s]以及应用深度和广度的拓展6.]等。中国煤化工收稿日期:2014-08-07:修回日期:2014-11-11基金项目:教育部高等学校博士学科点专项科研基金联合资助项目(20132121.MHCNMHG通信地址:123000辽宁省阜新市辽宁工程技术大学优化与决策研究所Address: Institute of Optimization and Decision, l.iaoning T echnical U niversity，Fuxin 123000, L.iaoning,P. R. China高雷阜等:SVM参数优化的AFMC算法1305SVM性质分析中,核函数和核参数的选择对再结合KKT ( Karush-Kuhn-Tucker)条件可得SVM分类性能具有重要影响,目前核参数的优化选择已成为SVM研究的一个重要方向,但仍无成w. =2xy,A;'x; 选择λ"的一个正分量入;可得形的、系统的理论来指导参数选择。目前常用的参b*=y,-y;x;(x,●x),从而得到SVM的决数优化方法主要有经验选择法、网格搜索法[8.9]和策函数为:群体智能优化算法。但是,经验选择法对人的先验f(x) = sgn((w"●x)+b")知识要求较为严格;网络搜索法需要对有限离散参数进行一一比对,较为费时,同时随着参数的增加，对线性不可分问题,通过非线性映射φ将样时间复杂度增加严重;相对而言，群体智能优化算本集从低维输入空间R"映射到高维Hilbert 空间法利用种群个体间的并行寻优提高了参数的寻优中以实现线性分类,其原始最优化问题为:效率,且具有初值不敏感等特性,是一类较为理想mino" .o+cZe的参数优化方法。基于群体智能算法优化SVMs.t. y;(@.中(x)+b)≥参数的方法有:遗传算法["0]、粒子群算法11.121、蚁1-ξ.&≥0,i= 1,2..,N(4)群算法[13.1]和多种智能算法的融合方法[5等。最终所得的决策函数为:文献[16]中比较了遗传算法、粒子群算法、蚁群算法和人工鱼群AF(Artificial Fish)算 法在f(x)= sgn( EyxaiK(x,x)+b") (5)SVM参数优化中的性能,在一定程度上验证了AF算法在SVM参数优化中的相对有效性和可行3基于AFMC算法的SVM参数优性。但是,在寻优过程中AF算法也存在一定的问化模型题:它一般前期就能寻到一个较优解,后期只是在该解附近进行迭代寻优,从而导致较大的时间复杂3.1AFMC融合思想的构建度。针对该问题,本文构建了能在提高参数寻优效AF算法[18.19]是由李晓磊博士于2002年提出率的同时尽可能提高分类性能的AFMC算法,并的一种群体智能优化算法,具有较强的并行寻优能.将其用于SVM参数的优化选择中。力、对初值不敏感和全局寻优性能等优点而得到广泛应用。但是,它也存在一定的瑕疵:当利用AF2支持向量机的数学描述算法寻找所研究问题最优解时,最终得到的解往往假设二分类问题的训练样本集为A = {(x)，是位于最优解微小邻域中的一个近似最优解(简称近优解),即AF所得的解通常是能满足所有约束y),(xz,yz)...,(xN,yw)) ,其中x∈R";yi∈条件的满意解中较为接近最优解的一个解;由于Y ={-1,1},i= 1,2,..N ,则支持向量机对线性AF算法的较强寻优性能,一般前期就能较快收敛可分问题[17]的原始优化问题为:到一个近优解,后期只是在该近优解的邻域中继续迭代寻优，相对于分类精度的可能微小提高,更多min-o" .o+c2e的是造成了寻优时间的严重增加。s.t. y((@. x)+b)≥1-ξ，针对上述问题,本文将具有较好迭代寻优性能ξ≥0,i = 1,2,..,N(1)的AF算法与较好随机搜索性能的MonteCarlo法其中,C为惩罚参数，&为松弛变量。相融合构建了AF-MonteCarlo融合算法(即引人Lagrange 函数,得式(1)的对偶问题为:AFMC算法),该算法能在减少寻优时间的同时有效获得一个强于原近优解的近优解(简称强近优max Q() =2x.-艺xwy.y;(x.x,) .解)。强近优解是指与所研究问题最优解的微小邻域半径不大于近优解与最优解邻域半径的满意解，s.tZxy.=0,0≤λ≤C,i= 1.2.-.N三者之间的关系见图1，(2)AFMC中国煤化工AF算法迭代其中,入为Lagarange乘子。寻优过程中fYHCNMHG值小于微小量.求解式(2)得最优解λ° = (hi ,hi ,.2)T,σ且预测集的分类准确率大于设定的阈值θ时，则.1306Computer Engineering &. Science 计算机工程与科学 2015,37(7)认为满意解X。(此时为近优解)已位于最优解微参数C和核参数g。对分类问题,一般以SVM的小邻域8中;若继续采用AF算法寻优,则只会在分类准确率最大化为优化原则,对应数学模型为:近优解X。附近波动，最终不一定能得到一个更优max F(C,g)的解,但一定会增加算法的时间复杂度。对此的处jC∈[Cmin ,Cmx]s. t.(7)理策略就是跳出AF算法,在X。的δ邻域中采用\g∈[gmin,gmux]MonteCarlo法进行随机搜索,搜索策略是:若近优其中，F(.)为罚参数C和核参数g的二元函数。解X。与变量取值范围(m,n]的上下边界的差值εAFMC算法对二元函数F(C,g)进行参数寻均大于或等于8时，即搜索范围没有超出变量取值优，即实现以较高的寻优效率获得具有较好分类性的边界,则MonteCarlo法以该近优解X。为中心，能的SVM强近优解(即参数组合(Ceavgesn) ),其.以δ为搜索半径,搜索区间为[X。-8,X。+8](见程序流程见图3,具体操作步骤为:图2a),且各分量x;均服从[X。-δ ,X。+δ门的均步骤1数据预处理。为消除数据集不同属匀分布;若近优解X。与变量取值范围(m,n]的某性间存在的量纲差异,一般需要进行标准化(或归侧边界的差值ε小于δ ,则MonteCarlo法搜索区一化)等预处理。间的该侧以区间边界为限值,另- .侧以X。土(28 -步骤2确定模型中相关 数据集。将预处理e)为限值(见图2b或图2c)。按上述策略确定变后的数据集整理为分析数据集,并确定出SVM的量的搜索区间,并利用MonteCarlo法对AF算法训练集D.和预测集Dpr。所得的近优解X。进行随机寻优，以获得问题的强步骤3模型中参数设置。 AF算法中需要设近优解。置的参数有:最大进化次数Nrer、种群规模Ncem、感知距离Dv。、移动步长Sux、觅食最大试探次数Nry和拥挤度因子中;SVM中参数C和g的取值满意解集(近优解集(强近优解集范围设置; MonteCarlo法仿真搜索次数Nmc ，参数C和g搜索邻域δc和δ。的设置。Figure 1 Relationship among solutions步骤4鱼群初始化。 鱼群中每条人工鱼代图1解之间的关系表SVM二元函数F(C,g)的待优化参数组合(C,g) ;根据步骤3中罚参数C和核参数g的取值范.X-8X+8mXX+26-e围随机进行鱼群的初始化,使NGe条人工鱼对参a ep28.E.28b e,<8.E.≥8数组合(C,g) 并行寻优。28-∈步骤5初始鱼群中各人工鱼食物浓度值的X-26+δ,ε<δ .计算。以预测集的分类准确率最大化为优化原则Figure 2 Schematic diagram of the计算每条人工鱼的食物浓度值并比较大小,将鱼群search interval for the MonteCarlo algorithm中最大值作为当前鱼群的最优目标值,并保存对应图2 MonteCarlo 法搜索区间示意图人工鱼的参数组合(C,g)。3.2AFMC算法优化SVM参数模型步骤6对鱼群中人工鱼进行行为操作。 鱼将3.1节分析中所构建的AFMC算法用于群中各人工鱼分别模拟自然鱼的觅食、追尾和聚群SVM参数的优化选择。SVM分类模型中需要优行为;缺省行为为随机游走。化的参数主要有罚参数C和核参数。罚参数C主步骤7鱼群中最优目标值的确定。鱼群每要是对错分样本的惩罚,是在机器结构风险和泛化执行--次行为操作,就计算一次当前鱼群的最优目性能之间寻求一种折衷;核参数主要影响核函数的标值(即最大食物浓度值):如果当前鱼群中存在人分析性能,继而影响SVM的泛化性能。目前常见工鱼的食物浓度值大于当前保存的最优食物浓度的核函数主要有多项式核、RBF核、Sigmoid核等，值,则以该食物浓度值替代原最优食物浓度值,并由于RBE核只有一个待优化参数,且对低维和高保存相应的参数组合(C,g) ;否则鱼群中最优食维空间数据都具有较好的适用性,故选用RBF核物浓度值和参数组合(C.o)保持不变。作为SVM核函数，其表达式为:步骤MH中国煤化工到终止条件,即K(xx) = exp(一x.- x1*/(2r2)) (6)在满足鱼CNMH G直小于误差限σ令g= 1/(2r2),则SVM中待优化参数为罚的件下,判断当前鱼群最大迭代次数Nrer是否达高雷阜等:SVM参数优化的AFMC算法1307base(WD)共计五组数据集，各实验数据集的属性数据收集和数据归- -化设置AF参数和SVM参数范围情况见表1。Table 1 Attributes of the experimental鱼群的初始化datasets in UCI database确定分类模型的训练集和预测集计算食物浓度值表1 UCI 数据库中实验数据集属性分类准确率行为操作，数据集名数据长度属性维数类别数目生新鱼群鱼群算法迭代寻优,判断是否达到~N↑IP18032SOMEA的年优误差限或最大迭ris150代次数或阈值HYTAE15输出最优目标值和IS210+2351设置近优解邻域大小近优解即参数组合WD5 000确定仿真搜索次数其中IS数据集中的“210+235”数字分别表示UCI给定的训练集数和预测集数。设置(Cg)搜索区间各实验数据集均采用均匀随机选取方式[15]确MonteCarlo法对近优解邻随机生成满足边界域进行搜索，以获得强近条件参数(Ce定出SVM的训练集Da，剩余数据作为预测集优解和更优的分类准确率Dp，各数据集的训练集选取情况见表2。在近优解邻域内搜索强Table 2 Design of the training datasets近优解即参数组合(Cg)和相应的分类准确率表2训练数据集的设置输出最优目标值(分类数据集名训练样本数各类别选取训练数准确率)和强近优解P60Figure 3 Flowchart using the AFMC10/10/10algorithm to optimize SVM parameters25/25/25图3AFMC算法优化SVM参数的流程图Is210到迭代上限或分类准确率是否大于阈值θ。若是，VDo057/47/96则得到AF算法的最大分类准确率和近优参数组4.2模型参 数的设置合(C,g) ,否则迭代次数加1,并跳转执行步骤6。步骤9 MonteCarlo 法寻优搜索。根据步骤鱼群中参数设定;种群最大迭代次数Nrer =3中参数设置情况,在步骤8所得近优解的δ邻域100、种群规模Ncem=5、感知距离Dvx=0.5、移中随机生成Nmc组新的参数组合(C,g) ,并计算动步长Slg = 0.05、觅食最大试探次数Nry= 8各参数组合(C,g)对应的分类准确率,以最大者和拥挤度因子φ = 0. 618 ;MonteCarlo法中仿真作为AFMC算法寻优的最终值,其参数组合(C,搜索次数Nmc= 1 000,参数C和g的搜索邻域分g)即为强近优解。别为8c= 1和δg=0.1。跳出AF算法的限制条步骤10输出AFMC算法优化SVM参数的件是鱼群前后代分类准确率误差限σ= 0.01 ;阈最大分类准确率和强近优解Cesogten)。值θ则依据AF算法对各数据集的10次分类准确率均值来设定,结果见表3。网格搜索法参数设4数值实验置:罚参数C和核参数g的取值区间分别为(0,10]和(0,1] ,搜索步长分别为0.01和0.001。为验证AFMC算法优化SVM参数模型的较好Table 3 Threshold design of the experimental datasets性能,以UCI标准数据库中的数据集为实验数据,同表3实验数据集阈值设定时以网格搜索法、AF算法为对比算法,以验证AFMC阈值算法优化SVM参数模型的有效性和可行性。IF95.04.1 实验数据中国煤化工实验数据选用UCI标准数据库中的Image_YHCNMHGSegmentation(IS)、Ionosphere(IP)、Iris、Teaching82.0_Assistant_ Evaluation(TAE) 和Waveform_ Data-高雷阜等:SVM参数优化的AFMC算法130998厂99.0[7:。98.5客7198.070第97.5-二AF 寻优自线年69二AF寻优曲线"APIMnr-Celo法分界线 」AFMatecCr欧分界线J920 204060 80 10020406080100送代60 80100迭代次数a lonosphere集 寻优对比图b lris集寻优对比图e Teaching-Assistant-Evaluation集寻优对比图9.0 :公了保川琴数设置研文:移动步长: 05拥桥度内子: 0.618常97.5.二AF4优曲线82.5一-AF小优曲线... Matranto界线82.0....-Ca.o界线280 T00T00d Image. Segmentation集寻优对比图e Waveform. Database集寻优对比图Figure 5 Effect comparison between the AF algorithm and the AFMC algorithm图5AF算法和AFMC算法的效果对比图优,以提高SVM模型的分类性能,在一定程度上[8] Guo Chao, Song Wei-hua, Wei Wei. Stope roof stability pre-验证了该算法在SVM参数优化中的有效性和可diction based on both SVM and grid-search method[J]. ChinaSafety Science Journal,2014,24(8) :31-36. (in Chinese)行性。9] Li Qing-yi,Zhou Hao,Lin A-ping,et al. Prediction of ash fu-(3)在分类问题中,对同一组训练集和预测集sion temperature based on grid search and support vector ma-进行反复实验时,最大分类准确率一般对应着强近chinie[J]. Journal of hejiang University ( Engineering Sci-优解的一个微小邻域,其原因可能是:SVM在对预ence) ,2011,45(12) :2181-2187. (in Chinese)测集的分析中可能产生了相同数量的错分样本(只[10] Martins M,Costa L, Frizera A,et al. Hybridization between是被错分的样本可能是不同的样本)。针对该问题multi-objective genetic algorithm and support vector ma-的分析和研究将是下一步分析的重点。chine for feature selection in walker-assisted gait[J]. Com-puter Methods and Programs in Biomedicine, 2014,113(3):参考文献:736-748.1] Vapnik V. The nature of statistical learning theoryCM]. New[11] Yuan Rong-di, Peng Dan, Feng Hui-zong,et al. Fault diag-York: Wiley, 1998.nosis for engine by support vector machine and improved[2] Zhang Yan-ping , Zhang Ling. Machine learning theory and al-particle swarm optimization algorithm[J]. Journal of Infor-mation and Computational Science, 2014, 11 (13); 4827-gorithm[M]. Beiing :Science Press ,2012. (in Chinese)[3] Tsyurmasto P, Zabarankin M, Uryasev S. Value-at-isk sup-port vector machine: Stability to outliers[J]. Journal of Com-[12] Sun Wei, Liu Xuan. The safety asessment of power infor-binatorial Optimization,2014,28(1):218-232.mation system with particle swarm optimization based sup-4] Liang Zhi- zheng, Liu Ning. Efficient feature scaling for sup-port vector machine[J]. Journal of Information and Compu-port vector machines with a quadratic kernel[J]. Neural Pro-tational Science,2014.11(14) :4921-4929.cessing Letters,2014,39(3) :235-246.[13] Pan Yun-liang, Du Jun, Hu Weitao. Air to ground target[5] Tian Yingjie,Ju Xu-chan, Qi Zhi-quan. Eficient sparse non-optimal tracking method by ant colony optimization-basedparallel support vector machines for classification[J]. NeuralSVM[J]. Journal of Computational Information Systems,Computing and Applications,2014,24(5): 1089-1099.2014,10(5):1805-1810.6] Ghosh A,Guha T, Bhar R. Categorization of fabric design u-[14] Al-Dulaimi H B A, Ku-Mahamud. Solving SVM model se-sing multi-class least- square support vector machine[J]. In-lection problem using ACOR and IACOR [J]. WSEASternational Journal of Clothing Science and Technology,Transactions on Computers,2013,12(9).1109-2750.2014,26(1) :58-66.[15] Ghamisi P, Benediktsson J A. Feature selection based on[7] Vahdani B, Mousavi S M, Hashemi H,et al. A new hybridhybridizand n-rticle swarm opti-model based on least squares support vector machine for pro-mization[中国煤化工，: Sensing Letters,ject selection problem in construction industry[J]. Arabian2015,12YHCNMH GJournal for Science and Engineering , 2014 ,39(5) :4301-4314.[16] Gao Lei-fu, Zhao Shi-jie, Gao Jing. Application of artificial1310Computer Engineering & Science 计算机工程与科学2015,37(7)fish-swarm algorithm in SVM parameter optimization selec-作者简介:tion[J]. Computer Engineering and Applications, 2013, 49(23) :86-90. (in Chinese)高雷阜(1963-),男,辽宁阜新人,博[17] Deng Nai-yang, Tian Yingjie. Support vector machines-the-士，教授,研究方向为最优化理论与应用。ory, algorithms and development [ M]. Beiing: ScienceE-mail: gaoleifu@ 163. comPress , 2009. (in Chinese)GAO Lei-fu, born in 1963, PhD, pro-[18] Li Xiao-lei, Shao Zhirjiang,Qian Ji- xin. An optimizing meth-fessor , his research interest includes opti-od based on autonomous animats: Fish-swarm algorithmmization theory and application.[J]. Systems Engineering Theory& Practice 2002,22(11);32- 38. (in Chinese)赵世杰(1987-),男,山东日照人,博19] Li Xiao-lei,Qian Jjrxin. Studies on artificial fish swarm opti-士生,CCF会员(E200031372G) ,研究方向mization algorithm based on decomposition and coordination为数据挖掘、优化与管理决策和人工智能。techniques[J]. Journal of Circuits and Systems, 2003,8(1)。.E-mail: zhao2008shiie@ 126. com1-6. (in Chinese)ZHAO Shi-jie, born in 1987, PhD can-附中文参考文献:didate , CCF member( E200031372G), his research interestsinclude data mining , optimazation and management deci-[2]张燕平,张玲.机器学习理论与算法[M].北京:科学出版社，.sion, and artificial intelligence.2012.[8] 郭超,宋卫华,魏威.基于网格搜索支持向量机的采场顶板稳于冬梅(1986-),女,辽宁鞍山人,博定性预测[J].中国安全科学学报,2014,24(8) :31-36.士生,研究方向为最优化理论与方法。[9] 李清毅,周吳,林阿平,等.基于网格搜索和支持向量机的灰YU Dong mei, born in 1986 , PhD can-熔点预测[J].浙江大学学报(工学版),2011,45(12):2181-didate, her research interest includes opti-[16]高雷阜,赵 世杰,高晶.人工鱼群算法在SVM参数优化选择中的应用[J].计算机工程与应用,2013,49(23) :86-90.17]邓乃扬,田英杰.支持向量机--理论,算法与拓展[M].北徒君(1982-),男,安微滁州人,博士，京科学出版社,2009.研究方向为物流与供应链管理。E-mail:[18] 李晓磊,邵之江，钱积新. -种基于动物自治体的寻优模式: .tovegar@ 126. com鱼群算法[J].系统工程理论与实践,2002 ,211);:32-38.TU Jun, born in 1982, PhD, his re-[19]李晓磊，钱积新.基于分解协调的人工鱼群优化算法研究search interests include logistics and supply[J].电路与系统学报,2003,8(1);1-6.chain management.中国煤化工YHCNMHG