一种基于SVM的非均衡数据集过采样方法

张忠林，冯宜邦，赵中恺

兰州交通大学 电子与信息工程学院，兰州 730070

1 引言

在现实生活中，许多数据集分布不均匀，类与类之间的样本数差异很大，即不平衡数据集：如信用卡欺诈检测[1]、故障诊断[2]、医疗诊断[3]、垃圾邮件过滤[4]等。而传统分类算法在最初被设计和实验时都是基于分布均匀的数据集提出的，将不平衡数据集不加处理直接送入传统分类算法训练，分类器为了确保总体性能，部分少数类样本会被错误地归类，致使少数类的分类准确率下降。但是，通常更重视少数类样本的分类准确性，因为少数类样本携带的信息具有更高的价值，是数据挖掘的重要目标。因此，很多研究学者将目光聚焦于不平衡数据集的分类研究，并将提升少数类样本的分类精度以及总体性能作为目标。

针对不平衡数据在分类过程中呈现的问题，业界主要通过数据采样和算法两个方向进行相关研究。在算法层面，探究不同错分情形代价的差异性通过引进惩罚机制对算法进行优化，如代价敏感学习[5]、集成学习[6]以及模糊支持向量机[7]等。通过算法解决不平衡数据问题，不改变原始数据的分布，避免了合成或删除样本引进的误差，但算法优化、参数的选用比较困难。而数据层面通过平衡数据集的方式提升分类器的性能如：欠采样、过采样以及混合采样。

文献[8]提出了典型的过采样算法SMOTE，该算法通过分析少数类样本，并与k个同类样本间线性插值合成新样本。该算法虽然使少数类的预测精度有所提升，但由于在合成新样本时没有考虑样本的分布，易合成噪声样本和冗余样本，而且不能避免过拟合的情形。文献[9]提出了Borderline-SMOTE 算法，该算法对SMOTE 的不足进行优化，认为分类边界处的样本含有更丰富的信息，因此该算法只在边界处合成少数类样本。文献[10]提出ADASYN算法，其由每个少数类样本采取某种方法自动决定合成样本的数量，但该算法易受离群点的干扰。文献[11]提出基于自然最近邻的不平衡数据过采样方法，该方法首先确定少数类的自然最近邻，然后根据样本的自然近邻关系对少数类样本进行聚类，找到核心点与非核心点，最后在核心点与非核心点之间合成样本。

随机欠采样[12]核心思想是随机删除多数类样本的部分样本达到均衡数据集的目标，但是随机欠采样可能会丢失对分类效果有重要影响的样本。因此，杨杰明等[13]针对上述不足点提出了US-DD算法，该算法依据数据的密度分布，将数据集区分为高低不同的密度簇，然后对不同的密度簇运用不同的采样方法。文献[14]提出基于KNN 的NearMiss 算法，该算法通过设定启发式规则欠采样，改进了随机欠采样的不足。

对于欠采样可能会丢失关键样本信息、过采样会合成无效样本的问题，文献[15]提出基于边界混合重采样的分类方法（BMRM），该算法引入k-离群度将数据集划分边界样本和非边界样本，然后对少数类的边界样本使用优化的SMOTE 算法采样，对多数类样本采用基于距离的欠采样算法采样，达到平衡数据集的目的。文献[16]提出基于分类超平面的混合采样算法SVM_HS，该算法运用SVM分类超平面找出分错的少数类样本进行采样，同时对离分类超平面较远的多数类样本进行随机删除。该算法虽然考虑了不同样本对分类算法的重要程度不同，但在过采样的过程中没有考虑少数类样本的分布情况。

针对现有采样算法的不足，本文根据每个少数类样本的重要程度不同，同时考虑少数类样本的类内平衡，提出一种基于SVM 的非均衡数据集过采样方法（SVMOM）。算法根据少数类样本到分类超平面的距离和样本的分布情况赋予每个少数类样本选择权重，最后根据样本的选择权重选择样本运用SMOTE迭代合成新样本，以达到均衡数据集的目的。最后将本文提出的SVMOM 算 法 与 SMOTE 算 法 、Borderline-SMOTE 算法、ADASYN 算法、NearMiss-2 算法、SMOTE+ENN 算法在6个UCI数据集上进行实验，并将采样的后的数据在SVM、Logistic Regression 和RandomForest 三个分类器上进行性能比较，实验结果表明，本文算法在F-value、G-mean和AUC上都具有较好的表现。

