融合特征边界信息的不平衡数据过采样方法

孟东霞，李玉鑑

1.河北金融学院 信息管理与工程系，河北 保定 071051

2.北京工业大学 信息学部 计算机学院，北京 100124

1 引言

不平衡数据集指各类别数据采样数量差异较大，在分布上不平衡的集合，其在疾病的识别诊断、信用风险识别、异常天气预报、攻击检测等领域中广泛存在。其中，样本数量较少的类别被称为少数类，样本数量较多的类别是多数类。在现实的信用评估问题中，客户数据的类别分布都很不平衡，即信用差的客户样本往往要比信用好的样本少很多。在这种情况下，传统的分类模型例如神经网络、贝叶斯网络、K-近邻、支持向量机等对信用差的少数类客户的错误分类率要比信用好的多数类客户高很多，将导致企业极大的损失。因此在不平衡数据集中，提高少数类样本的分类性能是一个有意义的研究课题。

目前，主要从算法和数据两个层面解决不平衡数据集的分类问题：在算法设计上，通过改变现有算法使其分类更偏向于少数类，代价敏感学习方法[1]、提升算法[2]和集成算法；在数据层面上，通过某些策略增加少数类样本（过采样）和减少多数类样本（欠采样）以达到平衡样本分布的目的。本文采用从数据层面上增加少数类样本数量的方法平衡数据分布。

最简单的过采样方法是随机复制少数类样本，虽能从数量上达到快速增加样本数量的目的，但实际效果不够理想[3]。SMOTE算法（Synthetic Minority Over-sampling Technique）基于K近邻确定少数类样本的K个近邻，通过对少数类样本和K个近邻插值合成新的少数类样本，以增加少数类样本的数量，是目前最为典型的过采样方法[4]。SMOTE算法虽然能在一定程度上改善少数类样本的分类性能，但是由于未考虑邻近样本点的分布，容易引入噪声和引起过拟合。赵等人将产生的新样本限制在一定区域内，使得样本集分布趋于中心化，用更少的正类样本点人为构造样本，提出了基于SMOTE的改进算法TSMOTE（Triangle SMOTE）和MDSMOTE（Max Distance SMOTE）[5]。Borderline-SMOTE（Borderline Synthetic Minority Over-sampling Technology）强化了边界点在插值中的影响，根据少数类样本点周边的近邻分布，将其分为safe（近邻均为少数类样本）、danger（近邻中包含少数类和多属类样本）和noise（近邻均为多属类样本）三种类型，只选取danger样本利用smote算法合成新样本[6]。杨等人提出了精化Borderline-SMOTE方法（RB-SMOTE），其加强了对边界样本的进一步区分，不同的边界样本合成不同数量的新样本[7]。为有效避免新合成样本的重叠问题，带多数类权重的少数类过采样法被提出，其核心思路是根据少数类和多数类样本的距离信息，识别出难以学习的信息丰富的少数类样本，使用聚类方法从加权信息量大的少数类样本中合成新样本[8]。夏等人在利用层次聚类算法对少数类聚类后，根据类簇的密度因子和少数样本到多数类边界的距离确定少数样本的采样权重，提出一种加权过采样方法[9]。考虑到支持向量对分类间隔决策边界的影响，一种基于支持向量的过采样方法被提出，该方法在利用支持向量机对训练集进行学习后，根据统计特性对少数类样本中的支持向量添加一定数量的噪声来平衡数据集[10]。算法L-SMOTE将SMOTE与SVM有机结合起来进行迭代，对SVM的错分样本进行循环采样，有效解决了SMOTE和SVM在处理不平衡数据集分类问题时的不足[11]。改进的FTL-SMOTE算法借助混合核SVM分类器对数据集分类后，针对噪声样本首次提出了噪声样本识别三原则，克服了L-SMOTE算法产生大量噪声点的问题，有效提高了分类模型的整体性能[12]。

