基于PSO与GA的SVM特征选择与参数优化算法

温海标

摘要摘要：支持向量机（SVM）在处理大样本特征维数较多的数据集时，算法消耗时间长而且容易陷入局部最优解，选择不合适的SVM算法参数会影响SVM模型分类性能。为了提高SVM性能，提出了基于粒子群算法（PSO）和遗传算法（GA）相结合的SVM特征选择与参数同步优化算法PGS。在UCI标准数据集上的实验表明，PGS算法能有效地找出合适的特征子集及SVM算法参数，提高收敛速度并能在较小的特征子集获得较高的分类准确率。

关键词关键词：粒子群算法；遗传算法；支持向量机；特征选择；参数优化

DOIDOI：10.11907/rjdk.171267

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2017）005002103

0引言

分类问题主要是分类器模型的选择、分类样本的特征选择以及分类器参数优化等问题，是模式识别领域的基础问题。Vapnik等[1]在1995年提出一种新型有监督的统计学习方法——支持向量机（Support Vector Machines，SVM），在文本分类、图像分类、人脸识别等诸多领域得到了成功应用，成为机器学习领域的研究热点。研究表明，SVM分类器的参数例如核函数参数、惩罚参数C与SVM 的分类性能有很大关系[2]，选择合适的参数能显著提高SVM的分类精度。特征选择是根据某种评估标准从样本的原始特征中选择部分特征作为特征子集[3]。大数据时代下，样本冗余特征不断出现，如何从大样本特征中去除冗余、选取有利特征是机器学习的重要研究课题。样本特征选择合理，不但可以消除冗余，而且可以降低算法时间复杂度，加快算法运行速度，提高分类器的准确率。

粒子群优化算法（Particle Swarm Optimization，PSO）是根据鸟群扑食行为产生的仿生设计算法，属于一种简单有效的全局优化算法，已在许多领域得到应用，如用于参数选择[4]。遗传算法（Genetic Algorithm，GA）是根据遗传变异论和“适者生存”原理启发设计的算法，经过一系列的选择、交叉、变异操作，使个体不断进化，越来越适应环境，即越来越接近问题的最优解。GA算法不依賴于求解问题的具体领域，有较强的鲁棒性，主要用于解决优化问题。

一般通过大量实验获得较优的参数和特征子集，但这种方法要消耗大量的时间，而且获得的参数和特征子集不一定好。本文提出一种特征选择和参数同步优化算法，该算法使用了PSO、GA 和SVM算法，简称为PGS算法。

1相关概念

1.1支持向量机

支持向量机（SVM）是一种机器学习过程，基本原理是将样本数据映射到一个高维空间，并在高维空间中寻找一个最大间隔超平面，将不同类别的样本数据隔离，使间隔最大，从而正确分类样本数据。

e是元素全为1的向量，ξ为误差，C > 0为惩罚参数，该参数的作用是调整误差。式（3）最小化问题取决于参数C和核函数的参数选择。选择合适的参数可以提升SVM分类性能。

1.2PSO算法

Kennedy等[5]通过观察鸟群捕食行为得到启发，于1995 年提出粒子群优化算法（PSO）。PSO属于启发式算法，与遗传算法不同，它不是根据个体自然进化规律设计，而是以生物群体的社会行为启发设计。鸟群的个体与个体、个体与群体间相互作用、相互影响，通过鸟群个体之间的协作和信息共享为群体进化提供帮助。PSO中粒子追随当前最优的粒子在整个解空间进行搜索，通过协作和信息共享机制寻找最优解。算法具有调节参数少、收敛速度快、对特征变化不敏感等优点。PSO 算法将每个个体看作是在n 维搜索空间中具有一定飞行速度的微粒，该飞行速度可由微粒的飞行经验和所有微粒飞行经验进行动态调整。算法描述如下：

式（5）中，w是非负常数，称为惯性因子；c1，c2称为学习因子，一般取非负常数，分别用来调节粒子向个体最优粒子和群体最优粒子方向飞行的步长。合适的学习因子参数值可加快算法的收敛速度且不易陷入局部最优，通常取[0，2]之间的值；参数r1和r2是介于[0，1]之间的随机数。

1.3GA算法

HollandJ[6]教授于1975年提出遗传算法，算法基于生物学的进化论和遗传变异理论，自然界的物种不断进化以适应自然环境，不断迭代更新个体基因。每一次迭代根据设定的适应度函数计算群体所有个体的适应值，然后根据适应值计算被选中的概率，根据概率选择一部分个体。被选中的个体一部分直接进入下一代，一部分经过交叉变异操作产生下一代。通过种群初始化、选择、交叉、变异操作，产生新的一群更适应环境的个体，使群体进化到待求解问题空间中越来越好的区域，最后得到最适应环境的个体，也就是问题的最优解。

2PGS算法

2.1粒子设计

当缺乏先验知识时，SVM分类器选择高斯核函数通常比选择其它核函数有更好的分类结果[7]。因此，本文采用RBF径向基函数作为核函数。RBF核函数为：

ψ（x，xi）=exp-||x-xi||22σ2（7）

式（7）中，σ为径向基函数的宽度，为待定优化参数。另外一个待优化参数是式（2）中的C。因此，粒子包括两个部分，即参数C和参数σ。

2.2染色体构成

遗传算法中每个个体的染色体采用二进制编码方式编码，每一个二进制位对应特征集中的一个特征，使用特征长度为N的0、1二进制字符串（x1，x2，...，xN）表示一个个体。这个个体对应N维特征向量。xi=1代表第i项对应的特征选入特征子集中，反之xi=0代表第i项对应的特征排除于特征子集之外。

