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 所以如果是取值更多的属性，更容易使得数据更“纯”，其信息增益更大，决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很
11、浅的树，这样的划分是极为不合理的。o C4.5：信息增益率 gr(D,A)=g(D,A)/H(A)o CART：基尼指数o 总结：一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。24/60决策树的例子o 对于下面的数据，希望分割成红色和绿色两个类25/60决策树的生成过程26/60决策树的生成过程27/60决策树的生成过程28/60决策树的生成过程29/60决策树的生成过程30/60决策树的生成过程31/60决策树的生成过程32/60决策树的生成过程33/60决策树的生成过程34/60决策树的过拟合o 决策树对训练属于有很好的分类能力，
12、但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。n 剪枝n 随机森林35/60Bootstrapingo Bootstraping的名称来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。n注：Bootstrap本义是指高靴子口后面的悬挂物、小环、带子，是穿靴子时用手向上拉的工具。“pull up by your own bootstraps”即“通过拉靴子让自己上升”，意思是“不可能发生的事情”。后来意思发生了转变，隐喻“不需要外界帮助，仅依靠自身力量让自己变得更好”。36/60Bag
13、ging的策略o bootstrap aggregationo 从样本集中重采样(有重复的)选出n个样本o 在所有属性上，对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic回归等)o 重复以上两步m次，即获得了m个分类器o 将数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类37/60Another description of Bagging38/60Bagging39/60Bagging的结果40/60随机森林o 随机森林在bagging基础上做了修改。n 从样本集中用Bootstrap采样选出n个样本；n 从所有属性中随机选择k个属性，选
14、择最佳分割属性作为节点建立CART决策树；n 重复以上两步m次，即建立了m棵CART决策树n 这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类41/60应用实例：KinectReal-Time Human Pose Recognition in Parts from Single Depth Images,Jamie Shotton etc,2001,42/60随机森林/Bagging和决策树的关系o 当然可以使用决策树作为基本分类器o 但也可以使用SVM、Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。o 举例43/60回归问题o 离
15、散点是样本集合，描述了臭氧(横轴)和温度(纵轴)的关系o 试拟合二者的变化曲线44/60使用Baggingo 算法过程n做100次bootstrap，每次得到的数据Di，Di的长度为Nn对于每一个Di，使用局部回归(LOESS)拟合一条曲线(图中灰色线是其中的10条曲线)n将这些曲线取平均，即得到红色的最终拟合曲线n显然，红色的曲线更加稳定，并且没有过拟合明显减弱记原始数据为D，长度为N(即图中有N个离散点)45/60附：局部加权线性回归o LWR：Locally Weighted linear Regressiono LOESS:LOcal regrESSion46/60附：线性回归与局部加
16、权回归o 黑色是样本点o 红色是线性回归曲线o 绿色是局部加权回归曲线47/60投票机制o 简单投票机制n 一票否决(一致表决)n 少数服从多数o 有效多数(加权)n 阈值表决o 贝叶斯投票机制48/60贝叶斯投票机制o 简单投票法假设每个分类器都是平等的。o 在实际生活中，我们听取一个人的意见，会考虑这个人过去的意见是否有用，从而加大或者减少权值。o 贝叶斯投票机制基于每个基本分类器在过去的分类表现设定一个权值，然后按照这个权值进行投票。49/60投票机制举例o 假定有N个用户可以为X个电影投票(假定投票者不能给同一电影重复投票)，投票有1、2、3、4、5星共5档。o 如何根据用户投票，对电
17、影排序？n 本质仍然是分类问题：对于某个电影，有N个决策树，每个决策树对该电影有1个分类(1、2、3、4、5类)，求这个电影应该属于哪一类(可以是小数：分类问题变成了回归问题)50/60一种可能的方案o WR：加权得分(weighted rating)o R：该电影的用户投票的平均得分(Rating)o C：所有电影的平均得分o v：该电影的投票人数(votes)o m：排名前250名的电影的最低投票数n根据总投票人数，250可能有所调整n按照v=0和m=0分别分析51/60评价指标o 以下近考虑二分类问题，即将实例分成正类(positive)或负类(negative)。o 对一个二分问题来说
18、，会出现四种情况。如果一个实例是正类并且也被 预测成正类，即为真正类(True positive),如果实例是负类被预测成正类，称之为假正类(False positive)。相应地，如果实例是负类被预测成负类，称之为真负类(True negative),正类被预测成负类则为假负类(false negative)。52/60混淆矩阵(Confusion Matrix)o TP：正确肯定实例是正例，划分为正例o FN：漏报实际是正例，却划分成了负例o FP：误报实际是负例，却划分成了正例o TN：正确拒绝实例是负例，划分为负例53/60o 误分率Error Rate：(FN+FP)/Co 准确度A
19、ccuracy：(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/60使用TPR和FPR分析二分类模型o 对于一个二分类模型，假设已确定一个阀值，比如说 0.6，大于这个值的实例划归为正类，小于这个值则划到负类中。如果减小阀值，比如减到0.5，一方面，能识别出更多的正类，即提高TPR(样本集合的正例总
20、数没变)；另一方面，也将更多的负实例当作了正实例，即提高了FPR。o 根据不同的阈值，将离散点(TPR,FPR)绘制成曲线，就得到ROC曲线，可以用于评价一个分类器。nReceiver Operating Characteristic，接受者操作特性曲线55/60ROC曲线o 以假正类率FPR为横轴，真正类率TPR为纵轴，得到ROC曲线n 虚报概率(代价)为横轴，击中概率(收益)为纵轴56/60ROC曲线的分析o 对于一个分类器，n 每个阈值对应一个(TPR，FPR)；n 阈值最大时，没有实例被分成正例，因此，TP=FP=0，对应于原点(0,0)；n 阈值最小时，所有实例都被分成正例，TN=F
21、N=1，对应于右上角的点(1,1)；n 随着阈值从最大变化到最小，TP和FP都逐渐增大。57/60ROC曲线实例58/60使用ROC曲线评价分类器o 在ROC曲线中，通常，如果曲线X始终位于曲线Y的左上方，则曲线X优于曲线Y。这意味着，对于所有可能的错误分类代价，X分类器的正分类率总是比Y要高。o 如果一条ROC曲线是经过(0,0)和(1,1)的直线，则该分类器为随机猜测分类器。o 如果X并不总是位于Y的左上侧，可以使用ROC曲线下方的面积作为度量，即：AUC值。nArea Under roc Curve59/60参考文献o Elements of Information Theory(Cover&Thomas)o Pattern Recognition and Machine Learning,Bishop M,Springer-Verlag,2006o 统计学习方法，李航著，清华大学出版社，2012年o Jamie Shotton,Andrew Fitzgibbon,etc,Real-Time Human Pose Recognition in Parts from Single Depth Images,2011o http:/en.wikipedia.org/wiki/Local_regression60/60 谢谢大家！恳请大家批评指正！
