赵锦阳 卢会国,2 蒋娟萍,2 袁培培 柳学丽

1(成都信息工程大学电子工程学院 四川 成都 610225) 2(中国气象局大气探测重点开放实验室 四川 成都 610225) 3(电子科技大学航空航天学院 四川 成都 611731) 4(南京财经大学信息工程学院 江苏 南京 210000)

0 引 言

随机森林RF[1]比单个决策树分类器有较高的分类精度和较低的预测误差，其适合多种环境，不需要剪枝，对噪声数据不敏感等众多优点，已在众多领域得到了广泛的应用；但和其分类器一样，数据集的非平衡程度会很大地干扰分类器的分类。在现实生活中，非平衡数据的少数类样本往往受到广泛关注，例如在金融欺诈领域，不安全的数据信息所占的比例很小，然而这些很少的数据会造成重大的后果[2]。因此对非平衡数据的准确分类已成为重要话题，如何提高随机森林对非平衡数据集的分类精度已受到业界人士的广泛关注。

黄衍等[3]通过比较随机森林和支持向量机在非平衡数据集分类问题上的性能，得出支持向量机在处理非平衡数据集要优于随机森林。根据随机森林的构造过程可知其对非平衡数据集分类差的原因在于随机森林使用Bagging随机选取训练集，因为原训练集为非平衡数据集，故少数类有较低的选中概率，进行多次循环之后，被选中的少数类势必与原始数据集的少数类在数量上有较大差别，这样使得训练出的森林过于依赖多数类样本，失去了代表性。对于面向非平衡数据集的随机森林，如何提高少数类样本被选中的概率，是优化森林算法的关键所在。

目前主要对数据层进行处理和改进分类器自身构建过程来提高分类器的预测精度。改进分类器自身算法主要涉及随机森林中单个决策树的生成，合理选择属性，使得森林中各决策树之间的关联度降到最低，同时使得各决策树充分生长。而数据层方面主要将原始数据进行预处理，筛选出需要的数据信息，并将处理后的数据与分类器算法相结合进行分类。

对于数据预处理方法，吴琼等[4]提出将NCL技术引入随机森林算法，对非平衡数据进行NCL处理，然后用随机森林算法对处理后的数据进行分类，结果表明改进后的随机森林算法分类效果更好。由上述面向非平衡数据集的随机森林分类差的原因，以及现有研究可知，对非平衡数据集进行预处理，可有效地提高随机森林的预测精度。目前比较常用的数据层处理方法是对数据进行重采样(欠采样和过采样)。欠采样方法是适当的选取一部分多数类样本(负类)，使得新数据集的多数类和少数类样本的个数处于均衡状态，由此可知选取的多数类样本可能会丢失有效信息，从而造成合成的数据集与原数据集相差很大，不具有代表性；过采样方法采用增加少数类样本(正类)的思想，使得原数据集中重要信息保留下来，合成的数据能够较好地表现出原数据的特征，因此在处理不平衡数据时，过采样技术成为了主流方法。

过采样技术中最为经典的是Chawla提出的SMOTE算法，其主要思想是找出数据集中少数类样本集，在少数类样本与其K近邻之间的连线上产生合成样本[5]。由其理论可知，SMOTE算法虽然增加了少数类样本个数，但只是不加分析的复制样本，并且在合成过程中也会出现重复问题，从而使得随机森林对合成后的数据集分类性能没有本质上的提高。

本文提出一种改进的算法——SCSMOTE算法，根据少数类样本与多数类样本的边界区分程度，得到合适的候选样本，并且计算出候选样本的中心，在候选样本与其中心连线上产生合成样本，从而达到数据集的平衡。

1 算法设计

本节结合SMOTE算法的思想，提出一种基于候选样本集中心的过采样技术方法。

1.1 SMOTE算法

SMOTE是过采样方法中的经典算法[6]，其主要思想基于k近邻算法，每个少数类样本确定k个近邻的少数类，然后在少数类样本与其近邻样本的连线上合成新的少数类样本，通常近邻参数k取5。

算法实现如下。

1) 对于每个正类样本P_i，在正类样本集中选取K个近邻样本，记为Q_k。

2) 按式(1)合成syn_i，其中g为确定合成样本位置的随机数，其值在(0,1)之间：

syn_i=P_i+g×(Q_k-P_i)

(1)

3) 将合成的syn_i样本添加到原始正类集中得syn_dat样本。

