基于遗传算法的支持向量机的参数优化*

曹　路　欧阳效源

(1.五邑大学信息工程学院　江门　529020)(2.中山大学信息科学与技术学院　广州　510006)



基于遗传算法的支持向量机的参数优化*

曹路1,2欧阳效源2

(1.五邑大学信息工程学院江门529020)(2.中山大学信息科学与技术学院广州510006)

摘要支持向量机的性能主要受到核函数的参数和惩罚因子的影响,其中,以高斯核函数作为支持向量机的核函数的应用最为广泛。论文在研究了惩罚参数C及高斯核函数参数σ对支持向量机分类性能影响的基础上,利用网格搜索法和遗传算法对基于RBF核的SVM进行了参数优化,并通过UCI数据集进行了验证。实验结果显示,遗传算法相较于网格搜索算法具有更快的搜索速度,在实际运用中更加高效。

关键词支持向量机; 核函数; 参数; 遗传算法

Class NumberTP273

1　引言

传统的统计研究方法都是建立在大数定理基础上的渐近理论,要求学习样本数足够多。然而在实际应用中,这一前提往往得不到保证。20世纪60年代V.Vapnik等提出的支持向量机(Support Vector Machine,SVM)是以统计学习理论为基础的机器学习方法,它通过寻求结构化风险最小来提高学习的泛化能力,即使在小样本的情况下,也能获得良好性能;同时,SVM克服了传统分类器过学习、局部极值和维数灾难等缺点,在理论和实际应用中表现出很多优越的性能[1]。

SVM是一种基于核函数的学习方法,通过引入核函数,SVM将低维空间不可分的数据映射到高维空间。但核函数的选取并没有公认统一的方法。常用的核函数有线性核函数,多项式核函数,高斯核函数和多项式核函数,其中以高斯核应用最为广泛[2]。本文主要讨论了惩罚参数C及高斯核函数参数σ对支持向量机性能的影响,并运用遗传算法对参数进行寻优得到最优参数。

2　支持向量机理论

支持向量机的基本思想为:寻找一个最优超平面,使得该超平面在保证分类精度的同时,最大化超平面两侧的区域,并利用凸优化中的对偶方法将间隔最大化的问题转化为一个凸二次规划问题进行求解[3]。

在标准的支持向量分类器中,独立的超平面可定义为

f(x)=wTx+b=0

(1)

通过引入正则化项和松弛变量ξ,优化问题可以描述为

s.t.yi(wΤxi+b)≥1-ξi,ξi≥0∀xi

(2)

其中C为惩罚参数。为求解式(2)的对偶问题可以获得最优分界面。为了求解非线性情况,SVM通过核函数将原始特征空间中的非线性分界面映射到高维空间中以获得更好的分类效果。

3　参数对SVM的影响

3.1惩罚参数C的影响

为了测试惩罚参数C对SVM分类器的影响,对两类符合正态分布的人工数据样本用SVM进行分类,如图1所示。采用的两类数据为均值分别为0和4,方差为1的20*2维的随机向量。实心圆点和空心方块分别表示两类数据,并在样本集中加入一个噪声点(坐标为(1,2)),灰色圆点为支持向量。C的取值分别为10,1,0.01和0.25。其中C=0.25是采用3折交叉验证情况下用网格搜索法获得的C的最优解,此时分类准确率为97.561%,即41个训练点有一个点被错分。

图1　C取不同值时的分类面和支持向量

惩罚参数C用于控制模型的复杂程度。由图1可以得到,当C过大时,噪声对分界面的影响非常大。C越大,对数据集的拟合程度越大。当C取值趋于无穷大时,此时目标函数问题的所有约束条件都要满足,所有的训练样本数据都要正确分类,容易出现过拟合的现象。随着C的减小,每个训练点对最大间隔的潜在影响被削弱,越来越多的训练点成为支持向量在决策中起作用。当C太小,学习机器的复杂度将减小但经验风险误差将变大,容易出现欠拟合的情况,不能很好地泛化新数据。

3.2高斯核参数σ的影响

为了测试高斯核参数σ对SVM分类器的影响,对两类线性不可分的人工数据样本用高斯核SVM进行分类,如图2所示。

图2　σ取不同值时高斯核SVM分类面和支持向量

