面向不平衡数据集的改进SMOTE算法

董永峰，董彦琦，张亚娟

（1.河北工业大学 人工智能与数据科学学院，天津 300401；2.河北省大数据计算重点实验室，天津 300401）

0 引言

不平衡数据是指数据集中某一类别的样本数量明显少于其他类别的样本数量，其中样本数量较少的一类称为少数类，样本数量较多的一类称为多数类。在实际应用中，不平衡数据是经常存在的，特别是在网络安全、医疗诊断、客户流失预测等领域[1]。以随机森林为代表的传统分类器在处理不平衡数据分类问题时，分类结果往往会倾向于多数类，而忽略少数类，从而导致算法性能大幅下降[2]。为了提高分类器对不平衡数据的分类性能，学者们主要从算法和数据层面进行了改进。算法层面的改进主要是结合不平衡数据集的内在特征，在现有分类算法基础上进行改进或设计新的分类算法，以适应不平衡数据进行分类的需要，主要包括代价敏感学习[3]、单类学习[4]和特征选择[5]等方法。数据层面的改进主要是结合重采样技术，使不平衡数据集在训练之前就趋于平衡，再利用分类器进行训练，重采样技术主要包含欠采样[6]和过采样[7]两种方法。以上方法中使用最为广泛的是文献[8]中提出的SMOTE算法，该算法在少数类样本及其近邻样本之间合成新样本，但SMOTE算法没有对少数类样本进行区别性的选择，因此在合成新样本时存在盲目性与边缘化等问题，众多学者对其进行了改进。

文献[9]中提出了Borderline-SMOTE算法，该算法只对决策边界附近的少数类样本进行过采样，从而改善了SMOTE的盲目性，但会丢失其他少数类样本所包含的信息。文献[10]中提出了ADASYN算法，该算法规定每个少数类样本合成新样本的个数与模型学习该样本的困难程度成正比，但学习难度越大的样本是噪声的可能性也越大，在其周围生成新样本会进一步放大数据集中的噪声。文献[11]中提出了ISMOTE算法，该算法在以少数类样本为中心，以该样本到其最近邻样本之间的距离为半径的n维球体内进行过采样，从而消除了少数类样本分布的限制，但在插值的过程中容易造成新样本与多数类样本的重叠，进一步加大分类难度。文献[12]中提出了KM-SMOTE算法，该算法对数据集中的少数类样本进行聚类，在簇心及对应簇样本之间生成新样本，但在插值的过程中会使新样本集中分布于簇心周围，导致样本之间的重叠。为了克服SMOTE算法及以上改进算法的不足，论文基于聚类划分和重心牵引的思想提出了一种改进算法BSMOTE，该算法有效改善了SMOTE算法生成新样本时存在的盲目性和边缘化的问题，从而保证了新样本的有效性，同时由于新样本的加入使不平衡数据集在训练之前就趋于平衡，再利用随机森林进行训练，从而提升了传统分类器在不平衡数据集上的分类性能。

1 SMOTE算法

合成少数类过采样技术（Synthetic Minority Over-sampling Technique，SMOTE）是基于传统随机过采样的一种改进算法，该算法避免了数据集内少数类样本大量重复出现，有效降低了过拟合问题出现的机率。SMOTE算法流程如下。

输入：不平衡数据集D，近邻数K，采样率N。

输出：平衡数据集Dnew。

1）筛选出原始数据集D中的全部少数类样本，构成少数类样本集Dmin，其余样本构成多数类样本集Dmaj。

2）对于Dmin中少数类样本xi，计算它到Dmin中所有样本的距离，得到其K近邻，从其K近邻中任取一个样本xj，xi与xj之间的距离d(xi,xj)计算公式如式（1）所示：

式中：xi=(xi1,xi2,…,xin)，xj=(xj1,xj2,…,xjn)表示2个n维属性的数据样本。

3）计算样本xi与xj各个对应属性上的属性值之差，将差值乘以区间（0，1）内的一个随机数，再加上样本xi各个对应的属性值，即可生成一个新的少数类样本xnew，具体计算公式如式（2）所示：

式中：rand（0，1）表示区间（0，1）上的一个随机数。

