优化合成样本分布的加权过采样方法

张忠林，赵喆梅，马海云

（1.兰州交通大学电子与信息工程学院，兰州 730079；2.天水师范学院电子信息与电气工程学院，甘肃 天水 741001）

0 引言

随着大数据时代的到来和数据采集系统的不断完善，不平衡数据处理已成为学术界和应用领域的研究热点。传统的分类算法对不平衡数据进行分类使得类分布向多数类严重倾斜，容易产生错误的分类结果，这会误导人们做出错误的判断从而造成不可挽回的损失。因此，最大限度提高少数类样本分类精度是很多学者的研究目标。在分类任务中处理数据不平衡问题的方法可分为以下两个层面：算法层面和数据层面。算法层面的方法主要是从根本上改进现有的分类算法，包括集成学习[1]、代价敏感等[2,3]。集成分类器的性能往往优于单个分类器的性能，常见的集成方法有提升（Boosting）[4]和袋装（Bagging）[5]，随机森林（Random Forests）[6]是袋装的一个变种。代价敏感实质上是为错分到多数类的少数类赋予更大的错分代价[7]，降低少数类的误分率。数据层面的方法指通过改变样本数量来处理数据不平衡问题，有两种方法：合成新的少数类样本的过采样[8]和删除部分多数类样本的欠采样[9]。相比过采样，欠采样在删除样本的过程中可能会丢失一部分关键信息，降低了分类器的泛化性能。

近年来研究者更多地关注过采样方法。过采样方法中最经典的方法是Chawla 等（2002）[10]提出的SMOTE 算法（Synthetic Minority Oversampling Technique），该算法通过在两个已有少数类样本之间插值来生成新的少数类样本。SMOTE算法虽然提高了少数类的预测精度，但在合成新样本时没有区别地选择每个样本，当少数类样本个数较少并含有较多噪声信息时，SMOTE算法会受近邻随机性干扰，易合成冗余样本和噪声样本。针对SMOTE 算法的局限性，文献[11]提出了Borderline-SMOTE 算法，此算法应用k近邻算法判断少数类样本位置，认为少数类边界处的样本含有更重要的信息，只在少数类边界处应用SMOTE 合成新的样本。He 等（2008）[12]提出一种基于少数类样本分布的自适应过采样算法（Adaptive Synthetic Sampling Method，ADASYN），该算法根据少数类样本的学习复杂程度来确定每个少数类样本需合成新样本的个数，能有效提升分类器的分类性能，但该方法易受离群点影响而生成代表性不足的少数类样本。Douzas 等（2018）[13]提出基于K-means 聚类的过采样方法K-means SMOTE，该算法可以有效改善类不平衡问题，但其采样结果受K-means 聚类效果的影响，易放大少数类样本的误差，降低分类器分类性能。

上述过采样方法基于不同的侧重点来处理不平衡数据，但这些方法在选择种子样本时仍存在一定的不足。基于此，本文提出了一种根据权重选择种子样本，优化生成样本分布的方法，使合成的新样本更有类别代表性，有利于分类器识别少数类样本边界。

1 理论基础

1.1 SMOTE算法

2002 年Chawla 等提出了SMOTE 算法[10]，该算法是处理不平衡数据问题最经典的过采样方法之一，避免了随机过采样存在的过拟合风险。这项技术产生了人工样本，而不再仅仅是复制已有的样本。如下页图1所示，这是通过线性插值一个随机选择的少数类样本和它邻近的少数类样本来实现的。SMOTE算法执行三个步骤来生成新的样本。首先，选择一个随机的少数类样本a；然后，在其k个邻近的少数类中，随机选择样本b；最后，通过对两个样本进行插值，生成一个新的样本x=a+w(b-a),其中，w为在区间[0,1]中随机取的权重。

图1 SMOTE线性插值一个随机选择的少数类样本及其k=6 的最近邻

1.2 WKMeans算法

