基于边界混合重采样的非平衡数据分类方法

侯贝贝，刘三阳，普事业

西安电子科技大学 数学与统计学院，西安710126

1 引言

最近几年，非平衡数据分类问题一直活跃在各个领域，如垃圾邮件过滤[1]、文本分类、信贷欺诈[2]、客户账户信息流失和网络入侵数据[3]等，这些问题存在一个共同的特征，即数据集中的某一类别的样本数量远远多于另一类（分别称为多数类和少数类），具有这种特征的数据集被看作是非平衡的。但实际问题重点考察的对象往往是已知信息较少的一类，这对传统的分类算法有着天然的缺陷，因为它们最初的设计思想是以提高整个数据集的分类性能为标准，为了满足这类算法的目标函数要求，分类器会将某些少数类样点划分到多数类，使得少数类样本的分类准确率降低。因此，采取合适的策略或方法，降低由数据样本数量的非平衡所带来的影响是目前分类算法研究的难点和热点[4]。

现有的关于非平衡数据分类问题的研究主要从数据和算法方面着手。数据层面上，重采样技术是颇受关注的[5-6]，其中，较具有代表性的是过采样SMOTE[7]（Synthetic Minority Oversampling Technique）算法和欠采样[8]（Under-Sampling）算法，分别通过对少数类和多数类进行添加数据和剔除数据，以此来达到数据的平衡。在此基础上，相关学者提出了一些改进的算法，文献[9]中提出的Borderline-SMOTE 算法，区别于S-MOTE 算法中将所有少数类点作为种子节点，该算法认为少数类中的边界样本是更有价值的点，进一步合成新的样本点，有效地避免了SMOTE算法容易造成过拟合的现象，但因其主要合成边界样本，加大了边界模糊的可能，使得分类难度增大。针对随机欠采样算法中易删除含有重要信息样本点的问题，赵自翔等[10]提出基于欧氏距离的欠采样算法（OSED），该算法在删除多数类样本时既保留了样本的分布情况又平衡了数据集，一定程度上提高了少数类的分类精度。从算法层面上，通过引入某种机制来克服样本数量非平衡对算法造成的影响，常用的算法有基于代价敏感学习法[11]（DEC）、集成学习方法[12]和模糊支持向量机[13]等，虽然这类算法避免了由合成数据或删减样本带来的误差，但其较难改进，因为不同类别的惩罚因子人为较难设定，并且对于不同分布的数据集，算法中参数的选择也会较棘手，往往需要做大量的实验去寻找。针对欠采样和过采样在非平衡数据分类上的不足之处，混合采样的非平衡数据分类方法相继被提出。文献[14]提出了基于边界混合采样的非均衡数据处理算法，该算法利用变异系数对训练样本边界进行区分，对多数类边界样本利用基于欧氏距离的欠采样算法删除，但对少数类边界样本仅使用SMOTE合成样本，仍无法避免SMOTE易过拟合的缺陷。文献[15]提出了一种基于邻域混合抽样和动态集成的不平衡数据分类方法，该算法依据每个数据点的危险程度赋予样本点一定的权重，对多数类样本和少数类样本分别进行处理，实验结果表明，该算法能够提高数据集的分类性能。

针对上述多数类样本易删除重要信息点和少数类样本合成无效样本点的问题，本文提出一种基于边界混合重采样的分类方法（BMRM）。该算法通过设置支持k-离群度阈值[16]来划分边界样本和非边界样本，对少数类中的边界样本使用改进的SMOTE 算法，多数类中的非边界样本使用基于距离的欠采样算法[17]，最后将本文算法与SMOTE 算法、Borderline-SMOTE 算法、基于欧氏距离的欠采样算法，以及基于支持k-离群度概念定义非边界样本，对多数类的非边界样本使用随机欠采样的算法进行对比。实验结果显示，本文算法具有更好的分类性能，SVM算法是具有代表性的数据分类算法，本文实验中均将其作为基准分类器。

2 基于边界混合重采样的非平衡数据处理

文中提出的基于边界混合重采样的非平衡数据分类方法，主要以两个过程对样本点的边界集和非边界集进行处理，在使多数类和少数类样本数量达到平衡的同时，最小程度地降低样本信息的流失，保留对分类性能有影响的点，以此达到更好的分类效果。其主要思想是，引入支持k -离群度和边界因子概念区分数据集中的边界点集和非边界点集，找到对分类性能有影响的点，使混合重采样算法更加合理。

2.1 边界集的识别

