随机森林.ppt

上传人:ga****84 文档编号:384411 上传时间:2018-09-29 格式:PPT 页数:27 大小:411.50KB
下载 相关 举报
随机森林.ppt_第1页
第1页 / 共27页
随机森林.ppt_第2页
第2页 / 共27页
随机森林.ppt_第3页
第3页 / 共27页
随机森林.ppt_第4页
第4页 / 共27页
随机森林.ppt_第5页
第5页 / 共27页
点击查看更多>>
资源描述

1、决策树与随机森林,李宁,2,目标任务与主要内容,信息熵熵、联合熵、条件熵、互信息决策树学习算法信息增益ID3、C4.5、CARTBagging与随机森林的思想,3,熵,将离散随机变量X的概率分布为P(X=xi),则定义熵为:若P为连续随机变量,则概率分布变成概率密度函数,求和符号变成积分符号。在不引起混淆的情况下,下面谈到的“概率分布函数”,其含义是:1、若X为离散随机变量,则该名称为概率分布函数;2、若X为连续随机变量,则该名称为概率密度函数。,4,对熵的理解,熵是随机变量不确定性的度量,不确定性越大,熵值越大;若随机变量退化成定值,熵为0均匀分布是“最不确定”的分布熵其实定义了一个函数(概

2、率分布函数)到一个值(信息熵)的映射。P(x)H (函数数值),5,联合熵和条件熵,两个随机变量X,Y的联合分布,可以形成联合熵Joint Entropy,用H(X,Y)表示H(X,Y) H(Y)(X,Y)发生所包含的信息熵,减去Y单独发生包含的信息熵在Y发生的前提下,X发生“新”带来的信息熵该式子定义为Y发生前提下,X的熵:条件熵H(X|Y) = H(X,Y) H(Y),6,推导条件熵的定义式,7,相对熵,相对熵,又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等设p(x)、q(x)是X中取值的两个概率分布,则p对q的相对熵是说明:相对熵可以度量两个随机变量

3、的“距离”在“贝叶斯网络”、“变分推导”章节使用过一般的,D(p|q) D(q|p),8,互信息,两个随机变量X,Y的互信息,定义为X,Y的联合分布和独立分布乘积的相对熵。I(X,Y)=D(P(X,Y) | P(X)P(Y),9,计算H(X)-I(X,Y),10,整理得到的等式,H(X|Y) = H(X,Y) - H(Y)条件熵定义H(X|Y) = H(X) - I(X,Y)根据互信息定义展开得到有些文献将I(X,Y)=H(Y) H(Y|X)作为互信息的定义式对偶式H(Y|X)= H(X,Y) - H(X)H(Y|X)= H(Y) - I(X,Y)I(X,Y)= H(X) + H(Y) - H

4、(X,Y)有些文献将该式作为互信息的定义式,决策树示意图,11,12,决策树 (Decision Tree),决策树是一种树型结构,其中每个内部结点表示在一个属性上的测试,每个分支代表一个测试输出,每个叶结点代表一种类别。决策树学习是以实例为基础的归纳学习。决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶节点中的实例都属于同一类。,13,决策树学习算法的特点,决策树学习算法的最大优点是,它可以自学习。在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。显然,属于有监督学习。从一

5、类无序、无规则的事物(概念)中推理出决策树表示的分类规则。,14,决策树学习的生成算法,建立决策树的关键,即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数,建立决策树主要有一下三种算法。ID3C4.5CART,15,信息增益,概念:当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。定义:特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:g(D,A)=H(D) H(D|A)显然,这即为训练数

6、据集D和特征A的互信息。,16,基本记号,设训练数据集为D,|D|表示其容量,即样本个数。设有K个类Ck,k=1,2,K,|Ck|为属于类Ck的样本个数。k|Ck|=|D|。设特征A有n个不同的取值a1,a2an,根据特征A的取值将D划分为n个子集D1,D2,Dn,|Di|为Di的样本个数,i|Di|=D。记子集Di中属于类Ck的样本的集合为Dik,|Dik|为Dik的样本个数。,17,信息增益的计算方法,计算数据集D的经验熵计算特征A对数据集D的经验条件熵H(D|A)计算信息增益:g(D,A)=H(D) H(D|A),18,经验条件熵H(D|A),19,其他目标,信息增益率:gr(D,A)

7、= g(D,A) / H(A)基尼指数:,20,三种决策树学习算法,适应信息增益来进行特征选择的决策树学习过程,即为ID3决策。所以如果是取值更多的属性,更容易使得数据更“纯” ,其信息增益更大,决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很浅的树,这样的划分是极为不合理的。 C4.5:信息增益率 gr(D,A) = g(D,A) / H(A)CART:基尼指数总结:一个属性的信息增益越大,表明属性对样本的熵减少的能力更强,这个属性使得数据由不确定性变成确定性的能力越强。,21,决策树的过拟合,决策树对训练属于有很好的分类能力,但对未知的测试数据未必有好的分类能力,

8、泛化能力弱,即可能发生过拟合现象。剪枝随机森林,22,剪枝,预剪枝在构造决策树的同时进行剪枝。(为了避免过拟合,可以设定一个阈值)后剪枝决策树构造完成后进行剪枝Reduced-Error Pruning (REP,错误率降低剪枝)Pessimistic Error Pruning (PEP,悲观剪枝),23,Bagging的策略,bootstrap aggregation 从样本集中重采样(有重复的)选出n个样本在所有属性上,对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic回归等)重复以上两步m次,即获得了m个分类器将数据放在这m个分类器上,最后根据这m个分类器的投票结果,决定数据属于哪一类,24,Bagging,25,随机森林,随机森林在bagging基础上做了修改。从样本集中用Bootstrap采样选出n个样本;从所有属性中随机选择k个属性,选择最佳分割属性作为节点建立CART决策树;重复以上两步m次,即建立了m棵CART决策树这m个CART形成随机森林,通过投票表决结果,决定数据属于哪一类,26,随机森林/Bagging和决策树的关系,当然可以使用决策树作为基本分类器但也可以使用SVM、Logistic回归等其他分类器,习惯上,这些分类器组成的“总分类器”,仍然叫做随机森林。举例,27,谢谢大家!,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 学术论文资料库 > 毕业论文

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。