基于混合采样和特征选择的改进随机森林算法研究

汪力纯，刘水生

（1.南京工程学院信息与通信工程学院，江苏 南京 211167 2.江苏省烟草专卖局信息中心，江苏 南京 210018）

随着信息全球化以及数字信息急速地增长，数据挖掘领域［1］受到了人们的广泛关注。其中，该领域的分类算法是研究的重点，分类主要是对获取到的数据运用一定的算法规则预测未知数据的对应类别，通常在分类预测问题上常用随机森林算法来建立分类模型，实现分类结果的预测［2］。

随机森林［3］主要是由多棵决策树组合而成的一种集成分类模型，与其他传统的单分类器相比有更高的分类精度和更低的泛化误差，对异常值有较好的容忍度。但是，在信用贷款［4］、电信欺诈［5］和医疗诊断［6］等实际生活中产生的数据一般都具备高维不平衡的特征，而原始随机森林算法在针对高维不平衡数据［7］做分类预测时，构建的分类模型复杂，容易发生过拟合现象，导致预测结果偏向于多数类，分类精度显著降低，且算法训练时间变长，计算过程变得更为复杂。

当下，业界关于对高维不平衡数据的分类问题，主要从数据的高维度及不平衡性等两方面作为切入点，凭借数据与算法两个层面来尽可能改善模型的分类精度。其中，在数据层面上，主要凭借过采样或欠采样等方式来处理不平衡数据。例如 Ha等［8］提出了基于遗传算法的欠采样GAUS算法来均衡数据集和杨毅等［9］提出了Borderline⁃SMOTE算法只对分布在边界的少数类进行过采样以达到数据的均衡。算法层面主要是对现有的算法进行改进优化，使改进后的算法可以更好地处理高维数据，即对高维数据进行降维处理，主要包括特征选择和特征提取两种。例如Guo等［10］提出的特征选择与 Adaboost相结合的集成学习算法，通过筛选出重要特征组成新的特征子集，以此达到降维的目的。因此，针对高维不平衡数据的分类问题，结合数据和算法两个层面对原始随机森林进行优化与改进，提出了改进的随机森林算法HF_RF。首先通过SMOTE算法和随机欠采样相结合的方式对高维不平衡数据集进行预处理，同时引入聚类算法对SMOTE算法进行改进，提高对负类样本的处理性能；然后通过Relief F算法对平衡后的高维数据进行特征加权，递归地剔除不相关和冗余特征，筛选出有效的维度较低的子集以提高分类精度和效率；最后采用加权投票原则进一步提高算法的分类性能。

1 相关工作

根据相关研究文献可以看出，随机森林算法具备很多其他机器学习算法没有的优点，它能处理大规模数据，预测精度不受数据丢失的影响，输入特征可以是离散数据，也可以是连续数据。算法的精度高于单一的决策树分类算法，一定程度上避免了过拟合问题，同时能够较好地处理噪声和异常值。但是随机森林仍然存在着许多不足之处：一方面，在处理有较多特征冗余和不平衡的数据集时，算法会将少数类样本错分为多数类，此时选用不恰当的评价标准就会导致假高分类精度的情况，同时会降低单棵决策树的分类精度，导致算法整体性能下降；另一方面，预测投票阶段为每棵决策树都赋予相同的权重，导致分类性能差的决策树影响最终整体的分类结果。

