基于密度和粒子群的SVM 算法研究∗

唐 瀛 闫仁武

（江苏科技大学计算机学院 镇江 212028）

1 引言

在1995 年时Vapnik 和Cortes 领导的AT&Bell实验室［1］正式提出了支持向量机（SVM）算法［2］。支持向量机在对数据进行分类时通过结构风险最小化原则寻找超平面从而进行分类，并且它能够将低维的不可分特征向量通过使用核函数映射，从而转换到高维特征空间，进而进行分类，这样在实际的机器学习问题中能够得到应用［3］。由于SVM 算法在训练样本的训练阶段进行超平面划分过程中会出现设置不准确的情况，本文提出使用基于密度的裁剪方法对训练样本进行裁剪，去除样本集的噪声和冗余样本，优化分类超平面的划分。因为惩罚因子C 和核函数g对于分类性能影响较大［4］，提出基于粒子群算法对SVM算法进行改进，通过粒子群算法优化惩罚因子C和核参数g，提高SVM分类准确率。

2 支持向量机（SVM）算法

支持向量机实质是一种分类算法，能够解决在样本集中两类样本分类问题，通过寻找一个最优超平面使得对两类样本的分割间隔达到最大，从而将样本集按照规则进行分类。

1）线性可分支持向量机原理

假设训练样本集为（xi，yi）（i=1，2…,m），其中xi∊Rn为输入变量，yi是对应的预期值，m 是样本的数量，在线性回归［5～6］的情况下，利用SVM构造一个目标函数，可获得最优分割超平面的函数为

式中：ω∊Rn为权值矢量，b ∊R 为偏差量，对于需要分类的两类样本来说，它们之间的距离为此时为了使分类效果最优，则需要让两类样本距离最大，所以相当于求||ω||的最小值。那么求权值ω和偏差b就可以通过下面的求解最优问题来解决：

引入拉格朗日［7］公式，然后再根据转换后的问题求解，从而获取最优解：

在式（4）中取得最优解后，于是将a的最优解设为a*，把最优解a*代入下列公式，并求出关于分类面的分类器阈值b*以及全系数向量ω*：

对于取得的值b*和ω*，将其代入下列公式当中，形成分类决策的超平面形式化方程：

再通过将样本转化的数据代入最后的方程中进行分类，得到分类结果。

2）线性不可分支持向量机原理

在目前日常生活中我们遇到的问题很多都是线性不可分问题，在线性不可分的情况下，使用SVM 算法进行分类时会通过引入一个松弛变量δi，然后在松弛变量前加入一个惩罚系数C，通过将惩罚系数C 的变化来控制分类错误的数量，然后通过下面的求解最优问题来解决：

式中：C 为惩罚因子，δi为松弛变量，当C 取值大时表示对分类的惩罚力度大。使用拉格朗日函数和核函数后可获得线性回归函数：

式中：αi为拉格朗日参数，K(xi,yi)为核函数。

本文采用高斯核函数来映射数据并求取最优分类面，高斯核函数的计算公式为

3 改进支持向量机算法

3.1 基于密度的训练样本裁剪方法算法原理

为了衡量样本分类密度，实现对于训练样本的裁剪，接下来给出关于裁剪算法的相关定义：

定义1设样本集中样本X 与样本Y 之间的距离为Dis（tX，Y），定义X的ε邻域为

定义2设定样本集M=C1∪C2∪C3∪C4∪…Cm（i=1，2…,m）代表一个样本类别，且Ci∩Cj=∅（i，j=1，2…,m），对于任意的X∊Ci，若X 的ε邻域内任何样本都属于Ci，则X 在类内区域，否则，X 在类边界区域。

定义3给定样本阈值Minpts（Minpts>0，Minpts∊Z），那么对于任意的样本X，若X 的ε邻域中存在的样本数|Nε(X)|>Minpts时，则X 处于高密度区域，若X 的ε邻域中存在的样本数|Nε(X)|=Minpts时，则X 处于均匀密度区域，若X 的ε邻域中存在的样本数|Nε(X)|

定义4给定邻域半径ε和样本阈值Minpts（Minpts>0，Minpts∊Z）。对于任意的样本X 和X 邻域内的样本Y，若|Nε(Y)|>Minpts，则Y处于高密度区域，且Y 与X 高密度可达；此时把所有高密度可达的样本Y 的样本集定义为RH（X），同理把所有均匀密度可达的样本Y 的样本集定义为RA（X），把所有低密度可达的样本Y的样本集定义为RL（X）。

基于密度的训练样本裁剪方法［8］原理如下：

