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

刘小生;章治邦

【摘 要】支持向量机的学习和泛化能力很大程度上取决于其相关参数的选取.针对传统网格算法的不足,引入全局粒子群算法,利用其能够快速到达最优解附近的优势:先使用粒子群算法进行粗搜;再使用网格搜索法进行小步长的精细搜索得到最优解.实验结果表明:基于改进的网格搜索法SVM对比传统网格搜索法SVM,在预测精度和运算时间上都具有优势.

【期刊名称】《江西理工大学学报》 【年(卷),期】2019(040)001 【总页数】5页(P5-9)

【关键词】支持向量机;参数优化;网格搜索法 【作 者】刘小生;章治邦

【作者单位】江西理工大学建筑与测绘工程学院,江西 赣州 341000;江西理工大学建筑与测绘工程学院,江西 赣州 341000 【正文语种】中 文 【中图分类】TP181 0 引 言

支持向量机 (Support Vector Machine，简称SVM)是一种基于统计学习理论中的结构风险最小化的原则提出的机器学习算法，具有坚实的理论基础和良好的泛化

能力[1-2]，在解决小样本、非线性问题中相比于其他机器学习算法具有一定的优势.但是要实现这些优势的前提是要选取合适的核函数及其参数，特别是其参数的优化选择对于SVM的学习和泛化能力的优秀与否起着举足轻重的影响.国内外许多学者已经在这方面开展了非常深入的研究，各种参数优化方法也层出不穷，但至今还没有形成公认统一的最优方法.

关于SVM参数的优化方法，目前较为常用的方法有：粒子群算法[3]（Particle Swarm Optimization,简称 PSO）、网格搜索算法[4-5]（Grid Search）、遗传算法[6]（Genetic Algorithm，简称 GA）、蚁群算法[7-8]（Ant Colony Optimization,简称 ACO）等.但这些传统方法都存在不足之处，如：遗传算法编码复杂，参数众多，且参数的初始值会对结果有非常大的影响；粒子群算法虽然收敛速度较快，但是相对的也容易陷入局部最优解；网格搜索法使用较多，在设定区间足够大，且步长足够小时，可以找出全局最优解,但遍历所有网格会相当浪费时间．文中针对上述提到的传统网格搜索算法的一系列问题，提出一种改进的网格搜索法支持向量机． 1 支持向量机

SVM的原理是把在常规下无法正确分类的数据利用核函数投影到一个特征空间中去，并在这个特征空间中寻找一个最优的分类超平面对数据样本进行划分．以两类数据为例，所谓最优分类超平面，即为在保证样本数据分类准确率的基础上，使得两类数据的分类间隔最大化[9-12]．

再次以两类数据为例，给定训练样本集（xi，yi），i=1，2，…，l，x∈Rn，超平面记作（w·x）+b=0 则它满足如下约束：yi[（w·xi）+b]≥1，i=1，2，…，l． 在这里可以计算出分类间隔为2‖w‖，所以要建立最优超平面的问题变成在有约束条件下求：

为了解决该最优化问题，引入Lagrange函数：

式（2）中，这个最优化问题的解由Lagrange函数的鞍点控制，并且最优化问题的解在鞍点处满足对w和b的偏导为0，将该凸二次规划问题转化为相应的对偶问题即：

解得最优解

计算最优权值向量w*和最优偏置b*，分别为：

其中，下标因此获得了最优分类超平面（w*·x）+b*=0，其中它所对应的最优分类函数即为：

上面的情况都是针对线性可分的情况，对于另一种线性不可分的情况时，需要在其中加入一个惩罚函数C来解决，C也称为松弛变量，现在原本的求最优分类面问题就变为求下列函数的极小值：

式（7）中，C 为常数，这里既要最小化（w·w）（最大化间隔），又要最小化参数C的作用是调整（w·w）和的对于整个式子的权重大小．这时就可以考虑引入核函数K（xi，x），实现从线性分划到非线性分划的过渡，则可以得到最优分类函数为：

2 网格搜索法及其改进

网格搜索法是一种最基本的参数优化算法[13]．它实质上就是将待搜索参数在一定的空间范围按照拟定的坐标系中划分成长短相同的网格，坐标系中每一个点都代表

一组参数，进而可以通过将这个给定区间内的每个点带入支持向量机系统中验证其性能，使得整个系统的性能最优秀的那个点我们称它为最优参数．但是这种方法也有缺点，它在设定区间足够大，且步长足够小时，可以找出全局最优解，但是这是有代价的，因为所划分网格内绝大多数的点所对应的分类准确率都非常低，只有在一个较小的区间中所对应的参数的准确率较高，由于网格搜索的算法就是要遍历所有网格对应的点，所以这必然产生大量不必要的无效计算，进而导致运算时间呈幂级上升．图1为举例数据的网格搜索法SVM搜索准确率结果图，其中三维坐标中的竖坐标Accuracy（%）表示分类准确率，横纵坐标分别表示参数（C，g）的选值，可以从图1中看出，绝大部分区间内的准确率都非常低（左侧平整部分），然后在交界处准确率开始迅速上升，直至高准确率部分（右侧平整部分），由此可见，绝大部分区间内的参数所代表的准确率非常低． 图1 网格搜索法SVM参数选取结果