近年来研究人员针对原有的随机森林算法存在的缺点和在实际应用中的不足进行了相关改进。Zhu等［11］提出一种基于随机森林的类权重投票算法（CWsRF），该算法为每个类赋予单个权重，以充分区分少数类和多数类，但是会导致数据过度冗余。Mashayekhi等［12］提出一种基于爬山策略的贪婪方法，该方法选择一组精度高、相似度低的决策树来改进随机森林算法，实验证明改进算法的分类精度得到大幅提高，但在处理高维不平衡数据方面依然存在缺陷。Gregorutti等［13］提出一种递归特征消除（RFE）算法，利用随机森林的置换重要性测量算法计算决策树之间的相关性对特征置换的影响，计算特征权重，递归删除权重低的特征。胡玮［14］针对随机森林建立分类模型时间较长的缺点，在改进的领域粗糙集属性约简算法的基础上，对随机森林算法进行了改进，该方法有效减轻过拟合问题，但会导致结果产生偏向性。黄青平等［15］利用模糊聚类对随机森林进行改进，用相似度高的样本训练随机森林预测模型，提高了算法的预测精度。房晓南等［16］采用SMOTE算法计算出一批少数类样本，降低了数据的不平衡程度，然而该方法不能保证伪样本的类型正确性。

以上的改进算法大多都是从算法或数据的单一层面出发来提高算法的分类性能，不能同时兼顾数据高维和不平衡的特征。本文提出的基于混合采样和特征选择的改进随机森林算法主要结合数据和算法两个层面对原始随机森林算法进行优化改进，使改进后的算法可以更好地处理生活中最常出现的高维不平衡数据。虽然改进后的算法提高了针对高维不平衡数据的分类精度，但是因为改进算法的时间复杂度增加，使得算法的整体计算效率一定程度的降低，今后的研究方向将会针对目前存在的不足做出进一步改进。

2 随机森林算法

随机森林是一种集成学习算法［17］，它是一个由多棵决策树共同参与的集成分类器。随机森林中的每棵决策树都是基于Bootstrap抽样得到的，然后将多棵决策树组合之后通过投票由得票多的类别作为最终分类结果。随机森林的构建过程如下：

假设原始训练数据集D中，n为样本数量，M为特征总数，所需构建的决策树数量为k。

（1）抽取训练子集。从原始训练集D中有放回地随机选取n个样本，并重复n次，其他的则构成袋外数据集OOB。

（2）构建决策树。先在M个特征中随机抽取m个组成特征子集（m＜M），然后利用相关准则选择最佳分割点，将其划分为子节点，同时将训练集划分到相应节点中，重复地逐层划分，最终得到所有节点。

（3）随机森林生成。循环执行步骤（2），直至建立 k棵决策树，以构成随机森林｛ti，i＝1，2，…，k｝。

（4）通过借助随机森林中k棵决策树来分类预测测试集，最终得到 k 个预测结果 ｛t1（x），t2（x），…，tk（x）｝。

（5）把各决策树预测结果的众数作为各样本最终的预测结果。

3 算法改进

然而需要指出的是，借助随机森林算法来处理高维不平衡数据时，主要具有以下不足：（1）在处理高维数据时稍显冗余，且极易忽略一部分类强相关特征，同时还会加大算法的时间复杂度；（2）在处理不平衡数据时，分类结果较偏向于多数类，使得算法分类精度降低。因此，为了解决特征之间的冗余且数据分布不均衡问题，提高算法的分类精度，本文提出了基于混合采样和特征选择相结合的改进随机森林算法HF_RF。首先通过改进的SMOTE算法和随机欠采样相结合的方式对高维不平衡数据集进行预处理，达到均衡原始数据集的目的；然后通过Relief F算法对均衡后的高维数据进行特征加权和维度约简，筛选出有效的维度较低的子集训练决策树；最后采用加权投票原则进一步提高算法的分类性能。

3.1 基于改进的SMOTE算法的混合采样

SMOTE算法［18］主要是在少数类样本中随机插入人造的正类样本使类间分布平衡，提高分类器在测试集上的分类性能。SMOTE算法大致执行过程如下：在处理正类样本X时，确定最接近正类样本X的k个近邻样本，再从此k个近邻样本中随机选择m个样本，然后针对这m个样本中的每一个样本Xi（i＝1，2，…，m），按照式（2） 生成新的人造样本点。

式中，rand（0，1）表示产生一个0到1的随机数。