2 相关工作

2.1 SVM算法

SVM算法是由Vapnik[17]在20世纪90年代提出的可用于回归和分类的机器学习技术，对于分类问题，SVM的基本思想是在最小化分类误差的同时，求解一个能够正确划分训练数据集且最大化两个类之间的几何间隔。

SVM 不仅可以用于线性可分的情况，也可以用于线性不可分的情况，当两个类数据不可分时，可以通过应用核技巧将数据映射到高维的特征空间，而在高维的特征空间中数据是可分的。线性可分的SVM算法如算法1所示。

算法1线性可分的SVM算法

输入：训练集D={(x1,y1),(x2,y2),…,(xN,yN)}，其中，x∈Rm，y∈{1,-1}，i=1,2,…,N ii

输出：分类超平面与决策函数

步骤1构造并求解约束最优化问题：

其约束条件为：

其中，ξi为松弛因子，C ＞0 是惩罚系数。

步骤2求得最优解w*、b*。

步骤3由此得到分类超平面：

分类决策函数为：

w*、b*的求解，可以通过对式（1）使用拉格朗日乘子法得到其对偶问题。

其约束条件为：

对于式（5），通过序列最小优化算法（SMO），得到最优的α*=(α1,α2,…,αN)T，进而求得w*、b*。

在线性SVM 训练的对偶问题里，目标函数和分类决策函数都只涉及样本与样本之间的内积。因此，对于非线性分类问题，并不需要显示的指定线性变换，只需用核函数K(x,z)代替当中的内积。最后求解的决策函数为：

2.2 不平衡数据集对SVM的影响

SVM 是一个有监督的机器学习算法，其在平衡数据集上具有良好的性能，但将非均衡数据集送入SVM训练时，分类器为了确保总体性能，SVM 的分类超平面会向少数类倾斜，这致使部分少数类样本被错误地划分为多数类，如图1 所示。图1 中实线为SVM 在非均衡数据集上训练得到的决策边界，虚线为真正的决策边界。

图1 不平衡数据集决策边界

研究结果表明[18]，SVM在非均衡数据集上的决策边界向少数类倾斜，这是因为SVM 中的分类决策边界是由支持向量决定的，在非均衡数据集中，多数类样本比少数类样本可能有更多的支持向量，这就导致了不平衡的支持向量比，致使决策边界向少数类移动。为了使决策边界向正确的位置移动，应对少数类进行过采样，使少数类样本具有更多的支持向量。

不同分布区域的样本的重要程度不同，往往越靠近类边界的样本携带的信息量越高。在SVM 算法中，样本到决策边界的距离反映了样本所携带信息的信息量[19]。离决策边界越近，则样本所携带信息量越高，样本越重要；离决策边界较远，则样本携带的信息量越低。考虑图1，其中样本点A与样本点B离决策平面较近，而样本点C离决策平面较远。因此样本点A与样本点B相比样本点C更重要。同样的，稀疏簇的样本比密集簇的样本更重要，这是因为密集簇的样本更多，携带的信息量更为丰富，而稀疏簇样本较少，则携带的信息量较少。同样考虑图1，样本点A与样本点B到决策平面的距离相同，但样本点A的密度低于样本点B的密度，在合成样本时，应对样本点A附近合成更多的样本，使少数类样本类内更加平衡。

3 基于SVM的非均衡数据集过采样算法

3.1 算法思想

如2.2 节所述，SVM 在用于非均衡数据集时，决策边界将更接近于少数类，致使少数类样本分类精度下降。而离决策边界越近且处于低密度区域的样本重要程度越高，离决策边界越远且处于高密度区域的样本重要程度越低。基于以上分析，本文结合SVM 设计了SVMOM 算法。SVMOM 算法通过迭代合成样本。在每轮迭代的过程中，首先运用SVM 分类器在训练集上得到决策边界，在测试集上计算G-mean值，并根据样本点到SVM 决策边界的距离赋予样本距离权重，同时考虑少数类的分布情况，计算样本的密度，根据样本的密度赋予样本密度权重。然后根据样本的距离权重和密度权重计算每个少数类样本的选择权重，最后根据样本的选择权重选择样本运用SMOTE 合成新样本，将合成的样本加入到训练集中。迭代完成，最后选择G-mean值最大的那轮采样后的训练集作为最终的平衡数据集。

