基于不等距超平面距离的模糊支持向量机①

李村合,姜 宇,李 帅

(中国石油大学 计算机科学与技术学院,青岛 266580)

支持向量机是常见的一种基于统计学习理论的分类算法,核心是结构风险最小化和VC 维理论.其主旨是在高维空间中寻找一个最优分类面,将样本正确分类且保证分类间隔最大化[1].随着人工智能时代的到来,支持向量机成功应用至许多方面,尤其是在分类问题的解决上已经成为了主流方法,如网页分类[2],手写识别[3]等.

但在实际生活及现实应用中,许多常见的数据往往具有极大的不平衡性,如缺陷数据[4],文本数据[5]、疾病数据[6]等.当利用支持向量机处理不平衡数据时,往往会出现分类结果具有一定倾向性的现象,即分类器对多数类的分类准确度较高,而对少数类的分类准确度较低.另外超平面的位置对支持向量机的性能有很大的影响,并且超平面的确定极易受样本中噪点的影响[7].所以为了解决上述问题,提高支持向量机的分类性能成为众多学者亟待解决的问题[8].

在支持向量机的决策过程中,决策面位置的选取取决于样本空间的分布.由于不平衡数据集的类不平衡性较大,许多样本点对决策面的确定贡献度不大,容易识别为噪声并对分类器的性能造成影响.模糊向量机可以改善噪声数据造成的分类精度下降现象,通过为样本点赋予不同的隶属度来确定样本点的性质.但传统的模糊支持向量机在确定样本隶属度时,仅考虑了类内距离,应用于不平衡数据集分类时容易出现较大误差[9].故本文提出一种应用不等距超平面距离的改进模糊支持向量机.文中将样本数量多的类规定为正类,将样本数量少的类规定为负类.通过向标准模糊支持向量机中引入参数 λ,以控制超平面与样本之间的距离.在构造隶属度函数时,不仅取决于样本之间的距离,还考虑了样本之间的互距离,更精准的表示样本分布,以减小不平衡的样本分布给分类准确度带来的影响.

1 相关工作

在不平衡样本集上进行训练时,相关的修改算法主要在两个方面上进行相关的改进,样本数据上和训练算法上[10].在训练样本数据上进行的改进,主要有两种方法,分别是增加负类样本数量和减少正类样本数量,如欠采样和过采样.但采样方法容易造成分类模型在训练和测试过程中具有较大的误差,无法获得较准确的分类结果.文献[11,12]中解释了减少正类样本数量虽然可以改善数据的不平衡性,但会使样本所含信息丢使,分类效果降低;文献[13]证明了增加负样本也会出现过拟合现象,令噪声数据对模型分类准确度的影响更显著.

在用于不平衡数据分类的支持向量机训练算法中,不断有学者提出改进的算法.在文献[14]中,算法引用补偿因子以修正超平面的偏移量,利用支持向量的决策值估计补偿因子的数值,文献中所做的实验表明引用的补偿因子,训练样本离超平面的间隔可以在一定程度上得到正确的修正.但是,当不平衡样本集中正负类的训练样本有很大的交叉区域和有噪音数据时,算法的分类性能有很大的下降.在文献[15]中,算法在支持向量机训练过程中的为正负类样本分别设置了各自的惩罚因子,并将约束条件中加入新的参数控制分类间隔.将改进的近似支持向量机应用到不平衡样本的分类,减小样本数量对分类面的影响,提高了算法精度.但这种方法的改善效果受到KKT 条件的限制,KKT条件将惩罚参数作为其上限条件,而不是下限条件,同时寻找合适的惩罚参数是比较困难的.在文献[16],算法对相关的核函数进行修改并将其应用于不平衡样本集中,在黎曼几何结构上对核函数优化,提高了不平衡数据的分类准确率.在文献[17–20]中,介绍了SVM相关的改进算法,将其应用于不平衡样本,从各种方面使得负类样本的分类结果得到优化.

在文献[21]中,介绍了模糊支持向量机,它在处理分类和预测等现实问题时表现出了十分出色的性能,相较支持向量机而言,它可以减轻噪声数据对分类器性能的影响.隶属度函数的确定影响着模糊支持向量机分类性能,已有许多算法应用于解决隶属度函数的选择问题,如聚类算法[22,23]、启发式算法[24]等,但至今为止,模糊隶属度函数的确立尚无系统的理论规定和准则.