虽然SMOTE算法之前的采样方法可以均衡数据集，但因为随机采样缺乏原则，不能考虑到边缘数据的分布状态，容易产生边界模糊的问题［19］，导致采样效果不理性。针对以上问题，在此次研究中，引入了聚类算法［20］来改进SMOTE算法，大致实现流程如下：先借助聚类算法对少数类实施聚类操作，以确定少数类中各簇的分布状态，然后计算各个簇的簇心，在簇内簇心与簇内样本的连线上根据式（3）进行插值增加人造样本数据，这样能很好地解决边界模糊问题。

式中，Xnew为新插值的样本，ci为簇心，X是以ci为簇心聚类中的原始样本。

基于改进SMOTE算法的混合采样具体步骤如下：

（1）依次计算多数类与少数类样本的采样数量，假设样本集D中的多数与少数类样本数分别为M与N，混合比列系数为∂，则混合采样数量Pmix的计算公式为

其中欠采样的数量PM＝Pmix∗∂，过采样的数量 PN＝Pmix∗（1-∂）。

（2）针对多数类与少数类，分别采取欠采样与过采样的方式进行处理，从而分别得到全新数据集Mnew与Nnew。

（3）合并以上新得到的两数据集Mnew与Nnew，从而得到平衡数据集Dnew。

3.2 Relief F算法与随机森林结合

在已有的特征选择［21］方法中，Relief算法［22］避免使用全局搜索方法，仅根据特征间的关联性来赋予对应的权重，根据权重的大小来排列对应特征，并把权重值高于阈值的特征作为特征子集，为一种简单高效的Filter型特征选择算法［23］。正因为如此，使得Relief算法被广泛应用于海量高维数据中。但是Relief算法只能处理二分类问题，当数据存在缺失以及噪声时，Relief不能对其进行良好的处理，因此为解决上述问题，学者们提出了ReliefF算法。该算法可以更好地处理多分类问题。

ReliefF算法的大致流程如下：先把训练集D中各样本的所有特征权值设为0，再从训练集样本D中随机选取样本R，依次选择R的k个同类与不同类最近邻样本，得出对应特征的权重值，最后重复m次后通过求取平均值的方法计算最终的权重值，求出各个特征与类的相关性权重W后，将其按降序排列。Relief F算法的权重计算公式为

式中，W（Aj）表示特征Aj的权重，p（C）表示第C类目标的概率；diff（Aj，R，Hi） 为两个样本 R 与 Hi在特征Aj上的差，其计算公式为

式中，R［Aj］表示样本 R在特征 Aj下的样本值，Hi［Aj］表示样本Hi在特征Aj下的样本值。

diff（Aj，R，Mi（C）） 是两个样本R与Mi（C） 在特征Aj上的差，其中Mi（C）表示类C中与样本R的第i个最近邻样本，C表示与R所在类不同的类；class（R）表示样本R所在类；p（class（R））表示R所在类的概率。

由于随机森林算法在构建决策树时会随机选择部分特征值，最终导致过多冗余特征被选中，降低单棵决策树的精度。因此本文通过Relief F算法剔除样本集中的无用特征，按照权值大小将剩余特征均匀分到高、中、低3个区域中，最终通过获取的3个特征区域来训练决策树，得到随机森林分类模型，达到提高分类精度的目的。具体流程如图1所示。

图1 Relief F算法结合随机森林流程图

3.3 加权随机森林

随机森林算法在分类问题的预测方面采用的是众数投票法［24］，即统计每种分类标签得到各棵决策树的相应票数，将投票数最多的作为最终的预测结果。该投票法忽略了不同决策树之间的强弱差异，无法增强随机森林中分类性能优秀的决策树对投票结果的影响，最终导致具备优秀分类性能的决策树被分类性能较差的决策树所影响使算法的分类效果降低。因此，为了进一步提高随机森林算法的分类预测性能，本文在构建决策树时，利用OOB袋外数据判断决策树分类精度，为各棵决策树赋予不同的权重，增强分类性能优秀的决策树在投票时的比重，同时降低分类性能较差的决策树的比重，以此提高随机森林分类模型的分类精度。