由上可知，如果一数据集正类样本边缘化严重，那么由于不加分析地在正类样本之间复制产生新样本，势必会使原本就边缘化的数据更加边缘化，从而使得边界更加难以区分。这种情况虽然在数量上改善了数据集的平衡性，但造成了随机森林算法进行分类时的难度。

本文认为边界样本在分类中比远离边界的样本更容易被错分。但由上述可知，在产生新样本时又不能刻意避开边界样本，因为一个类的边界样本或多或少会携带原始数据集的信息。因此本文根据少数类样本与多数类样本的边界区分程度进行分析，对于存在有危险区域(正类边界样本的k近邻样本中负类样本数量多于正类样本数量)的数据集[7]而言，当危险区域中的数据样本在全体正类样本个数占比较高时，在合成新样本时要尽量克服SMOTE算法不加分析复制边界样本的缺点，对危险区域样本进行合理控制，从而减少分类器对边界样本的错分率。对于有清晰边界的数据集而言，即危险区域的正类样本个数在全体正类样本个数占比较少，此时危险区域不具有代表性，要尽可能克服SMOTE算法过采样过程中模糊边缘的问题。

本文认为危险区域的正类样本数大于总正类样本数量的四分之一时，边界样本携带原始数据集的多数信息，分类器容易把边界样本中的正类样本判为负类样本。故在合成新样本时要对危险区域样本加大学习力度，并进行合理控制。此时计算出危险区域的样本中心，并把危险区域中的样本作为候选样本；对于危险区域的正类样本个数小于总正类样本数量的四分之一时，认为边界样本占据原始数据集的信息比重较小，此时计算全体正类样本的中心，把全体正类作为候选样本。用得到的候选样本和样本中心，得出一种新的学习算法：找出数据集的危险区域，若此区域中的正类样本能较好地代表整体正类样本，则把此区域作为候选样本(反之以全体正类样本为候选样本)，计算候选样本中心。在候选样本和候选样本中心的连线上产生新的正类样本，把产生的新样本合并到原始数据集中，从而使得数据平衡化。

1.2 非平衡数据集学习算法SCSMOTE

计算需要合成的正类样本数量并得到合适的候选样本，最后计算合成样本位置实现对非平衡数据集的平衡化处理。

1.2.1 正类样本数据的合成

设原始数据集T，其中负类样本集合N={N1,N2,…,Nnnum},Ni=(ni1,ni2,…,nir)，其中nnum表示负类样本数量，r代表样本特征个数；正类样本集合P={P1,P2,…,Ppnum}，Pi=(pi1,pi2,…,pir)，其中r代表样本特征个数，pnum表示正类数量。

定义1危险区域

定义2危险区域样本中心

危险区域样本中心是指上述危险区域集S数据空间的中心，Scenter是与样本维数相同的向量，计算公式表示为：

(2)

定义3正类样本中心

正类样本中心即正类样本的中心点，记为Pcenter，根据上述定义及向量的概念，可得：

(3)

根据上述定义，本文首先选择候选样本集，对于危险区域样本占比总正类样本数较大的原始数据集而言，处于边界的样本经常会被错分。因此选取危险区域的正类样本为候选样本集，此区域的样本中心为候选样本中心。对于危险区域样本占比较小的原始数据集而言，为了避免在合成人造数据时使边界区分度降低，选取总体正类样本为候选样本，正类中心为候选样本中心。根据SMOTE算法思想，此算法根据危险区域正类样本占比总正类样本数的大小，分别用式(4)、式(5)在候选样本与候选样本中心之间合成新样本。

Psynj=Si+rand(0,1)×(Scenter-Si)

(4)

式中：Si(i=1,2,…,dnum)为危险区域的正类样本，dnum为此区域的正类样本的总个数；

Scenter为此区域正类样本的中心点；

Psynj为合成的样本；

rand(0,1)用于确定合成样本在连线上的具体位置；

Psynj=Pi+rand(0,1)×(Pcenter-Pi)

(5)

式中：Pi(i=1,2,…,pnum)为正类样本，pnum为正类样本总个数；Pcenter为正类样本的中心点。