聚类是将一组对象划分为多个类的过程，使同一聚类中的对象比不同聚类中的对象更相似。K-means 算法[14]由于其原理比较简单、收敛速度快、容易实现等优点被广泛应用。但K-means算法由于对所有的特征都一视同仁，因此在聚类过程中无法区别不同特征的重要性。因此Huang 等（2005）[15]提出了一种改进的K-means 算法，即WKMeans 算法，它可以根据特征属性在聚类中的重要性对特征自动加权，该方法基于迭代K-means算法过程中的当前划分，根据聚类内聚类的方差计算每个变量的新权值，新权值用于确定下一次迭代中对象的聚类成员关系。在算法收敛时找到最优权值，权值越大表示该特征对聚类结果越重要。WKMeans算法的目标函数为：

其中，U是簇分配矩阵；Z是簇中心矩阵；W是权重矩阵；ui,l表示将样本i分配到簇l中；为权重参数，β控制权重W的分布；xi,j表示各目标点；zl,j表示各聚类中心；k为簇数；n为各聚类簇；d是数据集维数；d(xi,j,zl,j)为目标点到聚类中心的距离。

其中，Dj表示所有样本点在第j个特征属性上的距离和，d(xi,j,zl,j)=(xi,j-zl,j)2。

各个参数服从的约束条件为：

1.3 随机森林算法

随机森林算法是一种基于决策树的集成算法，通过添加基本模型的预测来做出决定。训练样本通过自助抽样获得，且每个基本模型都是一个简单的决策树。算法步骤为：首先，对样本集自助抽样生成训练集；然后，在生成的训练集上随机选择部分特征构建决策树；最后，采用投票的方式得到模型的输出：

其中，x为数据集；C为类别数；T为决策树数量；ht(x)是决策树t的模型；I(·)为指示函数，参数为真时取值为1，否则为0。

随机森林模型整合了每棵树的预测，从而降低了模型的误差。此外，因为该模型具有泛化能力较强、能够容忍少量的异常值和缺失值、训练速度快等优点，因此在机器学习中被广泛使用。图2为随机森林模型示意图。

图2 随机森林模型

2 基于WKSMOTE和随机森林的分类模型

2.1 WKSMOTE方法思想

针对原有过采样方法在合成新样本时没有区别地选择每个样本的问题，本文提出了根据权重选择种子样本，优化合成样本分布的加权过采样方法。应用特征加权的聚类算法WKMeans对原数据集进行预处理。对少数类样本的划分，以少数类样本的近邻含有多数类样本的个数Δ为阈值标准，将少数类样本划分为两类：安全样本和边界样本。对边界样本赋予较大的权重，安全样本权重相对较小，根据样本权重计算边界样本和安全样本分别需要合成的样本个数。根据安全样本和边界样本到P个多数类样本间的欧氏距离赋予少数类样本中每个样本权重，距离越小，则样本越靠近决策边界，权重越大，合成越多新样本，从而得到每个少数类样本需要合成新样本的个数。应用SMOTE算法依照每个少数类样本需要合成新样本个数对少数类样本进行过采样。最后将采样过的均衡数据集在随机森林分类器中进行训练。

2.2 WKSMOTE方法描述

设不平衡数据集为D，训练集为T，测试集为S，T中少数类样本个数为Tmin，多数类样本个数为Tmaj。

WKSMOTE方法的步骤如下：

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

步骤2：应用WKMeans算法对T中样本进行预处理。

步骤3：计算训练集T需要合成的样本数n_to_sample=Tmaj-Tmin。

步骤4：以少数类样本的k 近邻含有多数类样本的个数Δ为阈值标准，将少数类样本划分为安全样本T_safe和边界样本T_border。

对于训练集Tsample={(xi,yi)|i=1,2,…,p,yi∊{0,1}}，xi是特征为i的样本，yi是类标签。集合Tmin={(xmin,i,yi)|i=1,2,…,p,yi=0}是Tsample中的少数类样本，集合Tmaj={(xmaj,i,yi)|i=1,2,…,p,yi=1}是Tsample中的多数类样本，对于任意一点P∊Tmin，若满足sum(y=1)≤sum(y=0)，则称P点为边界样本点；若满足sum(y=1)>sum(y=0)，则称P点为安全样本点。

步骤5：统计安全样本和边界样本个数nT_safe、nT_border，分别取其倒数为bsafe、bborder，则式（5）为安全样本区域权重，式（6）为边界样本区域权重。