可以看到,当C=10,σ=0.05时,决策边界过于简单,决策边界不能很好地弯曲从而围住方块数据;而当C=10,σ=20时,几乎所有的训练点都成为支持向量,决策面过于复杂;当C=10,σ=1时,模型的效果较好。很明显,在高斯核中,增加σ会增加边界的复杂度。只有选取适合的参数(C,σ),在拟合数据和泛化数据之间达到一种折衷,模型才能有较好的性能。

图3是选取UCI数据库中glass数据集进行的测试,得到的是测试精度随参数(C,σ)变化的曲线图。从图3(a)图可知,当惩罚参数在3附近时,能获得最佳分类精度;从图3(b)图中可知,取不同的σ值,预测分类时出现不同的精度。人造数据集和标准数据集均说明,要想得到分类精度较好的SVM学习模型,必须对参数(C,σ)进行优化。

4　参数优化方法

4.1网格搜索法

网格搜索法首先将C和σ设定一个区间范围,设定步进值;然后在该区间分别取M个值和N个值,组成M×N个不同的(C,σ)参数,利用训练数据集样本分别训练出不同的支持向量机;然后通过测试数据集来估计其学习精确度,从而在M×N个(C,σ)参数中选出模型学习精度最好的一组参数C和σ作为最优参数[4]。

采用网格搜索在某种小步长情况下可以获得学习模型的最高分类准确率,即获得全局最优解。但要获得全局最优解(步长较小),其计算量比较大,特别是大范围搜索计算花费时间更长。通过对基本的网格搜索法进行改进,可以大大减少计算量,节省计算时间。其基本思想是:首先用较大的步长在某个区间范围进行搜索,寻找出最优参数(此时缩小了搜索范围);然后以最优参数为中心,在附近的一定范围内以更小步长进行更细小的网格搜索,可得到更加精确的结果。

图3　参数对SVM的影响

4.2遗传算法

遗传算法(Genetic Algorithm,GA)起源于对生物系统研究的计算机模拟研究,是模拟生物界遗传形式和参考生物进化理论而形成的一种可以并行随机搜索的优化方法,它把自然界生物自然选择优秀个体的方法引入到优化参数问题形成的串联编码的群体中,参照自然界适者生存的选择办法,按照所选择的适应度函数对个体进行测试和选择,通过选择、交叉、和变异等步骤对个体进行筛选,使适应度好的个体得以保留[5]。通过归一化的计算方法,将适应度大小转换为概率问题,对应地,概率大的个体被选中的概率大,即对应上面的适应度好的个体得以保留,概率小的对应个体淘汰的概率也会更大,而新的个体继承上一代的信息后,又进一步进化,这样往复循环,直至选择出最优参数。

4.3两种优化算法比较

网格搜索法的优点是算法构造简单,可以并行处理数据,每个参数的SVM训练都是独立的,缺点是效率低,计算量过大,参数多时计算量呈现次方增长,如两个参数时计算次数为O(n2)。遗传算法的优点是擅长解决全局最优化问题,算法鲁棒性强,过程简单,并可与问题领域无关进行快速搜索,扩展性好。本文将通过实验说明遗传算法在寻优方面的优势。

5　实验

本实验的数据来源于标准数据库UCI数据集,实验数据集的描述见表1。实验中将数据按比例提取一部分数据作为训练数据,另一部分作为测试数据;接着对数据进行归一化处理,训练优化参数C和σ;然后对训练数据集训练数据,构建模型,建立SVM;下一步测试测试集数据,比较分类准确率和寻优时间。表2为基于高斯核的SVM参数优化的网格搜索法和遗传算法的比较。

表1　数据集描述

表2　基于RBF核参数优化算法的比较

从表2中显示,网格搜索法和遗传算法在搜索精度上没有明显的差别,但是优化参数的搜索速度不相同。很明显地,遗传算法的搜索速度更快,这在实际运用有巨大的优势。因此,遗传算法相对于网格搜索法,在基于RBF核的SVM分类器的参数优化运用中具有更好的可行性。

6　结语

本文在研究了惩罚参数C及高斯核函数参数σ对支持向量机分类性能影响的基础上,利用网格搜索法和遗传算法对基于RBF核的SVM进行了参数优化,并通过UCI数据集进行了验证。实验结果显示,遗传算法相较于网格搜索算法有更快的搜索速度,在实际运用更加高效。然而遗传算法容易受到随机的初值影响,其效果与适应度函数的选择有关,利用改进的遗传算法对支持向量的参数进行优化是下一步的工作计划。