加权随机森林的具体步骤如下：

（1）凭借Bagging算法，随机抽样均衡处理后的数据集N，以得到样本子集。同时会存在未被抽取的OOB数据，OOB中每个样本没有被抽到的概率约等于0.368，如式（7）所示。

当 N→∞时，P≈0.368。

（2）设T为训练完成的K棵决策树分类器集合，通过OOB数据得到每棵决策树对OOB数据的正确分类的比率。

（3）计算各棵决策树的权重值，计算公式为

（4）选出权重最高的作为最终分类结果。

3.4 混合采样和特征选择结合的改进随机森林算法HF_RF

相较于原始随机森林算法，HF_RF算法主要有效以下优点：第一，从数据层面出发，针对原始随机森林算法在处理不平衡数据集方面，分类结果较偏向于多数类，算法分类准确率不高等问题，凭借结合改进的SMOTE算法和随机欠采样，来预处理数据集，以确保数据集达到均衡状态；第二，从算法层面出发，针对高维数据集中存在特征冗余，原始随机森林在处理时增加了算法的时间复杂度等问题，引入了Relief F算法与随机森林相结合，对高维数据进行特征约减；第三，利用OOB数据对决策树赋予不同的权重，进一步提高改进算法的分类性能。HF_RF算法的流程如图2所示。

图2 HF_RF算法的流程图

4 实验与结果分析

4.1 评价指标

正确率通常为评估传统分类算法分类性能最重要的指标。但是，在高维不平衡数据集中，正确率不能准确提供少数类的精度，而高维不平衡数据的重点在于对少数类的处理上，所以需要引入其他评价指标来判断算法的分类性能。因此对于高维不平衡数据一般采用查全率 Recall、F⁃measure、AUC值等作为评价标准，这些评价标准都是在混淆矩阵的基础上建立的。混淆矩阵如表1所示。

表1 混淆矩阵

其中，TP、FN分别表示的含义是正确与错误预测的正类，FP、TN分别表示错误与正确预测的负类，进而可得样本总数N＝TP+FP+FN+TN。

（1）Recall查全率，其含义为被正确预测的少数类样本占比。其中，正确预测少数类的样本的识别率与查全率之间成正比关系，因此Recall可以用来评价分类算法对少数类的性能，公式为

（2）F⁃measure为一个全新的评价指标，其综合了查全率和查准率两种标准，算法对于少数类的分类精度和F⁃measure的值同样成正比关系，公式为

4.2 实验数据集

此次研究所涉及的数据集，来自于美国加州大学UCI所公开的数据集。其中，糖尿病导致的视网膜病变数据集与甲状腺疾病数据集为特征数少且分布较均衡的数据集；而卫星与麝香区分数据集为特征数多且分布不均衡的数据集；最后页面块分类数据集为分布极不平衡的数据集。以上5个数据集可以充分展现HF_RF算法在处理高维不平衡数据上的分类性能。具体参数如表2所示。

表2 数据集的具体参数

4.3 实验过程

此次实验环境的硬件方面配置如下：Intel（R）Core（MT） i7⁃4600U CPU@2.10 GHz处理器、8 GB内存、64位Windows 10企业版操作系统。而软件环境如下：Java环境，WEKA开放源码包。

实验时随机森林决策树个数初始定为N＝100，取样次数m，少数类个数为k；改进SMOTE算法对于数据集中的少数类过采样时，将聚类算法的迭代次数最大值设置为50，随机选取5个点作为簇心开始聚类和插值操作。

