数据挖掘之随机森林算法论文

1、摘要随机森林(Random Forests )算法是一种集成分类、是简单而有效的集成学习分类算法，它在属性属性较多的数据上有极佳的分类效果，广泛应用于文本分类与检索、生物医学数据分类等实际应用中。通过对随机森林算法进行分析，并用通过代码实验来体会其算法中参数对分类效果的高效性，通过对比其最终分类的准确率来判断随机森林算法设计的好坏。关键词 随机森林集成学习121 引言 32 理论介绍 32.1 信息、熵以及信息增益的概念 32.2 决策树算法 32.3 CART 决策树算法 32.3.1 CART算法的认识 32.3.2 CART算法的原理 32.4 C4.5 决策树算法 42.5 集成学习

2、42.5.1 集成学习的发展 42.5.2 集成学习定义 42.6 随机森林的生成 42.6.1 随机森林的生成 42.6.2 随机森林的生成规则 42.7 决定随机森林分类效果(错误率)的两个因素: 52.7.1 袋外错误率(OOB error) 52.8 随机森林的简单实例分析 53 实验 73.1 数据集选取 73.2 测试代码 73.3 测试结果 83.4 总结 84 结束语 8数据挖掘之随机森林算法研究与实现作者： XXX1 引言随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支集成学习（ Ensemble Learning）

3、方法。随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。 “森林”我们很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，这样的比喻还是很贴切，其实这也是随机森林的主要思想-集成思想的体现。通过此次对随机森林算法的研究与实验分析，更好的理解并掌握此算法。2 理论介绍2.1 信息、熵以及信息增益的概念信息熵：信息论中最核心的概念和度量方法。熵：描述变量取值的概率的不确定性。不确定性越大，熵值越大。信息增益：在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好2.2 决策树算法决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用

4、归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。2.3 CART 决策树算法2.3.1 CART 算法的认识Classification And Regression Tree ，即分类回归树算法，简称CART 算法，它是决策树的一种实现。CART 算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此 CART 算法生成的决策树是结构简洁的二叉树。由于CART 算法构成的是一个二叉树，它在每一步的决策时只能是“是 ”或者 “否 ”，即使一个feature有多个取值，也是把数据分为两部分

5、。在 CART算法中主要分为两个步骤（ 1）将样本递归划分进行建树过程；（ 2）用验证数据进行剪枝。2.3.2 CART 算法的原理设代表单个样本的个属性，表示所属类别。CART 算法通过递归的方式将维的空间划分为不重叠的矩形。划分步骤大致如下：（ 1 ）选一个自变量，再选取的一个值，把维空间划分为两部分，一部分的所有点都满足，另一部分的所有点都满足，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。（2）递归处理，将上面得到的两部分按步骤（1）重新选取一个属性继续划分，直到把整个维空间都划分完。2.4 C4.5决策树算法C4.5是决策树算法的一种。决策树算法作为一种分类算法，目标

6、就是将具有p维特征的n个样本分到c个类别中去。相当于做一个投影，c=f（n）,将样本经过一种变换赋予一种类别标签。决策树为了达到这一目的，可以把分类的过程表示成一棵树，每次通过选择一 个特征pi来进行分叉。2.5 集成学习2.5.1 集成学习的发展集成学习的理论基础是 PAC理论、强可学习与弱可学习理论。集成学习的理论基础表 明强可学习器与弱可学习器是等价的，因此可以寻找方法将弱可学习器转换为强可学习器，而不必去直接寻找较难发现的强可学习器。具有代表性的集成学习方法有Boosting , Bagging ,随机森林。见图3-1。匚 P&CI BoosiingBaggingRandom

7、Forest I|1984| 型二师一绊! Weakly and Strongly I I teamingEnsemble Leming|（c）1994|图3-12.5.2 集成学习定义集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分 类器，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何-一个单分类的做出预测。随机森林是集成学习的一一个子类，它依靠于决策树的投票选择来决定最后的分类结 果。2.6 随机森林的生成2.6.1 随机森林的生成随机森林中有许多分类树。如果要将一个分类树进行分类，需要将样本输入到每棵树 中进行分类。Bootstraping采样

8、方法：有放回采样。随机森林的bagging思想：将若干个弱分类器（多棵树）的分类结果进行投票选择， 通过表决从而组成一个强分类器。2.6.2 随机森林的生成规则1）如果训练集大小为N,随机且有放回地从训练集中抽取N个训练样本，构成一个新的样本集（含重复的训练样本）。2）如果每个样本的特征维度为M ,指定一个常数 m ,且m< M ,随机地从 M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的，决策树成长期间 m 的大小始终不变。（注意：此处采用无放回的选择）3）每棵树都尽可能最大程度地（完全地）生长，并且没有剪枝过程。（将预测结果累加起来从而得到整个随机森林的预测结果

9、）通过之前的三步就可以得到一棵决策树，重复 X 次这样的过程那么就能得到X 棵决策树。来一个测试样本就对它分类一遍，就得到X 个分类结果。使用简单的投票机制（或用最终分类结果）来判别该样本的所属类。注意：两类随机性的引入对随机森林的生成至关重要。2.7 决定随机森林分类效果（错误率）的两个因素:1 .森林中任意两棵树的相关性:相关性越大，错误率越大;2 .森林中每棵树的分类能力:每棵树的分类能力越强，整个森林的错误率越低。减小m （特征选择个数），树的相关性和分类能力也会相应的降低；增大m,两者也会随之增大。所以关键问题是如何选择最优的m （或者是范围），这也是随机森林唯一的一个参数。2.7.

