第26卷第7期 2009年7月 计算机应用与软件 Computer Applications and Software VoL 26 No．7 Jul．2009 采用遗传算法优化最小二乘支持向量机参数的方法 王克奇 杨少春戴天虹 白雪冰 (东北林业大学机电工程学院黑龙江哈尔滨150040) 摘要 支持向量机是建立在统计学习理论上的一种学习算法，较好地解决了小样本学习问题。由不同的参数和核函数构造的 支持向量机在性能上存在很大差异，而在参数和核函数的选择上目前还没有明确的理论依据。针对支持向量机的参数选择问题，提 出了一种采用遗传算法优化最小二乘支持向量机参数的方法。结合LS．SVMIab工具箱，在MATLAB实验平台的仿真实验表明，该 方法提高了支持向量机的参数选择效率，得到的参数对测试样本的分类结果是最优的，从而避免了人为设定参数的不足，同时缩短 了优化时间。 关键词 最小二乘支持向量机遗传算法参数选择I．S．SVMIab工具箱 METHoD OF oPTIMIZING PARAMETER oF LEAST SQUARES SUPPoRT VECTOR MACHINES BY GENETIC ALGoRITHM Wang Keqi Yang Shaochun Dai Tianhong Bai Xuebing (College ofMachinery and Electron Engineering，Northeast Forestry Un西ersity，Harbin 150040，Heilongjiang，China) Support vector machines(SVM)，a learning method based on statistical learning theory(SLT)，call solve small-sample learning Abstract problems better．SVMs with different parameters or kernel functions display very different performances．and there isn’t a manifest theory sup— porting the selection of them up to now．In this paper a method that optimises the parameters of Least Squares Support Vector Machines(1．SS— VM)by using Genetic Algorithm is presented．The simulative experiment executed on MATLAB experimental platform with l_S-SVMlab toolbox shows that this method鲈emly impmves the efficiency of SVMs parameters selection，and with the parameters selected，the classification result for the testing samples is the optimum．It avoids the disadvantage of manually specifying the parameters，and also scales down the optimisation time． Keywords Least squares support vector machines Genetic algorithm Parameters selection LS—SVMlab toolbox 0引 言 统计学习理论是由V．Vapnik等人建立的一种专门研究小 样本情况下机器学习规律的理论，为解决有限样本学习问题提 供了一个统一的框架，支持向量机就是在这一理论基础上发展 语言的最dx--乘支持向量机工具箱(LS-SVMlab)，利用遗传算 法实现了对支持向量机模型的参数优化，并基于一组木材表面 颜色特征得到了很好的实验效果。 1最小二乘支持向量机 而来的一种新的通用学习方法…。支持向量机通过结构风险 支持向量机的基本思想是通过非线性变换将输入空间变换 最小化原理来提高泛化能力，较好地解决了小样本、非线性、高 到一个高维空间，然后在这个新空间中求取最优线性分类超平 维数等实际问题，已在模式识别、信号处理、函数拟合等领域得 到了成功应用，成为机器学习领域的研究热点之一。然而，用支 面。支持向量机具有全局最优性和很强的泛化能力，能够很好 地解决小样本学习问题，因此在模式识别、函数拟合等领域得到 持向量机求解分类问题，其本质上是一个二次规划问题，当样本 了广泛的应用。但同时，由于统计学习理论尚有很多问题需要 数据量较大时，常规的数值优化算法及软件很难实现二次规划 进一步研究，在支持向量机结构、参数和核函数选择上还未有明 问题的求解。因此，运行时间和计算内存是支持向量机求解的 确的理论指导。 主要瓶颈旧j。而作为支持向量机的改进算法，最小二乘支持向 量机在运行速度上有了很大提高，同时减少了求解所需的计算 最dx--乘支持向量机LS—SVM(Least Squares Support Vector Machine)是在标准支持向量机上的一种扩展，由J．A．K．． 资源，而其准确率并未明显下降，因此在模式识别和非线性函数 拟合上得到了很好的应用。和其它算法一样，支持向量机的性 SuyKens和J．Vandewalle提出‘引。它采用最小二乘线性系统误 差平方和作为损失函数，将求解过程变成了解一组等式方程，加 能也依赖于模型的参数，研究人员对支持向量机的参数选择已 快了求解速度，求解所需的计算资源较少，在模式识别和非线性 作了很多研究，但至今还未提出明确的理论依据。如何实现模 型的参数优化成为提高支持向量机学习性能和泛化能力的主要 收稿日期：2007—09—12。黑龙江省自然科学基金项目((：2004一 问题之一。本文结合J．A．K．Suyken等人开发的基于MATLAB 03)。王克奇，教授，主研领域：自动化监测与计算机控制。 万方数据 

110 计算机应用与软件 2009年 函数拟合的应用中取得了很好的效果。 个核函数，由于不同的核函数构成的分类器的性能不同，因此选 设训练样本D={(‰，YI)I k=1，2，…，川，其中‰∈R“为 择哪种核函数对于支持向量机的设计是非常重要的。研究表 输入数据，Y。∈R是输出类别。在权∞空间(原始空间)中的最 小二乘支持向量机分类问题可以描述为求解以下问题： 明，惩罚因子和核函数的参数是影响支持向量机性能的主要原 因，其中核函数的参数主要影响样本数据在高维特征空间中分 m。in．毋(w，b，e)=如7∞+如∑‰2 ● 埘，D．c 二 ‘一i (1) 约束条件：Yk[∞7妒(‰)+6]=1一气k=1，．．．，Ⅳ(2) 定义拉格朗目函数： L(to，b，e；a)=毋(∞，b，e)一三嘞{Yk[∞7妒(钆)+6卜1+‰} 其中，拉格朗El乘子％ER。对上式进行优化： (3) 芝=。一∞=耋“肌9c¨ 盖=。一砉口一。 aa_eLt=0。％2慨 瓦aL=0---+yk[wrap(扎)+6]_1+e^=o 上式可化为求解下面的矩阵方程： 厂1 o 0 o 0 o o l o ．yj Lz y ， 一Z7-IF∞ 一矿¨ 。一川。 o jL仅 0 0 O Pl 即曙彪f■蚴=盯 其中，Z=[9(髫1)7Yl，妒(鬈2)7Y2，…，妒(鬈Ⅳ)7YⅣ]7，Y=[Y1，y2， …，YN]7，P1=[1，1，…，1]7，e=[e1，e2，…，e_Iv]7，a=[al，d2， …，口Ⅳ]7，同时将Mercer条件代入到力=ZZ7，可得： 』如=YkYj妒(菇★)2妒(茹z)=扎，，j肇K茗^，髫1) (6) 因此，式(1)的分类问题通过式(5)和式(6)的线性问题得 到最终解，而不是解二次规划问题。核函数可采用高斯径向基 核函数、多项式核函数、多层感知器核函数和线性核函数等多种 符合Mercer条件的核函数一一]。常用的核函数的表示形式如表 1所示㈣。 表1常用的核函数 核函数 线性核函数 多项式核函数 高斯径向基核函数 Sigmoid核函数 表达式 K(x，。‘)=z·。f K(x，茗；)=(名·戈i+c)。 r(x，zf)=exp(忪一z。If 2／cr2) K(z，xf) =tanh(七(鼻·石。)+") 最小二乘支持向量机将不等式约束转化为等式约束，将误 差平方和损失函数作为训练集的经验损失，这样就将二次规划 问题转化成线性方程组的求解，简化了计算复杂性，提高了支持 向量机求解问题的速度和收敛精度。但同时也必须指出，由于 每个样本数据对分类期都有贡献，LS．SVM失去了标准SVM稀 疏性的优点。 2最小二乘支持向量机的参数优化 布的复杂程度，而惩罚因子的作用是在确定的特征空间中调节 支持向量机的置信范围和经验风险的比例【6 J。所以，要想获得 泛化能力良好的支持向量机，首先要选择合适的核函数参数将 数据映射到合适的特征空间，然后针对该确定的特征空间寻找 合适的惩罚因子以使支持向量机的置信范围和经验风险具有最 佳比例。 作为支持向量机的一种扩展，最小二乘支持向量机同样存 在参数选择问题。目前应用较多的是采用网格搜索和交叉验证 相结合的支持向量机参数优化算法，该算法由初始给定的参数 出发，在给定的参数范围内采用网格搜索算法和交叉验证寻找 ㈩ 最优参数‘“。首先网格搜索算法选择要优化的参数对(7，P)， 然后用交叉验证法对目标函数(如均方差最小)进行寻优，直至 找到最佳的参数对，使交叉验证的精度最高。其中，网格搜索算 法要将惩罚因子y和核函数参数形成M×N个(7，P)组合(其 中M和N分别为7和P的个数)，分别训练不同的支持向量机， 估计其学习精度，从而在M×N个(y，P)的组合中得到学习精 度最高的一个组合作为最优值。其计算量较大，尤其是训练样 (5) 本集较大时搜索过程非常费时，因此这种方法在使用上受到一 定程度的限制。在最优化方法众多的算法中，遗传算法以其强 大的全局搜索能力、并行性、高效性的优点得到了广泛的应用。 本文正是利用遗传算法的优点优化最／1、--乘支持向量机的参 数，得到了较好的结果。 2．2用遗传算法优化最小二乘支持向量机参数 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随 机搜索算法，能够在搜索过程中自动获取和积累有关搜索空间 的知识，并自适应地控制搜索过程以求得最优解。它模拟自然 选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群 出发，通过随机选择、交叉和变异操作，产生一群更适应环境的 个体，使群体进化到搜索空间中越来越好的区域，这样一代一代 不断繁衍下去，最后收敛到一群最适应环境的个体，求得问题的 最优解‘“。 用遗传算法优化最小二乘支持向量机参数主要过程如下： 步骤1：设置初始值，如遗传算法的初始种群规模、最大遗 传代数r、交叉概率、变异概率等。 步骤2：对要优化的参数根据其设定的范围进行二进制编 码，随机产生初始种群。染色体为各参数二进制顺序排列组成， 长度即为各参数二进制长度之和。设置遗传代数计数器t=0。 步骤3：计算种群中各个个体的适应度。这里将最小二乘 支持向量机的分类正确率作为目标函数值，即个体的适应度，个 体对应的参数的分类正确率越高，则该个体的适应度越大。 步骤4：根据个体适应度，按照一定规则(这里采用轮盘赌 法)从当前种群中选出个体进入下一代。 步骤5：选择群体中的两个个体髫。、戈：作为父体以某个概率 (交叉概率)进行交叉操作，产生两个新个体。这里采用单点交 叉，交叉概率设为0．8。 步骤6：随机选择种群中的个体以一定的概率(变异概率) 进行变异操作，通过随机改变个体中某些基因而产生新个体。 2．1支持向量机的参数选择问题 变异概率设为0．05。 采用支持向量机求解模式识别或函数拟合问题需要选择一 步骤7：终止条件判断。若t≤T，则转到步骤2；若t>T或 万方数据 

第7期 王克奇等：采用遗传算法优化最小二乘支持向量机参数的方法 111 平均适应度值变化持续小于某一常数超过一定代数，则所得到 裹3其它核函数优化后的分类结果比较 的具有最大适应的个体作为最优解输出，算法终止。 步骤8：对得到的最优解译码，得到优化的参数。 3实验及结果 核函数类型 遗传算法 网格搜索算法 平均正确率(％) 优化时间(s) 平均正确率(％) 优化时问(s) 多项式核函数 94．725 12640．275 93．3 5161．55 线性核函数 Sigmoid核函数 71．3 82．6 661．9812 69．00 562．5344 7242．0016 这里选择了东北常见的五种树种的木材样本，建立了包含 1000幅图像的图像库。其中包括白桦、红松、落叶松、水曲柳和 4结论 柞木五种树种的径切和弦切样本，共十类，每类各100个样本。 提取了这些木材图像的19个L+d+b’颜色空间的颜色特征(包 括L+、口‘、b’分量、色相角船’、色饱和度c+、色差AE‘、色相 差AH‘七个量的均值与标准差，以及前5个分量与其均值的差 的均值)，以此作为支持向量机的输入。选择每类样本中的30 个作为参数优化及最终分类的训练样本，另外的30个作为参数 优化时的测试样本，剩余的40个作为最终分类的测试样本。实 验基于MATLAB R2007a实验平台，所用计算机配置为：P4 3．00 CPU、256M内存、80G硬盘、中文Windows XP操作系统。 本文采用LS—SVMlab工具箱中提供的最d'-乘支持向量机 模型，将用遗传算法优化最小二乘支持向量机参数的方法与此 工具箱中网格搜索优化参数的方法进行比较，每种方法分别运 行10次，初始参数值均在设定范围内随机产生，最后将优化得 到的参数构造支持向量机模型进行分类比较，比较结果如表2 所示。 ‘ 本文提出了一种采用遗传算法优化最小二乘支持向量机参 数的方法。对于支持向量机参数的选择，现在也只能采用各种 优化算法进行优化，而各种算法的寻优性能不同，采用遗传算法 优化支持向量机参数的方法充分利用了遗传算法全局寻优和很 强的搜索能力的优点，试验表明其在优化结果和时间上均优于 采用网格搜索算法，取得了较为满意的效果。 参考文献 [1]张学工．关于统计学习理论与支持向量机[J]．自动化学报，2000， 26(1)：32—42． [2]杜树新，吴铁军．模式识别中的支持向量机方法[J]．浙江大学学 报：工学版，2003，37(5)：521—527． [3]Suyken J A K，Vandewalle J．Least squares support vector machine classifiers[J]．Neural Processing Letters，1999，9(3)：293—300． [4]朱家元，陈开陶，张恒喜．最小二乘支持向量机算法研究[J]．计算 襄2遗传算法和网格搜索算法优化支持向量机参数结果(RBF核函数) 机科学，2003，30(7)：157—159． 次数 l 2 3 4 5 6 7 8 9 lO 平均值 遗传算法 网格搜索算法 平均正确率(％) 优化时间(s) 平均正确率(％) 优化时间(s) [5]邓乃扬，田英杰．数据挖掘中的新方法——支持向量机[M]．北京： 科学出版社。2004． [6]Vapnik V．Statistical Learning Theory[M]．New York：Wiley—Inter- 95．75 4425．3125 94．25 10269．7188 science．1998． 95．75 95．75 95．5 57“．4062 4807．3438 93．00 94．75 11762．6719 15482．6406 [7]王兴玲，李占斌．基于网格搜索的支持向量机核函数参数的确定 [J]．中国海洋大学学报，2005，35(5)：859—862． [8]雷英杰，张善文，李续武，等．MATLAB遗传算法工具箱及其应用． 5062．7031 94．50 14415．9062 西安：西安电子科技大学出版社，2005． 96．25 4682．8438 93．75 9453．3438 96．25 5019，9375 96．25 7546．0312 95．5 5462．4062 94．50 94．25 94．00 93．50 94．25 12183．5938 13166．6406 11284．125 13391．6562 13157．5 5846．9375 4835．0312 96．25 95．75 95．9 5345．2953 94．075 12456．7797 (上接第55页) 参考文献 [1]Dongyan Xu，Sunil Suresh Kulkami，Catherine Rosenberg，et a1．Analy- si8 of a CDN—P2P hybrid architecture for cost-effective streaming media distribution．Multimedia Systems．2006，1l(4)：383—399． [2]Shomb Khan，Rudiger Schollmeier．A Performance Comparison of Mul- tiple Description Video Streaming in Peer-to-Peer and Content Delivery Networks[J]．2004 IEEE International Conference on Multimedia and 从表2的结果可以看出，用遗传算法进行优化得到的总体 Expo(ICME)． 结果优于网格搜索的优化方法得到的结果，并且在运行时间上 [3]冯玮，刘心松，付国为．基于P2P技术的CDN中内容路由算法的改 大大缩短了。由于篇幅有限，仅列出其它三种核函数参数优化 的平均分类正确率和优化时间作为比较(10次)，如表3所示。 表3的结果中，采用线性核函数和多项式核函数用遗传算法进 行参数优化在结果上优于网格搜索的优化方法得到的结果，而 采用遗传算法也实现了对多层感知器核函数参数的优化，10次 的平均分类正确率达到了80％以上。从各种核函数的结果对 比也可以看出，采用不同的核函数对支持向量机分类器的分类 性能也有很大差异，其中采用高斯径向基核函数和多层感知器 核函数的结果都比较好，而采用线性核函数的分类结果并不理 进[J]．成都信息工程学院学报，2006，12(6)． [4]杨传栋，余镇危，王行刚．结合CDN与P2P技术的混合流媒体系统 研究[J]．计算机应用，2005，9． [5]姚源，褚伟．P2P和CDN中MDC流媒体的性能对比[J]．计算机技 术与发展。2007。9． [6]邓亮．P2P与CDN结合实现的IPvT点播业务[J]．网络应用， 2007，1． [7]。杨扬，王嵩，朱明．基于P2P的CDN系统的安全认证模型一DPI(I [J]．计算机应用，2007，3． [8]杨晓波．P2P技术在CDN网络中的应用研究[J]．计算机系统应 想(仅有70％左右)，这也充分说明了核函数选择的重要性。 用，2007，3． 万方数据