通过计算类内距离确定样本隶属度,是构造隶属度函数的经典方法.计算样本到其类中心点的距离,若距离小则判定该样本点属于该类的可能性较大,为该其赋予一个较大的隶属度值;若距离过大则判定该样本点为噪声数据,并赋予该点一个较小的隶属度值.以此作为样本贡献度的衡量指标,可能会令分类器对噪声的辨识度降低[25],使分类器训练时误差较大,降低分类器的分类精度和泛化性能.

2 不等距超平面距离改进的模糊支持向量机(IFD-FSVM)

模糊支持向量机模型为:训练集为{(xi,yi,ui)|i=1,2,···,l},xi为样本集,yi为样本xi的标签且yi∈{+1,−1},ui为模糊隶属度,反映了不同的类对分类面形成的贡献度,参数 εi为 松弛变量,参数C为惩罚参数.通常将类到超平面之间的分类间隔成为超平面距离,利用支持向量机求解分类问题的本质就是使超平面距离最大化.

其数学模型用公式表示为:

不等式约束条件为:

式中,ω为决定超平面方向的法向量,b表示该决策面到坐标轴原点的距离.

模糊支持向量机的决策函数为:

K(x,xi)为核函数,常见的核函数有线性核函数、多项式核函数、高斯核函数等,在求解过程中核函数的选择要视数据集性质而定.

利用不等距超平面距离改进后的模糊支持向量机.当0<λ<1,超平面距离正类样本较近;反之则超平面距离负类样本较近.改进后的模糊支持向量机最优决策面即为下列公式的最优解:

不等式约束条件变为:

通过引入拉格朗日乘子求解上述不等式约束的凸优化问题:

其中,ai为拉格朗日因子

求解的关键变为得到(7)的最小值,故对(7)式中的ω,b,ε分别求偏导得到:

将式(8)中得到的结果代入到式(7),利用拉格朗日对偶性可以将求解原问题满足约束条件的极小值转化为:

将上面列出的凸优化问题求解完毕,得到改进的模糊支持向量机的决策函数:

λ的值影响超平面与类之间的空间距离,若0<λ<1,则超平面与正类间的空间距离较小;若 λ>1,则超平面与负类之间的空间距离较小;若 λ=1 该算法等同于标准的模糊支持向量机.

从式(11)、式(12)可以得到改进后的模糊支持向量机和标准的模糊支持向量机的基本原理相同的结论,可以将标准模糊支持向量机的训练方法应用于改进的模糊支持向量机上.

3 确定隶属度函数

在超平面的确定过程中,并不是所有的样本点都能起到决定性作用的,样本贡献度就是度量求解超平面所需的样本点的性质.图1展示了样本空间的分布状态,其中深色区域中的样本贡献度较大,区域外的样本贡献度法较小,在求解过程中更有被识别为噪声数据的可能性,影响超平面位置的选取.另外,大部分的支持向量样本位于阴影部分.本文提出一种确定隶属度函数的方法,既考虑到了样本内的距离关系,又考虑到了样本之间的相互关系.

图1 样本的空间分布

通常定义隶属度函数如下:

定义1.类中心:一类样本的平均样本特征定义为该类的中心.如训练样本标记为:{x1,x2,···,xn},类中心记为正类样本的类中心记为m+,负类样本的类中心记为m−.

定义2.两类样本之间的距离:两类样本的类中心之间的距离为两类样本之间的距离,记为d,d=|m+−m−|.

定义3.两类样本之间的互距离:规定所有正类样本到正类中心的距离=|xi−m+|,到负类中心的距离=|xi−m−|.同样地,规定所有负类样本到负类中心的距离=|xi−m−|,到正类中心的距离=|xi−m+|.

由于支持向量机是通过将样本映射到高维空间寻找最优决策面,依据上文给出的定义,各类的样本距离和样本互距离在高维空间中求解过程为:

为此提出了隶属度函数的设计算法如算法1.

