基于节点匹配代价优化的随机森林算法

朱 瑛，谢 睿，郑若池

(沈阳航空航天大学 机电工程学院，辽宁 沈阳 110136)

0 引 言

近年来，随着随机森林算法的研究和应用越来越多，如何提高随机森林的分类精度已然成为了研究的热点。作为一种以决策树为基学习器的有监督的集成学习算法[1]，决策树的数量和决策树间的多样性对随机森林的分类精度有着重大影响[2]。研究过程中发现，过多的决策树，不仅不能有效地提升分类精度，反而会增加随机森林训练的时间，因此越来越多的学者开始围绕如何提升随机森林中决策树的多样性进行研究。薛铭龙等[3]通过设置不同的惩罚项因子来保证在训练随机森林中生成结构不同的决策树。关晓蔷等[4]通过为不同的类别设置不同侧重的基分类器，使产生的决策树结构尽可能的不同。王诚等[5]以Kappa的统计量作为决策树间相似度的判别依据，对随机森林中的决策树进行有选择的保留。Mashayekhi等[6]基于爬山策略的贪婪方法，增删若干决策树来确保随机森林的多样性。上述改进算法均能有效增加随机森林的多样性，提升随机森林的分类精度，但是在随机森林的训练中改变决策树的结构，会增加算法的复杂性。增删决策树，虽然计算简单，但会导致随机森林陷入局部最优。因此在实际应用中，需要一种简单高效的方法来计算出决策树间的相关性，丰富随机森林的多样性，进而提升随机森林的分类精度。

本文基于决策树的分支节点信息，以决策树节点间的最高匹配代价作为两个决策树间的相似度，构建决策树间的相似度矩阵，结合相似度矩阵对随机森林中的决策树进行聚类分析，保留每类中Kappa系数最高的决策树构建新的随机森林，并利用Kappa系数对保留的决策树进行加权处理，进一步弱化分类精度差的决策树对分类结果的影响。

1 决策树的相似度

随机森林是以决策树为基分类器，通过统计每个决策树分类输出结果的众数来得出随机森林的分类结果，因此决策树之间的相似度对随机森林的分类精度有着巨大的影响[7]。随机森林的多样性越丰富，分类结果的可信度越高，在一定程度上增加随机森林中决策树的数量能有效地丰富随机森林的多样性，提高随机森林分类的精度，但是过多的决策树数量，会增加算法计算的时间，同时增加过多的决策树会随机引入更多分类精度差的决策树，影响随机森林的分类性能。因此，通过对随机森林中决策树之间的相关性进行分析，增加随机森林的多样性，能有效地提升随机森林的分类精度。

本文在Perner[8]所提出的对比决策树分支结构来计算相似度的基础上进行研究。在随机森林中决策树均为自由生长，不剪枝，若匹配决策树的分支结构会增大计算负担，且会弱化两个子规则相似，结构不同的决策树之间的相似度。为此本文提出通过计算节点间的匹配代价来评估两个决策树之间的相似度。相对于计算分支结构，通过比对节点属性信息的方法计算量更小，方法更简单，通过形成决策树节点间代价矩阵，以最高总匹配代价的均值作为决策树之间的相似度能更好评估出具有相同结构或相同节点的两棵决策树之间的相似度。决策树之间相似度的计算步骤如下：

步骤1 通过Bootstrap法对原训练集进行重采样，建立与原训练集大小一致的新训练集，并对新生成的训练集每一列单独进行归一化处理。

步骤2 对每个训练子集训练得出与之对应的决策树，并记录下每个决策树的根节点，内部节点的位置以及其对应的分裂节点属性X和分裂值T。

步骤3 统计两个决策树中的分支节点数量为N1和N2，选取两个决策树中分支节点数量最大的值作为n。在两个决策树中任意选取两个分支节点，构建两个决策树节点间n×n维的代价矩阵Sim_node

(1)

节点间匹配代价的计算规则如下：

(1)当决策树Tree1的分支节点数N1

(2)当决策树节点属性为离散属性时，先判断决策树Tree1中的分裂节点与决策树Tree2中分裂节点的属性值是否一致。若属性值不一致，Sim.n=0。若属性值一致，Sim.n=1

(2)

M=|Ttree1.node1-Ttree2.node2|

(3)

(4)

步骤4 通过分裂节点的相似度矩阵Sim_node，计算出两个决策树中任意两节点间匹配代价之和最高的组合，即在每一行(列)中找出一个值，Sim(k)=Sim.n(i,j)(i,j,k∈(1,2,3…n))，其中i和j的取值均不重复，从所有组合中通过匈牙利匹配算法找出使Sim(k) 之和最大的组合，即找出两个决策树节点间匹配的最大值，使总匹配代价最高，并将得到的总的匹配代价均分到n个节点上，即得出两个决策树之间的相似度Sim.t

(5)