4）循环执行步骤2）～3），算法终止条件为达到预先设置的采样倍率N，将生成的全部少数类样本加入原始数据集D中，得到平衡数据集Dnew。

2 SMOTE的改进算法：BSMOTE

2.1 BSMOTE算法原理

SMOTE算法认为在距离相近的少数类样本之间生成的新样本仍为少数类，为了确保新样本的有效性，未改进的SMOTE算法在插值过程中需要找到少数类样本的K个最近邻，并在其与随机的一个近邻样本之间生成新样本，但该算法在插值过程中未考虑少数类样本的分布，具有一定的盲目性。SMOTE算法生成新样本的示意图如图1a）所示，图中圆形表示多数类样本，空心五角星表示少数类样本，实心五角星表示新合成的少数类样本。假设采用SMOTE算法对少数类样本A进行过采样，该算法首先在样本A的5个近邻少数类样本中随机选择了样本B，然后在样本A和样本B之间线性插值生成新的少数类样本A1，但从图中可知新样本A1位于多数类样本较多的区域，因此该样本是一个噪声样本，并不会有助于分类算法进行训练。

同时，SMOTE算法还存在样本分布边缘化的问题，如果一个少数类样本处在多数类与少数类样本的决策边界，则由此样本和近邻样本生成的新样本也将处在这个边界，且越来越边缘化。如图1a）所示，少数类样本B和少数类样本C均处在多数类与少数类样本的决策边界，采用SMOTE算法在2个样本之间生成的新样本C1也处在这个边界，从而将边界模糊化，加大了分类算法进行分类的难度。

图1 a）SMOTE算法生成新样本的示意图；b）BSMOTE算法生成新样本的示意图Fig.1 a)Schematic diagram of SMOTE algorithm generating new samples;b)Schematic diagram of BSMOTE algorithm generating new samples

针对以上2个问题，论文提出了改进算法BSMOTE，该算法首先采用K-means聚类算法对少数类样本进行聚类产生k个簇，以此确定少数类样本的分布情况，同时基于距离的聚类划分使得簇中样本的相似性较高，故该算法省去了SMOTE算法求解少数类K近邻的步骤，直接在各个簇中选择少数类样本以生成新样本。然后在聚类产生的各个簇Ci(i=1,2,…,k)中随机选取3个样本点构造三角形，计算其重心样本数据，在三角形重心与顶点之间随机生成新的少数类样本，新样本会向所在三角形的重心位置靠拢并远离决策边界，从而使新样本的生成过程具有一定的方向性。最后将不断生成的新样本加入到原始数据集D中以降低不平衡率，直至数据集中的少数类样本数量不小于多数类样本数量时终止算法，得到平衡数据集Dnew。

BSMOTE算法生成新样本的示意图如图1b）所示，图中圆形表示多数类样本，空心五角星表示少数类样本，实心五角星表示新合成的少数类样本，椭圆虚线表示BSMOTE算法采用K-means对少数类样本聚类得到的2个簇，生成新样本仅在各个簇中进行，由此避免了SMOTE算法生成新样本的盲目性问题。图中的实心点表示少数类样本B、C、D所构成三角形的重心，BSMOTE算法在三角形重心与顶点之间生成新的少数类样本，因此生成的新样本会向重心位置靠拢，从而远离决策边界，有效克服了SMOTE算法生成新样本的边缘化问题。

图2 BSMOTE算法流程图Fig.2 Flow chart of BSMOTE algorithm

2.2 BSMOTE算法设计

在样本类别不平衡问题中，通常将数量较少的少数类样本视为正类样本，数量占优的多数类样本视为负类样本。BSMOTE算法流程图如图2所示，算法流程如下。

输入：不平衡数据集D，聚类个数k。

输出：平衡数据集Dnew。

1）筛选出原始数据集D中的正类样本，构成正类样本集Dmin，其余样本构成负类样本集Dmaj。

2）在正类样本集Dmin中随机选取k个样本，作为首次聚类的中心点。

3）采用公式（1）计算其余各样本到每个聚类中心点的距离d(xi,xj)，并将该样本划分到与之最近的聚类中心所在的簇Ci(i=1,2,…,k)中。