步骤6：计算T_border和T_safe分别需要合成的样本个数n_T_safe（式（7））和n_T_border（式（8））。

步骤7：计算T_border和T_safe中每个样本到P个最近的多数类样本的欧氏距离，式（9）为样本i和样本j间的欧氏距离，其中，C为特征数。

步骤8：计算步骤7 中P个距离之和Di，设权重为1Di。

步骤9：分别计算T_border和T_safe中所有样本权重之和BNDi和SNDi。

步骤10：根据式（10）和式（11）计算T_border和T_safe中每个样本需要合成的样本个数NBe和NSe。

步骤11：对于Tmin中的每个样本xi, 应用SMOTE 算法按照每个样本需要合成新的样本个数合成新样本Tnew。

步骤12：将合成的新样本Tnew加入训练集T中生成新的数据集Dnew。

2.3 模型构建

本文利用WKSMOTE方法合成新样本，并将其加入原训练集中来改善数据集不平衡问题，使用随机森林分类器进行学习，建立WKSMOTE-随机森林模型。整体流程如图3所示。

图3 整体算法流程图

具体过程如下：（1）输入数据集，应用WKSMOTE方法合成新的少数类样本，并将其加入数据集中，构成新的数据集。（2）利用随机森林分类器对数据集进行训练，并用网格搜索方法进行参数寻优，得到分类模型。（3）用测试集进行测试，验证模型分类性能。

在用SMOTE 方法合成新样本时，每个少数类样本生成的新样本个数相同，导致合成了一些类别区分不大的样本，进而影响分类模型训练结果。由于每个样本区分类别的价值不一样，决策边界处的样本更有利于正确区分类别，因此，本文通过建立WKSMOTE-随机森林模型，改进SMOTE方法，在少数类的类边界处合成更多新样本，强化决策边界，提高少数类样本的分类性能。随机森林作为经典集成分类算法，将多个弱分类器分类结果投票选择组成一个强分类器，优于单分类做出的预测。在随机森林分类过程中采用网格搜索方法选择最优参数，提高预测准确性。

2.4 WKSMOTE方法时间复杂度分析

WKSMOTE 方法时间复杂度主要由步骤2、步骤4、步骤7、步骤11决定。在步骤2中，WKMeans算法和KMeans时间复杂度相似，约减后都为O(n)。步骤4中将样本划分为边界样本和安全样本是基于KNN 算法进行的，时间复杂度为O(dn2),d是样本特征数。步骤7计算每个正类样本与每个负类样本间的欧氏距离并求出p个距离最小值时间复杂度为O(pTminTmaj) ，其中，p是常数且Tmin

3 实例分析

3.1 实验数据集

为了评价本文方法的有效性，选取UCI机器学习库中的7 个不平衡数据集wave、abalone、car、haberman、yeast、ecoli、spect 和5 个KEEI 机器学习库中的不平衡数据集balance、pima、phoneme、page-blocks、winequality 进行实验验证。对于包含两个以上类的数据集，将其中样本数目较少的几类标记为少数类，并将其他所有样本合并到多数类中。数据集具体信息如表1 所示。最后一列的IR 值表示数据集不平衡比率，本文选取数据集的不平衡比率在1.17至12.49之间。

表1 数据集信息

3.2 评价指标

在对不平衡数据进行分类时，通常称数目多的样本为负样本，数目少的样本为正样本。在非平衡数据学习中，主要目标是提高正样本的分类性能，同时对负样本保持合理的性能。分类评估指标将每个观测值的真实隶属度与分类器的预测值进行比较，对于分类问题，混淆矩阵通常用来记录样本正确或错误分类的结果。混淆矩阵如表2所示，其中，TP为正确分类的少数类样本数；TN为正确分类的多数类样本数；FP 为误分为少数类的多数类样本个数；FN为误分为多数类的少数类样本个数。

表2 混淆矩阵

