一种改进型PSO算法在SVM参数寻优中的应用

房乐楠，何腾鹏，刘宇红

(贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

20世纪90年代，Vapnik等人首提支持向量机(Support Machine Vector，SVM)算法，该算法在小样本、非线性和高维模式分类中表现出特有的优势，因此得到了广泛的应用[1]。SVM作为一种机器学习算法的主要优势是泛化能力强，预测精度高，由于其独特的核函数机制，对非线性问题有着良好的逼近能力，但核函数对参数选取十分敏感，如何选取最优参数决定了SVM分类器的性能，针对SVM算法参数寻优问题，目前引入了诸多仿生算法如遗传算法、粒子群(Particle Swarm Optimization，PSO)算法、蚁群算法等[2]。

本文基于对PSO算法的研究，针对PSO算法在粒子搜索过程中易陷入局部最优的缺点，提出一种应用非线性惯性权重策略并引入双变异算子(边缘变异算子和全局变异算子)的改进型PSO算法，并将其应用于SVM参数寻优中。

1 SVM算法理论

SVM算法的主要思想是以统计学习理论为基础，可以概括为两点：(1)努力结构风险最小化，寻找最大化分类间隔以控制VC维，并使之最小，因而具有很强的泛化能力；(2)引入核函数和松弛变量技术，处理样本线性不可分问题[3]。

SVM算法解决样本线性不可分问题的主要思想是：通过非线性映射将低维线性不可分样本映射到高维特征空间，进而在高维特征空间进行线性分类。假设训练样本是Di=(xi,yi)其中：xi∈Rn,yi∈{-1,1},i=1,2,3…m,定义一个样本点到超平面的距离：

L=y1[(wx1+b)]

(1)

SVM分类可表示为：

f(x)=sgn[∑wφ(x)+b]

(2)

其中，sgn(·)是符号函数,w∈Rn,b∈R。

在高维空间进行线性分类是一个寻找最大化几何间隔的过程，其数学实质是求解凸优化问题[4]，即

(3)

yi[(wxi+b)]≥1-ξi

(4)

ξi≥0

(5)

其中，i=1,2,3,…,m是样本数；c是惩罚因子；ξi是松弛变量。

方程(2)可以转化为一个凸二次规划问题，所以分类函数可以写成

(6)

其中，αi为凸二次规划问题中的朗格朗日乘子，是满足Mercer条件的核函数，本文采用RBF核函数，公式如下

(7)

对于采用RBF核函数的SVM分类器来说，如何选取合适的c和σ值是至关重要的问题，其中惩罚因子值c的大小决定着样本对离群点的重视程度[5]，参数σ与输入空间的样本宽度和范围相关。

2 改进型PSO算法

PSO算法是一种全局进化算法，由Eberhart博士等人提出，源于对鸟群捕食行为的研究，利用个体之间信息共享使整个群体产生从无序到有序的演化过程，从而获取最优解，因此该算法是一类基于群体智能的仿生算法[6]。

2.1 标准PSO算法

在N维空间初始化一群粒子，其中第i个粒子的位置和速度信息可以用N维向量Xi和Vi表示：Xi=(Xi1,Xi2,Xi3,…,XiN)T，Vi=(Vi1,Vi2,Vi3,…,ViN)T。在找到个体极值P和全局极值G后，粒子根据如下公式更新自身的速度和位置

(8)

(9)

2.2 惯性权重策略

PSO算法的搜索过程是一种不断迭代收缩，初期快后期慢的过程，Eberhart等人提出线性惯性权重法以调整粒子的全局与局部搜索能力[7]，但粒子群搜索是一个复杂的过程，W值线性减小并不能反映出粒子实际的搜索过程，本文引入非线性惯性权重法[8]，递减策略为指数曲线，公式为

(10)

其中：Wmax和Wmin是W的最大值和最小值，iter和itermax是粒子当前迭代次数和最大迭代次数，a是调整因子，其作用是控制曲线的下降效果。为取得合理的下降效果a取10，实验表明：采用指数曲线的递减策略在搜索前期W值快速减小，后期递减速度明显变慢，符合粒子群前期收敛快后期慢的特点，且前期快速收敛可以使粒子更快进入精细的局部搜索。

2.3 双变异算子PSO算法

实验研究表明，粒子无论在进行全局搜索或是局部搜索时，都会出行“聚集”现象，此时种群的多样性十分欠缺，PSO算法过早收敛陷入局部最优正是由于种群多样性匮乏所致[9]。

2.3.1 边缘变异算子

随机产生一群粒子P，粒子的位置：Xi={Xmin,Xmax}，当一部分粒子收敛到位置的边缘或是粒子的位置超过最大范围而被限制在边缘时，此时边缘位置粒子(如：Xi=Xmax)的适应度值恰是当前群体的最佳适应度值，粒子便会向此边缘位置“聚集”，从而使算法陷入边缘局部最优。实验表明：初始化的粒子群是随机产生的，多数粒子因超出位置的限定范围而被限制在边缘位置，算法陷入边缘局部最优的概率增大，因此引入边缘变异粒子r1，公式为

(11)

2.3.2 全局变异算子

在粒子群搜索过程中出行“聚集”现象，粒子多样性十分匮乏时，粒子群迭代产生的全局最优解会出现停止更新现象，而该全局最优解极有可能是局部最优解，如果是则算法陷入局部最优[10]。因此针对全局最优解G引入全局变异算子r2，改变此解以改变当前粒子的前进方向，使粒子重新进入极值更新搜索过程，产生更为优秀的全局最优解。公式如下

Gk+1=(g1(g2-g1)×r2)×Gk

(12)

其中，g1和g2是限制范围，一般范围控制得较小，不会使已迭代产生的全局最优解发生大幅度变动，本文g1取0.8，g2取1.2。Gk和Gk+1是当代和次代的全局最优解，r2是服从正态分布的随机变量。

2.3.3 双变异算子PSO算法流程

所提算法流程可描述如下：(1)随机产生一群粒子，并初始化粒子的速度和位置；(2)根据目标函数计算每个粒子的适应度值；(3)根据式(8)和式(9)更新粒子的位置和速度，根据式(10)对惯性权重W进行非线性调整；(4)迭代过程中，根据粒子的位置和边缘适应度值判断其是否陷入边缘局部最优，如果是，根据式(11)调整粒子的位置；(5)迭代过程中，如果全局最优解停止更新(一般约为10次不发生明显变化)，如果是，根据式(12)对最优解进行小范围调整；(6)根据迭代条件停止迭代。

3 SVM参数寻优仿真实验

针对SVM参数寻优进行仿真实验，在Windows10和Matlab R2015b软件平台下利用工具箱Libsvm软件[11]进行训练预测，其中分类类型为C-SVC，核函数为RBF核函数。电脑硬件平台为Core-i3双核处理器，运行内存4 GB。

实验所用的Segment数据集来自于UCI公共数据库，其中包含了7个类型、19个特征、2 310个数据。实验采用K-fold交叉验证法，将数据分为K组(本实验K取3)，其中一组作为测试集，K-1组作为训练集，循环K次验证，取K次结果均值作为最终结果，K-fold交叉验证法可以最大程度的利用样本，有效的避免过学习以及欠学习状态的发生[12]。

3.1 仿真实验

在仿真实验中应用3种算法：(1)线性惯性权重标准PSO算法；(2)非线性惯性权重标准PSO算法；(3)非线性惯性权重改进型PSO算法，进行SVM参数寻优。实验对比结果如表1所示。

表1 3类算法实验结果对比表

以上3类实验中，粒子的最佳适应度和平均适应度迭代图如下。

图1 算法(1)适应度值迭代图

图2 算法(2)适应度值迭代图

图3 算法(3)适应度值迭代图

3.2 实验分析

图1～图3是最佳适应度值与平均适应度值迭代变化曲线(x轴是迭代数，y轴是适应度)，最佳适应度值是根据全局极值G和目标函数得出，其更新情况可以反映全局极值的变化，若保持不变或无明显变化，则算法陷入局部最优[13]。平均适应度值计算公式为

(13)

其中：argfitness(i)是当代平均适应度值， fitness(j)当前粒子的适应度，N是种群粒子数。分析公式得出：相似的粒子有着近似的适应度值，在迭代前期粒子多样

性丰富，平均适应度迭代曲线会产生较大幅度的振荡，后期曲线收敛变慢，粒子多样性减少[14]。

图1是采用线性递减惯性权重的标准PSO算法，最佳适应度曲线在迭代初期跳动之后一直保持不变，算法陷入局部最优；平均适应度曲线在收敛到一定值之后振荡幅度变化不明显，平均适应度值趋向近似，表明粒子已出现“聚集”现象，种群多样性减少。图2是采用非线性递减惯性权重的标准PSO算法，平均适应度曲线迭代初期收敛速度较快，但同样出现图1迭代后期值趋于平稳的现象。图3是采用非线性递减惯性权重的改进型PSO算法，如图所示，最佳适应度曲线每隔一定的代数增加，表明双变异算子的引入，改变了其易陷入局部收敛的情况，平均适应度曲线初期振荡明显，后期振荡变得微弱，但值仍保持递增趋势。从表1也可以看出采用改进型PSO算法进行分类的平均准确率明显优于采用标准PSO算法，但是由于改进PSO算法增加了运算量，耗时相对较长。

4 结束语

SVM算法以其独特优势已广泛应用于数据挖掘、文本分类等诸多领域[15]。本文针对该算法核函数参数最优化问题提出一种采用非线性递减惯性权重策略，引入双变异算子的改进型PSO算法，实验证明所提算法在SVM参数寻优中有着良好的效果，所确定的SVM分类器在分类中有着良好的性能。

[1] Keerthi S S, Shevade S K.SMO algorithm for least-squares SVM formulations[J].Neural Computation, 2014,15(2):487-507.

[2] 张东东.基于遗传算法的支持向量机分类算法[J].电子科技,2015,28(12):32-35.

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

[4] 陆星家,王玉金,陈志荣,等.基于隐性SVM和混合高斯模型的目标检测算法[J].计算机工程,2016,42(6):287-292.

[5] 王道明,鲁昌华,蒋薇薇,等.基于粒子群算法的决策树SVM多分类方法研究[J].电子测量与仪器学报,2015(4):611-615.

[6] Moradi M H,Abedini M.A combination of genetic algorithm and particle swarm optimization for optimal DG location and sizing in distribution systems[J]. International Journal of Electrical Power & Energy Systems, 2012, 34(1):66-74.

[7] Fan H.A modification to particle swarm optimization algorithm[J].Engineering Computations,2013,19(8):970-989.

[8] 敖永才,师奕兵,张伟,等.自适应惯性权重的改进粒子群算法[J].电子科技大学学报,2014,43(6):874-880.

[9] 夏学文,王博建,金畅,等.一种自适应多种群的PSO算法[J].系统仿真学报,2016,28(12):2887-2895.

[10] 周利军,彭卫,邹芳,等.自适应变异粒子群算法[J].计算机工程与应用,2016,52(7):50-55.

[11] 韩兆洲,林少萍,郑博儒.多类支持向量机分类技术及实证[J].统计与决策,2015(19):10-13.

[12] 杨静,王瑞波,李济洪.一种均衡的RHS交叉验证[J].南京大学学报:自然科学版,2015(4):842-849.

[13] 吴润秀,孙辉,朱德刚,等.具有高斯扰动的最优粒子引导粒子群优化算法[J].小型微型计算机系统,2016,37(1):146-151.

[14] 黄明,张春蕾,武耀旭,等.一种多样性反馈高斯粒子群算法[J].大连交通大学学报, 2015,36(1):105-108.

[15] 魏芳芳,段青玲,肖晓琰,等.基于支持向量机的中文农业文本分类技术研究[J].农业机械学报,2015(s1):174-179.