采用粒子群优化的SVM算法在数据分类中的应用

邹心遥， 陈敬伟， 姚若河

(1. 广东农工商职业技术学院 机电系， 广东 广州 510507；

2. 华南理工大学 电子与信息学院， 广东 广州 510641)



采用粒子群优化的SVM算法在数据分类中的应用

邹心遥1， 陈敬伟1， 姚若河2

(1. 广东农工商职业技术学院 机电系， 广东 广州 510507；

2. 华南理工大学 电子与信息学院， 广东 广州 510641)

摘要：针对分类数据集合线性不可分的问题，改进了支持向量机(SVM)的分类方法，构建新的分类决策函数和高斯核函数.在支持向量机关键参数的优化环节，采用粒子群算法对惩罚参数和高斯参数进行优化，设计便于操作的优化流程，并针对Iris数据集合展开实验研究.结果表明：相比于基于遗传算法优化的SVM方法，所提出的方法执行速度快、分类准确率高.

关键词：数据分类； 支持向量机； 粒子群优化； Iris数据集； 惩罚参数； 高斯参数

数据分类作为数据库管理系统的核心技术，已经成为国内外学者广泛关注的焦点研究[1].通过数据分类，可以将数据库中的各项数据分门别类，分类后的数据将具有明显的内在联系或意义近似性，更利于数据管理与维护,尤其是缩小数据查找的范围[2].已经成功用于数据分类的方法很多，如邻近算法、贝叶斯算法、决策树算法、神经网络算法等[3-5].Agarwal等[6]在Fisher核函数的基础上进行改进，形成一种含有概率特征的离散化形式，对数字数据挖掘具有较强的针对性.Durduran[7]构建一个新的核函数空间，并设计在全空间上进行搜索的分类策略.李婷等[8]以车载激光点云数据为分类对象，借助混合核函数的理念，对传统的高斯核函数进行修正，建立一种新的支持向量机(SVM)分类方法.陆慧娟等[9]面向基因表达数据，针对局部分类采用径向基函数(RBF)核函数，针对全局分类采用线性核函数.支持向量机方法的关键在于如何对关键参数优化，如果能用智能算法实现这些参数的优化,并获得最优结果，就可以获得更高性能的SVM分类结果[10].本文选择支持向量机的方法作为数据分类的研究对象，并在参数优化环节中选取粒子群(PSO)算法，构建出一种新的数据分类方法.

1支持向量机分类方法

在线性可分的情况下，支持向量机分类方法通过在高维空间构造最优分类超平面，以最低的结构风险进行分类，具有学习能力强、训练速度快、分类精度高等诸多优点.然而，很多分类问题中的数据集合并不是线性可分的.此时，数据分类过程中的优化问题需要的数学模型定义为

(1)

式(1)中:(pi，qi)为第i个训练样本，i=1，2，…n；v∈Rd为SVM分类中超平面的法向向量；z∈R为阈值；ρ为惩罚参数，其值越大表示对不正确分类结果的惩罚程度越大，但过大的ρ值会降低SVM方

法的泛化能力，所以ρ的选取要在分类精度和泛化能力之间寻求平衡.

式(1)是一个典型的二次规划问题，对此问题的求解可以采用拉格朗日乘子算法，即

(2)

式(2)中:θi，ϑi都是不小于0的拉格朗日乘子.

针对式(2)，分别对变量v，z，ηi求偏导，并让3个偏导值为0，将此时求得的结果代入式(1)，可得

(3)

对于式(3)，能够满足θi≤ρ的情况称为支持向量.据此，最终可以得到用于分类的决策函数为

(4)

要判断任意一个样本数据的类别情况，只要将其代入式(4)进行计算即可.

核函数是构造SVM分类方法的另一个关键问题.因为考察的是一般分类情况，所以选取高斯核函数作为文中SVM分类方法的核函数，其简化形式为

(5)

式(5)中:参数κ=1/σ2，σ称为高斯核函数的高斯系数.

2SVM分类中的粒子群参数优化

要提升SVM分类方法的精度和效率，对关键参数的设置和优化至关重要[11].因此，采用粒子群算法对2个关键参数进行优化调整，以达到最佳的分类效果[12].粒子群算法在执行过程上类似于遗传算法，也需要对粒子群进行初始化，并根据适应度函数进行优化操作.相比于遗传算法，粒子群算法的实现更为简单，一方面,粒子群算法无需执行交叉和变异操作，另一方面,粒子群算法需要调整的参数没有遗传算法多.基于这些情况，粒子群算法可以以更快的速度达到收敛、获得最优解[13-15].

