决策树与随机森林课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《决策树与随机森林课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 决策树 随机 森林 课件
- 资源描述:
-
1、决策树与随机森林 邹博 北京10月机器学习班&ML在线公开课第1期 2015年1月11日2/60目标任务与主要内容o 复习信息熵n 熵、联合熵、条件熵、互信息o 决策树学习算法n 信息增益n ID3、C4.5、CARTo Bagging与随机森林的思想n 投票机制o 分类算法的评价指标n ROC曲线和AUC值3/60决策树的实例(Weka自带测试数据)注:Weka的全名是怀卡托智能分析环境(Waikato Environment for Knowledge Analysis),是一款免费的,非商业化(与之对应的是SPSS公司商业数据挖掘产品-Clementine)的,基于JAVA环境下开源的机
2、器学习(machine learning)以及数据挖掘(data minining)软件。它和它的源代码可在其官方网站下载。4/60复习:熵o 将离散随机变量X的概率分布为P(X=xi),则定义熵为:o 若P为连续随机变量,则概率分布变成概率密度函数,求和符号变成积分符号。o 在不引起混淆的情况下,下面谈到的“概率分布函数”,其含义是:n1、若X为离散随机变量,则该名称为概率分布函数;n2、若X为连续随机变量,则该名称为概率密度函数。XxxpxpXH1log5/60对熵的理解o 熵是随机变量不确定性的度量,不确定性越大,熵值越大;若随机变量退化成定值,熵为0n 均匀分布是“最不确定”的分布o
3、熵其实定义了一个函数(概率分布函数)到一个值(信息熵)的映射。n P(x)H (函数数值)n 泛函o 回忆一下关于“变分推导”章节中对于泛函的内容。6/60联合熵和条件熵o 两个随机变量X,Y的联合分布,可以形成联合熵Joint Entropy,用H(X,Y)表示o H(X,Y)H(Y)n(X,Y)发生所包含的信息熵,减去Y单独发生包含的信息熵在Y发生的前提下,X发生“新”带来的信息熵n 该式子定义为Y发生前提下,X的熵:o 条件熵H(X|Y)=H(X,Y)H(Y)7/60推导条件熵的定义式 yxyxyxyxyxyxyyxyxpyxpypyxpyxpypyxpyxpyxpypyxpyxpyxp
4、ypypyxpyxpYHYXH,)|(log),()(),(log),()(log),(),(log),()(log),(),(log),()(log)(),(log),()(),(8/60相对熵o 相对熵,又称互熵,交叉熵,鉴别信息,Kullback熵,Kullback-Leible散度等o 设p(x)、q(x)是X中取值的两个概率分布,则p对q的相对熵是o 说明:n相对熵可以度量两个随机变量的“距离”o 在“贝叶斯网络”、“变分推导”章节使用过n一般的,D(p|q)D(q|p)nD(p|q)0、D(q|p)0 提示:凸函数中的Jensen不等式9/60互信息o 两个随机变量X,Y的互信息,
5、定义为X,Y的联合分布和独立分布乘积的相对熵。o I(X,Y)=D(P(X,Y)|P(X)P(Y)yxypxpyxpyxpYXI,)()(),(log),(),(10/60计算H(X)-I(X,Y)|()|(log),()(),(log),()()(),(log),()(log),()()(),(log),()(log),()()(),(log),()(log)(),()(,YXHyxpyxpypyxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpxpYXIXHyxyxyxyxyxxyyxx 11/60整理得到的等式oH(X|Y)=H(X,Y)-H(
6、Y)n条件熵定义oH(X|Y)=H(X)-I(X,Y)n根据互信息定义展开得到n有些文献将I(X,Y)=H(Y)H(Y|X)作为互信息的定义式o对偶式nH(Y|X)=H(X,Y)-H(X)nH(Y|X)=H(Y)-I(X,Y)oI(X,Y)=H(X)+H(Y)-H(X,Y)n有些文献将该式作为互信息的定义式o试证明:H(X|Y)H(X),H(Y|X)H(Y)12/60强大的Venn图:帮助记忆13/60决策树示意图14/60决策树(Decision Tree)o 决策树是一种树型结构,其中每个内部结点表示在一个属性上的测试,每个分支代表一个测试输出,每个叶结点代表一种类别。o 决策树学习是以实
7、例为基础的归纳学习。o 决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶节点中的实例都属于同一类。15/60决策树学习算法的特点o 决策树学习算法的最大优点是,它可以自学习。在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。n 显然,属于有监督学习。n 从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。16/60决策树学习的生成算法o 建立决策树的关键,即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数,建立决策树主要有一下三种算法。n ID3n C4.5
8、n CART17/60信息增益o 概念:当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。o 信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。o 定义:特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:ng(D,A)=H(D)H(D|A)n显然,这即为训练数据集D和特征A的互信息。18/60基本记号o 设训练数据集为D,|D|表示其容量,即样本个数。设有K个类Ck,k=1,2,K,|Ck|为属于类Ck的样本个数。k|Ck|=|D|。设特征A有n个
9、不同的取值a1,a2an,根据特征A的取值将D划分为n个子集D1,D2,Dn,|Di|为Di的样本个数,i|Di|=D。记子集Di中属于类Ck的样本的集合为Dik,|Dik|为Dik的样本个数。19/60信息增益的计算方法o 计算数据集D的经验熵o 计算特征A对数据集D的经验条件熵H(D|A)o 计算信息增益:g(D,A)=H(D)H(D|A)KkkkDCDCDH1log20/60经验条件熵H(D|A)niiikiikKkiniikikKkiniikikiKkkiikikikiikikDDDDDDADpADpApADpADpApADpADpApADpADpADH111111,log|log|l
10、og|log|log,|21/60其他目标o 信息增益率:gr(D,A)=g(D,A)/H(A)o 基尼指数:21121111KkkKkkKkkkDCppppGini22/60讨论(一家之言)o 考察基尼指数的图像、熵、分类误差率三者之间的关系n 将f(x)=-lnx在x0=1处一阶展开,忽略高阶无穷小,得到f(x)1-x KkkkKkkkppppXH111ln23/60三种决策树学习算法o 适应信息增益来进行特征选择的决策树学习过程,即为ID3决策。o 所以如果是取值更多的属性,更容易使得数据更“纯”,其信息增益更大,决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很
展开阅读全文