随机森林简介

随机森林•决策树•分类器组合•随机森林决策树的定义•决策树是这样的一颗树:–每个内部节点上选用一个属性进行分割–每个分叉对应一个属性值–每个叶子结点代表一个分类A1A2A3c1c2c1c2c1a11a12a13a21a22a31a32决策树框架•决策树生成算法分成两个步骤–树的生成•开始，数据都在根节点•递归的进行数据分片–树的剪枝•防止过拟合•决策树使用:对未知数据进行分割–按照决策树上采用的分割属性逐层往下，直到一个叶子节点决策树续2—分裂属性的选择度量原则：分类效果最好的（或分类最纯的，或能使树的路径最短）的属性常用度量信息增益——Informationgain(ID3/C4.5)•所有属性假设都是取离散值的字段（ID3）•经过修改之后可以适用于连续值字段（C4.5）基尼指数——Giniindex(ClassificationandRegressionTress,CART,Breiman,1984)•能够适用于离散和连续值字段信息增益•任意样本分类的期望信息：–I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)•其中，数据集为S，m为S的分类数目，Pi≈|Si/|S|•Ci为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数–I(s1,s2,……,sm)越小，s1,s2,……,sm就越有序（越纯），分类效果就越好。•由属性A划分为子集的熵：–A为属性，具有V个不同的取值，S被A划分为V个子集s1,s2,……,sv，sij是子集sj中类Ci的样本数。–E(A)=∑(s1j+……+smj)/s*I(s1j,……,smj)–信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)•分裂属性选择规则：选择具有最大信息增益的属性为分裂属性基尼指数•集合T包含N个类别的记录，那么其Gini指标就是pj类别j出现的频率•如果集合T分成m部分N1,N2,…,Nm。那么这个分割的Gini就是•分裂属性选择规则：选择具有最小Ginisplit的属性为分裂属性(对于每个属性都要遍历所有可能的分割方法).njpjTgini121)(11()()()mmsplitNNTginiginiginiTTNN过拟合•过拟合的原因：训练样本带噪声或不充分等ErrorOverfittingUnderfittingComplexityErrorLSErrorunseen树的剪枝•剪枝原因和目的：解决决策树对训练样本的过拟合问题•解决方法：剪枝（预剪枝，后剪枝）和树组合•后剪枝原则–最小描述长度原则(MDL)•思想：最简单的是最好的•做法：对Decision-Tree进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”–期望错误率最小原则•思想：选择期望错误率最小的子树进行剪枝•对树中的内部节点计算其剪枝和不剪枝可能出现的期望错误率，比较后加以取舍决策树的用法•大数据集(理想情况):–将数据集划分成3部分:GS,VS,TS–根据GS生成一个树–根据VS进行后剪枝–在TS测试该树的准确率•小数据集(通常)–根据整个数据集生成一个树–用10折交叉验证进行后剪枝–用10折交叉验证测试树的准确率分类器组合•AdaBoosting(AdaptiveBoosting)–对每个样本赋予一个权重，代表该样本被当前分类器选入训练集的概率，并根据预测函数的输出与期望输出的差异调整权重：如某个样本点已被正确分类，则它的权重减小，否则，它的权重增大；通过这种方式，使得学习算法能集中学习较难判别的样本。–经过T轮训练，得到T个分类函数{f1,f2,…,fT}及对应的权重{1,2,…,T}，最终的分类规则为加权投票法•Bagging(Breiman,1996)–在训练的每一轮中，均从原始样本集S中有放回地随机抽取训练样本集T（T的样本个数同S），这样一个初始样本在某轮训练中可能出现多次或根本不出现（S中每个样本未被抽取的概率为(1-1/|S|)|S|≈0.368，当|S|很大时）。–最终的分类规则为简单多数投票法或简单平均法AdaBoosting和Bagging的比较•Adaboosting的训练集选取与前面各轮的学习结果相关；而Bagging训练集的选取是随机的，各轮训练集之间相互独立。•Adaboosting的每个分量分类器有权重，而Bagging的没有权重。•Adaboosting的每个分量分类器只能循序生成，而Bagging可以并行生成。随机森林•随机森林定义•随机森林算法•随机森林的泛化误差•OOB(Out-Of-Bag）估计：泛化误差的一个估计•随机森林的特点随机森林的定义•随机森林是一个树型分类器{h(x,k),k=1,…}的集合。其中元分类器h(x,k)是用CART算法构建的没有剪枝的分类回归树；x是输入向量；k是独立同分布的随机向量，决定了单颗树的生长过程；森林的输出采用简单多数投票法（针对分类）或单颗树输出结果的简单平均（针对回归）得到。随机森林算法•随机选取训练样本集：使用Bagging方法形成每颗树的训练集•随机选取分裂属性集：假设共有M个属性，指定一个属性数F≤M，在每个内部结点，从M个属性中随机抽取F个属性作分裂属性集，以这F个属性上最好的分裂方式对结点进行分裂（在整个森林的生长过程中，F的值一般维持不变）•每颗树任其生长，不进行剪枝随机森林的泛化误差随机森林的泛化误差影响随机森林分类性能的主要因素•森林中单颗树的分类强度（Strength）：每颗树的分类强度越大，则随机森林的分类性能越好。•森林中树之间的相关度（Correlation）：树之间的相关度越大，则随机森林的分类性能越差。OOB估计•计算1（以树为单位,错误）：对每颗树，利用未被该树选中的训练样本点，统计该树的误分率；将所有树的误分率取平均得到随机森林的OOB误分率•计算2（以样本为单位，正确）：对每个样本，计算它作为OOB样本的树对它的分类情况（约1/3的树）；然后以简单多数投票作为该样本的分类结果；最后用误分个数占样本总数的比率作为随机森林的OOB误分率•OOB误分率是随机森林的泛化误差的一个无偏估计•OOB估计是高效的，其结果近似于需要大量计算的k折交叉验证。随机森林的特点•两个随机性的引入，使得随机森林不容易陷入过拟合•两个随机性的引入，使得随机森林具有很好的抗噪声能力•对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。•可生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性：pij=aij/N,aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数。•可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量）主要参考文献1.J.R.Quinlan.InductionofDecisionTrees[J].Machinelearning1986,1:81-106.2.S.L.Salzberg.BookReview:C4.5ProgramsforMachineLearningbyJ.RossQuinlan[J].MachineLearning,1994,3:235-240.3.L.Breiman,J.Friedman,al.et.ClassificationandRegressionTrees[M].NewYork:Chapman&Hall,1984.4.L.Breiman.RandomForests[J].MachineLearning,2001,45(1):5-32.5.