算法1.利用样本距离确定隶属度函数算法d−ip 1)计算样本中心点之间的距离,计算正类样本的互距离 ;d−ip>d d−ip≤d d 2)比较样本距离与样本互距离的大小:若,样本大都位于图1深色区域外部分,若,样本大都位于图1深色区域内部分;d−ip≤dd+ipR+3)取 的样本点计算其,将其中的最大值记为.R−4)同理得到负类样本的.

最终得到两类样本的隶属度函数:

4 实验结果与分析

当分类问题应用到现实生活中时,往往对负类的分类结果有更高的要求.本文应用两种评价准则来验证改进算法的分类效果,即准确率和召回率.其中准确率描述的是分类结果,表示负类分类结果中实际负类样本的比例.召回率描述的是原有样本的分类覆盖率,表示的是原有样本中的负类被正确分类的比例.其表达式分别为:

准确率Precision=TN/TN+FN

召回率Recall=TN/TN+FP

TN代表实为负类且分类结果为负类的样本,FN代表实为负类但分类结果为正类的样本,FP代表实为正类但分类结果为负类的样本.

实验基于UCI 数据集,并选出4 种不平衡率不同的训练样本集,样本不平衡率如表1所示.

表1 样本训练集

实验将IFD-FSVM 算法应用于UCI 数据集验证算法性能,并将实验结果与SVM、FSVM 在相同场景下的分类结果进行比较.

SVM 算法:等距超平面且没有将隶属度函数应用于支持向量机.

FSVM 算法:等距超平面线性隶属度函数的模糊支持向量机.

IFD-FSVM 算法:应用不等距超平面距离的改进模糊支持向量机.

首先,将4 种样本集的参数分别设置为 λIrist=0.8,λBalance=0.7,λYeast=0.63,λAbalone=0.37,δ=0.2 时,各样本集的负类分类结果如表2所示.

表2 各数据集在3 种算法下的分类准确率与回归率(%)

由表2可以看出,相比其他算法,IFD-FSVM 算法明显提高了分类准确率与回归率.在Irist 数据集上应用IFD-FSVM 算法进行分类,准确率分别比应用标准SVM 和FSVM 提高了15.68%和7.29%.在Balance Scale 数据集上应用本文算法进行分类,准确率分别比应用标准SVM 和FSVM 提高了14.83%和10.46%.而在Yeast 数据集上,IFD-FSVM 算法的分类准确率比其他两种算法分别提高了19.31%和7.01%,在Abalone数据集上则具有较大的准确度改善,较其他两种算法分别提高了26.92%和15.93%.

各样本集的负类分类效果如图2、图3所示.

图2 负类样本分类准确率对比

图3 负类样本回归率对比

图2和图3分别展示了3 种算法在4 种样本集上负类的分类的准确率和召回率.可以看出,IFD-FSVM算法的分类效果明显优于另外两个标准算法.且样本数据不平衡比例越高,分类效果的改善越明显,在Abalone数据集上的负样本分类准确率和召回率都有较大幅度提升.

虽然参数 λ对分类器性能有着至关重要的影响,当参数 λ<1 时,负类的分类效果有明显改善,但并不是参数 λ的设置越小越好.当参数 λ过小时,正类的分类效果受到影响.如将4 种样本集的参数分别设置为 λIrist=0.21,λBalance=0.19,λYeast=0.12,λAbalone=0.08 时,各样本集的正类分类准确率如图4所示.

图4 正类样本分类准确率对比

从图4中可以看出,若将参数 λ的值设置为如上,相较于标准的模糊支持向量机,IFD-FSVM 算法对正类分类效果明显下降.由于参数 λ过小,超平面与正类样本距离过小,负类样本被识别为噪声的概率增加,导致正类分类准确率受到影响.

5 结论与展望

通过对不平衡支持向量机的研究,本文提出了应用不等距超平面距离改进的模糊支持向量机IFDFSVM.算法通过改进原有的模糊支持向量机,引入参数 λ以调节超平面到正类的距离,实验时规定 λ<1,令超平面接近正类样本.利用样本之间的互距离确定模糊隶属度函数,有利于确定贡献度大的样本数据,更好的反映了训练样本对超平面形成的贡献作用,降低了噪声数据给分类器性能带来的影响.最后利用UCI 数据集来验证IFD-FSVM 算法的有效性,实验结果说明IFD-FSVM 算法能够有效提高不平衡样本的分类准确率.