图1给出了SCSMOTE算法合成新样本的原理图，其中空心圆代表正类样本，正方形代表负类样本，三角形代表候选样本中心，实心黑点代表合成正类样本。其合成新样本的位置已在图中标示。P1样本的5个近邻分别是P2、N1、N2、N3、N4，可知其5个近邻中正类有1个，负类有4个，即把P1划分到危险区域；而对于P2而言，其5个近邻分别是P1、P3、P4、N1、N2，可知其近邻中正类个数多于负类个数，故不能把P2划分到危险区域。对每一个正类P_i进行上述过程，此时候选样本为危险区域的样本，计算出候选样本中心，在候选样本和候选样本中心之间产生新的少数类样本。

图1 SCSMOTE算法原理图

1.2.2 算法实现

在以上定义以及SMOTE算法的基础上，基于R语言开发环境实现算法。设程序中原始样本集合为X，target是数据集X的目标类属性的向量，K、C为近邻参数，用于标记指定样本的近邻个数，默认值为5。

算法1SCSMOTE(X,target,K,C)

1) 对于初始数据集X，计算并找出正类集合P_set，在整个初始集合X中对P_set中的每一个样本P_i根据k近邻算法原理计算其C个近邻。若其C个近邻类别中负类数量多于正类数量，且不全部为正类，则把此样本放入危险区域Danger集合中。

2) 统计Danger区域样本数量，当其小于(等于)总体正类数量的四分之一，即认为此时得到的危险区域不具有代表性，计算正类集合中心synP_center，把全体正类样本作为候选样本。

3) 当Danger区域样本数量大于总体正类数量的四分之一，计算危险区域集合的中心syn_center，把危险区域中的样本作为候选样本。

4) 计算需要合成正类个数的平衡因子sum_dup。

5) 按条件选择式(4)、式(5)确定合成样本syn_dat。

2 实验与结果分析

2.1 数据集

为了更好地验证算法的有效性，从UCI数据集中选择11个数据集作为验证集，本文将选取的数据集分为训练集和测试集，各数据集的基本信息见表1。

表1 各数据集样本分布

其中选取的数据集abalone_I来自UCI中abalone数据集，abalone数据集中的样本共有28个类别，人为将类别5作为正类样本，类别6作为负类样本。glass_I来自UCI中glass数据集，glass数据集中的样本共有7个类别，人为将类别5、6、7合成一类作为正类样本，其余样本合为一类作为负类样本。Yeast_I来自UCI中Yeast数据集，Yeast数据集中的样本共有10个类别，人为的将类别EXC作为正类样本，CYT作为负类样本。Ecoli_I来自UCI中Ecoli数据集,共有8个类别，人为的将类别im作为正类样本，其余的合为一类作为负类样本。Breast数据集中的样本共有6个类别，人为的将类别car作为正类样本，其余法人合为一类作为负类样本。Wine_I来自UCI中Wine数据集，共有3个类别，人为的将类别1作为正类样本，类别2和类别3作为负类样本。seeds_I数据集中的样本共有3个类别，人为的将类别1作为正类样本，类别2和类别3作为负类样本。数据集具有不平衡特征的界限是数据集中少数类样本个数与多数类样本个数的比例低于1∶2[8]。本文采用R语言完成SCSMOTE、SMOTE和RF算法的构造。

2.2 评价度量

对于非平衡数据集来说，采用分类精度来评价分类器的性能是不合理的[9]。一般使用混淆矩阵来评估，分别将两类分为正类(positive)、负类(negative)，如表2所示[10]。混淆矩阵的列用来表示类的预测结果，行用来表示类的实际类别[11]。其中，TP(ture positive)表示正类样本中被划分正确的样本数，即真正类，TN(true negative)表示负类样本中被划分正确的样本数，即真负类，FP(flase positive)表示正类样本中被划分错误的样本数，即假正类，FN(flase negative)表示负类样本中被划分错误的样本数，即假负类[12]。

表2 混淆矩阵

由表2，可得出准确率(Precision)、召回率(Recall)和真负类率如式(6)-式(8)所示，其是分类器最基本的指标[13]。定义为：

(6)

(7)

(8)

F-value是准确率和召回率的调和均值，定义如下：

(9)

式中：参数β一般取值1，可知只有准确率和召回率均较大时,F-value才会有较大值。

若要对算法进行总体评价，则要借助G-mean值，它是用来衡量分类器对正负样本分类的平均性能[14]。其公式如下：

(10)

本文选用Recall、Precision、F-value、G-mean等值作为算法性能指标的度量。

2.3 实验数据分析

