随机森林简介.ppt

随机森林 决策树 分类器组合 随机森林 决策树的定义 决策树是这样的一颗树: 每个内部节点上选用一个属性进行分割 每个分叉对应一个属性值 每个叶子结点代表一个分类 决策树框架 决策树生成算法分成两个步骤 树的生成 开始，数据都在根节点 递归的进行数据分片 树的剪枝 防止过拟合 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到一个叶子节点 决策树续2—分裂属性的选择度量 原则：分类效果最好的（或分类最纯的，或能使树的路径最短）的属性 常用度量 信息增益——Information gain (ID3/C4.5) 所有属性假设都是取离散值的字段（ID3） 经过修改之后可以适用于连续值字段（C4.5） 基尼指数——Gini index (Classification and Regression Tress,CART,Breiman,1984) 能够适用于离散和连续值字段 信息增益 任意样本分类的期望信息： I(s1,s2,……,sm)=－∑Pi log2(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的属性为分裂属性 (对于每个属性都要遍历所有可能的分割方法). 过拟合 过拟合的原因：训练样本带噪声或不充分等 树的剪枝 剪枝原因和目的：解决决策树对训练样本的过拟合问题 解决方法：剪枝（预剪枝，后剪枝）和树组合 后剪枝原则 最小描述长度原则(MDL) 思想：最简单的是最好的 做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树” 期望错误率最小原则 思想：选择期望错误率最小的子树进行剪枝 对树中的内部节点计算其剪枝和不剪枝可能出现的期望错误率，比较后加以取舍 决策树的用法 大数据集 (理想情况): 将数据集划分成3部分: GS, VS, TS 根据GS生成一个树 根据VS进行后剪枝 在TS测试该树的准确率 小数据集 (通常) 根据整个数据集生成一个树 用10折交叉验证进行后剪枝 用10折交叉验证测试树的准确率 分类器组合 AdaBoosting(Adaptive Boosting) 对每个样本赋予一个权重，代表该样本被当前分类器选入训练集的概率，并根据预测函数的输出与期望输出的差异调整权重：如某个样本点已被正确分类，则它的权重减小，否则，它的权重增大；通过这种方式，使得学习算法能集中学习较难判别的样本。 经过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是独立同分布的随机向量，决定了单颗树的生长过程；森林的输出采用简单多数投票法（针对分类）或单颗树输出结果的简单平均（针对回归）得到。 随机森林算法 随