对于均衡数据集，常用准确率（式（12））来评价分类性能，但用它来评价非均衡数据集的分类是不合理的。为此，有学者提出了一些新的不平衡数据分类评价指标，其中最常用的评价指标是F-measure，F-measure同时考虑了准确率（Precision）和召回率（Recall），是一个较全面的评价指标。Kubat 等（1997）[16]提出的G-mean 值主要关注少数类样本和多数类样本的召回率情况，只有多数类样本分类精度和少数类样本分类精度都比较大时，G-mean 才能比较大。Roc 曲线是以False Positive Rate（FPR）为横坐标轴、True Positive Rate（TPR）为纵坐标轴的曲线，其下方的面积用数值表示就是AUC（Area Under the Roc Curve）。马修斯相关系数（Matthews Correlation Coefficient，MCC）考虑了TP、TN、FN、FP，是一个比较综合的指标，描述了预测分类与实际分类之间的相关系数。

本文采用F-measure、G-mean 和MCC 值来评价不均衡数据集的整体分类性能，采用AUC 值评价分类模型的稳定性。各分类评价指标计算如下：

β为调节Precision 和Recall 相对重要性的系数，当β=1时，即F1-Score。其中：Precision=，Recall=。

其中，specificity=TN/（TN+FP）。

3.3 结果分析

为了验证WKSMOTE 方法的有效性，本文将其与SMOTE[10]及现有的改进SMOTE 算法Borderline SMOTE[11]、ADASYN[12]、SVMSMOTE 和Kmeans SMOTE[13]在balance、pima、wave、abalone、car、haberman、yeast、ecoli、spect、phoneme、page-blocks、winequality 12 个数据集上进行实验验证，上述方法都使用随机森林分类器。本文为保留类别比例，用分层划分将数据集按7：3的比例划分为训练集和测试集，并使用五折交叉验证方法得到最终的分类结果。

本文实验环境为：Inter i7-7500u，4核CPU，主频2.70GHz，内存4G，操作系统为Windows 10 64 位，仿真环境为Python 3.7。实验中，k的取值为5；WKMeans 算法中方聚类簇数设为5；最近欧氏距离P取值为5。下页表3至表5分别列出了6 种方法在8 个不均衡数据集上的F-measure、G-mean 和AUC 值，最后一行为每种方法在8 个数据集上的平均提高率，倒数第二行为每种方法在8个数据集上的平均结果。

表3 6种方法在8个数据集上的F-measure对比

表4 6种方法在8个数据集上的G-mean对比

表5 6种方法在8个数据集上的AUC对比

由表3 至表5 可知，本文提出的WKSMOTE 方法与其他5种方法相比，在处理不均衡数据分类问题上有了一定的提升。与SMOTE方法相比，F-measure值平均提高率为2.04%，G-mean 值平均提高率为2.62%，AUC 值平均提高率为1.01%。WKSMOTE方法相比SMOTE方法，在决策边界合成更多新样本，进而在一定程度上更具优势。与Borderline SMOTE 方法相比，WKSMOTE 方法在yeast 数据集上的F-measure 值和在winequality 数据集上的AUC 值略低，在haberman数据集上的F-measure值和AUC值提升最明显，分别提高了16.03%和8.93%；在balance 数据集上G-mean 值提高了5.02%。WKSMOTE 方法相比Borderline SMOTE方法在少数类样本非边界区域也合成了部分新样本，使生成样本分布更合理，实验效果相对更好。与ADASYN 方法相比，在balance 数据集上，F-measure 值没有取得最佳结果，在其他两个指标上效果最佳，尤其在haberman数据集上，AUC值提升了10.36%。WKSMOTE方法相比ADASYN方法，在权重分配上更优化，使合成的样本更有代表性，提高了分类准确率。与SVMSMOTE 方法相比，WKSMOTE 方法在8 个数据集上的F-measure 值和AUC值相差不大，但均有所提高，在haberman数据集上提高率达到最大，F-measure 值提高了7.2%；AUC 值提高了3.13%。和Borderline SMOTE 方法相似，SVMSMOTE 方法也只是对边界样本进行采样，存在一定的局限性。WKSMOTE方法和Kmeans SMOTE方法在各个数据集上的分类性能比较接近。WKSMOTE方法相比Kmeans SMOTE方法，F-measure 值平均提高率为1.17%，G-mean 值平均提高率为1.08%，AUC 值平均提高率为0.60%。Kmeans SMOTE 方法相比其他4 种方法的平均提高率较低。总体来说，WKSMOTE 方法在大部分数据集上的分类性能优于其他5种方法。印证了本文所提采样方法在F-measure、G-mean、AUC 这3 个评价指标上分类效果有一定的提升。

