基于旋转平衡森林的不平衡数据分类算法

周尔昊，高 尚，申 震

(江苏科技大学 计算机学院，江苏 镇江 212100)

0 引 言

不平衡数据分类问题一直是机器学习领域研究的一大热点。所谓不平衡数据分类问题，是指分类任务中不同类别的训练样本数目差别很大，由此训练得到的分类器过于关注多数类而忽略了少数类分类精度。在现实生活中,该类问题也随处可见。如检测未知和已知的网络入侵、卫星雷达图像中漏油情况检测、医疗行业中的病情诊断等[1,2]。在以上问题中，少数类别的分类准确性往往显得更为重要，但目前大多数的机器学习分类算法往往基于类别平衡假设，导致其应用于不平衡数据时性能并不理想[3]。针对不平衡数据分类问题,学者们提出了相应的解决方法。总的来说可以分为以下3个角度：①从数据层出发，主要的方法有过采样、欠采样、数据合成以及一些相应的改进方法；②从算法层出发,主要的方法有代价敏感学习[4]、集成学习[5]等；③从数据层和算法层结合出发，主要方法有SMOTEBoost(synthetic minority over-sampling technique boosting)、RUSBoost(random under-sampling boosting)、代价敏感集成(AdaCost)等，前两种算法是采样方法和集成学习相结合，AdaCost则是代价敏感和集成学习结合的典型方法。

本文从数据层和算法层结合角度出发，提出了基于旋转平衡森林(rotation balanced forest，ROBF)的不平衡数据分类算法。本算法运用旋转森林基分类器差异性大、集成精度高的优势，通过引入数据层面的Hyper-Safe-Level-Smote方法来缓解各训练子集的不平衡率，再经集成获得的模型可以更好处理不平衡数据。本文研究旨在完善旋转森林算法处理不平衡数据分类问题的相关研究。

1 相关技术

1.1 旋转森林

旋转森林算法[6](rotation forest，ROF)是一种基于特征选择的分类器集成方法。先将特征集随机划分为K个子集，接着对每个特征子集进行主成分分析(PCA)并保留全部主成分，最后通过旋转矩阵得到新的样本数据用以训练基分类器。通过以上操作使得用于训练各基分类器的样本数据有所差异并且起到一定数据预处理效果。无论是差异性误差图或是分类器的分类精度，ROF算法都有更为出色的表现。

现设定F为特征集，C1,CL,……CL表示L个基分类器。其中基分类器采用决策树算法，因为它对特征轴的旋转更为敏感。用N×n的矩阵X表示训练集中有N条样本数据，且特征数为n。算法描述如下：

(1)将F随机划分为大小相等的K个子集，则每个子集约有M=n/K个属性。

(3)重复步骤(2)，将得到的K个子特征集的主成分系数存入系数矩阵Ri

1.2 SMOTE及相关改进算法

在传统过采样的基础上，Chawla等提出的合成少数类过采样技术(synthetic minority over-sampling technique，SMOTE)是目前常用的解决数据分布不平衡问题的数据层面的方法之一。该方法本质上是一种基于特征空间的过采样技术。相比于传统的过采样方法，SMOTE方法可以有效缓解过拟合问题并且提高模型在测试集上的泛化能力。但该算法仍然存在一定的局限性，SMOTE本质上还是不断得到一些人工生成的样本，会出现分类器过学习现象，同时训练时间也会延长。文献[8]中总结了SMOTE方法存在以下一些问题：①合成样本的质量问题；②模糊类边界问题；③少数类分布问题。针对SMOTE存在的问题，学者们提出了一些改进算法，主要分为两类：一类是SMOTE算法本身的改进；一类是SMOTE与其它方法相结合。SMOTE改进算法有Borderline-SMOTE、Safe-Level-SMOTE、ADASYN、G-SMOTE[9]等；相关结合方法主要有欠采样与SMOTE结合[10]、过滤技术与SMOTE结合[11]、聚类算法与SMOTE结合[12]等。

2 旋转平衡森林算法

2.1 Hyper-Safe-Level-Smote

本文提出的Hyper-Safe-Level-Smote是对Safe-Level-Smote的改进方法。Safe-Level-SMOTE方法为每一个少数类样本分配一个安全系数,以少数类样本为根样本，以安全系数高的少数类样本为辅助样本，以此来进行样本合成。安全等级(safe level,sl)和安全等级率(safe level ratio，sl_ratio)如下式所定义，其中最近邻样本采用欧氏距离定义，t是算法中的超参数，即在样本空间中选取距目标样本欧氏距离最近的t个样本

