【《基于混合采样的改进随机森林算法概述》7200字】

基于混合采样的改进随机森林算法概述目录TOC\o"1-3"\h\u19450基于混合采样的改进随机森林算法概述 1143571.1问题分析 1235551.2算法的基本思路 2155291.3算法的具体实现 4260661.1.1混合采样算法的实现 4142601.1.2改进随机森林算法的实现 535621.4实验分析与验证 8194301.4.1实验环境 890951.4.2实验数据集 9116671.4.3评价指标 9193471.4.4实验结果分析 111.1问题分析在用于电信单宽转融预测的数据集中，具有转融倾向的单宽用户与非转融倾向的单宽用户在数量上存在着较大的差异，类别不平衡是其显著的特点，因此，电信的单宽转融预测问题本质上属于不平衡数据集的分类问题。传统的分类算法对不平衡数据集进行分类时，会出现多数类样本的识别准确率高，少数类样本的识别准确率较低的出题。在电信的单宽转融预测问题中，重点关注的是少数类样本即具有转融倾向的单宽用户。因为，少数类样本能反映出重要的信息。因此，本章的首要目标是提高少数类样本的识别准确率。目前，针对不平衡数据集分类问题的研究，主要包括数据层面的方法和算法层面的方法。数据层面上的方法包括欠采样算法、随机过采样算法、SMOTE算法等。其中，欠采样算法通过随机的删除部分多数类样本，来达到平衡数据集的目的，在这一过程中，会导致部分多数类样本的重要信息丢失。随机过采样算法只是随机的对少数类样本进行简单的复制，来保证不同类别的样本数量的平衡。在这个过程中没有产生任何新信息，因此会产生过拟合的问题。SMOTE算法由于忽视了少数类样本内部分布不均匀的问题，导致在合成新的少数类样本过程中会产生模糊边界的问题。算法层面上的方法包括集成学习、代价敏感方法等。本章将选用集成方法中的随机森林算法开展研究。随机森林算法对不平衡数据集进行分类时，在一定程度上可以平衡类别误差。但是，传统的随机森林算法也存在着一些不足。首先，由于随机森林算法采取有放回的方式随机的为每棵决策树选择训练子集，使得训练子集之间具有相同的重复样本，导致训练出的决策树之间存在着一定的相似性，降低了随机森林树结构的多样本，而影响随机森林算法的整体泛化能力。其次，传统的随机森林算法在投票阶段，为每棵决策树赋予相同的投票权重，因此，会有一些分类性能不好的决策树投出错误的票数，而影响随机森林算法的整体分类准确率。针对以上问题，本章提出了基于混合采样的改进随机森林算法（简称BSM-TL-IRF），来解决不平衡数据集的分类问题。1.2算法的基本思路针对1.1节的问题分析，本章从数据层面和算法层面出发，提出了BSM-TL-IRF算法来解决不平衡数据集分类问题中少数类样本识别率低的问题。图1.1为BSM-TL-IRF算法的流程图。该图详细地描述了BSM-TL-IRF算法对不平衡数据集的分类过程。图1.1BSM-TL-IRF算法流程Fig.1.1BSM-TL-IRFalgorithmflow由图1.1可知，BSM-TL-IRF算法主要分为两个层面来解决不平衡数据集的分类问题。在数据层面上提出了将改进的SMOTE算法和TomekLinks算法相结合的混合采样算法（简称BSM-TL），该混合算法在处理不平衡数据集时，首先将少数类样本分为边界样本、安全样本和噪声样本。然后，采用SMOTE算法对边界样本进行线性插值，合成新的少数类样本。最后，采用TomekLinks算法清除数据集中的噪声样本和合成少数类样本过程中产生的边界重叠样本。在算法层面上提出了IRF算法，IRF算法是对传统随机森林算法的改进。该算法的基本思想是根据决策树的分类性能和决策树之间的相似性来优化随机森林的树结构，通过选取分类性能较好且相似性较低的决策树组成新的随机森林，并在最后的投票表决阶段，为决策树赋予不同的投票权重，使得分类性能较好决策树拥有较大的投票权重，来提高随机森林算法的整体分类准确率。1.3算法的具体实现本节将对BSM-TL-IRF算法的具体实现进行详细的介绍，该算法在对不平衡数据集进行分类时，主要分为两个阶段，第一个阶段利用BSM-TL算法对数据集进行平衡化处理，第二阶段利用IRF算法对平衡化后的数据集进行分类。下面将分别对BSM-TL算法和IRF算法的实现过程进行详细的阐述。1.1.1混合采样算法的实现混合采样算法(BSM-TL)的核心思想是在处理不平衡数据集时，首先对少数类样本进行区分，将其划分为安全样本，边界样本，噪声样本，然后利用公式(1.1)对边界样本线性插值，合成新的少数类样本，最后利用TomekLinks算法清除数据集中的噪声样本、边界重叠样本以及位于类别边界处上距离较近的异类样本对，得到一个类簇分布良好的平衡数据集。BSM-TL算法的流程如图1.2所示。BSM-TL算法的具体步骤如下：假设原始的训练样本集为T，多数类样本集为M，少数类样本集为N，其中M={m1,m2,⋯,m输入：原始的训练数据集T，近邻样本个数k输出：平衡数据集T(1)计算少数类样本中的每个样本点ni(2)对少数类样本进行划分，假设在k近邻中有k'若k'=k，若0≤k'≤k/2，ni若k/2≤k'≤k，其中，边界样本记为{(n(3)计算边界样本点ni'与少数类样本N的k近邻，利用公式(n(1.1)(4)将合成的少数类样本与原始的训练样本T合并，构成新的数据集T'(5)对数据集T'，进行TomekLinks数据清洗操作，将Tomek-links对中的多数类样本进行删除，得到平衡的数据集T图1.2BSM-TL算法流程Fig.1.2BSM-TLalgorithmflow1.1.2改进随机森林算法的实现IRF算法是对传统随机森林的改进，该改进算法主要分为三个阶段，第一阶段，采用AUC评价指标评估随机森林中决策树的分类性能。并设置相应的阈值，选取高于阈值的决策树进行组合，形成新的随机森林。第二阶段，计算新的随机森林中每棵决策树之间的相似性，将相似性较高的决策树进行有选择性的保留，来保证随机森林树结构的多样性，提高其整体的泛化性能。第三阶段，在前两个阶段的基础上，改进随机森林的传统投票机制，在投票阶段，根据决策树的分类精度，为不同的决策树分配不同的投票权重，使得分类精度越好的决策树，具有的投票权重越大，进而提高随机森林的整体分类性能。该算法的流程如图1.3所示。图1.3IRF算法的流程Fig.1.3IRFalgorithmflow(1)选取分类性能好的决策树输入训练样本集，训练出原始的随机森林模型。然后将测试集输入到训练好的模型中去，计算出每棵决策树的AUC值。利用AUC指标来衡量决策树的分类性能。其中，AUC值越大，表明决策树的分类性能越好。反之，AUC值越小，决策树的分类性能越不好。因此，将AUC值作为单棵决策树的分类精度。本文的方法是筛选出分类精度超过原始随机森林F={ti,i=1,2⋯N}平均分类精度的决策树，来组成新的随机森林。如公式(1.2)所示，其中，A表示原始随机森林的平均分类精度，SubF表示新的随机森林子集。tSubF={(1.2)如果SubF中决策树的数量超过原始随机森林的2/3,则将SubF作为新的随机森林，否则，降低决策树的选择标准，计算出原始随机森林中每棵决策树的AUC值的标准差σ，再筛选出AUC值大于等于A−σ的决策树组成新的随机森林。SubF={(1.3)通过以上分析，选取分类性能较好的决策树，组成新的随机森林，其具体步骤如下：1)采取Bootstrap的方式，从原始数据集中随机有放回的选取出k个训练子集。2)基于训练子集，训练出k棵决策树，并组合成随机森林模型。3)将测试集输入到训练好的模型中，计算每棵决策树的AUC值。4)计算随机森林中每棵决策树的平均精度和标准差σ5)从随机森林中筛选出AUC≥A或AUC≥A−σ的决策树组成新的随机森林。(2)计算决策树的相似度在上一阶段中，得到的新的随机森林通过剔除了传统随机森林算法中分类性能不好的决策树，提升了算法的整体分类性能。但是在上一阶段中，没有考虑到决策树之间的相似性。如果组成随机森林算法的决策树之间具有相似性，在使用这些决策树进行分类时会有相同的分类行为，如果出现分类错误，那么具有相似性的决策树都会分类错误。不但降低了随机森林算法的多样性，导致算法的泛化能力较差，而且也影响了随机森林模型的整体分类准确率。针对上述分析，本阶段将基于相似性进一步优化随机森林算法的树结构。优化的基本思路是，首先，计算各决策树的相似性。然后，将相似性较高的决策树进行有选择性的保留，保留精度较高的决策树。最后，将筛选出的高精度且相似性不同的决策树进行组合，得到进一步的改进随机森林算法。本文选用kappa系数来评估决策树的相似性，kappa系数越大，决策树的相似性越高。kappa系数的计算是基于混淆矩阵的，其计算公式如(1.4)所示。k=(1.4)其中po是样本的总体分类准确率，假设每一类的真实样本个数分别为a1,a2⋯amp(1.5)(3)加权投票策略的实现传统的随机森林算法在投票阶段，为每棵决策树分配相同的投票权重。因此。会导致一些分类性能不好的决策树投出错误的票数，而影响随机森林算法的整体分类效果。为了避免这种情况的发生，引入了“加权”的思想来改进随机森林的传统投票机制。改进策略的核心思想是，根据决策树的分类精度，为每棵决策树分配相应的投票权重。分类精度的计算如式(1.6)所示W(1.6)其中，Wl表示第l棵决策树的分类精度。Xlcor为第l采用上述方法为每棵决策树赋予相应的权重。则改进后随机森林模型的输出可表示为如式(1.7)所示。f(1.7)其中，f为模型输出；x为模型的待测样本；c为模型的类别数目，i是c中的某一类。L为决策树的数目。1.4实验分析与验证1.4.1实验环境在实验中，使用的操作系统为Windows10，处理器为Intel(R)Core(TM)i7-8550UCPU@1.80GHz和16GRAM内存。编程语言为python1.7，开发平台为jupyternotebook,实验的主要配置如表1.1所示。表1.1实验配置表Table1.1Experimentalconfigurationtable软硬件环境配置情况操作系统Windows10CPUIntel(R)Core(TM)i7-8550UCPU@1.80GHz2.00GHz开发平台Jupyternotebook开发语言Python1.7内存16G1.4.2实验数据集为了验证本文提出的BSM-TL-IRF算法的有效性。从UCI机器学习库中选择了5个经典的不平衡数据集作为实验数据集。数据集的详细信息如表1.2所示。本文研究的是不平衡数据集的二分类问题，因此，对多类别的数据集进行人为的调整，将其转换为二分类数据集。调整后将样本数较多的一类定义为多数类，样本数较少的一类定义为少数类。其中，数据集的不平衡率定义为多数类样本数和少数类样本数的比值，表示数据集中多数类样本和少数类样本之间的不平衡程度。不平衡率越大，数据集越不平衡。表1.2UCI数据集Table1.2UCIdatasets数据集维度总样本数多数类少数类不平衡率breast116994582411.90german2010007003002.33ecoli8336259771.36car7172812105182.34pima97685002681.871.4.3评价指标传统的机器学习算法通常以准确率作为模型的评价指标，准确率是指分类正确的样本数与总样本数的比。针对不平衡数据集问题，仅使用准确率作为模型的评价指标时，会导致少数类样本的分类准确率较低。传统的评价指标易受到样本类别分布的影响，不适用于对不平衡数据集的分类问题进行评估。因此，本章采用适合评估不平衡数据集分类性能的评价指标。下面，首先引入了混淆矩阵[57]的概念，如表1.3所示。表1.3混淆矩阵Table1.3confusionmatrix预测正类预测负类实际正类TPFN实际负类FPTN其中TP表示实际为正类且预测为正类的样本数，TN表示实际为负类且预测为负类的样本数，FN表示实际为正类预测为负类的样本数，FP表示实际为负类预测为正类的样本数。根据上述混淆矩阵，本文引入了准确率(Accuracy)、G-mean、F-value和AUC四个评价指标[58]用于评估算法的分类性能，各指标的详细描述如下：(1)AccuracyAccuracy是指分类正确的样本数与总样本数的比,其定义如式(1.8)所示。Accuracy=(1.8)(2)G-meanG-mean评价指标是由KubatM等人[59]提出的，G-mean是一个综合性的评价指标，可以反映出多数类样本和少数类样本的识别准确率，用来表示分类器的综合分类性能。是不平衡数据集分类问题中常用的评价指标。其计算公式如式(1.9)所示。G−mean=(1.9)其中，TP(TP+FN)表示的是少数类样的识别准确率，(3)F-valueF-value指标综合考虑了不同类别样本的查准率和查全率[60]，是查全率和查准率的调和平均值。其计算公式如式(1.10)所示。F−value=(1.10)其中，β是一个系数，表示的recall和precision的相对重要性，F-value可以正衡量出不同类别样本的分类性能，当precision和recall的值都比较高时，对应的F-value的值会比较大，说明少数类样本的识别准确率较高。(4)ROC曲线及AUC值受试者工作特征曲线（简称ROC曲线）是由SwetsJ提出的，是评价不平衡数据集的综合指标[61]。ROC曲线的横轴是假阳性率，纵轴是真阳性率。通过对测试样本的预测概率排序，不断改变决策阈值，将测试样本分为正类和负类两部分。将得到的每一个样本的(FPR,TPR)点连接起来，并拟合成曲线。ROC曲线越靠近左上角，表明分类器的分类性能越好。ROC曲线的优点是不受数据集类别分布的影响，非常适用于作为不平衡数据集分类问题的评价指标。图1.4是ROC曲线的示例图，该图引用自维基百科。图1.4ROC曲线示例图Fig.1.4ExampleROCcurvechart虽然ROC曲线绘制简单，可以直观的反映出分类器的分类性能，但是ROC曲线不能对分类器的分类性能进行定量的评价，因此，引入了新的评价指标AUC值[62]，AUC值本质上是ROC曲线的量化指标，ROC曲线下的面积表示AUC值。AUC值越大，分类器的分类性能越好。在本章的实验研究中，将选用Accuracy、G-mean、F-value以及AUC值作为本章提出的BSM-TL-IRF算法的评价指标。1.4.4实验结果分析本章实验选用上述提到的5个数据集，利用python语言在jupyternotebook平台上做了相关的对比实验。对本章提出的BSM-TL-IRF算法的有效性进行验证。实验首先将TomekLinks算法(简称TL)、SMOTE算法（简称SM）、SMOTE+Tomek-Links(简称SM-TL)算法和本章提出的混合采样算法(简称BSM-TL)在KNN、决策树和随机森林上进行对比，来验证BSM-TL算法的有效性。然后将经过BSM-TL算法预处理后的数据集，分别在传统的随机森林算法和本文提出的改进随机森林算法(简称IRF）上进行实验，来验证改进随机森林算法的有效性。实验中各采样算法在KNN上的实验结果的各项指标如图1.5到和1.8所示。图1.5KNN上的分类准确率Fig.1.5ClassificationaccuracyonKNN图1.6KNN上的分类AUCFig.1.6ClassificationAUConKNN图1.7KNN上的分类G-mean图1.8KNN上的分类F-valueFig.1.7ClassificationofG-meanonKNNFig.1.8ClassificationofF-valueonKNN分析上述的实验结果可知，本文提出的BSM-TL算法在breast、german、ecoli和car这4个数据集上的四个指标均优于其他采样算法。经过BSM-TL算法预处理后的数据集，其分类结果的Accuracy和F-value值在4种采样算法中都是最优的。而在pima数据集上，BSM-TL算法的AUC值和G-mean值略低于SM(SMOTE)算法。这是因为pima数据集的不平衡率相对较低，且数据集中的噪声样本较少，导致BSM-TL算法没有充分发挥出其优势。SM(SMOTE)算法在对pima数据集进行平衡化的过程中，产生了过拟合的问题，因此，出现了其AUC值和G-mean值略高于本文提出的BSM-TL算法。但从整体上来看，BSM-TL算法的分类性能优于其他三种对比算法，是较为有效的。为了充分地对比本文提出的BSM-TL算法的优势，在图1.9到1.12中分别绘制了各采样算法在5个数据集上的预测结果变化曲线。图1.9决策上的分类准确率图1.10决策树上的分类AUCFig.1.9ClassificationaccuracyondecisiontreeFig.1.10ClassificationAUCondecisiontree图1.11决策上的分类G-mean图1.12决策上的分类F-valueFig.1.11ClassifiedG-meanondecisiontreeFig.1.12ClassifiedF-valueondecisiontree分析图1.9到1.12的实验结果可知，本文提出BSM-TL算法在5个数据集上的4个指标上的值均优于其他三种对比算法。尤其在german数据集上，BSM-TL算法在各指标上的提升效果较明显。综合以上实验结果分析可知，BSM-TL算法对平衡率不同的各非平衡数据集具有较强的适应性，可以作为不平衡数据集分类问题的算法。为了验证本文提出的改进随机森林算法(简称IRF)的分类性能，将其与传统的随机森林算法在5个数据集上进行实验对比，实验结果如表1.4和1.5所示。表1.4传统随机森林算法上的分类结果Table1.4Classificationresultsontraditionalrandomforestalgorithm数据集算法AccuracyAUCG-meanF-valueBreastTomekLinks0.91190.89220.90870.8919SMOTE0.92000.91300.91170.9053SMOTE-TL0.93220.92770.92200.9283BSMOTE-TL0.94540.93920.94530.9375germanTomekLinks0.68800.72720.62130.7103SMOTE0.78190.73150.69680.7806SMOTE-TL0.80000.76010.79800.7965BSMOTE-TL0.81330.80740.79680.8158ecoliTomekLinks0.87270.80540.86540.8731SMOTE0.88310.87630.87500.8824SMOTE-TL0.90460.88610.89610.9187BSMOTE-TL0.92750.90500.91630.9155carTomekLinks0.89590.91940.90200.9107SMOTE0.91170.92790.9110.9203SMOTE-TL0.92030.94960.92470.9343BSMOTE-TL0.93590.96660.94660.9570pimaTomekLinks0.75440.76600.76250.8068SMOTE0.78650.78400.79610.8188SMOTE-TL0.79140.80320.80150.8297BSMOTE-TL0.80170.82150.81650.8417表1.5改进随机森林算法上的分类结果Table1.5Classificationresultsonimprovedrandomforestalgorithm数据集算法AccuracyAUCG-meanF-valuebreastTomek-links0.93520.90080.91400.9123SMOTE0.94780.91620.92540.9285SMOTE-TL0.95110.93190.94810.9427BSMOTE-TL0.97650.95790.95060.9500GermanTomek-links0.72720.74770.64130.7382SMOTE0.80120.76850.70250.7956SMOTE-TL0.81330.77980.79920.8174BSMOTE-TL0.83600.81580.81780.8457EcoliTomek-links0.89080.87320.89150.8907SMOTE0.90170.89370.90220.9110SMOTE-TL0.92310.91610.92290.9248BSMOTE-TL0.93460.92930.93420.9324carTomek-links0.92090.92500.91110.9203SMOTE0.93450.93110.91310.9378SMOTE-TL0.94350.95570.92550.9422BSMOTE-TL0.95940.96970.94970.9659pimaTomek-links0.76540.79650.78700.8329SMOTE0.80670.80140.80660.8550SMOTE-TL0.82140.82670.83630.8715BSMOTE-TL0.84400.84140.85710.8706通过对比分析表1.4和表1.5可