基于扩展近邻SMOTE过采样的SVM分类器

宋艳，白治江

（上海海事大学信息工程学院，上海 201306）

0 引言

不平衡数据集是指数据集中某类别样本的数量在整个数据集中占主导优势。一般把数据集中数量较多的类标记为多数类或负类，数量处于劣势的类标记为少数类或正类。这类数据在现实生活中普遍存在，如网站中用户搜索行为，客户的个人信誉评估[1]。然而使用传统的支持向量机[2]已不足以在庞大的数据集中识别出正类样本。因此，如何在信息时代正确地区分和预测正类样本，成为众多学者的研究重点。

目前，多数学者主要从算法和数据两个层面对不平衡数据进行处理。算法层面一般通过改进分类算法提高正类样本的识别精度，如代价敏感法[3]、集成学习[4]、主动学习等。算法改进的办法一般只适用于某些特定分布特征的数据集，因为数据集的分布仍然保持原样。数据层面主要以欠采样（Under-Sampling）[5]与过采样（Over-Sampling）[6]为原型，使原始数据集中两类样本数量上相近。欠采样通过随机删减负类样本使两类样本的数量相同，却有可能将带有重要信息的负类样本舍弃，从而使分类器的学习能力下降；过采样则以随机复制正类样本的方式平衡两类样本，但新增的样本数据不仅需额外的计算代价并且会造成过度拟合。2002年，Chawla等人提出SMOTE算法[7]，极大地改善了过学习问题，但该算法新增样本时不加区分地在正类样本间线性插入新样本，限制了新增样本的生成位置，忽略了靠近分类边界附近的样本才影响分类边界的位置。

鉴于SMOTE算法插值的局限性，众多学者在此基础上提出了改善策略。Han等人提出了Borderline-SMOTE方法[8]，其基本思想是在正类数据集的边界样本之间线性插值，使得平衡后的数据中更多的样本出现在类边界附近，致使分类边界模糊。文献[9]在正类样本及其最近邻正类样本构成的n维球体内随机插值，扩大了新样本生成的区域，致使数据集边界附近聚集过多新样本。

基于上述分析,本文提出一种结合邻域样本分布特征的改进型SMOTE算法（简称E_SMOTE算法）,其要点是探察近邻的近邻，即用SMOTE算法插值时充分利用K近邻候选点的M近邻样本分布特征,实现对新样本分布区域的控制，克服新样本引起的边界模糊问题。通过实验表明，与其他相关算法对比，本文算法确实提升了不平衡数据集的整体分类准确性。

1 相关算法简介

1.1 SMOTE算法

SMOTE是一种过采样方法。具体操作如下：首先，根据不平衡度设置采样倍率N；接着，对数据集的每个正类样本x计算其k个同类最近邻样本，并在这k个样本中随机选择N个，记为y1y2...yN，按公式（1）生成N个新样本；最后，把每个正类样本新增的N个样本加入原始数据集中，构成新的样本数据集。

其中rand是（0,1）内一个随机数，NewMinority代表新合成的样本。

1.2 支持向量机

支持向量机（Support Vector Machine,SVM）是Vap⁃ink等人提出的以统计学习理论原理为基础的机器学习方法。在解决分类问题、非线性和高维模式识别中展现出独特的优势，同时也具备抑制局部极值和过学习的特性，从而受到广泛的关注。传统的SVM分类器在处理样本数量基本相同、分布均匀的数据集时，表现出极优分类结果。然而实际应用中更可能面向不平衡数据的分类问题，这使得SVM分类结果并不理想，其结果更可能偏向负类样本，使得正类样本分类精度下降。

1.3 NCL（Neighborhood Cleaning Rule）

NCL基本原理：对训练集中的每一个样本x，计算x的3个最近邻样本。若x是正类样本，且其3个最近邻样本中存在2或3个负类样本，则删除这些负类样本，如图1（a）所示；若x是负类样本，且其3个最近邻样本中存在2或3个正类样本，则删除x。如图1（b）所示。

图1 NCL原理

（a）正类样本x的3个近邻中，有x1和x2两个负类样本，所以删除x1和x2。（b）负类样本x的3个近邻样本，有x2和x3两个正类样本，所以删除x。

1.4 SMOTE_NCL算法

SMOTE_NCL方法先使用SMOTE对数据集过采样处理，然后使用NCL方法对训练集进行欠采样处理。该方法的缺点是当NCL清洗了一定数量的负类样本后，可能导致两类样本数量再度失衡。