sl=t个最近邻样本中少数类样本数

(1)

sl_ratio=某个少数类安全等级/该少数类t个最近邻样本中某一少数类的安全等级

(2)

该方法从某一正类(少数类)样本p的最近邻t个样本中随机选取一个样本q作为辅助样本，通过分类讨论p、q之间安全等级率的大小，选择在合适的位置插值或者不插值。以此保证新合成的样本均落在安全区域内。但该算法存在以下问题：①模糊类边界问题。对处在类边界的少数类样本进行插值，若辅助样本同样处在类边界上，随着合成样本的增多会使类边界愈加模糊，虽然数据不平衡率得到改善，但是大大增加了分类算法的难度；②该方法对于新合成样本的分布约束力较小。算法本意是希望合成样本更靠近安全等级更高的原始样本，但在某些情况下合成结果却并不理想,新样本的实际分布未达到预期效果。

针对Safe-Level-SMOTE方法存在的问题，本文做出了以下改进：①设定安全等级划分标准J。根据所有少数类样本的安全等级再进行一次划分，得到高安全样本和低安全样本两类。对于某一少数类样本而言，若其属于高安全样本，则使用原始插值方法不变；若其属于低安全样本，则遍历其t个最近邻样本并选取其中安全等级最高的少数类样本作为辅助样本进行插值。这样操作虽然牺牲了一定的样本多样性，但能够保证即使是对那些处于类边界的少数类进行插值，依旧有较大概率使得新样本落在安全区域。这一改进有效解决模糊类边界问题，降低了算法的分类难度；②针对样本分布与预期有偏差的问题，本文改进的思路是通过人为添加控制因子α、β来约束合成样本的空间分布以达到预期。参照算法1，去除p、q均为噪声的情况，再加入α、β后可以得到如下的插值规则

其中，sl_ratio=slp/slq(slp和slq定义见式(1))，根据sl_ratio的不同情况，gap在相应的区间取随机值，最后通过步骤(4)中的第5)～第6)步完成特征插值。分析α和β的取值范围，控制因子的引入是为了约束样本的空间分布，在这里即是考虑让合成样本更靠近高安全等级的样本。根据上述的插值规则，首先可以确定的是α和β应为(0,1)之间的随机数，前者使得合成样本更靠近p，后者使得合成样本更靠近q。例如若p的安全等级为3，q的安全等级为2，这时sl_ratio>1，若不加入控制因子，gap的取值范围应是[0,2/3]。当加入控制因子α∈(0,1) 后，gap的取值范围缩小了，即样本有更大概率更加靠近安全等级更高的p。为了进一步探究控制因子的取值对于样本合成的影响，对(0,1)这一区间做进一步细分，以α为例，划分规则如下所示

理论上，当控制因子取强约束范围时，合成样本最为靠近高安全等级样本。但这同时会存在一个问题，即新合成样本与原始少数类样本的相似度增加，样本多样性减少，盲目合成这些原始样本的“复制”样本并不会对模型性能有所提升，同时还会产生过拟合现象。所以，针对不同的具体数据集，在充分考虑其样本分布的前提下，为控制因子选择合适的约束标准就显得有意义了。根据上述划分标准，α和β各有3组取值范围，总计9组情况。在本文3.1节中，设计了在修改后的鸢尾花数据集上找到最优控制因子约束强度的预实验。并且后续正式实验中也均通过预实验找到了合适的控制因子约束强度。

Hyper-Safe-Level-Smote方法的步骤如算法1所示。

算法1：Hyper-Safe-Level-Smote

输入：一个包含了全部原始正类样本的数据集D

输出：一个包含了全部合成样本的数据集D′

(1)初始化D′=∅。

(2)对数据集D中的每一个正类样本p， 从其最近邻的t个样本中随机选取一个正类样本q作为辅助样本， 用2.1节中式(1)、 式(2)分别计算p、q的安全等级slp、slq， 以及它们的安全等级率sl_ratio。 若slq=0， 则设置sl_ratio=∞。

(3)判断p的安全等级， 如果slp≥J， 则将其归为高安全样本(high-safe)； 反之归为低安全样本(low-safe)。

(4)For each high-safepinD:

for (atti=1 tonumattrs){；numattrs是属性(atti)数。

1) if (sl_ratio=∞ ANDslp≠0){；q是噪声， 这时将直接复制样本p来达到远离样本点q的目的。

gap=0}

2) else if(sl_ratio=1){；p、q的安全等级相同， 选择在p、q间随意插值

gap∈,1] }

