基于特征约简的随机森林改进算法研究

王 诚，高 蕊

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

随着计算机网络的飞速发展，电子数据库的规模呈爆炸式增长，为帮助计算机更好地处理数据，得出可行的方法论，各分类回归算法不断焕发出新的生机。其中，随机森林算法是以决策树为基础的分类回归模型，它将多个单分类器集成，共同参与决策，因此分类精度要高于一般的单分类器。算法应用领域涵盖信用贷款[1]、生物医学[2]、图像[3]、销售[4]等。虽然其在大部分场景中能达到很好的效果，但在处理某些特殊数据，如不平衡且特征维度高的医疗数据时，过多的冗余特征使得模型极易过拟合；且模型为了提升整体分类精度，习惯将少数类归为多数类处理，得到虚假的分类精度。因此，算法不得不做出针对性的改进。

多年来学者们对原算法进行了很多改进，如通过聚类方式[5]、贪婪方法[6]挑选出一批具有代表性的高精度低相似性决策树，提高了部分数据集的分类精度，但对于上文提到的特殊数据集效果甚微；其他改进如针对不平衡数据：改变性能评价标准[7]、重采样数据[8-9]、生成合成数据[10-11]等；又如针对特征选择的：粗糙集[12]、邻域互信息[13]、聚类[14]等，这些改进有一定成效，但很难融合以同时解决上述两种问题。其中Marwa Hammami[15]提出了Filter与Wrapper结合的高维数据特征构造的多目标混合滤波器包装进化算法，在消除冗余特征方面效果显著；李硕[16]提出的基于改进的ReliefF算法结合支持向量机的非均衡特征选择方法有效解决了不平衡数据的问题。这两种改进一个针对特征排序，另一个针对特征约简，能很好互补。受此启发，文中提出一种基于特征约简的随机森林改进算法[17]：RW_RF。在随机森林的决策树构建过程中引入Wrapper递归特征消除与ReliefF算法结合的特征选择方法，尽可能挑选出拥有最佳分类性能的特征集，来减轻特征冗余和数据不平衡问题对模型的影响。

1 随机森林算法

随机森林算法(random forest，RF)，本质是由多棵相互之间并无关联的决策树整合而成的多分类器，单条数据经过每一棵决策树投票，得票数最多的类别即为最终分类结果。

假设原始样本集D(X,Y)，样本个数为n，要建立k棵树，随机森林的具体步骤大致如定义1所示。

定义1：随机森林。

(1)抽取样本集：从原始训练集中随机有放回地抽取n个样本(子训练集)并重复n次，每一个样本被抽中的概率均为1/n。被剩下的样本组成袋外数据集(OOB)，作为最终的测试集。

(2)抽取特征：从总数为M的特征集合中随意抽取m个组成特征子集，其中m

(3)特征选择：计算节点数据集中每个特征对该数据集的基尼指数，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，从节点生成两个子节点，将剩余训练数据分配到两个子节点中。

(4)生成CART决策树：在每个子节点的样本子集中重复执行步骤(3)，递归地进行节点分割，直到生成所有叶节点。

(5)随机森林：重复执行步骤(2)～(4)，得到k棵不同的决策树。

(6)测试数据：每一棵决策树都对测试集中的每一条数据进行分类，统计k个分类结果，票数最多的类别，即为该样本的最终类别。

2 算法改进

随机森林算法在处理不平衡且特征数非常多的数据时有几点弊端：第一，算法的分类思想是少数服从多数，因此在面对类别样本数相差悬殊的数据集时，容易将少数类归为多数类，造成很高的假分类精度；第二，过多的冗余特征会扰乱模型的学习能力，导致模型过拟合，限制了模型的普适性。因此，找出冗余度最小，且最能代表正负类数据之间的差异的特征子集，再生成随机森林，是文中算法改进的思路。基于此，提出了改进的随机森林算法RW_RF。首先在构建CART决策树的特征选择步骤中，使用改进的ReliefF算法初步筛选掉一批不相关特征，并将留下的特征根据权重排序；接着运用Wrapper的递归特征选择思想，依次删除低相关特征和冗余特征，得到最佳分类特征子集；最后在随机森林中构建整个分类模型。

2.1 改进的ReliefF算法

ReliefF，是由Relief算法发展而来的一个经典的特征权重赋值算法，它将特征与正负类之间的相关性作为依据，给每个特征赋予相应的权重。