粒子群算法的基本实现过程如下.

在一个维度为m的待查找空间上，假设粒子群的初始状态为S=(s1，s2，…，sn)，si代表优化问题的第i个解，它在待查找空间上的多维表示为si=(si，1，si，2，…，si，m).若各个粒子的速度为Vi=(v1，v2，…，vm)T，群内的粒子个体位置最优解为Li=(li，1，li，2，…，li，m)T，能使种群整体达到最优状态的解为Lg=(lg，1，lg，2，…，lg，m)T，找到当前状态下的Li和Lg以后，需要对群内的粒子进行位置更新和速度更新，其处理过程为

(6)

(7)

式(6)，(7)中:G为粒子飞行过程中的惯性权重；a1，a2为加速度参数；r1，r2为随机数.

对于文中SVM分类方法，要优化的参数主要有惩罚参数ρ和κ=1/σ2.根据粒子群优化方法的执行过程，为这2个参数的优化设置了6个优化步骤.

步骤1用(σ，κ)构建每一个粒子的初始状态，并完成种群内全部n个粒子的位置初始化和速度初始化，同时设定2个加速度参数a1，a2的数值为2，以及最大迭代次数T.

步骤2根据当前的各个粒子状态，计算适应度，并以SVM分类正确的比率作为评价各个粒子适应度高低的依据.

步骤3比较每一个粒子的适应度和其出现过的最优状态，选出Li并更新最优状态，以便于下一次迭代过程的比较.

步骤4比较各个粒子的适应度和整个种群出现过的最优状态，选出Lg并更新最优状态，以便于下一次迭代过程的比较.

步骤5根据式(6)，(7)更新粒子的位置和速度.

步骤6不断重复从步骤2到步骤5的工作，直到迭代过程达到最大迭代次数T，此时的Lg下各个粒子的状态，就是最终优化的结果.

3实验结果与分析

在分类方法的验证性实验中，选取数据分类领域中常用的标准测试数据集合Iris.该数据集合是根据鸢尾花这种植物的外形特征构建数据集合，包含3个种类的鸢尾花，分别是山鸢尾花(Irissetosa)、杂色鸢尾花(Irisversicolour)、维吉尼亚鸢尾花(Irisvirginica).Iris数据集合从鸢尾花的花萼长度特征、花萼宽度特征、花瓣长度特征和花瓣宽度特征等4个方面对上述3种鸢尾花进行特征区分.整个数据集合内共含有50个样本数据，有标准的正确分类作为分类方法分类结果测试的判断依据.

在分类性能测试过程中，采用了常见的交叉验证手段.即将Iris数据集合随机分作J个子集合，先用1到(J-1)和子集对分类方法进行训练，确定分类决策模型后，对第J个子集进行分类以考察分类模型的正确性；然后，用第2到J个子集对分类方法进行训练，确定分类决策模型后，对第1个子集进行分类以考察分类模型的正确性；以此类推，遍历所有可能的交叉验证.

在分类方法的参数设置上，设定初始种群的规模是20个粒子，设定加速度参数a1，a2为2，粒子飞行过程中的惯性权重G为1，设定最大迭代次数T为100.对于交叉子集J的设定则分别设置为3，5，7，9这4种情况.同时，选择遗传算法优化的SVM分类方法(简称SVM-GA)，作为提出的粒子群算法优化的SVM分类方法(简称SVM-PSO)的对比方法.两种方法的分类准确率和执行时间的对比结果，如表1所示.表1中：η为分类准确率；t为执行时间.

由表1可知：所提出的基于粒子群优化的SVM分类方法的分类准确率明显优于基于遗传算法的SVM分类方法.随着交叉验证的分类子集数目增多，文中方法的分类准确率一直保持在90%以上.由表1还可知：所提出的基于粒子群优化的SVM分类方法的执行时间明显低于基于遗传算法的SVM分类方法；随着交叉验证的分类子集数目增多，基于遗传算法的SVM分类方法的执行时间增加较为明显，而文中方法的执行时间增加幅度则不大.

表1　不同分类方法准确率和执行时间对比数据

4结束语

