【决策管理课件】第3章 决策树.pptx

Machine Learning第 3 章 决策树学习 决策树定义 适用问题特征 基本 ID3 算法 决策树学习的归纳偏置 训练数据的过度拟合 更深入的话题Machine Learning决策树学习是一种归纳学习方法，它的特点有： 是一种学习离散值目标函数的近似表达的方法函数表示形式: 决策树，易写为if-then 规则 实用性强，许多著名的学习系统（ID3, C4.5 , ASSISTANT 等）皆基于此方法，并成功应用到许多实际领域（学习疾病的诊断，信贷风险的评价，等） 能较好地抵抗噪音 能学习析取表达式 搜索完全的假设空间 它的归纳偏向是小树优先于大树Machine Learning决策树表示法 决策树 通过把实例从根节点排列到某个叶子节点来分类实例 叶子节点即为实例所属的分类 树上每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值 决策树代表实例属性值约束的合取的析取式从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取Machine Learning决策树代表一个假设: (Outlook=Sunny Humidity = Normal) (Outlook=Overcast) (Outlook= Rain Wind=Weak) 设输入的属性集为A1, A2, ., An，则决策树可写成：所有以yes结束的路i （(A1=v1i) (A2=v2i) . (An= vni)）OutlookHumidityWindSunnyOvercastRainHighNormalStrongWeakNoYesYesNoYesMachine Learning适用问题特征训练例的对象由属性-值的对序列表示，具有确定个数的属性，属性可取若干离散值（取值个数越小越好）. 目标函数具有离散型输出值。

最常见的是布尔型目标函数.可能需要析取表达式描述的问题显然决策树可自然地表达逻辑析取式.训练例有噪音决策树学习对训练数据中的噪音具有抵抗力噪音包括：训练例的分类错、训练例的属性值错、训练例的属性值不全等.Machine Learning基本的决策树学习算法 大多数决策树学习算法都是 ID3 核心算法的一种变体,它采用自顶向下的贪婪搜索遍历可能的决策树空间.Machine Learning ID3 的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试” 开始使用统计测试来确定每一个实例属性单独分类训练样例的能力 ID3 的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程Machine LearningID3 的简化描述:输入：Es: 训练例集, c: 目标概念, As: 属性列表输出：能够正确判别 Es 的决策树递归算法：ID3(Es, c, As)1. 建立决策树的根节点 root2. 若Es 均为正例，则返回单节点树root，root 标记+3. 若Es 均为负例，则返回单节点树root，root 标记-4. 若As 为空，则返回单节点树root，root 标记为Es 中占多数的c 值5. root 的决策属性 As 中可对Es进行最佳分类的属性A 对 A 的每一可能的值v 从 root 射出一条弧，代表测试 A=v Esv Es 中属性 A 取值为v 的那些例子组成的子集 若 Esv 为空 则在此弧下加一节点，并标记为Es 中占多数的c值 否则 在此弧下加一子树ID3(Esv, c, As-A) 返回以 root 为根的决策树 Machine Learning最佳分类属性的确定？ 关键：确定As中可对Es进行最佳分类的属性A，即在树的每一个节点上确定一个候选属性，它的测试对训练例的分类最有利。

训练例分类纯度的度量熵: 信息论中度量一组实例在某方面的纯度的方法给定训练例集 Es，其中正例的比例为 p+，负例的比例为 p- = 1- p+Es 的关于这个布尔分类的纯度可用熵定义为： Machine Learning 性质：实例集在目标分类方面越模糊、越杂乱、越无序，它的熵就越高；实例集在目标分类方面越清晰、越纯洁、越有序，它的熵就越低熵刻画了任意样例集的纯度. 一种解释：熵为 Es 中的任意实例的分类结果进行编码所需的最少比特数 . 更一般地，如果目标属性具有 c 个不同的值，那么 Es 相对于 c 个状态的分类的熵定义为:Machine Learning预计熵减弱的度量信息赢取 设Es 当前的熵为E，若用一个属性A 将 Es 分组（A=v 的实例分在同一组 Esv ），E 将会降低（从无序向有序）预计熵降低的数量称为属性 A 相对于实例集 Es 的信息赢取 Gain(Es, A)，定义为： 解释：由于了解分析A 的值而 1.引起的熵减弱（有序化）2.获得的关于目标分类的信息 3.节省的为Es中的任意实例的分类结果进行编码所需的比特数,信息赢取越大的属性对训练例的分类越有利.Machine Learning如何确定 As 中可对 Es 进行最佳分类的属性？ 原则: 信息赢取越大的属性对训练例的分类越有利; 操作: 算法在每一步选取 “As 中可对 Es进行最佳分类的属性 ; 可见, 计算各个属性的信息赢取并加以比较是 ID3 算法的关键操作。