2 E_SMOTE算法

靠近边界附近的样本带有重要信息，且决定着决策界面的位置，尤其是正类样本稀少且宝贵。E_SMOTE算法正是通过考察正类样本的扩展近邻，既突出了边界样本的重要性，又抑制了噪声点的干扰。为了便于描述，定义如下概念：

根据正类样本近邻的分布特征，把正类样本细分[10]为安全集和非安全集两类，具体定义如下：

定义1（安全集）S1=｛x|x的k近邻样本全部是正类样本｝。

定义2（非安全集）S2=｛x|x的k近邻样本不全是正类样本｝。

E_SMOTE算法基本思想如下：SMOTE算法对非安全集中每一个样本x与其正类近邻样本xi合成新样本时，如果 xi的 M个最近邻样本存在ω（M/2≤ω≤M）个负类样本，则不做任何处理，否则在x和xi之间插入一个新样本，重复这一过程直到非安全集中所有样本处理完毕。该算法中M2向上取整。该线性插值过程如图2所示，正类样本点x属于非安全集，假设采样倍率N=2。

图2 非安全集插样示例

图2表示，从x的同类最近邻样本中随机选择2个样本点，这里选择x1和x2；x1的3个最邻近样本存在2个负类样本点（x11和x12），则x与x1之间不合成新样本；而x2的3个近邻样本全部为正类样本，则在x与x2之间根据SMOTE算法合成一个新样本。

E_SMOTE算法的操作步骤如下：

①设置采样倍率N。

②根据正类样本的k近邻分布，把正类样本分为安全集S1和非安全集S2。

③对S1直接应用SMOTE算法插入新样本。

④对S2在使用SMOTE算法合成新样本前考虑扩展近邻的分布特征，符合条件的才插入新样本。

⑤用平衡后的数据集训练SVM分类器。

3 实验设计和结果分析

3.1 数据集及评价标准

本文选取UCI库的6种数据集完成实验，数据集具体信息如表1所示。对多类别数据集，选择其中样本数目较少的一类作为正类样本，其他类别样本的集合作为负类样本。例如，Wine数据集共有3个类别，本实验把类别1标记为少数类，其余2类合在一起作为负类。

评估标准是衡量分类器性能的准则。为了客观、公正地评价面向不平衡数据集的SVM分类器性能，结合实际需求，本文采用G-mean和F-value作为评价标准。

本文分类器性能的评价参数依据表2所示的混淆矩阵。

表1 数据集描述

表2 混淆矩阵

利用混淆矩阵，可得：

F-value标准是正类样本的召回率（Recall）和准确率（Precision）的调和值，其值靠近Recall和Precision中的较小者。只有当两者均较大时，F-value值才会变大。F-value计算公式如公式（3）所示：

G-mean是正、负类样本的召回率的几何均值。当两类的分类精度均较高时，G-mean的值才会增大。因此，采用F-value和G-mean作为衡量不平衡数据集的整体分类指标是合理的。G-mean计算公式如公式（4）所示：

3.2 实验数据分析

本文实验在MATLAB R2012a平台上运行。分类器是核函数为径向基函数（Radial Basis Function，RBF）的标准SVM。训练分类器之前，对6个数据集分别做如下四种平衡处理进行实验对比：①保持原样，不做平衡处理；②用SMOTE算法过采样；③用SMOTE_NCL算法过采样；④用E_SMOTE算法过采样。全部实验对每个数据集均采用2次5折交叉验证法，取10次分类结果的均值作为最终的分类结果，实验结果如表3-表8所示。

实验中SMOTE和E_SMOTE算法的近邻参数K都设置为5，并且E_SMOTE的扩展近邻参数M分别设置为3,4,5以便对比实验效果。NCL数据清洗算法中近邻参数C取3。

表3 Blood的分类情况

表4 Haberman的分类情况

表5 Diabetes的分类情况

表6 Wine的分类情况

表7 Breast的分类情况

表8 Balance的分类情况

由表3-表8可知，相比在原始数据集上直接训练SVM分类器，使用SMOTE、SMOTE_NCL和E_SMOTE算法对不平衡数据处理后提升了分类器的F-value和G-mean值。原因是对原始数据集采用SMOTE、SMOTE_NCL和E_SMOTE算法处理后，正负类样本基本达到平衡，因此绝大部分数据集的正类样本的识别率提升了，即 Acc+显著增大。在 6种数据集上SMOTE_NCL较SMOTE取得更高的 Acc+值，但同时Acc-的值却有不同程度的下降，致使SMOTE_NCL的F-value和G-mean值要么没有显著提高，要么略有下降，原因是在SMOTE_NCL方法中，NCL作为一种清洗式的欠采样方法，它只按照特定的近邻规则简单地删除负类样本，使得带有重要信息的负类样本也可能被删除，降低了负类样本训练分类器的能力。