1）类边界区域样本裁剪如图1所示：

图1 类边界样本裁剪示意图

设定Minpts=4，在图中三个圆形分别是对于样本A、B、C邻域ε的区域，图中分为两种类别的样本1 和样本2，此时样本B 处于类边界区域，且样本B的ε邻域内样本数量超过Minpts，是一个高密度区域样本，所以会对样本B 进行裁剪，根据上述定义，样本A 则会被裁减掉，且位于样本B 的ε邻域中的其他三个类别样本为1 的样本，而样本C 的ε邻域中的样本数量没有超过Minpts，则不会对其邻域进行裁剪，在裁剪后，样本B 会处于均匀密度区域，同时能够降低类别样本1对测试样本X（未知类别）的干扰，提高准确率。

2）在对于类内区域样本进行裁剪时，则会裁减掉更多的冗余样本，此时需要设置一个最少样本阈值lowpts（lowpts>0，lowpts ∊Z），且lowpts ≤Minpts，如果类内样本X的邻域内样本数量|Nε(X)|>lowpts，将与X 高密度可达的样本进行裁剪，直到|Nε(X)|=lowpts 时停止；当|Nε(X)|≤lowpts时，则将X 的ε邻域内所有训练样本进行保留。

基于密度的训练样本裁剪方法具体算法如下：

第一步我们首先需要把样本集X 中处于类内区域且邻域半径ε中样本数量少于Minpts 的低密度区域样本添加到我们新建的样本集W中，然后对样本集X 进行筛选，若样本集中X［i］的邻域半径ε内样本数量小于Minpts，则保留。

通过这样处理之后就能得到低密度区域的样本集W和高密度样本集WH，接下来进行第二步：

在第二步中我们首先一次遍历样本X，对每个样本X［i］获取它的邻域半径内样本集，此样本集会包含|Nε(X)|>lowpts 的样本，然后将这个样本集与低密度样本集Z 取差值，并添加到样本集Y 中，因为每次遍历都会去除样本集Y 中低密度样本，只有高密度样本，而且排除了|Nε(X)|lowpts 时，将与X 高密度可达的样本进行裁剪，直到|Nε(X)|=lowpts 时停止；当|Nε(X)|≤lowpts时，则将X 的ε邻域内所有训练样本进行保留。当RH 中的所有样本|Nε(X)|≤lowpts时，进行判断结束循环，返回裁减之后的样本集A。

3.2 基于密度裁剪算法的参数确定

在实际密度裁剪算法中的参数邻域半径ε、Minpts 和lowpts 的具体值会直接影响到裁剪效果，并且这几种参数值当中具有某种关联，而在这三种值当中，lowpts的值由Minpts间接决定，于是给出以下关于密度裁剪算法参数确定的定义：

定义5：给定训练样本集M，把训练样本集M中的样本距离训练样本集M 中的样本X 第k 近的样本，与样本X 之间的距离设为Distk（X），于是当训练样本集M 的最少样本数为Minpts时，样本集M 的平均邻域半径为

通过以上定义，在对参数邻域半径ε、Minpts和lowpts 的进行多次设定实验便能得到测试结果。从而可以得到参数设定的经验值［9］，当Minpts的值设置为训练样本的平均样本数的5%～8%，lowpts 的值设置为Minpts 的0.7～0.8 倍，此时的裁剪效果最好。

3.3 粒子群算法概述

粒子群算法［10-11］实质是基于模拟鸟群觅食过程而提出的一种寻优算法。研究人员Eberhart 和Kennedy 发现鸟群在觅食过程中如果发现草坪上某处有面包［12］，然后整个鸟群通过信息共享调整位置移动到面包地吃到面包。于是模拟鸟群的移动过程提出了粒子群算法，通过距离速度计算和个体鸟与群体鸟的信息共享［13］，然后找到调整整个鸟群所有鸟的位置的最优解，不断更新整个鸟群的位置，最终达到寻优目标［14］。粒子群算法选择精度和速度优良，在数据挖掘方向使用较多，对于算法的参数寻优方向也有大量使用。

假设寻优问题［15］的空间维度为N，寻优问题的种群大小为M，组成的初始种群为Xi=｛X1，X2，…，Xm｝，则第i个粒子在某一时刻的位置和速度分别为Xi（t）=［Xi1（t），Xi2（t），…，Xin（t）］和Vi（t）=［Vi1（t），Vi2（t），…。Vin（t）］，粒子的最优位置为pbesti（t）=［Pi1（t），Pi2（t），…。Pin（t）］，粒子的最优位置为gbesti（t）=［Gi1（t），Gi2（t），…，Gin（t）］。在迭代过程中，粒子的个体最优位置为