3) else if(sl_ratio>1){；p的安全等级高于q， 选择在更靠近p的位置进行样本合成，α用于约束合成样本空间分布

gap∈[0,α(1/sl_ratio)] }

4) else if(sl_ratio<1){；q的安全等级高于p， 选择在更靠近q的位置进行样本合成，β用于约束合成样本空间分布

gap∈[1-β(sl_ratio),1] }

5)dif=q[atti]-p[atti]

6)s[atti]=p[atti]+gap·dif}

D′=D′∪{s}

(5)For each low-safepinD:

遍历p的t个最近邻样本并选取其中安全等级最高的少数类样本作为q

for (atti= 1 tonumattrs){

if (sl_ratio=∞ ANDslp=0){；p、q均是噪声，这时将不在p、q间进行任何插值操作

gap=0 }

重复步骤(4)中的1)～6)}

更新D′

(6)returnD′

2.2 旋转平衡森林算法及流程图

利用旋转森林差异性大、分类精度高的优势,在旋转后得到的新数据集上引入Hyper-Safe-Level-SMOTE，缓解了各基分类器训练集的不平衡率,经整合后获得可以有效处理不平衡数据的新的集成模型。将结合后的算法叫作旋转平衡森林,意为在旋转过程中即平衡多数类与少数类的类别分布。现设定F为特征集，C1,CL,……CL表示L个基分类器,用N×n的矩阵X表示样本集有N条n维的数据。第Ci个(1≤i≤L)基分类器的构造流程图如图1所示。算法步骤如下：

(1)对特征集F进行无放回的随机采样K次(K是算法的超参数)，得到K个大小相等的特征子集,每个子集约有M=n/K个属性。

(2)对于每一个特征子集，从数据集中进行75%的有放回取样，得到对应该特征子集的子样本集，利用PCA对特征子集进行特征变换，得到K个变换后的特征子集,每个子集包含M个特征数。PCA是一种常见的数学变换方法，常用于数据降维，可用于提取数据的主要特征分量。ROBF中的PCA不是用于降维，原因是为了不丢失原有数据信息，ROBF保留了全部主成分，故PCA在这里仅起到特征变换作用。且新特征子集是原始特征子集在新空间的映射，本质还是原来的数据，只不过表现形式不一样。

(3)将步骤(2)得到的K个特征子集的主成分系数存入系数矩阵Ri，根据原始特征集排列顺序重新旋转矩阵Ri得R′i。

(4)通过XR′i获得新训练集Xi， 在新训练集上使用Hyper-Safe-Level-Smote方法进行少数类样本插值，缓解新训练集的不平衡率。在插值后的新训练集上训练基分类器Ci。

(5)重复以上步骤L次得到L个基分类器，整合各分类器预测结果并输出。

图1 旋转平衡森林第Ci个基分类器构造流程

3 实 验

3.1 控制因子相关预实验

经典数据集鸢尾花数据集(iris)总共包含150个样本,每类各50个数据,每条数据有4项特征。这里对其修改,使其呈现二分类上的不平衡。修改后数据集见表1。

表1 修改后的iris数据集

实验前，选取其中70%作为训练数据，其它为测试数据。训练数据中少数类个数为21，测试数据中少数类个数为9。以测试集上少数类的分类正确个数衡量不同强度控制因子对模型性能的影响。分类器选用旋转森林算法，插值方法即为Hyper-Safe-Level-SMOTE。实验结果如图2所示，其中横坐标的编号1-9代表α和β分别取强约束+强约束、强约束+弱约束、强约束+适当约束、弱约束+强约束、弱约束+弱约束、弱约束+适当约束、适当约束+强约束、适当约束+弱约束、适当约束+适当约束。纵坐标代表不同编号下测试集上少数类的分类正确个数。

图2 控制因子约束强度对少数类分类的影响

从实验结果可以看出，修改后的iris数据集在α和β均取适当约束时分类器获得最好效果。

3.2 数据集

为了验证ROBF算法在不平衡数据分类问题上的有效性，本文从UCI上选择了6组数据集。通过调整使这些数据集呈现二分类上的不平衡。实验数据集不平衡度从1.87到28.4。经调整后的数据集情况见表2。

3.3 评价标准

对于二分类问题,通常用混淆矩阵来衡量分类算法的有效性，见表3。在这里正类即为少数类，负类即为多数类。