在考察数据集合线性不可分的情况下，设计SVM方法的分类决策函数和高斯核函数.为了进一步提升SVM方法的分类性能，采用粒子群算法对SVM方法的2个重要参数进行优化，包括对惩罚参数的优化和高斯系数的优化.以Iris为分类实验的测试数据集，并选择基于遗传算法优化的SVM方法作为比较方法.数据分类的验证实验表明，所提出的基于粒子群算法优化的SVM分类方法，具有更高的分类准确性和更快的分类速度.

参考文献：

[1]PALACIOS A，MARTINEZ A，SANCHEZ L.Sequential pattern mining applied to aeroengine condition monitoring with uncertain health data[J].Engineering Applications of Artifical Intelligence，2015(44):10-24.

[2]范士俊，张爱武，胡少兴，等.基于随机森林的机载激光全波形点云数据分类方法[J].中国激光，2013，40(9):1-7.

[3]刘红岩，陈剑，陈国青.数据挖掘中的数据分类算法综述[J].清华大学学报(自然科学版)，2002，42(6):727-730.

[4]杨帆，林琛，周奇凤，等.基于随机森林的潜在k邻近算法及其在基因表达数据分类中的应用[J].系统工程理论与实践，2012，32(4):815-825.

[5]TABKHI S，NAJAFI A，RANJBAR R.Gene selection for microarray data classification using a novel ant colony optimization[J].Neurocomputing，2015,168:1024-1036.

[6]AGARWAL S K，SHAH S，KUMAR R.Classification of mental tasks from EEG data using backtracking search optimization based neural classifier[J].Neurocomputing，2015，166:397-403.

[7]DURDURAN S S.Automatic classification of high resolution land cover using a new data weighting procedure: The combination of K-means clustering algorithm and central tendency measures (KMC-CTM)[J].Applied Soft Computing，2015，35:136-150.

[8]李婷，詹庆明，喻亮.基于地物特征提取的车载激光点云数据分类方法[J].国土资源遥感，2012，92(1):17-21.

[9]陆慧娟，安春霖，马小平，等.基于输出不一致测度的极限学习机集成的基因表达数据分类[J].计算机学报，2013，36(2):341-348.

[10]ELYASIGOMARI V，MIRJAFARI M S，SCREEN H R C.Cancer classification using a novel gene selection approach by means of shuffling based on data clustering with optimization[J].Applied Soft Computing，2015，35:43-51.

[11]喻小光，陈维斌，陈荣鑫.一种数据规约的近似挖掘方法的实现[J].华侨大学学报(自然科学版)，2008，29(3):370-374.

[12]王江海，武林仙，吴扬扬.基于刻画得数据空间数据源管理子系统[J].华侨大学学报(自然科学版)，2012，33(5):509-513.

[13]彭京,唐常杰,元昌安,等.一种基于概念相似度的数据分类方法[J].软件学报，2007,18(2):311-322.

[14]杨帆,林琛,周绮凤.基于随机森林的潜在k近邻算法及其在基因表达数据分类中的应用[J].系统工程理论与实践,2012,32(4):815-826.

[15]陆慧娟,安春霖,马小平，等.基于输出不一致测度的极限学习机集成的基因表达数据分类[J].计算机学报,2013,36(2):341-348.

(责任编辑： 钱筠 英文审校： 吴逢铁)

Application of SVM Algorithm Based on Particle Swarm Optimization in Data Classification

ZOU Xinyao1， CHEN Jingwei1， YAO Ruohe2

(1. Department of Mechanical and Electronic， Guangdong AIB Polytechnic College， Guangzhou 510507, China；2. School of Electronic and Information Engineering， South China University of Technology， Guangzhou 510641, China)

Abstract：According to the problem that the classification data set can not be divided, the classification method of support vector machine (SVM) is improved, and the new classification decision function and Gauss kernel function are constructed. Using particle swarm algorithm to optimize the penalty parameters and Gauss parameters, the optimization process is easy to operate. To experimental study the Iris data set, the results show that compared with the SVM method based on genetic algorithm, the proposed method performs fast and has high classification accuracy.

Keywords：data classification； support vector machine； particle swarm optimization； Iris data set; penalty parameter; Gauss parameter

中图分类号：TP 181

文献标志码：A

基金项目：国家自然科学基金资助项目(61274085)； 广东省大学生科技创新培育专项(PDJH2015A0718)

通信作者：邹心遥(1978-)，女，副教授，博士，主要从事新型光电器件、物联网技术的研究.E-mail:madelinexy@163.com.

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0171

文章编号：1000-5013(2016)02-0171-04