考虑到大多数数据集为非线性可分的情况，本文基于文献[13]在定义最优非线性分类边界时提出的特征边界点的概念，设计了一种融合特征边界的几何分布信息的过采样技术。所提方法首先采用K近邻方法去掉少数类样本中的噪声点，然后基于少数类样本点的多类近邻集合，根据特征边界点的计算过程识别出少数类样本中有利于定义最优非线性分类边界的样本点，通过其与少数类聚簇的结合生成新样本。

2 特征边界点

特征边界点的概念由Pujol O和Masip D提出，它实现了在数据集原始空间内准确地定义最佳非线性分类面的目标，是在分片线性分类器——优化几何集成模型中构造局部最优线性分类器的基础[13]。从几何角度来说，每个样本点周围都有一个“影响区”，即以样本点为中心构造的超球面。样本点对影响区内的噪声点具有鲁棒性，也就是位于这个超球面内的任意噪声点都被判定为与此样本点同类。如果两个样本点不属于同一类，则其影响区发生相互碰撞的位置就被称为边界二分点。位于最佳非线性分类边界上的边界二分点就是特征边界点，确定特征边界点的不同类样本参与了最佳非线性分类边界的构造，在各自类中蕴含的几何边界信息较强，若基于其合成新样本，有利于保留数据集中的边界信息。

如图1所示，假设空心点是正类样本点，三角形是负类样本点，样本点周围的虚线型圆圈表示该样本点的影响区，不同类样本点的影响区在图中实心点位置发生碰撞后，将分别被实心点以最大间隔分离开。因此，实心点是位于最佳分类边界上的特征边界点，在其基础上构造局部最优线性分类器并计算相应权重后，即可集成为优化几何集成模型，从而得到最佳非线性分类面。图中的不同类样本点A和B是确定特征边界点的点对，位于各自类中的边界位置。

图1 图中的实心点是特征边界点

已知训练集s={( xi,li)}包含M个样本点，其中xi=根据定义，特征边界点可由符合下列条件的不同类样本点对(x ,x)构造得ij到，快速算法可参考文献[14]：

（1）使特征边界点位于最佳非线性分类边界上。根据欧式距离计算，xi,xj比其他任意样本点xk接近，即：

其中，构造特征边界点的少数类样本可用来合成新样本，在上述条件的判定过程中可对其进行标记。

3 融合边界信息的过采样方法

根据特征边界点的定义，参与构造最佳非线性分类边界的少数类样本点位于样本分布的边界位置，若挑选其结合所属类簇中的样本点合成新样本，将使少数类样本的分布更加合理，有利于保留样本分布的边界信息，提高识别少数类样本的准确率。算法的具体流程如下：

输入：S为不平衡数据集；K1为用于筛选少数类噪声点的近邻样本数；K2为识别边界位置附近的少数类样本时，用于构造少数类样本的多数类邻居数量。

输出：过采样生成的少数类样本集合Sgen。

步骤1将原始数据集S分为训练集T和交叉验证集V。

步骤2利用K-近邻计算T中所有少数类样本的近邻集合(K=K1)，过滤掉近邻全为相反类别的样本（认定为噪声点），得到新的训练集T′。

步骤3根据特征边界点的定义，识别出T′中带有明显边界信息的少数类样本，加入集合,初始化为空集：

步骤3.1利用步骤2中计算得到的样本间距离，利用K近邻获得T′中所有少数类样本xi的多数类近邻集合

步骤3.2将少数类样本xi与近邻集合中的多类样本xj依次构造点对，检验其能否构造特征样本点，能参与构造特征边界点的xi具有明显的边界信息，将其加入集合。

步骤4对T′中的少数类进行聚类，得到N个类簇，C1,C2,…,CN。

步骤5初始化Sgen为空集，基于集合和所属类簇合成新样本：

步骤5.1根据距离信息，将T'cp中的样本点xi划分到对应的类簇Ck中，1≤k≤N。

将集合Sgen和T′一起构成新的训练集，获得分布较为平衡的数据集。用分类器对其进行训练后，可通过交叉验证集V评估其性能。