对于不平衡数据分类算法性能的衡量往往不能仅依据准确率，故除准确率外本文还选取了真正例率(TPR)和G-mean来衡量算法性能。TPR值反映的是少数类中有多少样本被真正预测为少数类；G-mean是特异度(Specificity)

表2 修改后的数据集

表3 二分类混淆矩阵

和TPR的几何平均值，由于同时考虑了正类和负类样本分类的性能，所以它对于不平衡的二分类数据集来说是一种较好的度量。式(3)～式(6)分别是准确率、TPR、Specificity和G-mean的计算公式

(3)

(4)

(5)

(6)

3.4 实验设计与结果分析

实验过程中，通过分割将数据集的80%用作训练，20%用作测试。采用5折交叉验证来避免过拟合。为了验证ROBF算法在处理不平衡数据时的有效性,本文选取了AdaCost、RUSBoost、Borderline-SMOTE+ROF、ADASYN+ROF这4种算法在6组数据集上与ROBF进行对比实验。前两者是Adaboost针对不平衡问题的改进算法,后两者是为了验证在旋转森林模型下，Hyper-Safe-Level-SMOTE方法相较于其它SMOTE的优势性。RUSBoost采用C4.5作为基分类器，其它算法均使用CART作为基分类器。另3个ROBF中涉及的参数是Hyper-Safe-Level-SMOTE方法中最近邻样本数t、划分安全等级标准J和控制因子α、β的强度，在实验中分别设置为t=5和J=3。各数据集上α、β的约束强度见表4，表4结果均是在各数据集上做类3.1节预实验后得出的最优控制因子约束强度。在此基础上，ROBF与其它4种算法的实验结果见表5～表7。

表4 各数据集控制因子最优约束强度

从实验结果分析，ROBF算法相较于其它4种算法在准确率上并未有明显提升，在vowel和crowdsourced上其准确率略低于RUSBoost算法，这说明ROBF在提升少数类分类精度的同时会降低多数类的分类精度。

表5 不同算法在数据集上的AccuracyRate对比

表6 不同算法在数据集上的TPR对比

表7 不同算法在数据集上的G-mean对比

ROBF的TPR值与其它算法相比有较大提升，这是因为经Hyper-Safe-Level-SMOTE合成的数据有着更大的概率落入安全区域，这意味着合成后的新数据中有更多的少数类样本被正确预测为少数类。Borderline+ROF由于其在区分噪声和类边界样本上的不准确性，导致TPR值低于ROBF算法。RUSBoost的TPR值在clients上明显低于其它算法，这很可能是因为在随机欠采样过程中删掉许多有潜在价值的多数类样本。

G-mean同时衡量了多数类和少数类的分类性能，从表5可以看出ROBF在其中4个数据集上是占优的，这是因为除了注重少数类的分类精度，Hyper-Safe-Level-SMOTE较好解决了模糊类边界问题，进一步提升了分类器的分类性能。相比之下，Borderline+ROF与ADASYN+ROF虽然和Hyper-Safe-Level-SMOTE应用于同一个集成模型之上，但前两者的插值效果相比于Hyper-Safe-Level-SMOTE还是略有不足的。在高度不平衡的clients数据集上，Adacost取得了最高的G-mean值，ROBF略低，这是因为在数据量较大且不平衡度较高的数据集中，少数类只占据了小部分，多数类的分类性能影响着G-mean值的高低。综上，ROBF算法不仅在少数类分类问题上有着更出色的性能，而且在多数类分类上也有着良好表现。

为了更加直观体现ROBF算法的优势，图3和图4展示了在6组数据集上5种算法的TPR和G-mean的实验结果折线图。从图可以看出，ROBF在处理不平衡数据分类问题上是有效的。

图3 5种算法的TPR比较

图4 5种算法的G-mean比较

4 结束语

针对不平衡分类中的二分类问题,本文从数据层和算法层结合的角度出发,提出了一种基于旋转森林的改进模型—旋转平衡森林。该模型选用基分类器差异性大，集成精度高的旋转森林算法作为基模型，通过引入改进的Hyper-Safe-Level-SMOTE方法，在缓解训练集不平衡率的同时，成功解决了模糊类边界问题，使得改进后的模型在处理不平衡数据时对少数类拥有更好的分类性能。在未来研究中，将继续针对模型做进一步的探索，如：①在旋转森林模型中，是否可以通过改变75%的重采样中正、负类比例来使训练模型更注重少数类分类；②Hyper-Safe-Level-SMOTE中控制因子的范围取值是人工设定的,约束强度的选择也仅是相对最优,是否可以设置自适应的控制因子来寻求最优的约束强度。