19决策树与随机森林

《19决策树与随机森林》由会员分享，可在线阅读，更多相关《19决策树与随机森林（60页珍藏版）》请在装配图网上搜索。

1、1决策树与随机森林 邹博 北京10月机器学习班&ML在线公开课第1期 2015年1月11日2目标任务与主要内容o复习信息熵n熵、联合熵、条件熵、互信息o决策树学习算法n信息增益nID3、C4.5、CARToBagging与随机森林的思想n投票机制o分类算法的评价指标nROC曲线和AUC值3决策树的实例(Weka自带测试数据)注：Weka的全名是怀卡托智能分析环境(Waikato Environment for Knowledge Analysis)，是一款免费的，非商业化(与之对应的是SPSS公司商业数据挖掘产品-Clementine)的，基于JAVA环境下开源的机器学习(machine le

2、arning)以及数据挖掘(data minining)软件。它和它的源代码可在其官方网站下载。4复习：熵o将离散随机变量X的概率分布为P(X=xi)，则定义熵为：o若P为连续随机变量，则概率分布变成概率密度函数，求和符号变成积分符号。o在不引起混淆的情况下，下面谈到的“概率分布函数”，其含义是：n1、若X为离散随机变量，则该名称为概率分布函数；n2、若X为连续随机变量，则该名称为概率密度函数。XxxpxpXH1log5对熵的理解o熵是随机变量不确定性的度量，不确定性越大，熵值越大；若随机变量退化成定值，熵为0n均匀分布是“最不确定”的分布o熵其实定义了一个函数(概率分布函数)到一个值(信息熵

3、)的映射。nP(x)H (函数数值)n泛函o回忆一下关于“变分推导”章节中对于泛函的内容。6联合熵和条件熵o两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，用H(X,Y)表示oH(X,Y)H(Y)n(X,Y)发生所包含的信息熵，减去Y单独发生包含的信息熵在Y发生的前提下，X发生“新”带来的信息熵n该式子定义为Y发生前提下，X的熵：o条件熵H(X|Y)=H(X,Y)H(Y)7推导条件熵的定义式 yxyxyxyxyxyxyyxyxpyxpypyxpyxpypyxpyxpyxpypyxpyxpyxpypypyxpyxpYHYXH,)|(log),()(),(log),()(l

4、og),(),(log),()(log),(),(log),()(log)(),(log),()(),(8相对熵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互信息o两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。oI(X,Y)=D(P(X,Y)|P(X)P(Y)yx

5、ypxpyxpyxpYXI,)()(),(log),(),(10计算H(X)-I(X,Y)|()|(log),()(),(log),()()(),(log),()(log),()()(),(log),()(log),()()(),(log),()(log)(),()(,YXHyxpyxpypyxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpyxpypxpyxpyxpxpxpYXIXHyxyxyxyxyxxyyxx 11整理得到的等式oH(X|Y)=H(X,Y)-H(Y)n条件熵定义oH(X|Y)=H(X)-I(X,Y)n根据互信息定义展开得到n有些文献将I(X,Y)=H(Y)H

6、(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强大的Venn图：帮助记忆13决策树示意图14决策树(Decision Tree)o决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。o决策树学习是以实例为基础的归纳学习。o决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，

7、此时每个叶节点中的实例都属于同一类。15决策树学习算法的特点o决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。n显然，属于有监督学习。n从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。16决策树学习的生成算法o建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。nID3nC4.5nCART17信息增益o概念：当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。o信息增益表示得知特征A的

8、信息而使得类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基本记号o设训练数据集为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的

9、样本个数。19信息增益的计算方法o计算数据集D的经验熵o计算特征A对数据集D的经验条件熵H(D|A)o计算信息增益：g(D,A)=H(D)H(D|A)KkkkDCDCDH1log20经验条件熵H(D|A)niiikiikKkiniikikKkiniikikiKkkiikikikiikikDDDDDDADpADpApADpADpApADpADpApADpADpADH111111,log|log|log|log|log,|21其他目标o信息增益率：gr(D,A)=g(D,A)/H(A)o基尼指数：21121111KkkKkkKkkkDCppppGini22讨论(一家之言)o考察基尼指数的图像、熵、

10、分类误差率三者之间的关系n将f(x)=-lnx在x0=1处一阶展开，忽略高阶无穷小，得到f(x)1-x KkkkKkkkppppXH111ln23三种决策树学习算法o适应信息增益来进行特征选择的决策树学习过程，即为ID3决策。o所以如果是取值更多的属性，更容易使得数据更“纯”，其信息增益更大，决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很浅的树，这样的划分是极为不合理的。oC4.5：信息增益率 gr(D,A)=g(D,A)/H(A)oCART：基尼指数o总结：一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。2

11、4决策树的例子o对于下面的数据，希望分割成红色和绿色两个类25决策树的生成过程26决策树的生成过程27决策树的生成过程28决策树的生成过程29决策树的生成过程30决策树的生成过程31决策树的生成过程32决策树的生成过程33决策树的生成过程34决策树的过拟合o决策树对训练属于有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。n剪枝n随机森林35BootstrapingoBootstraping的名称来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。n注：Bootstrap

12、本义是指高靴子口后面的悬挂物、小环、带子，是穿靴子时用手向上拉的工具。“pull up by your own bootstraps”即“通过拉靴子让自己上升”，意思是“不可能发生的事情”。后来意思发生了转变，隐喻“不需要外界帮助，仅依靠自身力量让自己变得更好”。36Bagging的策略obootstrap aggregationo 从样本集中重采样(有重复的)选出n个样本o在所有属性上，对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic回归等)o重复以上两步m次，即获得了m个分类器o将数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类37An

13、other description of Bagging38Bagging39Bagging的结果40随机森林o随机森林在bagging基础上做了修改。n从样本集中用Bootstrap采样选出n个样本；n从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；n重复以上两步m次，即建立了m棵CART决策树n这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类41应用实例：KinectReal-Time Human Pose Recognition in Parts from Single Depth Images,Jamie Shotton etc,2001,42

14、随机森林/Bagging和决策树的关系o当然可以使用决策树作为基本分类器o但也可以使用SVM、Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。o举例43回归问题o离散点是样本集合，描述了臭氧(横轴)和温度(纵轴)的关系o试拟合二者的变化曲线44使用Baggingo算法过程n做100次bootstrap，每次得到的数据Di，Di的长度为Nn对于每一个Di，使用局部回归(LOESS)拟合一条曲线(图中灰色线是其中的10条曲线)n将这些曲线取平均，即得到红色的最终拟合曲线n显然，红色的曲线更加稳定，并且没有过拟合明显减弱记原始数据为D，长度为N(即图中有N个

15、离散点)45附：局部加权线性回归oLWR：Locally Weighted linear RegressionoLOESS:LOcal regrESSion46附：线性回归与局部加权回归o黑色是样本点o红色是线性回归曲线o绿色是局部加权回归曲线47投票机制o简单投票机制n一票否决(一致表决)n少数服从多数o有效多数(加权)n阈值表决o贝叶斯投票机制48贝叶斯投票机制o简单投票法假设每个分类器都是平等的。o在实际生活中，我们听取一个人的意见，会考虑这个人过去的意见是否有用，从而加大或者减少权值。o贝叶斯投票机制基于每个基本分类器在过去的分类表现设定一个权值，然后按照这个权值进行投票。49投票机制

16、举例o假定有N个用户可以为X个电影投票(假定投票者不能给同一电影重复投票)，投票有1、2、3、4、5星共5档。o如何根据用户投票，对电影排序？n本质仍然是分类问题：对于某个电影，有N个决策树，每个决策树对该电影有1个分类(1、2、3、4、5类)，求这个电影应该属于哪一类(可以是小数：分类问题变成了回归问题)50一种可能的方案oWR：加权得分(weighted rating)oR：该电影的用户投票的平均得分(Rating)oC：所有电影的平均得分ov：该电影的投票人数(votes)om：排名前250名的电影的最低投票数n根据总投票人数，250可能有所调整n按照v=0和m=0分别分析51评价指标o

17、以下近考虑二分类问题，即将实例分成正类(positive)或负类(negative)。o对一个二分问题来说，会出现四种情况。如果一个实例是正类并且也被 预测成正类，即为真正类(True positive),如果实例是负类被预测成正类，称之为假正类(False positive)。相应地，如果实例是负类被预测成负类，称之为真负类(True negative),正类被预测成负类则为假负类(false negative)。52混淆矩阵(Confusion Matrix)oTP：正确肯定实例是正例，划分为正例oFN：漏报实际是正例，却划分成了负例oFP：误报实际是负例，却划分成了正例oTN：正确拒绝实

18、例是负例，划分为负例53o误分率Error Rate：(FN+FP)/Co准确度Accuracy：(TP+TN)/Co查准率Recall：TP/(TP+FP)o假正类率(False Positive Rate,FPR)：FP/(FP+TN)n虚报概率，代价(costs)o真正类率(true positive rate,TPR)：TP/(TP+FN)n击中概率，收益(benefits)o思考：可否按此模式，定义“真负类率TNR”？54使用TPR和FPR分析二分类模型o对于一个二分类模型，假设已确定一个阀值，比如说 0.6，大于这个值的实例划归为正类，小于这个值则划到负类中。如果减小阀值，比如减到

19、0.5，一方面，能识别出更多的正类，即提高TPR(样本集合的正例总数没变)；另一方面，也将更多的负实例当作了正实例，即提高了FPR。o根据不同的阈值，将离散点(TPR,FPR)绘制成曲线，就得到ROC曲线，可以用于评价一个分类器。nReceiver Operating Characteristic，接受者操作特性曲线55ROC曲线o以假正类率FPR为横轴，真正类率TPR为纵轴，得到ROC曲线n虚报概率(代价)为横轴，击中概率(收益)为纵轴56ROC曲线的分析o对于一个分类器，n每个阈值对应一个(TPR，FPR)；n阈值最大时，没有实例被分成正例，因此，TP=FP=0，对应于原点(0,0)；n阈

20、值最小时，所有实例都被分成正例，TN=FN=1，对应于右上角的点(1,1)；n随着阈值从最大变化到最小，TP和FP都逐渐增大。57ROC曲线实例58使用ROC曲线评价分类器o在ROC曲线中，通常，如果曲线X始终位于曲线Y的左上方，则曲线X优于曲线Y。这意味着，对于所有可能的错误分类代价，X分类器的正分类率总是比Y要高。o如果一条ROC曲线是经过(0,0)和(1,1)的直线，则该分类器为随机猜测分类器。o如果X并不总是位于Y的左上侧，可以使用ROC曲线下方的面积作为度量，即：AUC值。nArea Under roc Curve59参考文献oElements of Information Theory(Cover&Thomas)oPattern Recognition and Machine Learning,Bishop M,Springer-Verlag,2006o统计学习方法，李航著，清华大学出版社，2012年oJamie Shotton,Andrew Fitzgibbon,etc,Real-Time Human Pose Recognition in Parts from Single Depth Images,2011ohttp:/en.wikipedia.org/wiki/Local_regression60 谢谢大家！恳请大家批评指正！