步骤5 在随机森林中任意选取两个决策树Tree1和Tree2。通过上述方法，计算两个决策树之间的相似度，构建决策树间的相似度矩阵Sim_tree

(6)

决策树的多样性可由相似度矩阵的统计量V来判定，当V的值越大时，决策树的多样性越大，分类的精度也越高，分类结果的可信度越高；反之，当V的值越小时，决策树的多样性越小，分类的精度越小，分类结果的可信度也就越低

(7)

式中：N——决策树相似度矩阵中元素的总个数；S——决策树相似度矩阵中最多的同值元素个数。

通过比较决策树的节点信息，获得节点间匹配代价最高值来计算决策树间的相似度，相对于通过比较决策树的分支规则来建立相似度的方法而言，不仅计算量更小，同时还能减小决策树之间的类内差异度，增大决策树之间的类间差异度，更利于对决策树进行分类。

2 分类性能评估

分类器的性能评价准则多种多样，常用的二分类模型的评价准则有AUC(area under curve)指标、准确率(precision)、召回率(recall)和F1分数(F1-score)等[9]，但是对于多分类问题而言，二分类模型的评价准则指标难以满足评价要求，因此本文采用Kappa系数作为分类器性能的评价准则，来评价分类器的分类精度[10]。

计算Kappa系数，首先建立混淆矩阵(如图1所示)，在混淆矩阵中Tn表示分类器预测值属性与真实值属性一致的样本个数；Ei,j表示真实值类别属性为类别i，而分类器的预测值类别属性为类别j的样本个数；sum_t(s)(s∈[1,n]) 表示各个类别真实值的样本个数总和；sum_p(s)(s∈[1,n]) 表示各个类别预测值的样本个数总和。

图1 混淆矩阵

Kappa系数的计算方法如下式(8)所示

(8)

其中，Po为总体分类精度，即预测值类别与真实值类别一致的样本数之和与样本总数N的比值

(9)

Pe表示各预测值类别样本数与真实值类别样本数的乘积之和与样本数的平方N2之间的比值

(10)

根据Kappa系数的一致性检验等级标准，Kappa系数的取值在[-1,1]之间，在计算过程中K取值通常在[0,1] 范围内，当K的取值越大，一致性越高，分类精度越高，当K=1时，一致性最强，分类精度最高，K=0时，一致性与偶然误差相同，分类精度差[11]，当K<0时，此时建立的分类模型精度最差，可舍去此类模型。

3 随机森林算法的改进

目前决策树常用的生成方法有ID3、C4.5、CART(classification and regression tree)等，本文中的随机森林算法的子分类器决策树由CART分类回归树构建，CART算法采用的是一种二分递归分割，将当前的样本集分为两个子样本集，使得生成的每个非叶子节点都有两个分支[12]，且在构建决策树的过程中让决策树自由生长，不进行剪枝操作。本文采用的聚类加权随机森林算法，通过对随机森林中的子分类器进行聚类，以Kappa系数衡量每一个子分类器的分类精度，选出每一类中最高Kappa系数的决策树为该类决策树的代表，构建新的随机森林，并以Kappa系数对每一类中决策树的代表进行加权处理。改进的聚类加权优化随机森林算法流程如下所示：

步骤1 对原始的训练数据进行划分，随机抽取80%的原始训练数据用作决策树的训练数据，构建随机森林模型，20%的原始训练数据用于对随机森林模型的检验。

步骤2 预设决策树数量m，利用Booststrap算法对训练数据采样得到的训练集，生成决策树，并记录每个决策树的分支节点位置、节点的属性和分裂值，组合这些决策树构建出随机森林模型。

步骤3 计算任意两决策树中任意两节点的相似度Sim.n，构建两决策树节点间的代价矩阵Sim_node。通过匈牙利算法，计算得出两节点间匹配代价最高的组合。构建任意两决策树间的相似度矩阵Sim_tree。

步骤4 预设决策树聚类数量Q，根据决策树间的相似度矩阵Sim_tree，构建邻接矩阵W、度矩阵D和拉普拉斯矩阵L，得出标准化后的拉普拉斯矩阵D-1/2*L*D-1/2。寻找出D-1/2*L*D-1/2最小的k个特征值，并计算出其特征向量f，构建出特征向量空间，利用K-means对特征向量f进行聚类。

步骤5 利用检验数据，得出聚类后每个类别中决策树的Kappa系数，选取每个类别中Kappa系数最高的决策树重新组建新的随机森林模型，并以Kappa系数为权重对新随机森林中每棵决策树进行加权处理。

4 实验结果分析