3.2 SVMOM算法描述

设非均衡数据集为D(i=1,2,…,N)，N为样本数，d为样本维度，训练集为S，测试集为T，训练集S中少数类样本为Smin，m为少数类样本数，多数类样本为Smaj，n为多数类样本数，合成的样本为Snew。算法流程如图2。

SVMOM算法如算法2所示。

图2 SVMOM算法流程图

算法2SVMOM算法

输入：不平衡数据集D(i=1,2,…,N)，N为样本数量，每轮迭代采样倍率δ,0<δ<1。

输出：处理后的平衡数据集S

步骤1将数据集D划分为训练集S和测试集T。

步骤2在训练集S上计算要合成的样本数G_gap。

步骤3在训练集S上用SVM训练分类模型h(x)，其决策边界为D_B，并在测试集T上计算G-mean值。

步骤4对于每个xi∈Smin，根据xi到决策边界D_B的距离，计算样本xi的距离权重Distw(xi)。

步骤5对于每个xi∈Smin计算其密度权重Densityw(xi)。

步骤6根据Distw(xi)和Densityw(xi)计算样本xi的选择权重Sw(xi)。

步骤7计算本轮迭代要合成的样本数G_num。

步骤8以Sw(xi)为概率选择G_num个样本，其集合为SG。

步骤9对于SG中的每一个样本xi，计算其k近邻，并用公式（12）合成新样本。

步骤10将合成的新样本合并入训练集S。

步骤11重复步骤3～10，直到合成样本数达到G_gap。

步骤12选择G-mean最大的那轮采样后的训练集作为最终的训练集。

3.3 样本选择权重的计算

样本的选择权重Sw(xi) 反映了样本被选中的概率。本文根据少数类样本到决策边界的距离和样本的分布密度赋予每个少数类样本选择权重。样本离决策平面越近且样本密度越小，则样本的选择权重越大；样本离决策平面越远且样本密度越大，则样本的选择权重越小。具体步骤如下：

（1）对于xi∈Smin，根据公式（14）计算其到决策边界D_B的距离Dist(xi,D_B)。

（2）样本的距离权重为：

（3）对于xi∈Smin，根据公式（16）计算xi与xj∈Smin(j=1,2,…,m)的欧式距离，得到xi的k个近邻，在本文中k=5。

（4）样本xi的密度Density(xi)为。

（5）样本xi的密度权重为：

（6）最后样本xi的选择权重为：

其中α+β=1（本文中α=β=0.5）。

3.4 SVMOM算法时间复杂度分析

SVMOM 算法通过迭代合成样本。在每轮迭代的过程中首先运用SVM 算法训练分类器，然后计算样本的距离权重与密度权重，进而合成样本。而线性SVM的时间复杂度为O(dN)，非线性SVM 的时间复杂度为O(dN2)，其中N为训练样本数，d为特征维度。样本距离权重的计算需要计算少数类样本到决策边界的距离，其时间复杂度为O(m)，m为少数类样本数。样本的密度权重根据样本的k近邻估算。因此需计算少数类样本间的距离并进行升序排序，其时间复杂度为O(m2+mlogm)。因此SVMOM 算法一轮迭代的时间复杂度为O(dN2+m+m2+mlogm)=O(dN2)。

SVMOM的迭代次数与数据集的不平衡率有关，不平衡率越高，所需合成的样本数越多，迭代次数越多。假设迭代次数为l次，则SVMOM算法最终的时间复杂度为O(ldN2)。

基于以上分析，本文采样算法具有较高的时间复杂度，且数据集样本量越大，不平衡率越高，算法耗时越长。

4 实验结果与分析

4.1 评价指标

在不平衡数据集的研究中，通常将数目少的类别视为正类，数目多的类视为负类，而正类能否被准确分类是数据挖掘的目标。在不平衡数据集分类过程中，如果分类器将全部的样本都分类到负类，就可以轻松地达到很高的准确率，但实际上该分类效果并不好。因此，传统用于评估分类器性能的准确率和错误率可能就不再适用了，为了更精准地评价不平衡数据的分类性能，通常采用构造混淆矩阵，将 F-value[20]、G-mean[20]、AUC[21]等作为评价标准。构造的混淆矩阵如表1所示。