整体上，SMOTE_NCL方法确实提升了数据集正类样本的召回率，然而分类器的总体性能未显著提高。当然也有例外，比如Wine数据集使用SMOTE_NCL处理后，该算法较其他算法取得更高的F-value和G-mean值，说明NCL算法并无普遍适用性，只能在具有特定分布特征的数据集上才能体现其优势。由表3-表5可知，E_SMOTE算法比SMOTE算法获得更高的F-value和G-mean值，这是因为E_SMOTE算法插值新样本时综合了扩展近邻的分布信息，不仅能有效抑制噪声点的影响，同时也克服了类边界模糊的问题。而由表6-表8可以观察到SMOTE和E_SMOTE算法整体性能基本一样或略小，通过多次交叉验证试验结果对比发现，本文并没有对相似分布特征的样本点采取抉择策略，而是优先选择第一个满足条件的近邻样本点，这种随机选择结果的差异性在表6-表8上表现较为明显，导致整体分类精度的平均值降低。最后，6种数据集上的E_SMOTE算法比SMOTE_NCL算法的F-value和G-mean值均有不同程度的提高（除表6和表8中E_SMOTE的整体性能有微小下降）。此外，E_SMOTE算法在确保Acc+与SMOTE_NCL基本持平的情况下，其Acc-值有显著提高。负类样本分类精度之所以提高是因为SMOTE_NCL清洗样本时可能删除重要的负类样本，而E_SMOTE方法只是针对非安全集插入新样本时进一步考虑了扩展近邻的分布信息，并未删除任何负类样本。

全部实验中E_SMOTE算法中扩展近邻参数M的取值设置了3，4，5三个值，可以看出，除了表6和表8中当M=3时取得最优值F-value和G-mean外，其他4个数据集都在M=4时获得这两个度量的最大值，说明扩展近邻中的样本数量要适当，既不能太多也不能太少，跟我们的直觉一致。

4 结语

平衡数据的算法是数据层面处理不平衡数据的关键，本文提出了一种称作E_SMOTE的改进型过采样算法。实验结果表明考虑非安全集扩展近邻的分布特征有效地提升了数据集的分类精度。本文算法的不足之处包括两个方面，首先扩展近邻参数M的取值只能根据实验结果确定；其次本文使用rand函数选择近邻样本，满足M扩展近邻即可。而没有探察多个样本点的M近邻扩展分布，并引入合理的选择机制。今后工作重点将对这两个问题进行深入研究。

[1]李毅,姜天英,刘亚茹.基于不平衡样本的互联网个人信用评估研究[J].统计与信息论坛,2017,32（2）:84-90.

[2]Vapnik V N.The Nature of Statistical Learning Theory[M].New York:Springer，2000：138-167.

[3]杨磊,陆慧娟,严珂，等.一种计算代价敏感算法分类精度的方法[J].中国计量学院学报,2017,28（1）:92-96.

[4]李凯,高元,刘柏嵩.基于集成学习的标题分类算法研究[J].计算机应用研究,2017,34（4）:1004-1007.

[5]李村合,唐磊.基于欠采样支持向量机不平衡的网页分类系统[J].计算机系统应用,2017,26（4）:230-235.

[6]Batuwita R,Palade V.Efficient Resampling Methods for Training Support Vector Machines with Imbalanced Datasets[C].International Joint Conference on Neural Networks.IEEE,2010:1-8.

[7]Chawla N V,Bowyer K W,Hall L O,et al.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research,2011,16（1）:321-357.

[8]Han H,Wang W Y,Mao B H.Borderline-SMOTE:A New Over-Sampling Method in Imbalanced Data Sets Learning[C].International Conference on Intelligent Computing,icic 2005.2005:878-887.

[9]许丹丹,王勇,蔡立军.面向不均衡数据集的ISMOTE算法[J].计算机应用,2011,31（9）:2399-2401.

[10]古平,杨炀.面向不均衡数据集中少数类细分的过采样算法[J].计算机工程,2017,43（2）:241-247.