10、1 袋外错误率（OOB error ）构建随机森林的关键问题就是如何选择最优的m,要解决这个问题主要依据计算袋外错误率。在构建每棵树时,我们对训练集使用了随机且有放回抽样。所以对于每棵树而言,大约有1/3 的训练实例没有参与树的生成,它们称为树的袋外样本数据。这些数据没有参与训练模型的拟合，因此可以用来检测模型的泛化能力。而这样的采样特点就允许进行袋外估计,它的计算方式如下：a对每个样本，计算它作为袋外样本的树对它的分类情况（约1/3的树）；b.然后以简单多数投票作为该样本的分类结果；c.最后用误分个数占样本总数的比率作为随机森林的袋外错误率。OOB 错误率是随机森林泛化误差的一个无偏估计，它

11、的结果近似于需要大量计算的k折交叉验证。所以没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个 无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏 估计。当我们知道了 OOB的计算方法，我们可以通过选取不同的m,计算OOB error,找出OOB error 最小时对应的m 的值，就可以知道最优的m。2.8 随机森林的简单实例分析根据已有的训练集已经产生了对应的随机森林，随机森林如何利用某一个人的年龄（ Age） 、 性别 （ Gender） 、 教育情况 （ Highest Educational Qualification ） 、 工作领域 （ In

12、dustry） 以及住宅地（Residence）共5个字段来预测他的收入层次。收入层次：Band1 ： Below$40000Band 2:$40000 -150000Band3:More than $150000随机森林中每一棵树都可以看做是一棵CART （ 分类回归树），这里假设森林中有5 棵CART 树，总特征个数N=5， 取 m=1 （m 为建立决策树时，随机选取的特征个数，这里假设每个CART树对应一个不同的特征）。（表格中的百分数指的是在不同条件下的数据样本 占对应类别的比例）见图5-1。!5占 g iJkiM1上JM叫口叫电W5410%由，过27然k14%70H23%森OOfHa

13、zflfaMore 廿”7羯25%5%CART 1 ： VviAblQ Aeohlary felrtd1*GerxlerMele70%17%IhQmjki内,mJM(AKT S 1 Vari国 r：*即、fund1?4zGUCJtiCftjHigh 5<hn. 1技顺in%5稀14«kfcatftei jFt77%(JH白泓比W ： VnrAbl# t.4JCBTinn51-邙日孑由-12indu y中Fina，££三%ftcturmg5%Qt*ir5?0%5科CftJCT b ： Varldblh lrnl3krvUAKT 4 ； Tsri%ble Rns

14、iSis旬制T Aril11Mrirn-TflftXJ%RE -ipriirpNon-Metro20%15，图5-1假如要预测的某个人的信息如下(见图5-2):1. Age : 35 years ; 2. Gender : Male ; 3. HighestEducational Qualification : Diploma holder; 4. Industry :Manufacturing; 5. Residence : Metro.根据这五棵CART树的分类结果，可以针对此人的信息建立收入层次的分布情况CARTBand1123Age2S-4070%23%7%GenderMale70%2

15、7%3%EducationDiploma80%14%r e%IndustryManufacturing60%35%5%ResidenceMetro70%20%10%Final probabitityr 70%'24%6%图 5-2最后，我们得出结论：这个人的收入层次70%是一等，24%是二等，6%是三等。所以我们得出结论:这个人的收入层次是一等(小于$40000) 。3 实验3.1 数据集选取数据集选择UCI 数据集中的红葡萄酒的数据集。此数据集包含有红葡萄酒的11 个特征：非挥发性酸、挥发性酸度、柠檬酸、残糖、 氯化物、游离硫二氧化物、总二氧化硫、密度、PH、硫酸盐、酒精。通过红葡萄

16、酒的11 个特征判断红葡萄酒的品质，类标签用110 的数字来表示。共有 1599 个红葡萄酒的样本。3.2 测试代码%清空环境变量clear allclcwarning off%导入数据%1.随机产生训练集测试集a=randperm(1599);Train=winequalityred(a(1:1200),:); % 产生 1200 个训练集Test=winequalityred(a(1201:end),:); % 剩下的是测试集399 个%2.训练数据P_train=Train(:,1:11);T_train=Train(:,12);%3.测试数据P_test=Test(:,1:11);T_

17、test=Test(:,12);%调用Random Forest 算法btree=TreeBagger(50,P_train,T_train,'NVarToSample','all','Method','classification');pred_labels,scoresl=predict(btree,Test);predict_label=cellfun(x)str2double(x),pred_labels);%将 cell 类型的 pred_labels 转化为 double 型的 predict_labelT_test1

18、=table2cell(T_test);%将 table 型的 T_test 转化为 cell 型的 T_test1T_test2=cell2mat(T_test1);%各cell型的T_test转化为double型的T_test2accuray=sum(T_test2( :,1)=predict_label( :,1)/399;%十算测试集数而的标签预测准确率本次测试调用随机森林算法，对其参数NVarToSample和Method进行设置，也可以通过测试其他的参数来提高随即森领算法的预测率。3.3 测试结果如图6-1名称，一m士前E筠.回工 Ba.回EE若Ek白c匚 btree Ptest P