另一方面，步长的大小也是制约算法运算速度的重要因素之一，来看另外一组样本数量较大的数据，这组试算数据共有270个样本数据，把其中170个样本数据作为训练数据用以训练最优参数，另外100个样本数据作为测试数据．

图2为大步长网格搜索的SVC参数结果图，在参数搜索区间不变的情况下 （惩罚参数C与核函数参数 σ（g）的搜索区间均为 2-8～28），图 2 的搜索步长为1．寻优结束时所消耗的时间是0．5133 s，测试数据的准确率为77%． 图2 大步长网格搜索效果

图3 为小步长网格搜索的SVC参数结果图，为了对比不同步长下算法搜索消耗的时间，再设置搜索步长为0．1．寻优结束时，步长为0．1的算法搜索时间为．4848 s，测试数据的准确率为84．0122%． 图3 小步长网格搜索效果

对比两种步长的算法搜索时间和准确率，可以得知步长也是制约网格搜索算法运算

时间的重要因素．且随着步长的缩小，算法的搜索时间会越来越长，这相当于细化了原先了坐标系格网，大大增加了运算量．但是，随着步长的减小，算法的搜索必然越来越精确，所以算法所得参数的准确率也会随着步长的缩小而进一步提升（前提是大步长的参数寻优没有达到全局最优解，只是到达了最优解的附近）． 综上所述，网格搜索算法存在着无效搜索区域过多且算法运算时间受步长影响很大的缺点，为了尽可能达到算法的全局最优解，不能牺牲步长来换取算法在时间上的缩短．那么如何尽可能的避免无效区域的搜索，使算法能够根据实际情况快速定位到全局最优解附近，进而就可以使用小步长的网格搜索法对这个最优区间进行“精确”搜索，就成为了问题的关键所在．

因此，如果可以先定位出一个范围较小的“优秀”参数搜索区间，再在这个小区间内进行小步长的精确搜索，就可以减少不必要的计算，有效提高准确率，进而大大提高运算效率．在这里文中引入粒子群优化算法，缩写为 PSO，是近年来由J．Kennedy和 R．C．Eberhart等开发的一种新的进化算法[13]．粒子群算法的一大优势就是在算法初期可以迅速收敛至所需要的最优解附近，利用粒子群算法的这一优势，在算法前期使用粒子群算法先对所需参数进行一次粗略的最优参数搜索，以此来排除掉大部分分类准确率很低的区间．再使用网格搜索法对以粒子群算法确定参数为搜索中心，进行第二次小区间小步长的精细寻优，并且逐步扩大搜索范围，选取其中准确率最高的那一组参数作为最优参数．

SVM常用的核函数有多项式核函数、Gauss径向基核函数、sigmiod核函数等[14-15]，其中，Gauss径向基核函数是目前应用最广泛也是效果最好的核函数之一，无论是小样本还是大样本，高维还是低维等情况，Gauss径向基核函数均适用．它相比其它核函数具有所需要确定的参数少的优势，公式如下：

式（9）中：参数g是影响 SVM算法性能的重要参数．

文中以Gauss径向基核函数作为核函数为例，需要确定惩罚函数C以及参数g． 新算法的搜索步骤如下：首先运用全局粒子群算法对SVM所需要确定的参数（C，g）进行第一次寻优，快速搜索定位出最优参数区间，得到的结果为（C，g）1．此时若有多组（C，g）对应最高的分类准确率，则选取参数C最小的那一组．此时，从（C，g）1出发，以（C，g）1为区间搜索中心，重新确定并缩小搜索范围，运用网格搜索算法进行第二次小步长的精确寻优，并不断缓慢扩大搜索范围，逐步跳出粒子群算法所在的局部最优，在得到的多组寻优结果中取最优值，得到的结果为（C，g）2．将（C，g）2代入SVM的核函数中，就得到了改进的网格搜索法SVM． 3 实验及结果分析

实验采用的三组数据均来自加州大学欧文分校（University of CaliforniaIrvine）提出的用于机器学习的UCI数据库.第1组含有270个样本，每个样本包含13个特征分量；第2组含有150个样本，每个样本包含4个特征分量；第3组含有100个样本，每个样本包含2个特征分量.实验平台为MATLAB R2012b，采用大学林智力仁（Chih-Jen Lin）博士开发的LIBSVM工具包进行测试.

其中，第1组和第2组样本数据分为（1，2，3）三类，第 3 组样本数据分为（1，2）二类，并转化为LIBSVM所要求的格式进行输入，并经过改进的网格搜索法SVM进行参数寻优的过程如下：

1）首先设定所要搜索的参数（C，g）的初始范围以及粒子群算法初始进化代数和种群数量，其中（C，g）的搜索范围设置为[2-8，28]，初始进化代数设置为100，种群数量设置为20.

2）采用交叉验证方法[13]对训练样本进行测试，其中K=5，即5折交叉验证.得到的最优参数（C，g）1.第一次粒子群算法参数寻优得到的最优参数值记录于表1. 表1 PSO寻优参数结果参数 第1组 第2组 第3组C 范围 [2-8，28] [2-8，28]