从数据层面对数据集进行分类，为了使类之间的样本数量均衡，有时会将多余的数据点删除掉，但并不是仅仅去掉部分样本就能实现较好的分类效果。该前提是要将含有重要信息的样本点保留下来，从支持向量机（SVM）的分类思想上了解到，超平面只与支持向量有关，而支持向量大都位于多数类和少数类的边界样本上，所以，在处理数据时，直接删除边界上的数据点这种做法是不合适的。为了能更好地识别出边界样本点，文中采用基于支持k-离群度的边界点检测算法找出非平衡数据集中的边界集和非边界集，具体定义如下。

（1）对于数据集M 和任意正整数k，对象s 的k 距离记为k_dist(s)，对于任意对象o ∈M ，对象s 的k 距离为k_dist(s)=dist(o,s)，需满足：

①至少有k 个对象t ∈M-{s}使得

②至多有k-1 个对象t ∈M-{s}使得

其中，dist(o,s)为对象ο 与对象s 间的欧氏距离。

（2）对象s 的支持k-离群度的定义为：s 的k 距离与其ε 邻域内的所有点（包括s）的k 距离的平均值之比，记为k_od(s)，即

其中，Nε(s)为对象s 的ε 邻域内的所有对象， ||Nε(s) 表示对象s 的ε 邻域内的样本点个数，该公式主要利用样本点自身的k 距离与其邻居样本的k 距离来刻画数据的分布特征。

考虑到数据集中存在样本点分布不均匀的情况，较难为每个数据集样本点找到合适的ε 值，可能有的点处于高密度区域，有的点处于低密度区域，为了避免这种不确定因素，将点s 的ε 邻域半径设置为s 的k 距离。

（3）数据集M 中点s 的支持k-离群度与1 之差的绝对值记为点s 的边界因子k_bd(s)，即

如果一个数据样本的边界因子越小，那么就说明该点及其k 距离邻居的距离相差较小，数据分布相对均匀，该点是类内部的点的可能性较大。相反，如果一个数据样本的边界因子越大，那么就说明该点附近点的分布相对离散，k 距离变化较大，数据分布不均匀，即该点为类内部点的可能性就越小，设定一个阈值σ ，当k_bd(s)＞σ 时，称满足此条件的s 样本点为边界点，否则为非边界点。

2.2 边界集的处理

（1）Random-SMOTE算法

根据SMOTE 算法本身存在的不足，无法解决数据集中少数类样本分布过拟合以及计算复杂度大的问题。本文针对其不足引用Random-SMOTE 算法[18]，此算法重点关注新样本产生的区域，使得新样本更贴合样本点分布的随机性，Random-SMOTE 算法首先计算区域内少数类样本x0的k 个同类近邻样本，并在k 个同类近邻样本中任意选取两个，设这两个少数类样本点的向量表示为X 和Y ，然后在这两个少数类样本点之间随机确定一点P ，记P 为临时样本点，最后在样本x0与临时样本P 之间使用公式（5），合成新的样本点，记为Xnew1。

区域内的少数类样本点与它的两个近邻同类样本点组成三角形，这个方法使得新合成的样本点在三角形区域内具有一定的随机性，更贴合样本点本身的分布特性。

（2）NP-SMOTE算法

针对多数类样本分布对少数类分类效果有很大影响的问题，本文首先给出如下定义：

定义1 若样本x0的k 近邻都是同类样本，则x0为安全样本，若k 近邻中存在非同类样本，则x0为非安全样本。

为了提高边界集中少数类样本的分类效果，对边界集中少数类样本x0计算k 近邻样本，当k 近邻样本中存在多数类样本Q 时，在该少数类样本x0与多数类样本Q 之间使用公式（6），合成新的样本点，将算法命名为NP-SMOTE。

由于当样本点的k 近邻都是同类点时，该样本点相对来说不容易被分错，在边界集少数类样本与k 近邻多数类样本的连线上加入少数类样本，使得该少数类样本从非安全样本变成安全样本。

利用上节给定的边界定义公式，找到数据集中的边界集，对边界集中的少数类样本点，利用Random-SMOTE算法和NP-SMOTE 算法合成新的少数类样本点，该操作即减少了对分类性能影响不大的点的合成，又平衡了边界集中的多数类与少数类样本点。

2.3 非边界集的处理

现实中大规模的数据样本集普遍存在，对SMOTE算法来说，会增大算法的时间复杂度，为了降低算法的时间消耗，需要采用一种合适的欠采样算法。由于距少数类样本中心点远的多数类样本点为噪声的可能性较大，因此，本文对于非边界集的多数类样本点采用基于距离的欠采样算法，该方法首先需要先找到少数类的中心点，计算非边界集中的多数类样本到该中心点的距离，然后对距离进行排序，删除一定比例的多数类样本点，经过该算法处理后的样本点既保留了有价值的点，又使得数据点数量趋于均衡。