本次实验主要是为了验证本文提出的HF_RF改进算法在处理高维不平衡数据时的分类性能，因此利用目前常见的从数据层面出发的基于改进混合采样的随机森林算法HSRF和从算法层面出发的基于改进Relief F的随机森林算法R_RF这两种算法与本文提出的HF_RF算法分别对5个高维不平衡数据集进行分类，对比各自的查全率、F⁃measure和AUC指标以及相关参数来验证分类性能。

4.4 实验结果分析

实验对比了3种算法关于以上5个数据集的评价指标，最终实验结果如表3所示。

表3 3种算法在5个数据集上的评价指标 %

将5个数据集在3种算法中的各性能指标绘制成折线图，分别如图3、图4和图5所示。

图3 查全率

图4 F⁃measure

图5 AUC值

根据性能指标折线图可以看出HSRF算法和HF_RF算法在查全率、F⁃measure和AUC值都高于R_RF算法，由此看出仅仅降低数据集中的特征数不对数据集进行均衡处理，分类性能提升并不明显。其中DB、PG、TD数据集中的特征数相对较少，从结果可以看出HSRF算法虽然在不平衡数据的处理上有所提高，但没有HF_RF算法在处理不平衡数据集上的性能好，而对于SL、MUSK这类特征数多的不平衡数据集，改进算法达到了很好的分类效果。

从图3可以看出，随着数据集不平衡程度的增加，对数据进行预处理的改进算法的查全率也有一定程度的提高，因此查全率可以很好地反映算法对少数类的分类性能，HSRF算法与R_RF算法相比，通过混合采样来达到数据均衡，一定程度提高了算法的分类性能，而HF_RF算法对不平衡数据的整体分类性能更高。从图4可以看出，PG数据集的不平衡度最高，R_RF算法对于该数据集的分来效果较差，F⁃measure值为79.3%，在通过改进算法HF_RF算法训练之后得到的分类模型的F⁃measure值提高到了92.3%，提高了 13%。结合表 4可以看出，HSRF算法对于数据集中的特征数没有改进作用，不能达到特征约减的目的，只能一定程度地平衡数据集，而R_RF算法和HF_RF算法都能一定程度地删除数据集中的冗余特征。

表4 3种算法特征数对比

从图5的AUC值可以看出HF_RF算法在通过混合采样和特征选择对算法进行多层改进后，与其他两种算法相比AUC值有明显的提升，AUC曲线整体在其他算法之上，最高达到了95.6%。本文提出的HF_RF算法不仅可以很好地均衡数据集，还能进一步削减冗余特征，提高模型的分类性能。

综上所述，相比于HSRF算法和R_RF算法，改进的HF_RF算法不论是在特征约减，还是在数据均衡方面的总体分类效果都有所提高，但是在算法的整体运行时间上，3种算法的时间差异表现不明显，下一步可以在算法中引入并行化策略作为后面的主要研究方向，有效地降低算法的时间复杂度。

5 结束语

在此次研究中，针对随机森林算法在分类预测特征维度高且不平衡的数据时，所表现出的低性能问题进行了一定的改进，最终建立了HF_RF算法。首先针对原始随机森林算法在处理不平衡数据集方面，存在分类准确率低的问题，通过改进的SMOTE算法与随机欠采样相结合的混合采样策略对数据集进行预处理；然后针对高维数据集中存在特征冗余，原始随机森林在处理时增加了算法的时间复杂度等问题，引入了Relief F算法与随机森林相结合，对高维数据进行特征约减；最后利用OOB数据对决策树赋予不同的权重，进一步提高改进算法的分类性能。结果表明，改进的随机森林算法HF_RF在处理高维不平衡数据方面的分类预测性能高于其他分类算法。然而HF_RF算法也存在一些缺陷，虽然对高维数据进行了特征约减一定程度上降低了时间复杂度，但是算法的整体运行时间与其他算法相比没有显著优势，所以下一步在不影响分类性能的前提下引入并行化策略进一步提高算法的运行效率。