ReliefF算法的思路为：首先从测试集中任意抽取一个样本Rn，接着随机抽取数量相同的k个Rn的同类与不同类样本(Same spe/Diff spe)，分别计算特征A在Same spe和 Diff spe样本间的距离，如果两类距离的均值相差悬殊，说明该特征对此类样本有较大的区分能力，继而增加该特征的权重；反之，若距离相同，说明没有区分能力，则降低该特征的权重。重复m次后得到的均值，作为该特征的权重。权重计算如下：

(1)

其中，W(A)为特征A的权重，p(C)为原数据集中类别为C的样本所占比例，Mj(C)为类C∉class(R)中第j个最近邻样本。diff(A,R1,R2)表示样本R1和R2在特征A上的差，如下：

diff(A,R1,R2)=

(2)

由式(1)知，ReliefF将xi与异类C中距离xi最近的k个样本在特征A上的差异取平均，再乘以C类样本占所有与xi异类样本的比例，对所有与xi异类的样本执行此操作，得到特征A在异类样本间的差异均值。W={w1,w2,…,wn}是最终得到的特征权重向量，按权重从大到小对特征进行排序。

考虑到数据不平衡的问题，对以上的ReliefF算法稍作改进。为弥补非平衡数据对分类性能的影响，通过修改抽样参数使它相对类均衡。具体做法是，计算权值时，将原本需要设定的k值固定为当前样本集中少数类个数，保证计算权重时当前特征对应的正负样本数量均衡，理论上避免了分类结果偏向多数类的情况。具体步骤如定义2所示。

定义2：改进的ReliefF特征排序法。

输入：训练集D，抽样次数m，k=D中少数类样本个数；

输出：各个特征的特征权重W。

1.置0所有特征权重W={0,0,…,0}，T为空集；

2.fori=1 tomdo；

3.从D中随机选择一个样本R；

4.从R的同类样本集中找到R的k个最近邻Hj(j=1,2,…,k)，从每一个不同类样本集中找到k个最近邻Mj(C)；

5.forA=1 toN(all features) do；

6.将所有特征值归一化映射到[0,1]范围内；

8.删除权值<0的特征。

此改进目的是，先删除对分类效果有害的特征，再将剩余特征相对正类和负类的区分能力排序，以便接下来更方便地去除冗余和不相关的特征。

2.2 递归特征消除法

使用改进ReliefF算法快速筛选出分类性能最佳的特征，但没有达到消除冗余特征的要求，还需要进一步优化。文中借助Wrapper的递归特征选择思想来剔除冗余特征，找到最佳特征子集。具体方法为，将特征按计算好的权重排序，每次从特征集合中去掉L个权值最小的特征生成CART分类决策树，并计算其AUC值(具体见3.1节)。逐次迭代，直到找到AUC值最高的一组特征子集。这个过程采用k折交叉验证法来分割数据集，计算每次迭代的AUC值，选择值最大的一次迭代作为删除冗余特征的依据，具体过程如定义3所示。

定义3：递归特征消除法。

输入:对应特征的权值W={w1,w2,…,wn}，数据集D；

输出:最佳分类特征子集FGSort。

1.初始化:读入原始数据集D，设置FGSort=Null；

2.采用分层采样技术将数据集D划分为6等份，表示为:D=D1∪D2∪…∪D6；

3.设置6次迭代中每次训练得到的分类器的分类准确率向量TLAuc[1∶6]=0；

4.for(i从1到[N/L]) //i代表循环变量，N代表数据集中所有特征个数，L为每次删除的特征数量；

5.在数据集(D1-D5)上训练决策树分类器，对应特征子集记为FGSorti；

6.计算当前迭代的准确率TLAuci；

7.剔除权重最低的L个特征；

8.end for;

9.输出6次分类准确率最高的特征子集FGSorti。

此改进目的是将排好序的特征按末尾淘汰制训练决策树，选出分类性能最佳的子集。

2.3 改进特征选择法与随机森林算法结合的RW_RF算法

RW_RF算法相比于原始随机森林算法有两点改进：第一，随机森林随机选择特征的步骤替换为上述改进的ReliefF算法，在初步排除一批不相关特征的同时，对剩下特征的分类能力进行排序；第二，建立决策树时，采用递归特征选择思想依次删除低权值特征，得到分类性能最好的特征子集，最后构建随机森林分类模型。改进算法部分流程如图1所示。

3 实验及结果分析

3.1 评价指标

传统二分类数据的评价准则有几个重要指标，其中TP表示正确预测的正类，FN表示错误预测的正类，FP表示错误预测的负类，TN表示正确预测的负类。样本总数N=TP+FP+FN+TN。

(1)分类精度(Accuracy)。

(2)灵敏度/召回率/查全率(Sensitivity)。