表1 混淆矩阵

表1中TP表示实则为正类且预测为正类的样本数目。FN表示实则为正类且预测为负类的样本数目。TN表示实则为负类且预测为负类的样本数目。FP表示实则为负类且预测为正类的样本数目。

根据构建的混淆矩阵，引入查全率、真负率、假正率、查准率四个定义。

查全率，即真正类别为正类的样本中，被正确预测的样本所占比率：

真负率，即真正类别为负类的样本中，被正确预测的样本所占比率：

假正率，即真正类别为负类的样本中，被错误真正的样本所占比率：

查准率，正确分类的正类样本与所有预测为正类样本的比值：

在不平衡数据的分类评价标准中，正确率或错误率有时候并不能有效地评估模型表现，通常需要综合考虑，而F-value综合考虑了正类的准确率和召回率，其公式定义如下：

其中，TPR为查全率，RPR为查准率；β代表了TPR和RPR的相对重要性系数，在数据集分布不均匀的二分类问题中，β一般取值为1。

G-mean是评估不平衡数据集分类性能的另一个指标，其定义如下：

根据公式（24），G-mean取值与TPR、TNR有关，只有TPR、TNR同时增大时，G-mean的值才能提高，因此G-mean值是一个更加综合的分类器性能评价指标。

ROC曲线是由FRP（假正率）和TPR（查全率）构成的点连成的线，能很直观地看出任意界限值对性能的判别能力。ROC 曲线离左上角越近，实验的准确性就越高，模型的表现就越好，曲线下面积（Area Under Curve，AUC）也就越大。因而AUC 是评价模型表现优劣的一个有效指标。

本文将选取F-value、G-mean、AUC作为度量分类性能的评估标准。

4.2 数据集描述

本文从国际机器学习标准库UCI 中选取6 组不平衡数据集验证文中所提算法的有效性，数据集信息如表2所示。6组数据集既有二分类数据集也包含多分类数据集。对于多分类数据集，合并其中的几类样本形成二分类样本集。haberman数据集的类别1为多数类，类别2为少数类；transfusion数据集的类别0为多数类，类别1为少数类；credit 数据集的类别0 为多数类，类别1 为少数类；german 数据集的类别1 为多数类，类别0 为少数类；ionosphere 数据集的g 类为多数类，b 类为少数类；yeast 数据集的ME3 类为少数类，其他类合并为多数类。数据集的不平衡度定义为多数类样本数量与少数类样本数量的比值。

表2 数据集信息

4.3 实验及分析

为验证本文所提SVMOM算法的有效性和通用性，实验设置如下：

（1）将其与SMOTE算法、Borderline SMOTE算法、ADASYN、NearMiss、SMOTE+ENN 在 haberman、transfusion、credit、german、ionosphere、yeast 6 个数据集上进行采样实验。

（2）SVMOM 作为数据预处理阶段的算法，为进一步验证本文算法的通用性，分别将SVM、Logistic Regression、RandomForest作为分类器，用F-value和G-mean和AUC作为评价指标进行对比。

（3）为了更好地评价各种方法的性能，实验采用五折交叉检验法在6 组数据集上实验，每次选择其中4 组作为训练集，1组作为测试集。

本文实验环境使用Pycharm2018为仿真环境，所用其他对比算法使用imbalance-learn提供的算法实现。

4.3.1 参数敏感性分析

本文提出的SVMOM过采样算法，需要指定每次迭代的采样倍率δ、距离权重系数α和密度权重系数β。为了评估δ、α和β的影响，本文选取haberman、transfusion、credit、german、ionosphere、yeas 6 个数据集进行测试，并以SVM 作为分类器，核函数为高斯径向基，核宽度数设为10，惩罚因子C为1 000，k近邻k的取值为5。用F-value、G-mean和AUC评估参数的影响。

为了评估采样倍率的影响，对δ分别设置为0.1，0.2，0.3，0.4进行实验。实验结果如表3所示。通过表3可以看出当δ=0.2 时，F-value、G-mean 和 AUC 三个值普遍具有较好表现，如表中黑体表示。

