基于改进的网格搜索法的SVM参数优化

第39卷第3期应用科技Vol.39,No.32012年6月AppliedScienceandTechnologyJun.2012doi:10.3969/j.issn.1009-671X.201112016基于改进的网格搜索法的SVM参数优化王健峰，张磊，陈国兴，何学文哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001摘要：比较了现今应用比较广泛的3种支持向量机（SVM）参数优化方法.具体分析了网格法、遗传算法和粒子群算法在SVM参数优化方面的性能以及优缺点，提出了一种改进的网格法.先在较大范围内进行搜索，在得到的优化结果附近区域再进行精确搜索.实验表明改进的网格搜索法耗时短，更适用于有时间要求的说话人识别应用中.关键词：支持向量机；参数优化；网格搜索；遗传算法；粒子群算法；说话人识别中图分类号：TP273文献标志码：A文章编号：1009-671X（2012）03-0028-04AparameteroptimizationmethodforanSVMbasedonimprovedgridsearchalgorithmWANGJianfeng,ZHANGLei,CHENGuoxing,HEXuewenCollegeofInformationandCommunicationEngineering,HarbinEngineeringUniversity,Harbin150001,ChinaAbstract:ThreekindsofSVMparametersoptimizationmethodswerecomparedinthispaper.Theperformancesandcharacteristicsofgridsearch,geneticalgorithmandparticleswarmoptimizationinSVMparametersoptimizationwereanalyzed.Inthispaperanimprovedgridsearchmethodwasproposed.Firstly,wesearchedasetofparametersinalargespaceandthensearchedaccuratelyaroundtheparameterswehadfound.Thesimulationshowsthattheimprovedmethodueseslesstimeandissuitablefortheapplicationsofspeakerrecognitionlimitedbytime.Keywords:supportvectormachines;parametersoptimization;gridsearch;geneticalgorithm;particleswarmoptimization;speakerrecognitionSVM是一种基于统计学习理论基础上的机器学习方法，具有很好的泛化能力[1]，在说话人识别等模式识别领域得到了广泛的引用.与其他重视经验风险最小化的算法相比，SVM能够得到更好的泛化精度，在小样本、非线性模式识别中具有一定的优势.实践证明，核函数的参数以及惩罚系数对SVM的性能有着很大的影响[2].而对于一些对实时性要求较高的系统，如说话人识别系统而言，快速的选择合适的SVM参数，减少训练和识别时间有着很重要的实际意义.1关于SVM参数的优化选取，国际上并没有公认统一的最好的方法，目前较为常用的SVM参数寻优的方法有：实验法、网格搜索（gridsearch）法[3]、遗传算法（geneticalgorithm,GA）寻优法[4]、粒子群算法（particleswarmoptimization,PSO）寻优法[5]等.实验法是指通过大量的实验比较来确定参数，这种方法十分浪费时间，且不易寻得最优参数.网格搜索法是收稿日期：2011-12-08.作者简介：王健峰（1987-），男，硕士研究生，主要研究方向：语音信号处理、自然语言处理，E-mail:[e-mail].将待搜索参数在一定的空间范围中划分成网格，通过遍历网格中所有的点来寻找最优参数.这种方法在寻优区间足够大且步距足够小的情况下可以找出全局最优解.由于网格内多数参数组对应的分类准确率都非常低，只在一个比较小的区间内的参数组所对应的分类准确率很高，所以遍历网格内所有参数组会相当浪费时间.GA算法和PSO算法属于启发式算法，它们不必遍历区间内所有的参数组也能找到全局最优解，但这2种算法操作往往比较复杂，且容易陷入局部最优.针对网格搜索法搜索时间长的问题提出一种改进的网格搜索法，先采用大步距大范围粗搜，初步确定一个最优参数区间，之后在此区间内进行小步距精搜，大幅度地减少了参数寻优时间，使基于SVM的说话人识别系统更好地满足实时性的要求.1支持向量机SVM[6-7]的基本思想是通过非线性变化把原数据空间变化到某一高维的特征空间，然后在这个新空间第3期王健峰，等：基于改进的网格搜索法的SVM参数优化·29·中求取最优线性分类面，使得该超平面将2类样本正确无误地分开且使分类间隔最大.这种非线性变化通过定义适当的内积函数加以实现.SVM的特点在于根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折中，以获得最好的推广能力.对于给定的线性可分数据集{,},iixyi1,,,N{1,1},diiyxR，d维空间中的线性判别函数()gxxbw，则可用超平面0xbw（1）进行分离.式中w为权向量，b为分类阈值.而要求分类线对所有样本正确分类，就是要求它满足：()10,1,2,,.iiyxbin≥w（2）满足上述条件且使得分类间隔最大的超平面就是最优分类面，如图1所示.图1最优分类面经过整理，最优分类面问题可以表示成如下的约束优化问题，即在式（2）的约束下，求函数211()()22（3）的最小值.最终可以得出最优分类函数是：1()sgn(())sgn(()).Niiiifxxbayxxbw（4）式中：ia是二次规划优化问题所求解的拉格朗日因子，N为支持向量数.对于线性不可分情况，可以通过在约束条件中引入松弛变量，在目标函数中加入惩罚函数来解决这一问题.这时广义最优分类面问题可以进一步演化为求取下列函数的极小值：11(,)()().2niiC（5）式中：C为常数，它实际上起控制对错分样本惩罚的程度的作用，实现错分样本的比例与算法复杂度之间的折中.若C过大，就会引起过学习，影响分类器的泛化能力.如果一个问题在其定义的空间中不是线性可分的，可以考虑通过引入核函数(,)iKxx，把问题转换到一个新的空间中，相应的判别函数为1()sgn((,))niiiifxayKxxb（6）径向基核函数是目前应用最广泛的核函数[8-9]，文中采用的就是这一核函数，其形式如下：2(,)exp(),0ijijKxxgxxg（7）式中：参数g是核函数中的重要参数，影响着SVM分类算法的复杂程度.综上所述，惩罚参数C和核函数参数g是影响SVM分类器性能的关键参数，所以文中以（C,g）作为寻优变量.2改进的网格搜索寻优方法2.1交叉验证交叉验证（crossvalidation,CV）是用来验证分类器性能的一种统计方法，基本思想是把在某种意义下将原始数据进行分组，一部分作为训练集，另一部分作为验证集.首先用训练集对分类器进行训练，再利用验证集来测试训练得到的模型，以此作为评价分类器的性能指标.通常人们都采用K-foldCV，将原始数据分成K组（一般是均分），将每个子集数据分别做一次验证集，其余的K-1组子集数据作为训练集，这样会得到K个模型，用这K个模型最终的验证集的分类准确率的平均数作为此K-CV下分类器的性能指标.K一般大于等于2，实际操作时一般从3开始取.只有在原始数据集合数据量小的时候才会尝试取2.K-CV可以有效地避免过学习以及欠学习状态的发生,最后得到的结果也比较具有说服性.2.2改进的网格搜索法网格搜索法[10]的基本原理是让C和g在一定的范围划分网格并遍历网格内所有点进行取值，对于取定的C和g利用K-CV方法得到在此组C和g下训练集验证分类准确率，最终取使得训练集验证分类准确率最高的那组C和g作为最佳的参数.这里给出参数寻优结果如图2所示，其中C的范围设置为[2-10,27]，g的范围设置为[2-10,23]，步距为0.1.从图2中可以发现，参数C和g在一定区间上对应的分类准确率很高，但在多数范围内的分类准确率却很低，因此若能先定位出比较好的参数寻优区间，·30·应用科技第39卷再进行精确搜索，就能够减少不必要的计算，节省大量的时间.图2SVC参数选择结果针对以上问题，提出一种改进的网格搜索法.首先，在较大范围内采用大步距进行粗搜，选择使分类准确率最高的一组C和g.若参数选择过程中有多组的C和g对应于最高的验证分类准确率，则选取能够达到最高验证分类准确率中参数C最小的那组C和g做为最佳的参数；如果对应最小的C有多组g，就选取搜索到的第一组C和g做为最佳的参数.这样做是因为过高的C会导致过学习状态发生，即训练集分类准确率很高而测试集分类准确率很低(分类器的泛化能力降低)，在能够达到最高验证分类准确率中的所有的成对的C和g中认为较小的惩罚参数C是更佳的选择对象.在寻得了局部最优参数之后，再在这组参数附近选择一个小区间，采用传统方法中的小步距进行二次精搜，找到最终的最优参数.如果参数区间选择合理，那么改进的网格搜索法能够搜索出全局最优的参数，但由于这个区间的选择含有比较多的经验成分，所以通常情况下只能得到局部最优的参数.因此，这种改进的网格搜索法相当于牺牲了分类准确度，来减少大量的搜索时间.3实验结果及分析实验采用的数据是从4名说话人的语音数据中提取的4组13维Mel频率倒谱系数(melfrequencycepstralcoefficients，MFCC），其中第1组含有141个样本，第2组含有206个样本，第3组含有169个样本，第4组含有132个样本，每个样本包含13个特征分量.实验平台为MATLABR2010b，采用台湾大学林智仁（Chih-JenLin）博士等[11]开发设计的LIBSVM工具包进行测试.实验中首先将样本数据分为1,2,3,4（）4类，并转换成LIBSVM要求的输入格式.采用改进的网格搜索法进行参数寻优的实验过程如下：1）设定网格搜索的变量（C，g）的范围以及搜索步距.其中C的初始范围设置为[2-10,27]，g的初始范围设置为[2-10,23]，由于传统方法中步距一般设为0.1，所以改进方法中初始步距选为100倍的步距，设为10.2）采用K-CV方法对训练集进行测试，其中K=3，并得到使分类准确率最高的局部最优参数C=1和g=0.00097.根据得到的局部最优参数，在其附近选择不同的区间进行二次寻优，步距与传统方法一样设为0.1，比较不同的搜索区间对分类准确率的影响，结果记录于表1.表1不同搜索区间内参数寻优的结果比较参数第1组第2组第3组C范围[2-12][2-222][2-323]g范围[2-102-9][2-102-8][2-102-7]BestC1.41421.74111.8661Bestg0.00200.00390.0045准确率/%89.337291.066391.3545时间/s4.9118.9546.53从表1中可以看出，如果二次寻优的参数区间选择过窄，则可能出现局部最优，对应的分类准确率会低一些，而参数区间选择过宽，寻优时间又会过长.为了在两者间进行折中，提出的改进的网格搜索法采用第2组的参数区间.为了便于分析，分别采用传统网格搜索法、改进的网格搜索法、GA以及PSO进行参数寻优，比较各自性能.实验从4名说话人数据中随机抽取2名训练一个分类器进行寻优测试，一共做6组.其中GA参数寻优法和PSO参数寻优