(3)特异度(Specificity)。

(4)ROC曲线/AUC。

(a)随机森林流程 (b)特征选择流程

图1 改进的RW_RF算法

3.2 实验数据集

实验分别选择美国加州大学UCI公开数据集中共5个用于分类问题的数据集。其中包含特征数相对较少且类平衡的数据，如糖尿病引起的视网膜病变数据集、垃圾邮件区分数据集；还包括特征数相对较多且类不平衡的数据集，如癫痫诊断数据集、麝香判定数据集；最后是斯堪尼亚卡车故障数据集，此数据集极不平衡，正负类比例接近40∶1。这5个具有代表性的数据集，可以全面地展现改进的RW_RF算法在特征选择和处理不平衡数据方面的优势。具体参数如表1所示。

表1 选用的UCI数据集具体参数

3.3 实验过程

实验所用的RW_RF算法采用Java编程实现，主要用到Weka包来封装。硬件执行环境配置为：Intel(R) Core(TM) i7-7700HQ CPU @2.80 GHz处理器、16 GB内存、64位Windows 10企业版操作系统。随机森林决策树个数设置为50，取样次数m设置为当前数据集少数类个数k；构建CART决策树时基尼指数设为0.01。

此外，文中通过3种算法的对比来验证提出的RW_RF算法的分类效果。第一种算法是未经任何改进的原始随机森林算法；第二种是在原始随机森林算法中加入上文所提的改进ReliefF算法，命名为R_RF算法；第三种即提出的RW_RF算法。

分别将5个数据集在上述3种算法中进行分类，比较各自的分类精度(Accuracy)、灵敏度(Sensitivity)、特异度(Specificity)和AUC(area under the curve)指标以及相关的参数。

3.4 实验结果分析

实验结果如表2所示。

表2 各数据集在3种算法中的性能指标对比

将5个数据集在RF、R_RF和RW_RF算法中的各性能指标结果绘制成折线图，如图2所示。

图2 改进前后各指标对比结果

图2展示了5个数据集在原始RF、改进R_RF和最终RW_RF算法下分类精度、灵敏度、特异度的对比结果。其中DB和SB数据集本身的特征数和样本数较少，由结果可知改进的R_RF算法模型没有带来太大的性能提升。然而，在特征数较多的数据集ES、MUSK和APS中，两种改进算法均达到了很好的分类效果。结合表3可知，在改进的R_RF模型中训练后，3个数据集的特征数由原来的179、168、171，分别约简到165、143、139，初步删除了大量无关特征值后，4个分类指标结果都有大幅提升，参见图2(d)，在数据集ES、MUSK中整体分类性能提升最为明显，说明加入改进的ReliefF算法有效删除了不相关的特征，提高了模型分类性能。在RW_RF算法中，特征被进一步约简至138、127、114，各指标结果相较R_RF又有或多或少的提升，说明Wrapper递归特征消除法能在ReliefF的基础上进一步约简冗余特征，尽可能得到对分类最有帮助的特征集合。

表3 改进前后特征数对比

在处理数据不平衡问题中，改进的算法也体现了优越性。APS数据集不平衡问题最严重，由图2(a)可知，在原始RF中Accuracy分类精度非常高，但是由图2(b)、(c)可知，其正类分类准确率接近100%，负类分类准确率都不足50%。但是经过改进算法模型训练后，负类分类正确率有明显提升，在R_RF中特异度达到了60%，在RW_RF中更是达到了69%，说明所提出的ReliefF抽样改进方式确实能减轻随机森林算法在处理不平衡数据集中的短板。参见图2(d)，RW_RF的折线均在R_RF和RF之上，说明提出的RW_RF算法具有最佳的分类性能。

综上所述，RW_RF算法不论在消除冗余特征还是减轻不平衡数据对模型的影响方面，都带来了有效的提升。相比于初始随机森林算法，RW_RF算法更适用于解决特征维度高且不平衡的数据分类问题。

4 结束语

围绕多特征及不平衡数据的特殊性对随机森林算法做出了一些改进。将ReliefF算法和Wrapper递归特征选择法融合来代替随机森林算法中的特征选择过程，得到RW_RF算法，并选择5组有代表性的UCI数据集进行分类测试。结果表示，RW_RF算法有更好的分类性能，证明了该改进算法对解决数据的特征冗余和数据不平衡问题有积极意义。

由于使用了递归构造决策树的方法，使得算法时间复杂度大大增加。为了进一步优化模型性能，接下来考虑实现算法并行化，如将模型在Spark并行计算框架中运行，以此来提高整体运算效率。