4）重新计算各簇的聚类中心，重复Step2调整所有样本的划分，聚类中心更新迭代公式如式（3）所示：

式中：mi为簇Ci的聚类中心；|Ci|为簇Ci的样本数量；xp=(xp1,xp2,…,xpn)表示簇Ci内n维属性的数据样本。

5）计算正类样本集Dmin中全部样本及其所属簇的聚类中心之间距离的平方和，即误差平方和SSE，计算公式如式（4）所示：

6）迭代执行步骤3）～5），直到聚类划分不再发生变化或者SSE值收敛，至此聚类结束得到k个簇Ci(i=1,2,…,k)。

7）在任意一簇Cj中随机选取的3个正类样本xr，xs，xt构造三角形，计算其重心样本向量xB，重心样本xB计算公式如式（5）所示：

式中：xB表示由xj(j=r,s,t)所构成三角形的n维重心向量。

8）在三角形重心xB与顶点xj(j=r,s,t)之间随机生成一个新的正类样本xnew，将其加入正类样本集Dmin，生成的新样本xnew计算公式如式（6）所示：

式中：xnew表示由三角形顶点xj(j=r,s,t)及重心xB生成的n维新向量。

9）在k个簇Ci(i=1,2,…,k)中循环执行步骤7）～8），算法终止条件为正类样本个数 |Dmin|不小于负类样本个数 |Dmaj|。

10）合并正类样本集Dmin与负类样本集Dmaj，得到平衡数据集Dnew。

3 实验设计与结果分析

3.1 实验数据

论文采用KEEL数据库的7个不平衡数据集进行实验，分别为new-thyroid2，ecoli1，ecoli2，ecoli3，glass0，wisconsin和vehicle0。表1中描述了数据集的基本特征，其中包括总样本个数、属性个数、负类样本个数、正类样本个数和不平衡比率。

3.2 实验设计

论文在Window 10（64位）操作系统，Intel Core i7-7700HQ CPU@2.8 GHz，8GB RBM的环境下使用Python进行实验。为了验证BSMOTE算法的有效性，对比了原始数据集和经过SMOTE算法、ADASYN算法、Borderline-SMOTE（简记为BL-SMOTE）算法、ISMOTE算法以及KM-SMOTE算法处理后的数据集对分类器分类性能的影响。分类器采用传统机器学习算法随机森林（Random Forest，RF），该算法是一个由决策树分类器集合所构成的集成学习模型，有着良好的泛化性和鲁棒性。RF首先采用Bootstrap有放回抽样的方法从数据集D中随机采样，生成s个子数据集Di(i=1,2,…,s)；然后基于每个Di训练决策树模型hi(x)，在树生成的过程中，随机从M个属性中选择m个属性参与节点分裂（m＜M且m值恒定）；而后计算每个属性值的基尼系数，选择基尼系数最小的属性作为分裂节点进行分裂，由此生成s棵决策树；最后采用多数表决机制集成s棵决策树的预测结果得到待测样本x的预测标签。在本实验中，SMOTE、ADASYN和BL-SMOTE中正类样本的近邻个数K为5，KM-SMOTE和BSMOTE中正类样本的聚类个数k为5，森林中决策树的数量s为100，每棵决策树选用的属性数量m为log2M+1。

表1 数据集特征Tab.1 Data set features

3.3 评价指标

对于不平衡数据集的二分类问题，传统的性能评价指标准确率、灵敏度、特异度和查准率并不能很好地反映出一个分类算法的性能，论文将选取不平衡数据分类的常用评价指标G-mean值、F-measure值和ROC曲线的量化标准AUC值来反映模型性能的优劣，为方便指标描述，首先建立混淆矩阵如表2所示。

其中，TP（True Positive）表示模型正确分类的正类样本数量，FN（False Negative）表示模型错误分类的正类样本数量，FP（False Positive）表示模型错误分类的负类样本数量，TN（True Negative）表示模型正确分类的负类样本数量。

几何均值（G-mean）综合反映了算法模型对正、负两类样本的分类性能，计算公式如式（7）所示：