由6种方法在8个数据集上MCC值的柱形图（图略）可以看出，WKSMOTE方法相比其他5种方法在MCC评价指标上有了一定的提升，尤其在haberman 数据集上提升幅度较大，相比5种方法中效果最好的Kmeans SMOTE 算法，WKSMOTE 方法提高了8.57%。再次印证了本文所提采样方法的分类效果有一定的提升。

为了进一步衡量本文过采样方法的性能，与文献[17]中的NodeStrength-SMOTE 方法进行实验对比，表6 为两种采样方法在C4.5 决策树上的训练结果，参数设置同文献[17]。表6结果显示：在分类器C4.5决策树上，WKSMOTE方法在wave 数据集上的G-mean 值和spect 数据集上的F-measure 值低于NodeStrength-SMOTE 方法，其他分类结果均优于对比方法。综上所述，WKSMOTE方法可以有效提升分类效果，原因在于该方法生成的样本更具代表性，有利于少数类样本的正确分类。

表6 两种方法在4个数据集上的性能对比

下页表7 为3 种模型在8 个数据集上的F-measure、G-mean、AUC 和MCC 值对比，其中的最大值加下划线表示。由F-measure、G-mean和MCC值可得，WKSMOTE-RF模型在多个数据集上取得了最优值，说明对于经WKSMOTE方法采样后的数据，采用随机森林作为分类器更利于样本分类。从AUC 值看，在特征维度较高的page-blocks 和winequality 数据集上，WKSMOTE-RF 模型没有WKSMOTE-SVM 模型稳定，在其他6 个数据集上都是最稳定的，由此可知WKSMOTE-RF模型更适用于低维数据集。

表7 3种模型在8个数据集上的性能对比

3.4 各采样方法运算复杂度对比

下页表8 为6 种模型在8 个数据集上的运行时间，其中的最小值加下划线表示。6 种模型都以随机森林为分类器，因此其运行时间差异主要在采样方法上。聚类算法WKMeans 对整体运行时间影响很小，所以影响过采样方法运行时间是在样本的分配及合成新样本环节。本文方法WKSMOTE在对样本进行划分之前应用WKMeans算法进行聚类，使得相似的样本更相近，减少了样本分配和合成新样本的时间，进而减少了整体模型运行时间。从表8可知，随着数据集规模增大，运行时间大幅度增加，在balance、phoneme、ecoli、yeast、page-blocks 和winequality 数据集上，WKSMOTE-RF 模型相比于其他5 种模型运行时间都有所减少，在规模较小的数据集上运行时间和其他5种模型相近，随着数据规模增加，运行时间减少幅度较大。在abalone和haberman数据集上，WKSMOTE-RF模型运行时间大于Borderline SMOTE-RF，是由于WKSMOTE 方法在安全样本区域需要合成的样本远多于在边界样本区域需合成样本，而Borderline SMOTE 只在边界合成新样本，学习规模小于WKSMOTE方法。winequality数据集总的数据量小于phoneme数据集，但除WKSMOTE-RF模型外，其他5 种模型运行时间却大于phoneme 数据集，是因为winequality 数据集的不平衡度更高，需要合成的新样本更多，所以花费时间更长。

表8 6种模型在8个数据集上的运行时间对比

4 结束语

针对传统过采样方法在生成样本分布上存在的不足，本文提出了一种优化合成样本分布的加权过采样方法，根据权重分配在少数类边界区域合成较多新样本，在安全区域也合成一定的新样本，强化了决策边界。实验结果表明，本文提出的WKSMOTE 方法与原有的过采样方法相比，在同样采用随机森林作为分类器对过采样得到的数据集进行学习的情况下，本文方法对不均衡数据集整体分类效果有一定的提升，有效地解决了数据失衡问题，改善了分类结果偏向多数类样本的问题。