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