本文的仿真实验均是在R语言中实现，记录了随机森林在三种实验方案下的实验数据，即未采样、SMOTE采样和本文的采样算法。为了更好地分析近邻参数K值的影响，首先随机选取4个数据集进行不同的近邻参数实验分析，其F-value、G-mean值如图2-图3所示，横坐标为K的取值， RF参数统一采用默认参数设置；然后对全部数据集采用默认的近邻参数(K=5)进行三种算法预处理。

图2 不同近邻参数取值下的F-value值

图3 不同近邻参数取值下的G-mean值

从图2和图3可以看出，当K取不同值时，用SCSMOTE处理的数据集abalone_I、glass_I、SPECTE的F-value、G-mean值始终最大或者与SMOTE算法相等；对于数据集Statlog，SCSMOTE处理后的F-value值始终在最上方或者与SMOTE重合，而当K=5时，SCSMOTE算法的G-mean值比SMOTE算法要小，可知SCSMOTE算法提高了F-value值，却降低了G-mean值。

为了整体分析算法的优势，采用统一的近邻参数(K=5)对全部数据集进行实验分析，图4-图7绘制了11个数据集上3种算法的测试结果图,其中，横坐标为所选取的不同数据集，纵坐标取值在0～1之间。表3-表6是它们的对应值表，可以看出，使用SCSMOTE算法进行过采样，少数类的分类性能有所上升。

图4 少数类准确率(Recall)变化曲线图

表3 少数类准确率(Recall)

图5 准确率(Precision)变化曲线图

表4 准确率(Precision)

图6 F-value变化曲线图

表5 F-value值

图7 G-mean变化曲线图

表6 G-mean值

由表3结合图4可知，大部分数据集在SCSMOTE算法处理后，经RF分类的Recall值大于未使用算法处理和SMOTE算法，表明RF在对经过SCSMOTE算法处理后的数据集分类时，有效地降低了实际正类预测为负类的错判个数。在表4和图5中，可以看出数据集经过随机森林分类后，准确率已经较高。然而大部分数据集在SMOTE算法处理后，经随机森林分类的Precision值不升反而降低，表明数据集经SMOTE算法处理后，增多了实际负类预测为正类的错判个数，从而使得Precision值有所降低，SMOTE算法并没有从根本上提高分类器的分类准确率。大部分数据集在SCSMOTE算法处理后，经随机森林分类的Precision值相比于未经任何算法处理进行随机森林分类的Precision值有所提高，并且相对于SMOTE算法有显著的优势。在表5和图6 中可以看到，对于非平衡程度高的数据集，其经过SCSMOTE算法处理后的数据集，经RF分类的F-value值高于未使用任何算法和SMOTE算法处理后的F-value值。而用于评价非平衡数据集整体性能的G-mean指标则可从表6中观察，表6和图7显示SCSMOTE算法在大部分的数据集上的 G-mean 值有显著的优势，说明本文提出的算法在这些数据集上有较好的总体分类性能。

综上所述，图表中的Breast_I数据集的训练集中正类样本有12个，经过SCSMOTE算法处理后，得到危险区域中的正类样本个数为3个，此时算法会选全部正类样本作为候选集(种子样本)。Wine_I数据集的训练集中正类样本个数为20个，经过SCSMOTE算法处理后，得到危险区域中的正类样本个数为3个，此时算法会选全部正类样本作为候选集(种子样本)。Seeds数据集的训练集中正类样本个数为16个，经过SCSMOTE算法处理后，得到危险区域中的正类样本个数为2个，此时算法会选全部正类样本作为候选集(种子样本)。由以上实验结果表明本文提出的算法在一定程度上提高了随机森林对非平衡数据分类的性能，分类效果有一定程度的改进，能够在不降低随机森林对多数类分类精度的同时，保证分类器对少数类的正确分类，并具有良好的适应性。

3 结 语

本文针对随机森林(RF)对非平衡数据集进行分类时所表现的不足，在分类器训练样本数据集之前，引入数据预处理，提出一种新的过抽样算法SCSMOTE。算法的关键是根据数据集自身分布情况，选择合适的候选样本，以增加对数据合成质量的控制。实验结果表明，经过本文方法处理的数据集，在进行数据集分类时，能有效地提高随机森林分类器的分类性能，使得随机森林在病毒入侵、设备故障检测领域具有显著优势。但算法程序中用于判定危险区域的近邻参数k往往需要人工设定，如何通过自适应方法产生类的近邻，是本文进一步的研究方向。