2.4 基于边界混合重采样的非平衡数据分类流程

基于边界混合重采样的非平衡数据分类方法，使得边界集和非边界集的少数类与多数类样本点均达到平衡，一定程度上提高了非平衡数据集的分类性能。

假设D 为处理前的非平衡数据集，则D 中的边界集、非边界集、边界集中的多数类样本、边界集中的少数类样本、非边界集中的多数类样本、非边界集中的少数类样本分别定义为BMRM 算法的流程如图1 所示。本文算法首先利用支持k-离群度概念计算原始数据集中每个样本点的边界因子，设置边界阈值σ ，将边界因子大于该阈值的样本归为边界集，反之归为非边界集；然后对边界集中的少数类样本利用改进的SMOTE算法合成新的少数类样本点，并加入到训练样本集中；对于边界集中的多数类样本点不做处理，同样加入到训练样本集中；最后，对非边界集中的多数类样本点采用基于距离的欠采样算法删除对分类性能影响较小的样本点，保留下的样本点连同非边界集中少数类样本点一起加入到训练集中。

图1 BMRM算法流程图

本文所提算法的具体过程分析如下。

输入：非平衡数据集D(i=1,2,…,N)，N 为样本总数，边界因子阈值σ。

输出：平衡化后的数据集。

1.计算训练集中每个样本的边界因子k_bd(xi)(i=1,2,…,N)

1.1.计算样本点xi到其余样本点的欧氏距离，并对该距离进行排序，得出其对应的k 距离

1.2.找到距离样本xi最近的k 个样本点，并计算这k 个点所对应的k 距离

1.3.计算每个样本点的支持k-离群度

1.4.求出每个样本点的支持k-离群度与1之差的绝对值，记为k_bd(xi)(i=1,2,…,N)

2.若k_bd(xi)＞σ，则将xi归为边界集D1中；否则归为非边界集D2中

3.将D1中的样本点使用Random-SMOTE 算法和NP-SMOTE 算法合成新的样本点集，并将其与、组成新的点集Train_data_1

4.将Dmajor2 中的样本采用基于距离的欠采样算法删减，然后将与删减后的的组成新的点集Train_data_2

5.将Train_data_1和Train_data_2合并成处理后的数据集Train_data

边界因子阈值σ 是本文算法需要解决的一个问题，下面给出相关定义。

定义2 平均k 距离：设有N 个样本点，N 个对象的k 距离为k_dist(s)，其中，s=1,2,…,N ，则可定义所有对象的平均k 距离为：

定义3 最大样本k 距离：

其中，s=1,2,…,N 。

定义4 一个样本数量为N 的数据集，选择样本间的平均k 距离与最大样本k 距离的比值作为边界因子阈值σ，即

通过大量实验，阈值在0.3～0.5 之间能够得到较好的边界识别结果。

3 实验及结果分析

3.1 评价指标

在非平衡数据分类问题中，一个分类算法的分类情况可通过混淆矩阵来评估，其对应的混淆矩阵如表1所示。

表1 中，TP 是实际为少数类且预测正确的样本个数，TN 是实际为多数类且预测正确的样本数量，FN 是实际为少数类且预测错误的样本数量，FP 是实际为多数类且预测错误的样本数量。因为非平衡数据分类中少数类样本较少，相比多数类样本较难识别，对于少数类样本的边界是较难准确定义的，为了最大化准确率，分类器往往会将整个数据集的大部分样本划分到多数类，如果仍以分类准确率作为评判标准，对于少数类样本显然是不公平的。因此，本文采用较为综合的F-value和G-mean 指标来衡量非平衡数据分类性能的优劣，公式定义为：

表1 混淆矩阵

其中，Se 代表分类器预测少数类样本的能力，Sp 代表分类器预测多数类样本的能力，G-mean 是比较综合的指标，而且只有当Se 和Sp 都较大时，才能保证G-mean也较大。

F-value作为非平衡数据分类的评价指标，其定义为：

3.2 数据集描述

为了验证本文所提方法的有效性，从UCI国际机器学习数据库（http：//www.ics.uci.edu）中选择了8 组非平衡数据集。由文献[19-20]可知，一般当少数类与多数类的类分布比例低于1∶2时，数据具有非平衡特征。所用数据集样本点个数范围为215～4 601，样本点的属性维数范围为3～57，非平衡比率为多数类样本数与少数类样本数的比值，本文解决的是二分类非平衡问题，对于含有多个类别的数据集，人为的进行重构，并将重构后样本数量多的一类定义为多数类，样本数量少的一类定义为少数类。其中，Haberman 数据集的第二类作为少数类，第一类作为多数类；Ecoli数据集的第pp、om为少数类，其他合起来为多数类；biodeg数据集的第RB类为少数类，NRB为多数类；Throid数据集第二类为少数类，其他类为多数类；Vehicle 数据集第van 类为少数类，其他合起来为多数类；Innosphere数据集的第b类为少数类，g类为多数类。各个数据集详细信息如表2所示。