图2直观地展示了算法合成少数类样本的基本原理：（a）中给出了训练集的原始分布情况，其中空心圆为少数类，X形为多数类，根据步骤2去掉其中的噪声点。（b）在新训练集T′，基于少数类样本的多数类近邻集合构造特征边界点，能定义特征边界点的少数类样本加入集合T'cp。图中实心点是特征边界点，假设实线型曲线是在其基础上定义的最佳非线性分类边界，经过实心点虚线一端的空心圆是带有显著边界信息的少数类样本，可参与样本的合成。（c）对少数类样本聚类，得到T'cp中样本点所属的类簇。（d）根据步骤5.2合成新样本，即图中的三角形。从图中可以看到，此方法减少了噪声点的引入，极大程度地保留了分类边界信息。

图2 融合特征边界信息的过采样方法图

4 实验

4.1 人工数据集

为了验证融合特征边界信息过采样方法的有效性，构造人工数据集对比表现不同方法新合成样本的分布情况。假设所构造的数据样本点为( )xi,yi，其中 xi是二维特征，其在两个维度上均服从均匀分布，yi是类别信息，在样本点特征信息平方根的基础上随机判定为+1或者－1。在实验中，实心点是多数类，X形是少数类，方块形是算法合成的少数类样本，其数量由多数类样本和少数类样本的差值确定。实验使用Python语言编写，SMOTE和Borderline-SMOTE方法使用的是Python库imbalance-learn package中的程序。

图3给出了采用不同过采样方法合成新样本的分布图。（a）中是数据的原始分布情况；（b）和（c）分别是采用SMOTE和Borderline-SMOTE方法合成的样本分布情况；（d）展示了本文方法所合成的新样本分布情况。从图中可以看到，本文方法较其他两种，引入了较少的噪声合成点，新样本的分布与原始分布较为一致，较大程度地保留了原始分类边界信息。

图3 不同方式下合成样本的分布图

4.2 UCI数据集

为了进一步验证所提方法的有效性，选择8组UCI[15]数据集进行测试，数据集信息如表1所示，不平衡率由少数类样本数量/多属类样本数量计算得到。对多类数据集，将其中一类设置为少数类，其余类合并为多属类。所有数据集均采用五折交叉验证的方法分成训练集和测试集，每种方法执行五次，取平均值作为实验结果。在实验前，所有样本点的特征值都被缩放到[0，1]之间。本文所提方法使用Python语言编写，SMOTE、Borderline-SMOTE和SVM过采样方法使用的是Python库imbalance-learn package中的代码，分类器选用支持向量机，核函数采用高斯核，使用Python库svm中SVC代码实现。

表1 实验所用数据集

目前，评价不平衡数据分类问题的标准有F-value和G-mean等，其计算过程均由混淆矩阵构造得到。混淆矩阵的定义如表2所示。

F-value：

表2 混淆矩阵

G-mean同时考虑了多数类和少数类的分类准确率，可用于衡量整体分类效果。

表3给出了不同过采样方法处理后使用支持向量机分类得到的F-value值和G-mean值。

表3粗体部分给出了同组数据集中F-value和G-mean值相对较高的采样方法。通过对比可以看出，本文所提方法在不平衡率较高的数据集中，F-value值相对较高，表示其对少数类的分类效果较好，在不平衡率较低的数据集中，F-value值与其他方法差异较小甚至基本持平。总体来看，所提方法能有效提高少数类分类准确率。从所有数据集的G-mean结果来看，本文所提方法提高了不平衡数据的整体分类性能。

5 结束语

本文提出了一种融合数据集特征边界几何信息的过采样方法。该方法在检测得到可构造特征边界点的少数类样本后，结合其所属少数类聚簇合成新样本，在保留分类边界信息的同时，减少了噪声点的引入。在人工数据集和UCI数据集上开展的实验证明所提方法有效改善了不平衡数据的整体分类性能，提高了少数类样本的分类准确性。本文方法在个别数据集上对少数类样本分类的一般表现可能与可构造的特征边界点数量较少有关，导致参与合成新样本的少数类样本点数量减少。在今后的工作中，将对此问题进一步深入研究，使算法更全面地融合特征边界信息。

表3 不同过采样方法下的分类性能比较