[2-8，28]g 范围 [2-8，28] [2-8，28] [2-8，28]BestC 6.9445 2.5748 0.1213 Bestg 0.0100 4.1911 6.4593

3）在其附近选择合适的区间进行小步长的网格搜索法寻优，由于传统网格搜索法中步距一般设为0.1，所以本次小步长精细寻优中，初始步距设置为0.05. 如果二次寻优的参数区间选择过窄，则可能出现无法跳出局部最优的情况，如果选择区间过大，寻优时间又会过长，所以根据表1数据，在两者中进行折中处理，缓慢扩大搜索区间，重新确定的（C，g）搜索范围为记录于表2.

在重新确定了新的（C，g）搜索区间之后，将这组搜索区间代入第二次小步长的精确网格搜索中去，实验进行到这里，就确定出了我们想要获得的最优（C，g）参数，结果见表2.将最终得到的参数（C，g）重新代入支持向量机的核函数中去，就建立了基于改进网格搜索法的支持向量机.将以上3组实验数据分别代入计算，即为实验结果.

表2 重新确定的参数搜索范围及搜索结果参数 第1组 第2组 第3组C 范围 [2，25] [20，23] [2-3，2]g 范围 [2-7，2-3] [2，23] [2-2，24]BestC 24.2515 1.0000 0.1250 Bestg 0.0583 0.8123 0.5000

实验结果与传统的网格搜索法SVM的结果进行比较，得出各自的性能优劣. 在传统网格搜索法SVM中，我们为了方便比较，使用的步长为一般使用的0.1，比较结果见表3.

表3 实验结果实验组别改进的网格搜索法SVM准确率/% 准确率/% 时间/s第一组 85.7143 85.7143 26.21第二组 96.0000 98.6667 4.50第三组 98.0000 100 2.74传统网格搜索法SVM时间/s 227.81 30.18 13.12

从表3可以看出，对比传统网格搜索法SVM，改进的网格搜索法SVM所消耗的时间却更短，准确率也有所提升，特别是在运算时间方面，改进的网格搜索法SVM遥遥领先于传统网格搜索法SVM.即改进的网格搜索法SVM在提升分类准确

率的基础上，大大缩短了计算时间，取得了良好的效果. 4 结 论

传统的支持向量机的参数优化选取方法还没有公认统一的最优方法，各种改进方法也有各自的优缺点，文中提出的基于改进网格搜索法SVM的参数寻优，经过实验证明，该改进算法能够利用全局粒子群算法快速收敛于最优区间的优势，加速网格搜索算法的前期搜索速度，并且在后期搜索中使用小步长的精细搜索，进一步提高分类准确率，得到的结果也证明了改进的网格搜索法SVM具有更快的搜索速度，更高的分类准确率. 参考文献：

【相关文献】

[1]Vapnik V,Levin E,Cun Y L.Measuring the VC-dimension of learning machines[J].Neural Computation,1994,6(5):851-876.

[2]邓乃扬，田英杰.支持向量机——理论、算法与拓展[M].北京：科学出版社，2009. [3]李喆，柏丛，孙健，等.基于PSO-SVM的出行方式识别研究[J/OL].计算机应用研究，2016(12):1-5.

[4]曲健，陈红岩，刘文贞，等.基于改进网格搜索法的支持向量机在气体定量分析中的应用[J].传感技术学报，2015，28(5):774-778.

[5]郑志成，徐卫亚，徐飞，等.基于混合核函数PSO-LSSVM的边坡变形预测[J].岩土力学，2012，33(5):1421-1426.

[6]刘东平，单甘霖，张岐龙，等.基于改进遗传算法的支持向量机参数优化[J].微计算机应用，2010，31(5):11-15.

[7]秦玲.蚁群算法的改进与应用[D].扬州：扬州大学，2004.

[8]俞俊平，陈志坚，武立军，等.基于蚁群算法优化支持向量机的边坡位移预测[J].长江科学院院报，2015，32(4):22-27.

[9]Vapnik V N.The nature of statistical learning theory[M].New York:Springer-Verlag,1995. [10]徐飞，徐卫亚，王珂.基于蚁群优化支持向量机模型的边坡稳定性[J].工程地质学报，2009，17(2):253-257.

[11]赵洪波，冯夏庭.非线性位移时间序列预测的进化-支持向量机方法及应用[J].岩土工程学报，

2003，25(4):468-471.

[12]王健峰，张磊，陈国兴，等.基于改进的网格搜索法的SVM参数优化[J].应用科技，2012，39(3):28-31.

[13]J Kennedy,R Eberhart．Particle swarm optimization[C]//Neural

Networks,1995.Proceedings,IEEE International Conference on.IEEE,1995:1942-1948. [14]毛伊敏，周昭飞，彭喆，等.基于不确定多分类支持向量机在滑坡危险性预测的应用[J].江西理工大学学报，2016，37(3):102-108.

[15]范永东.模型选择中的交叉验证方法综述[D].太原：山西大学，2013.