表2 数据集信息

3.3 实验及分析

为了验证本文所提出的基于边界混合重采样的非平衡数据分类算法的分类性能，将其与基于SVM 分类器的SMOTE 算法、Borderline-SMOTE（B-SMOTE）算法、基于欧氏距离的欠采样算法（OSED）和基于支持k-离群度概念，但对多数类非边界样本进行随机欠采样，与少数类边界样本进行SMOTE 结合的算法（RUSMOTE）进行对比。实验环境均在MATLAB2018b 软件运行，对于每一个数据集，均采用五折交叉验证，每次选择其中4组作为训练集，1组作为测试集，且每组数据集中的多数类与少数类样本个数比值为原始数据集中多数类与少数类样本数量非平衡比率，8个数据集在少数类上的对比结果见表3，多数类上的对比结果见表4，综合性指标（G-mean和F-value）对比结果见表5，并将最大的值用粗体标出。

从表3中观察发现，本文算法较好地提高了少数类的分类准确率，大部分数据集在经过本文算法处理后得到的Se 值大于文中列举的其他对比算法。因为本文算法在处理数据时，对多数类和少数类中的边界点分别作了相应的处理，较好地降低了由边界样本点分错而带来的不良影响，同时对于多数类中的非边界集，采取了基于距离的欠采样算法，保留了对分类结果有价值的样本点，相比随机欠采样算法，分类性能有了明显地改善。表4中本文算法在多数类上的分类准确率均较高，虽然在数据集Haberman 和Biodeg 上没有取得最优的值，但与其他对比算法相差不大，说明B-MRM算法在保证多数类样本分类性能的基础上，一定程度上可以提高少数类样本的分类性能，在实际应用中，少数类样本往往才是要考察的对象。

表3 5种算法在少数类上的对比结果

表4 5种算法在多数类上的对比结果

从表5 中发现，针对F-value 指标，在数据集Vehicle上，对比算法B-SMOTE 高于本文结果，这是因为Vehicle数据集的边界点重叠度较大，而B-SMOTE算法是针对少数类中的危险样本点设计的算法。本文算法虽然加入了边界因子概念，但对边界复杂度大的数据集显得有些不足，说明本文算法仍需改进。虽然本文算法较好地提高了少数类的分类准确率，但当数据集不平衡比率较大时，例如Abalone数据集，本文算法中的边界因子阈值这一关键参数对该数据集的分类性能有所影响，导致OSED 算法的F-value 值高于本文算法。但从Gmean指标上看，本文算法分类性能优于对比算法，是较为有效的。

表5 8种数据集在5种算法上的G-mean和F-value性能比较

为了更清晰地分析各个算法的分类效果，图2～5分别绘制了5 种算法在8 个数据集上的分类结果变化曲线。其中，横坐标代表不同算法，纵坐标代表分类结果取值，其范围在0～1之间，从图中观察得出，本文算法相比较其他算法在各个指标上都有了一定程度的提高。事实证明，综合考虑对分类性能有影响的样本点，对不同区域的数据样本采取不同的方法是有效的，并在一定程度上表现出更强的适应性。

图2 少数类准确率变化曲线

图3 多数类准确率变化曲线

4 总结与展望

图4 G-mean变化曲线

图5 F-value变化曲线

本文针对非平衡数据分类问题，提出了一种基于边界混合重采样的方法，通过计算数据集中每一个样本点的支持k-离群度，利用设定的阈值来划分边界集和非边界集，并对边界集中的少数类点进行Random-SMOTE和NP-SMOTE合成，非边界集中的多数类样本进行基于距离的欠采样剔除，以此实现数据集的平衡。实验结果对比表明，本文算法一定程度上提高了数据集的分类性能，可将该算法用于解决生活中普遍存在的非平衡分类和预测评估问题。但本文算法也存在着不足：一方面，边界因子阈值σ 在设置时，本文虽考虑了所有训练样本的分布特征，但却忽略了类内样本的分布情况；另一方面，在定义支持k-离群度时仅仅选择基于距离的离群度，对于文献[21]中所给的其他离群度定义形式还有待研究。今后的工作可以在本文算法的基础上，利用其他效果较好的重采样算法来实现非平衡数据分类，并研究如何通过自适应方法产生边界因子阈值。