种群最优位置为

更新公式为

式中：i∊［1，m］，i∊［1，n］，w为惯性权重［16］，c1和c2为加速因子，r1和r2取区间［0，1］内的随机数，t 为迭代数量。

粒子群算法具体流程步骤如下：

1）对数据集进行初始化，设置数据集中样本的位置和速度，对种群评估初始最优位置gbest，给每个样本设置个体最优位置pbest作为初始值。

2）对数据集中的样本进行适应度函数计算得到适应度函数值。

3）评估数据集中的样本，更新粒子个体的最优位置pbest。

4）评估种群的最优位置gbest。

5）更新样本的速度和位置，将样本位置移动至最优位置pbest

6）进行判定，如果失败，则对所有样本重新进行2）到5）的操作，如果成功，则输出种群最优位置并结束循环。

3.4 基于密度裁剪和粒子群算法的SVM 算法实现

为了考察上述的两种算法在SVM 算法中的性能，通过设定一种算法来实现对SVM 算法的改进，对原始训练样本集使用基于密度的裁剪方法，然后通过对裁减之后的新训练样本集进行训练建模并测试实验。本文对于SVM 算法的粒子群参数寻优方法是将粒子群的位置变量设置为二维变量，即X1和X2，其中X1的取值范围为（Cmin，Cmax)，X1的取值范围为（gmin，gmax)，通过对X1和X2进行计算来对SVM 算法参数C 和g 进行寻优。改进算法具体步骤如下：

1）由于需要处理的数据，首先设定原始样本集的数据为X=（xij）nxp，对原始训练样本集进行数据预处理，将数据各维归一到［0，1］的范围中，得到处理之后的数据集，便于剪裁算法进行计算。归一化公式如式（18）。

2）通过上述裁剪算法对处理后的数据进行裁剪，裁减掉冗余样本，生成新训练样本集。

3）对新训练样本集进行上述粒子群算法进行SVM 参数寻优，运行libsvm 工具箱中的svmtrain 函数，计算适应度值，建立优化后训练模型。

4）通过svmpredict（）函数对测试数据进行测试，得到准确率。

上述基于密度裁剪和粒子群算法的SVM 算法的具体算法流程如图2所示。

图2 具体算法流程图

4 算法测试和实验结果分析

本文实验是对UCI 标准数据库中样本集（Wdbc，Pima，Spambase，Shuttle）进行测试，验证本文提出算法的有效性，而且UCI标准数据库中的各类数据存在差异，在数据维度和数据分布情况上也皆不相同，所以可以比较客观地验证本文算法的可靠性。本文将在原始数据集中取训练样本集和测试样本集比值为4∶1 进行测试分析，具体情况如表1所示。

表1 原始实验数据集

采用上述提出的基于密度的裁剪方法进行裁减，得到裁剪率等于裁减掉的样本数量与训练样本数量的比值，情况如表2所示。

表2 裁剪后实验数据集

可以看到数据集的训练样本裁剪率在0.1～0.35 之间，在数据集维数较低时，裁剪的样本数更高，但是在数据集维数较高时，裁剪的样本数较低。然后对裁剪后的新训练样本使用libsvm 工具箱进行测试实验，得到使用基于密度裁剪和粒子群算法前后的识别准确率结果如表3和图3所示。

表3 使用算法前后准确率

图3 使用算法前后准确率比较图

对照使用基于密度裁剪和粒子群算法前后的数据，可以看出当使用算法后，所有测试数据的预测识别准确率均得到了提升，可以看到在Spambase数据集提升了11.5%的准确率，而在Wdbc 数据集中也有1%的准确率提升，可以说明使用基于裁剪和粒子群算法可以减少训练样本的部分冗余样本，提高分类超平面划分的准确程度，并提升SVM 算法的识别准确率。

5 结语

本文介绍了SVM 算法，并对SVM 算法提出了改进方向，为了提升算法的准确率，分别使用了密度裁剪方法和粒子群寻优方法对SVM 算法进行研究和优化。对密度裁剪方法在实行过程中的算法进行了分析，分步骤的对实行过程算法进行了实现，讨论了各个步骤算法实现的含义，通过对数据样本的测试，较为有效地减少了训练样本的冗余样本。对惩罚参数C 和核参数g 地粒子群算法进行了研究和使用，探讨研究了实现原理和过程。通过使用UCI 数据库的数据集对改进后算法进行实验论证，通过结果表明确实有效地提升了SVM 算法的性能。