12决策树学习

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,第,1.2,节 决策树学习,(Decision Tree),1,内容,决策树方法的原理,决策树中的过拟合问题,决策树的其他问题,属性的其他度量,2,决策树学习,决定是否打网球,看看天气,看看湿度,阳光明媚,下雨,看看风速,高,正常,不去打球,去打球,大,小,不去打球,去打球,节点：每一个节点测试一个属性,分支：属性的可选数值,叶子节点：最终预测,去打球,阴天,3,决策树学习原理简介,(ID3, C4.5,算法,),node,= root,循环,1.,为当下一个节点选择一个最好的属性,x,2.,将属性,x,分配给节点,node,3.,对于,x,的所有可能数值，创建一个降序排列的节点,node,4.,将所有训练样本在叶子节点排序分类,5.,如果分类结果达到了错误率要求，跳出循环，否则，,在叶子节点开始新循环,-,递归,4,决策树表示法,决策树,通过把实例从根节点排列到某个叶子节点来分类实例。,叶子节点即为实例所属的分类,树上每个节点说明了对实例的某个属性的测试,节点的每个后继分支对应于该属性的一个可能值,决策树代表实例属性值约束的合取的析取式。从树叶到树根的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。,5,决策树学习的适用问题,适用问题的特征,实例由“属性,-,值”对表示,目标函数具有离散的输出值,可能需要析取的描述,训练数据可以包含错误,训练数据可以包含缺少属性值的实例,问题举例,根据天气好坏确定是否去打球,根据疾病分类患者,根据起因分类设备故障,根据拖欠支付的可能性分类贷款申请,分类问题,核心任务是把样例分类到各可能的离散值对应的类别,6,基本的决策树学习算法,大多数决策树学习算法是一种核心算法的变体,采用自顶向下的贪婪搜索遍历可能的决策树空间,ID3,是这种算法的代表,7,基本的决策树学习算法,ID3,的思想,自顶向下构造决策树,从“哪一个属性将在树的根节点被测试”开始,使用统计测试来确定每一个实例属性单独分类训练样例的能力,ID3,的过程,分类能力最好的属性被选作树的根节点,根节点的每个可能值产生一个分支,训练样例排列到适当的分支,重复上面的过程,8,决策树学习原理简介,(ID3, C4.5,算法,),编号,天气,温度,湿度,风,是否去打球,1,晴天,炎热,高,弱,不去,2,晴天,炎热,高,强,不去,3,阴天,炎热,高,弱,去,4,下雨,适中,高,弱,去,5,下雨,寒冷,正常,弱,去,6,下雨,寒冷,正常,强,不去,7,阴天,寒冷,正常,强,去,8,晴天,适中,高,弱,不去,9,晴天,寒冷,正常,弱,去,10,下雨,适中,正常,弱,去,11,晴天,适中,正常,强,去,12,阴天,适中,高,强,去,13,阴天,炎热,正常,弱,去,14,下雨,适中,高,强,不去,表,-1,：是否去打球的数据统计,训练数据,9,决策树学习原理简介,(ID3, C4.5,算法,),湿度,高,正常,(3+, 4-),(6+, 1-),S: (9+, 5-),风,弱,强,(6+, 2-),(3+, 3-),S: (9+, 5-),问题：哪一个属性（特征）更好？,10,决策树学习原理简介,(ID3, C4.5,算法,),熵,:,物理学概念,􀁺宏观上：热力学定律,体系的熵变等于可逆过程吸收或耗散的热量除以它的绝对温度（克劳修斯，,1865,）,􀁺微观上：熵是大量微观粒子的位置和速度的分布概率的函数，是描述系统中大量微观粒子的无序性的宏观参数（波尔兹曼，,1872,）,􀁺,结论：熵是描述事物无序性的参数，熵越大则无序性越强,在信息领域定义为“熵越大，不确定性越大”（香浓，,1948,年）,11,决策树学习原理简介,(ID3, C4.5,算法,),随机变量的熵,熵 比较多的用于信源编码，数据压缩，假设,是最有效的编码方式是使用 位编码,于是对于随即变量的最有效编码位之和：,12,决策树学习原理简介,(ID3, C4.5,算法,),表示训练集合中的样本,表示训练集合中反例样本的比例,表示训练集合中正例样本的比例,表示训练集合的熵,13,决策树学习原理简介,(ID3, C4.5,算法,),信息增益：,information gain,􀁺,信息的增加意味着不确定性的减少，也就是熵的减小，信息增益在诸多系统中定义为：,在某一个操作之前的系统熵与操作之后的系统熵的差值，也即是不确定性的减小量,14,信息增益,(Information Gain),原来的不确定性,知道,x,之后的不确定性,信息增益,:,原来,-,知道,x,之后的,原来不确定性,-,经过属性,x,划分以后的不确定性,15,信息增益,(Information Gain),选择属性的标准：选择具有最高信息增益,(Information Gain),的属性,假设有两个类,+,和,-,假设集合,S,中含有,p,个类别为,+,的样本,n,个类别为,-,的样本,将,S,中已知样本进行分类所需要的期望信息定义为,:,16,信息增益在决策树中的使用,假设属性,x,将把集合,S,划分成,K,份,S,1,S,2,S,K,如果,S,i,中包含,p,i,个类别为,“+”,的样本,n,i,个类别为,“-”,的样本。那么熵就是,(,entropy),在,x,上进行决策分枝所获得的信息增益为,:,17,决策树学习原理简介,(ID3, C4.5,算法,),*,18,决策树学习原理简介,(ID3, C4.5,算法,),问题：哪一个属性（特征）更好？分析极端的情况,温度,高,正常,(4+, 4-),(4+, 4-),S: (8+, 8-),心情,好,坏,(8+, 0-),(0+,8-),S: (8+, 8-),E=1.0,E=0.0,E=0.0,Gain(S,温度）,=1.0-,（,8/16)*1.0-,（,8/16,）*,1.0,=0.0,Gain(S,心情）,=1.0-(8/16)*0.0-(8/16)*0.0,=1.0,E=1.0,E=1.0,19,决策树学习原理简介,(ID3, C4.5,算法,),湿度,高,正常,(3+, 4-),(6+, 1-),S: (9+, 5-),风,弱,强,(6+, 2-),(3+, 3-),S: (9+, 5-),问题：哪一个属性（特征）更好？,I=0.985,I=0.592,I=0.811,I=1.00,Gain(S,湿度）,=0.940-,（,7/14).985-7/14*0.592,=0.151,Gain(S,风）,=0.940-(8/14).811-(6/14)1.0,=0.048,E=0.940,E=0.940,20,决策树学习原理简介,(ID3, C4.5,算法,),决策树的构造过程示意,x1,x3,x8,x3,x7,+,-,+,-,+,-,21,决策树学习,将树转化为规则,将树转化为规则集合,测试规则是否相互矛盾,将规则排序存储,Tree:,If(,阴天）,-,去打球,If,（晴天）,If,（风速低）,-,去打球,Else -,不去打球,22,决策树学习的常见问题,决策树学习的实际问题,确定决策树增长的深度,处理连续值的属性,选择一个适当的属性筛选度量标准,处理属性值不完整的训练数据,处理不同代价的属性,提高计算效率,针对这些问题，,ID3,被扩展成,C4.5,23,决策树学习及,over-fitting,看看天气,看看湿度,阳光明媚,下雨,看看风速,高,正常,不去打球,去打球,大,小,不去打球,去打球,去打球,阴天,1,晴天,炎热,高,强,去打球,增加一个错误样本,24,决策树学习及,over-fitting,过度拟合,对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例,定义：给定一个假设空间,H,，一个假设,h,H,，如果存在其他的假设,h,H,，使得在训练样例上,h,的错误率比,h,小，但在整个实例分布上,h,的错误率比,h,小，那么就说假设,h,过度拟合训练数据。,25,决策树学习及,over-fitting,导致过度拟合的原因,一种可能原因是训练样例含有随机错误或噪声,当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。,26,决策树学习及,over-fitting,假设,在训练样本集合上的错误率为,样本集合上的真实错误率为,训练结果,在如下情况下即会产生过拟合,27,决策树学习及,over-fitting,28,决策树学习及,over-fitting,避免过拟合的方法,如果对数据划分没有明显好处的属性不选择，同时不再将决策数细分,构建完成整个树以后进行剪枝”,Prune”,在训练数据上测量性能,在交叉验证数据上测量性能,MDL,Minmize,(Size(tree)+Size(misclassifications(tree),29,决策树学习及,over-fitting,避免过拟合的方法,评估所生成的新节点对于,Validation,数据集合的性能,生成一些节点很少但是性能很好的“,Sub-tree”,30,决策树学习及,over-fitting,避免过度拟合的方法,及早停止树增长,后修剪法,两种方法的特点,第一种方法更直观,第一种方法中，精确地估计何时停止树增长很困难,第二种方法被证明在实践中更成功,31,决策树学习及,over-fitting,避免过度拟合的关键,使用什么样的准则来确定最终正确树的规模,解决方法,使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。,使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。,使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。,32,决策树学习及,over-fitting,方法评述,第一种方法是最普通的，常被称为训练和验证集法。,可用数据分成两个样例集合：,训练集合，形成学习到的假设,验证集合，评估这个假设在后续数据上的精度,方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动,验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。,常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。,33,训练误差升高修剪,将树上的每一个节点作为修剪候选对象,修剪步骤,删除以此节点为根的子树，使它成为叶结点,把和该节点关联的训练样例的,最常见分类,赋给它,反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点,继续修剪，直到进一步的修剪是有害的为止,数据分成,3,个子集,训练样例，形成决策树,验证样例，修剪决策树,测试样例，精度的无偏估计,如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪,34,规则后修剪,从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生,将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则,通过“任何能导致估计精度提高的前提”来修剪每一条规则,按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例,35,规则后修剪,规则精度估计方法,使用与训练集不相交的验证集,基于训练集合本身,被,C4.5,使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置,过程,先计算规则在它应用的训练样例上的精度,然后假定此估计精度为二项式分布，并计算它的标准差,对于一个给定的置信区间，采用下界估计作为规则性能的度量,评论,对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远,不是统计有效，但是实践中发现有效,36,规则后修剪,把决策树转化成规则集的好处,可以区分决策节点使用的不同上下文,消除了根节点附近的属性测试和叶节点附近的属性测试的区别,提高了可读性,37,合并连续值属性,ID3,被限制为取离散值的属性,学习到的决策树要预测的目标属性必须是离散的,树的决策节点的属性也必须是离散的,简单删除上面第,2,个限制的方法,通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合,38,合并连续值属性,例，,Temperature,应该定义什么样的基于阈值的布尔属性,选择产生最大信息增益的阈值,按照连续属性排列样例，确定目标分类不同的相邻实例,产生一组候选阈值，它们的值是相应的,A,值之间的中间值,可以证明产生最大信息增益的,c,值位于这样的边界中（,Fayyad1991,）,通过计算与每个候选阈值关联的信息增益评估这些候选值,方法的扩展,连续的属性分割成多个区间，而不是单一阈值的两个空间,39,属性选择的其他度量标准,信息增益度量存在一个内在偏置，,偏向具有较多值的属性,避免方法，其他度量，比如增益比率,增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性,SplitInformation(S,A)=,GainRatio(S,A)=,分裂信息项阻碍选择值为均匀分布的属性,问题，当某个,S,i,S,。解决方法：采用一些启发式规则， 比如仅对增益高过平均值的属性应用增益比率测试,40,决策树学习中的假设空间搜索,属性分段,观察,ID3,的搜索空间和搜索策略，认识到这个算法的优势,假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间,维护单一的当前假设,不进行回溯，能收敛到局部最优,每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强,41,决策树学习的归纳偏置,ID3,的搜索策略,优先选择较短的树,选择那些信息增益高的属性离根节点较近的树,很难准确刻画,ID3,的归纳偏置,近似的,ID3,的归纳偏置,较短的树比较长的树优先,近似在于,ID3,得到局部最优，而不一定是全局最优,一个精确具有这个归纳偏置的算法，,BFS-ID3,更贴切近似的归纳偏置,较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先,42,为什么短的假设优先,ID3,的归纳偏置的直观基础,奥坎姆剃刀,优先选择拟合数据的最简单的假设,科学上的例子,物理学家优先选择行星运动的简单假设,简单假设的数量远比复杂假设的数量少,简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述,43,属性选择的其他度量标准,基于距离的度量,定义了数据划分间的一种距离尺度,计算每个属性产生的划分与理想划分间的距离,Lopez de Mantaras,定义了这个距离度量，证明了它不偏向有大量值的属性,Mingers,实验，不同的属性选择度量对最终精度的影响小于后修剪的程度和方法的影响,44,缺少属性值的训练样例,例子，医学领域，很多待测属性无法观测,经常需要根据此属性值已知实例来估计这个缺少的属性值,一种策略，给它节点,n,的训练样例中该属性的最常见值,另一种策略是赋给它节点,n,的被分类为,c(x),的训练样例中该属性的最常见值,更复杂的策略，为,x,的每个可能值赋予一个概率，而不是简单地将最常见的值赋给,x,，决策树与概率结合,45,处理不同代价的属性,实例的属性可能与代价相关,优先选择尽可能使用低代价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性,通过引入一个代价项到属性选择度量中，可以使,ID3,算法考虑属性代价,加权的方法,46,小结,决策树学习为离散值输入提供了一个实用的方法,ID3,算法,从根向下推断决策树,搜索完整的假设空间,较小的树,C4.5,算法,过度拟合问题,决策树的其他问题,47,本章作业,本章作业：写出“利用决策树建立转基因植物生物安全评价的读书报告,”,格式为,PPT,或者,Word,，素材见课程网站,48,