Machine LearningID3算法举例 对象：日子 目标概念：适合打网球：日子集 D Bool 训练例：日子 属性表 A1 A2 A3 A4 正/负例 阴晴 气温 湿度 风力 x1 Sunny Hot High Weak 负 x2 Sunny Hot High Strong 负 x3 Overcast Hot High Weak 正 x4 Rainy Mild High Weak 正 x5 Rainy Cool Normal Weak 正 x6 Rainy Cool Normal Strong 负 x7 Overcast Cool Normal Strong 正 x8 Sunny Mild High Weak 负 x9 Sunny Cool Normal Weak 正 x10 Rainy Mild Normal Weak 正 x11 Sunny Mild Normal Strong 正 x12 Overcast Mild High Strong 正 x13 Overcast Hot Normal Weak 正 x14 Rainy Mild High Strong 负Machine Learning决策树学习的搜索空间和搜索策略 ID3 搜索的假设空间是所有可能的决策树的集合. ID3 搜索的目的是构造与训练数据一致的一棵决策树（即能够对训练例进行正确分类的一棵决策树）. ID3 的搜索策略是爬山法，在构造决策树时从简单到复杂，用信息赢取作为指导爬山法的评价函数. Machine Learning决策树学习的搜索空间和搜索策略(续) 优点搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险。

整体使用训练数据，而不是象候选剪除算法一个一个地考虑训练例能抵抗噪音（个例中的错误数据） 缺点:搜索中只维持一个解，不能象候选剪除算法那样返回所有可能的与训练例集一致的假设，也不能通过查询新例来优化获得的收敛于目标函数的解搜索过程无回溯如同一般的无回溯爬山搜索一样，它可能收敛于局部最优解而丢掉全局最优解因为不是一个一个地考虑训练例，不容易象候选剪除算法那样使用新例步进式地改进决策树Machine Learning决策树学习的归纳偏向 ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏向 近似的ID3的归纳偏向较短的树比较长的树优先近似在于ID3得到局部最优，而不一定是全局最优一个精确具有这个归纳偏向的算法，BFS-ID3 更贴切近似的归纳偏向较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先Machine Learning候选消除算法 ID3搜索范围不完整的假设空间,全搜完整的假设空间,但不全搜归纳偏置假设表示的表达能力,限制性(语言)偏向搜索策略排序,优先性(搜索)偏向限定偏向和优选偏向第一章讲的计算机下跳棋问题则综合运用两种偏向：将棋盘评价函数定为线性函数是一种语言偏向，而在调节系数时使用的最小均方系数调整规则（LMS系数调整规则）是一种搜索偏向。

Machine Learning为什么短的假设优先 ID3的短树优先于长树的偏向是所谓 Occam（奥卡姆）剃刀原理的一种体现 Occam 剃刀原理的一般表达为：偏向于与数据一致的最简单假设,即优先选择拟合数据的最简单的假设 为什么呢 ? 一般的解释是，与数据一致的简单假设的数量大大少于与数据一致的复杂假设的数量，所以简单假设与数据统计巧合的机会比复杂假设要小得多，从而选取简单假设更为保险 Machine Learning决策树学习的常见问题-与训练例过分吻合问题 过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例.定义：给定一个假设空间 H若存在两个假设hH 和 hH，如果在训练例上 h 比 h 的错误少，但在全部实例上 h 比 h 的错误少，则称假设 hH 与训练例过分吻合. Machine Learning 导致过度拟合的原因 一种可能原因是训练样例含有随机错误或噪声. x15 Sunny Hot Normal Strong 负 (加一个分类错误的训练例 ) 当训练数据没有噪声时，过度拟合也有可能发生，特别是当与叶节点对应训练例的数量太小时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系.Machine Learning假设hA1A3A4SORHNSW(1,2,8)(9,11)(3,7,12,13)(6,14) (4,5,10)A1A3A4SORHNSWA2假设hCMH(9)(11)(15)事例Machine Learning避免过度拟合数据 避免过度拟合的方法 及早停止树增长 后修剪法 两种方法的特点 第一种方法更直观，但精确地估计何时停止树增长很困难 第二种方法被证明在实践中更成功Machine Learning 避免过度拟合的关键： 使用什么样的准则来确定最终正确树的规模 解决方法： 使用与训练例互相独立的另一组实例，评价后剪除的效果(训练集与验证集分离) ，来评估通过后修剪方法从树上修剪节点的效用。

使用所有可用数据进行训练，但用统计方法（2测试）来估计一个节点的加入或剪除是否对训练例以外的数据分类有所改进 对训练例和决策树编码复杂度进行度量，当编码复杂度达到最小时停止树的增长（最小描述长度原理） Machine Learning减错剪除 将树上的每一个中间节点(决策节点）作为修剪的候选对象 修剪步骤删除以此节点为根的子树，使它成为叶节点将它标记为与它相关的那些训练例的最常见分类 节点剪除的标准是：剪除后的决策树在验证样例上的分类效果不低于原来的树节点剪除是一个重复过程，总是选取对验证例分类的精度改进贡献最大的节点先删除当进一步剪除有害时（降低对验证例分类的精度），节点剪除的过程终止 如果有大量的数据可供使用，那么使用分离的数据集合来进行修剪. 数据分成3个子集训练，形成树; 验证，修剪树; 测试，精度的无偏估计Machine Learning规则后修剪 从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生 将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则 通过删除任何能导致估计精度提高的前件来修剪每一条规则(一般化)，直到继续删除将降低估计精度为止 按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例Machine Learning 规则精度估计方法使用与训练集不相交的验证集基于训练集合本身。