表2 二分类问题混淆矩阵Tab.2 Confusion matrix of binary classification problem

只有当正、负两类样本的分类精度都处于较高的水准时，G-mean才会较大，该指标的数值越大，模型的总体分类效果越好。

正类检验值（F-measure）综合反映了算法模型对少数类样本的分类性能，计算公式如式（8）所示：

该指标的数值越大，模型对少数类样本的分类效果越好。

受试者工作特征曲线（Receiver Operating Characteristic，ROC）上点的坐标通过模型在获取分类结果时的概率阈值进行计算，不同的概率阈值对应不同的坐标点，其中点的横坐标表示负类样本分类错误的概率（False Positive Rate，FPR），点的纵坐标表示正类样本分类正确的概率（True Positive Rate，TPR），FPR和TPR计算公式分别如公式（9）～（10）所示：

ROC曲线下面积的大小称为AUC（Area Under the Curve）值，是通过ROC曲线来评判模型分类效果的量化标准，当AUC值等于0.5时表示该算法的分类性能等同于完全随机分类，该指标的数值越大，模型的分类效果越好。

3.4 结果分析

实验结果取100次运行结果的平均值，无重采样处理的随机森林和基于6种重采样算法的随机森林在不同数据集上的G-mean值、F-measure值和AUC值如表3～5所示，表格中加粗数据为各个性能评价指标在每个数据集上取得的最优值，G-mean值、F-measure值和AUC值的对比图如图3～5所示。

表3 不同数据集上的G-mean值Tab.3 G-mean values on different data sets

表4 不同数据集上的F-measure值Tab.4 F-measure values on different data sets

表5 不同数据集上的AUC值Tab.5 AUC values on different data sets

从表3～表5和图3～图5中可以看出：

1）在大部分不平衡数据集上，6种重采样算法均有效提升了RF的分类性能，不过在glass0数据集上，基于ADASYN算法和KM-SMOTE算法的RF表现不是很稳定，F-measure值和AUC值比未经过重采样算法处理的RF所得结果更低。

2）在new-thyroid2、ecoli1、ecoli3、glass0和vehicle0数据集上，BSMOTE算法与其他重采样算法相比具有更好的不平衡数据处理能力，各项指标值均达到最优，最大程度上提升了RF在不平衡数据上的分类性能。

3）在ecoli2数据集上，BSMOTE算法的G-mean值和AUC值达到最优，F-measure值比KM-SMOTE算法略低0.43%，总体上差距不大。同时，BSMOTE算法在该数据集上对RF的提升程度最大，G-mean值、F-measure值和AUC值分别提高了20.61%、22.36%和24.34%。

4）在wisconsin数据集上，BSMOTE算法的AUC值比ISMOTE算法低0.98%，不过G-mean值和F-measure值均达到最优，保证了正类样本的分类精度。

5）在全部数据集上，基于BSMOTE算法的RF的分类性能均优于传统RF，G-mean值、F-measure值和AUC值平均提升了11.71%、11.69%和12.81%，证明了BSMOTE算法对RF进行优化的有效性。

图3 G-mean值的对比图Fig.3 Comparison graph of G-mean values

图4 F-measure值的对比图Fig.4 Comparison graph of F-measure values

图5 AUC值的对比图Fig.5 Comparison graph of AUC values

通过上述分析可以看出，基于SMOTE的改进算法BSMOTE有效解决了不平衡数据分类的问题，同时改善了SMOTE算法合成新样本时的盲目性与边缘化，提升了传统分类器随机森林在不平衡数据集上分类性能，从而证明了BSMOTE是一种有效的改进算法。

4 结论

论文针对SMOTE算法生成新样本时存在的盲目性和边缘化的问题，提出了一种改进算法BSMOTE，该算法通过聚类划分和重心牵引的思想保证了新样本的有效性，同时由于新样本的加入使不平衡数据集在训练之前就趋于平衡，再利用随机森林分类器进行训练，从而有效提升了分类器对正类样本的分类精度。最后通过与5种重采样算法在7个不平衡数据集上进行对比实验，验证了BSMOTE算法在解决不平衡数据分类问题中的优势。