2.3适应度函数

算法的目标是提高SVM的分类准确率，尽可能降低所选特征数目。PGS算法是PSO算法和GA算法的结合，把PSO中的个体和GA中的个体组合，称之为PGS算法个体。若PGS算法个体能使SVM分类器分类精度提高，选定的特征数目减少，则算法个体的适应值就高。评价PGS算法个体的适应度函数定义为：

fitness=A1+Nm（8）

其中A為分类器的分类精度，N的选定的特征数目，m为平衡特征数目和分类精度权重的参数，本文m的取值范围是：0≤m≤1。

2.4PGS算法描述

PGS算法步骤如下：

（1）初始化PSO的粒子群和GA中的种群。本文随机产生一组初始值，该初始值是PSO的速度和位置及种群个体的二进制串值。在空间Rn中随机产生n个粒子x1，x2，...，xN，组成初始种群X（t）；随机产生各粒子的初始速度v1，v2，...，vN，组成速度矩阵V（t）；每个粒子的个体最优值f（Pbest，i）的初始值为xi的初始值。

（2）根据粒子所包含的参数σ、参数C 和种群个体特征子集，调用LIBSVM算法进行学习和训练，测试并记录分类精度。根据式（8）计算粒子适应度。

（3）对每个PGS组合个体进行适应度函数值f（xi）和自身的最优值f（Pbest，i）比较，如果f（xi）>f（Pbest，i），则更新组合个体的最优值，将当代适应值作为自身的最优值。

（4）将每个组合个体最好的适应值f（xi）与所有组合个体的最优适应值f（Gbest）进行比较，如果f（xi）>f（Gbest），更新全局最优，即用该组合个体的最好适应值取代原全局最优适应值。

（5）根据式（5）和式（6），更新粒子的速度和位置，速度调整规则如下：

当vi>vmax时，vi=vmax；当vi<-vmax时，vi=-vmax。

（6）每个基因个体根据适应值，计算各自被选中的概率P，P的计算公式如下：

P（i）=f（i）∑Nj=1f（j）（9）

根据每个个体的概率P，从群体中选择一部分个体。

（7）以一定的概率c作交叉运算，每两个基因个体执行单点交叉。

（8）每个基因个体发生变异的概率为m，若某个个体发生变异，则将它包含的二进制串中随机选取一位取反。

（9）检查是否满足设定的终止条件。如果满足，则算法结束，返回目前最优的特征子集、参数C、参数σ及分类精度；否则T=T+1，转至步骤（2）。设定终止条件为算法达到最大迭代次数T或组合个体适应值大于等于给定值。

3实验

为了验证基于PSO与GA的SVM特征选择与参数优化算法的有效性，选取UCI[8]机器学习知识库中的部分数据集进行实验，见表1。

实验结果的评价标准采用分类准确率，准确率值越大分类器性能越好。公式如下：

A=nN（10）

式（10）中N为测试样本的样本总数，n为正确分类的样本总数。

算法采用Matlab编程实现。Matlab软件版本为2014a，系统平台为AMD Athlon（tm）Ⅱ X2 B24 processor 3.0 GHz，Windows 7旗舰版，4GB内存。实验采用k 折交叉验证法进行评价。数据集随机分成k 个子集，第一次实验将第一个子集作为测试集，其余的子集作为训练集。本文实验k取10，表1中的每个数据集分别用PGS算法进行10次实验，每次取一个子集作为测试集，其余9个子集作为训练集，取10次实验所得的准确率均值加上标准差作为该数据集的分类结果，如图1所示。

从表2中可以看出，PGS算法的分类准确率比传统SVM算法有较大的提高。在每个数据集上，前者的分类准确率都高于后者，运行效率优于SVM。从标准差的值可以看出PGS算法比SVM算法有更好的稳定性，从图1可更直观看出PGS的优越性能，也证实了PGS算法比SVM具有更好的分类性能。

4结语

本文提出了一种PSO算法与GA算法组合同步优化SVM算法参数和样本特征的选择算法，解决了支持向量机用于学习时，选择合适算法参数和样本特征的问题。理论分析和实验表明，本文算法可有效找出合适的特征子集和SVM参数，取得了较好的分类效果。

参考文献参考文献：

[1]CORTES C，VAPNIK V.Supportvector networks[J].Machine Learning，1995，20（3）：273297.

[2]ZHANG L，WANG L，LIN W.Semisupervised biased maximum margin analysis for interactive image retrieval[J].IEEE Transactions on Image Processing，2012，21（4）：22942308.

[3]孟军，尉双云.基于近邻传播聚类的集成特征选择方法[J].计算机科学，2015，42（3）：241244.

[4]徐海龙，王晓丹，廖勇，等.一种基于PSO的RBFSVM模型优化新方法[J].控制与决策，2010，25（3）：367370.

[5]KENNEDY J，EBERHART R.Particle swarm optimization[C].IEEE International Conference on Neural Networks，1995：19421948.

[6]GOLDBERG D E.Genetic algorithm in search，optimization，and machine learning[J].Addisonwesley Pub.co，1989（7）：21042116.

[7]ZHANG Y，DAI M，JU Z.Preliminary discussion regarding SVM kernel function selection in the twofold rock slope prediction model[J].Journal of Computing in Civil Engineering，2015（6）：155158.

[8]UCI repository of machine learning datasets[EB/OL].http：//archive.ics.uci.edu/m.

责任编辑（责任编辑：杜能钢）