本文实验所采用的软件为MATLAB R2014，处理器为Intel(R) Xeon(R) CPU E5-1607 V2 @3.GHz，实验所采用的数据集从加州大学欧文分校(University of California Irvine，UCI)的机器学习数据库中选取。包括Gazi大学医学院博士Nilsel Ilter 提供的皮肤病学数据库(Dermatology Database)：利用临床数据和组织病理学属性用于对皮肤病进行分类；威斯康星大学提供的乳腺肿瘤诊断数据集(Breast Cancer Wisconsin (Diagnostic) Data Set)：通过对病灶组织的细胞核量化特征识别，分析对乳腺癌进行诊断；葡萄牙波尔图大学医学院提供的胎儿心脏图(CTG)并通过产科专家的诊断得到的特征数据集(Cardiotocography Data Set)：通过对胎儿心率(FHR)和子宫收缩(UC)特征等形态学模式分析，判断胎儿的状态。实验数据集的信息见表1。

表1 实验数据集信息

实验流程如图2所示。

图2 实验流程

本文实验利用上述3个数据集来对比聚类加权改进后的随机森林算法模型与原始的随机森林算法模型的分类精确度，分析改进后随机森林算法模型的分类性能。实验数据集Dermatology为不平衡数据集，由于随机森林在处理不平衡数据时的性能表现较差，分类误差大，分类的结果不稳定，为此在处理该类不平衡数据时，对实验数据集进行SMOTE过采样的方法[13]，来消除不平衡数据集对实验结果的影响。

在根据Kappa系数构建新的随机森林时，若某一类保留下来的决策树的Kappa系数小于0时，就舍弃该类决策树，避免在新的随机森林中引入分类能力差的决策树。由于决策树的棵数对随机森林的泛化性能有一定的影响，先设置原始森林中决策树的棵数m∈[10,20,30,40,50…240,250]，进行分类仿真实验，根据仿真结果，选择分类精度最高时所对应的决策树棵数m作为原始森林决策树的数量。再依次选取聚类数量Q(Q≤m)，得出不同聚类数量下优化后随机森林的分类精度，根据实验结果分析优化后随机森林模型的性能。为了避免随机性对分类精度的影响，确定决策树数量或聚类数量后，构建100个随机森林模型，以这100个随机森林分类精度的平均值作为当前决策树棵数或聚类数量下随机森林的分类精度。

在原始随机森林算法中选取不同的决策树数量，仿真实验得到的分类精度如图3所示。

在原始随机森林中，各个数据集对应的最优决策树数量及分类精度见表2。

由图3可以看出在测试3组样本数据时，在不同决策树的数量m下，原始随机森林的分类精度不同。在寻找聚类数量Q时，选取在原始森林中分类精度最高，决策树数量相对最小所对应的决策树的棵数(见表2)构建原始随机森林，再依次迭代Q值，得出优化后随机森林的分类精度，绘制出不同聚类数量Q下，各个数据集在优化后的随机森林中分类精度如图4所示。

表2 各个数据集下最优决策树数量及分类精度

在优化后的随机森林中，各个数据集对应的最优聚类数量及分类精度见表3。

在图3和图4中，随着决策树数量和聚类数量的增多，预测分类精度出现较大的曲折变化，这是由于随机森林的随机性导致。通过图4和表3中可以看出改进后的随机森林与原始随机森林中的最高预测分类精度相比较，优化后的随机森林对样本分类的分类精度更高，表明该种聚类加权的方法能有效地提升了随机森林分类器的分类性能。通过分析图4中3个样本预测分类精度曲线趋势，在聚类数量低时，优化后的随机森林分类的分类精度低于原始森林的分类精度，这是因为在聚类数量低时，随机森林的多样性较小，分类精度较低。随着聚类数量的增多，优化后的随机森林的分类精度高于原始的随机森林，此时随机森林的多样性大于原始森林的多样性，每棵决策树投票的可信度也更高。当聚类数量与原始森林中决策树的数量一致时，优化后的随机森林的多样性再次降低，分类精度也与原始森林基本一致。

图3 不同决策树数目下原始森林的分类精度

图4 不同聚类数量下改进森林的分类精度

表3 改进后各数据集的最优聚类数量及分类精度

5 结束语

本文通过比对任意两决策树中节点属性值和分裂属性来构建节点间的代价矩阵，以节点间匹配代价最高的均值作为决策树间的相似度，基于相似度矩阵利用谱聚类算法对原始随机森林进行分类，构建新的随机森林，在新的随机森林中单棵决策树以自身的Kappa系数进行加权投票，使得在增加随机森林的多样性的同时也增加了单棵决策树投票的可信度，提升随机森林的分类精度。通过UCI的3个样本数据集来测试聚类加权后新随机森林算法的性能，实验结果表明：

(1)通过计算随机森林中决策树节点匹配代价构造节点代价矩阵来得出决策树间相似度的方法简单可行，能有效评估出随机森林中决策树之间的相关性。

(2)在合适的聚类数量下，优化后的随机森林的分类精度高于原始随机森林的分类精度。

接下来对本文算法的改进工作是寻找出原始森林中最优决策树数量与聚类数量之间的联系，以便于快速找出最优的聚类数量，更进一步地提升优化后随机森林算法的性能。