距离权重系数α表示距离权重在样本选择权重的重要性，当α越大时，靠近决策边界的样本越容易被选中；密度权重系数β表示密度权重在样本选择权重的重要性，当β越大时稀疏处的样本越容易被选中。当α=β时，认为样本的距离权重与密度权重同等重要，即靠近决策边界且越稀疏处的样本更容易被选中。为了评估距离权重系数α和密度权重系数β影响。设置δ=0.2 ，且将 (α,β)分为（0.8，0.2），（0.6，0.4），（0.5，0.5），（0.6，0.4），（0.2，0.8）5组分别进行实验。实验结果如表4 所示。通过表4 可以看出当α=β=0.5 时，分类器在6个数据集上的整体性能表现较好，如表中黑体表示。

表3 不同采样倍率δ 下的分类效果对比

4.3.2 实验结果

根据4.3.1节讨论，本文实验参数设置如下：δ的取值为0.2，α=β=0.5，根据学者研究表明[22]，k近邻取值推荐设为5。SVM分类器的参数设置为：核函数为高斯径向基，核宽度数设为10，惩罚因子C为1 000。Logistic Regression、RandomForest分类器参数，使用算法开发人员推荐的参数值。表5给出了本文采样算法与其他5种采样算法在 SVM-RBF、Logistic Regression、Random-Forest 三个分类器上的实验结果，并将实验结果最大值加粗表示。

表4 不同α，β 下的分类效果对比

通过表5可以发现，本文所提采样算法，在用SVMRBF作为分类器时，除了credit数据集，在其他5个数据集上的表现均优于其他采样算法。这是因为本文算法通过支持向量机迭代合成样本，在每轮迭代的过程中，对离决策平面较近的且稀疏簇的样本赋予较高的采样权重，使这些样本更容易被选中合成样本，最终使决策平面向准确的方向移动。

而本文算法在Logistic Regression与RandomForest分类器上性能并不总是最好的。其中本文算法在Logistic Regression 上有三个数据集表现不是最好的；在RandomForest分类器中，有两个数据集表现不是最好的，但AUC 值都是最优的。本文所提SVMOM 算法是嵌入到SVM 中的，所以它在SVM 算法中有更好的表现。尽管本文算法在其他分类算法中表现不是最优的，但就整体而言，本文所提算法的整体性能较其他算法有较大的优势。通过实验对比发现，本文所提算法具有一定的有效性和通用性。

为了直观地体现不同算法的性能效果，图3～图5分别绘制了6 种算法在6 个数据集分别在SVM-RBF、Logistic Regression、RandomForest 三个分类模型上的实验结果曲线。其中横坐标代表6种算法，纵坐标代表性能评价指标结果。通过图可以直观地得出，当以SVM-RBF 作为分类器时，本文提出的采样算法相比较其他算法在F-value、G-mean、AUC三个分类评价指标上都有比较明显的提高。虽然在Logistic Regression、RandomForest 分类器上的性能在6 个数据集上并不都是最好的，但与其他算法相比，通过本文算法采样后的数据，总体性能更好，因此本文所提数据采样算法具有通用性，可用于其他机器学习算法。

表5 不均衡数据集在3个分类器上算法性能对比

图3 SVM-RBF作为分类器的性能对比

图4 Logistic Regression作为分类器的性能对比

图5 RandomForest作为分类器的性能对比

5 结束语

本文针对不平衡数据的分类结果偏向多数类的缺陷，提出了一种基于SVM 的不平衡数据过采样算法（SVMOM）。SVMOM 通过迭代合成样本。在迭代过程中，首先通过支持向量机算法，找到分类超平面，其次根据样本点到分类超平面的距离赋予样本距离权重；同时考虑少数类的分布情况，计算样本的密度，根据样本的密度分布赋予样本密度权重。依据样本的距离权重和密度权重计算每个少数类样本的选择权重，然后根据样本的选择权重选择样本运用SMOTE 迭代合成新样本，最后将过采样后的平衡数据集在SVM 分类器、Logistic Regression、RandomForest 中训练。实验结果表明，本文提出的采样算法优于其他采样算法，一定程度上解决了分类结果偏向多数类的问题，有效地改善了分类器的性能。但是，由于本文提出的算法，在每轮迭代进行采样时，首先要找出分类超平面，当算法应用非常大的数据集时，运行时间较长，尽管目前计算机计算能力有了很大的提升，但仍然需要提高算法在大数据集中的速度，如何提高算法的运行效率将是今后研究的重点。