参 考 文 献

[1] Vladimir N. Vapnik.统计学习理论[M].许建华,张学工,译.北京:电子工业出版社,2004.

Vladi-mir N. Vapnik. Statistical Learning Theory[M]. XU Jianhua, ZHANG Xuegong, translated. Beijing: Electronic Industry Press,2004.

[2] 梁礼明,钟震,陈召阳.支持向量机核函数选择研究与仿真[J].计算机工程与科学,2015,6(37):1135-1141.

LIANG Liming, ZHONG Zhen, CHEN Shaoyang. The selection of kernel function and simulation for SVM[J]. Computer Engineering and Science,2015,6(37):1135-1141.

[3] 邓乃扬,田英杰.支持向量机:理论、算法、与拓展[M].北京:科学出版社,2009.

DENG Naiyang, TIAN Yingjie. Support vector machine: theory, algorithms, and expand[M]. Beijing: Science Press,2009.

[4] 李琳,张晓龙.基于RBF核的SVM学习算法的优化计算[J].计算机工程与应用,2006(29):190-192.

LI Lin, ZHANG Xiaolong. Learning algorithm optimizing on support vector machines based on RBF kernel function[J]. Computer Engineering and Application,2006(29):190-192.

[5] 朱珏钰,李峰.matlab神经网络优化的遗传算法[J].赤峰学院学报(自然科学版),2011,3(27):35-36.

ZHU Jueyu, LI Feng. Genetic algorithm optimization of matlab neural network[J]. Journal of Chifeng University(Natural Sciences),2011,3(27):35-36.

[6] 刘飇,陈春萍,封化民,等.基于Fisher准则的SVM参数选择算法[J].山东大学学报:理学版,2012,47(7):50-55.

LIU Biao, CHEN Chunping, FENG Huaming, et al. A SVM parameters selection algorithm based on Fisher criterion[J]. Journal of Shangdong University: Natural Science,2012,47(7):50-55.

[7] Olivier Chapelle, Vladimir Vapnik, Olivier Bousquet, et al. Choosing Multiple Parameters for Support Vector Machines[J]. Machine Learning,2002,46(1):131-159.

[8] 王敏,王文剑.一种支持向量机集成的核选择方法[J].计算机工程与应用,2009,45(27):31-33.

WANG Ming, WANG Wenjian. A integrated selection of kernel function for support vector machine[J]. Computer Engineering and Application,2009,45(27):31-33.

[9] R. Sivaraj. A review of selection methods in genetic algorithm[J]. International Journal of Engineering Science and Technology,2011,3(5):3792-3794.

[10] 奉国和.SVM分类核函数及参数选择比较[J].计算机工程与应用,2011,47(3):123-125.

FENG Guohe, WANG Wenjian. Parameter optimizing for support vector machine classification[J]. Computer Engineering and Application,2011,47(3):123-125.

收稿日期:2015年10月3日,修回日期:2015年11月27日

基金项目:2014年五邑大学青年基金(编号:2014zk10);2015五邑大学青年基金(编号:2015zk11);2015年江门市科技计划项目(编号:201501003001556)资助。

作者简介:曹路,女,硕士,讲师,研究方向:模式识别。欧阳效源,男,硕士研究生,研究方向:机器学习及无线通信技术。

中图分类号TP273

DOI:10.3969/j.issn.1672-9722.2016.04.003

Parameters Optimization of SVM Based on Genetic Algorithm

CAO Lu1,2OUYANG Xiaoyuan2

(1. School of Information Engineering, Wuyi University, Jiangmen529020)(2. School of Information Science and Technology, Sun Yat-sen University, Guangzhou510006)

AbstractThe performance of SVM is mainly affected by the kernel function parameters and penalty parameter. SVM with RBF kernel function is the most widely applications. Using genetic algorithm to select optimum parameter, the paper mainly studies the performance of SVM with penalty parameter C and RBF kernel function parameter σ. Comparing grid search with genetic algorithm for optimum parameter to SVM based on RBF kernel function in experimental results, it is found that genetic algorithm has higher search speed in optimum parameter. Thus, genetic algorithm is more effective in practice.

Key WordsSVM, kernel function, parameter, genetic algorithm