第3章 决策树

MachineLearning第3章决策树学习•决策树定义•适用问题特征•基本ID3算法•决策树学习的归纳偏置•训练数据的过度拟合•更深入的话题MachineLearning决策树学习是一种归纳学习方法，它的特点有：•是一种学习离散值目标函数的近似表达的方法。函数表示形式:决策树，易写为if-then规则。•实用性强，许多著名的学习系统（ID3,C4.5,ASSISTANT等）皆基于此方法，并成功应用到许多实际领域（学习疾病的诊断，信贷风险的评价，等）。•能较好地抵抗噪音。•能学习析取表达式。•搜索完全的假设空间。•它的归纳偏向是小树优先于大树。MachineLearning决策树表示法•决策树–通过把实例从根节点排列到某个叶子节点来分类实例–叶子节点即为实例所属的分类–树上每个节点说明了对实例的某个属性的测试–节点的每个后继分支对应于该属性的一个可能值•决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。MachineLearning决策树代表一个假设:(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)设输入的属性集为｛A1,A2,...,An｝，则决策树可写成：所有以yes结束的路i（(A1=v1i)(A2=v2i)...(An=vni)）OutlookHumidityWindSunnyOvercastRainHighNormalStrongWeakNoYesYesNoYesMachineLearning适用问题特征•训练例的对象由属性-值的对序列表示，具有确定个数的属性，属性可取若干离散值（取值个数越小越好）.•目标函数具有离散型输出值。最常见的是布尔型目标函数.•可能需要析取表达式描述的问题。显然决策树可自然地表达逻辑析取式.•训练例有噪音。决策树学习对训练数据中的噪音具有抵抗力。噪音包括：训练例的分类错、训练例的属性值错、训练例的属性值不全等.MachineLearning基本的决策树学习算法•大多数决策树学习算法都是ID3核心算法的一种变体,它采用自顶向下的贪婪搜索遍历可能的决策树空间.MachineLearning•ID3的思想–自顶向下构造决策树–从“哪一个属性将在树的根节点被测试”开始–使用统计测试来确定每一个实例属性单独分类训练样例的能力•ID3的过程–分类能力最好的属性被选作树的根节点–根节点的每个可能值产生一个分支–训练样例排列到适当的分支–重复上面的过程MachineLearningID3的简化描述:输入：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=vEsvEs中属性A取值为v的那些例子组成的子集若Esv为空则在此弧下加一节点，并标记为Es中占多数的c值否则在此弧下加一子树ID3(Esv,c,As-{A})返回以root为根的决策树MachineLearning最佳分类属性的确定？•关键：确定As中可对Es进行最佳分类的属性A，即在树的每一个节点上确定一个候选属性，它的测试对训练例的分类最有利。•训练例分类纯度的度量熵:信息论中度量一组实例在某方面的纯度的方法。给定训练例集Es，其中正例的比例为p+，负例的比例为p-=1-p+。Es的关于这个布尔分类的纯度可用熵定义为：ppppEsEntroy22loglog)(MachineLearning•性质：实例集在目标分类方面越模糊、越杂乱、越无序，它的熵就越高；实例集在目标分类方面越清晰、越纯洁、越有序，它的熵就越低。熵刻画了任意样例集的纯度.•一种解释：熵为Es中的任意实例的分类结果进行编码所需的最少比特数.•更一般地，如果目标属性具有c个不同的值，那么Es相对于c个状态的分类的熵定义为:ciiippEsEntropy12log)(MachineLearning预计熵减弱的度量信息赢取•设Es当前的熵为E，若用一个属性A将Es分组（A=v的实例分在同一组Esv），E将会降低（从无序向有序）。预计熵降低的数量称为属性A相对于实例集Es的信息赢取Gain(Es,A)，定义为：)(||||)(),()(EsvEntropyEsEsvEsEntropyAEsGainAValuesv•解释：由于了解分析A的值而1.引起的熵减弱（有序化）→2.获得的关于目标分类的信息→3.节省的为Es中的任意实例的分类结果进行编码所需的比特数,信息赢取越大的属性对训练例的分类越有利.MachineLearning如何确定As中可对Es进行最佳分类的属性？•原则:信息赢取越大的属性对训练例的分类越有利;•操作:算法在每一步选取“As中可对Es进行最佳分类的属性;•可见,计算各个属性的信息赢取并加以比较是ID3算法的关键操作。MachineLearningID3算法举例•对象：日子目标概念：适合打网球：日子集DBool•训练例：–日子属性表A1A2A3A4正/负例–阴晴气温湿度风力–x1SunnyHotHighWeak负–x2SunnyHotHighStrong负–x3OvercastHotHighWeak正–x4RainyMildHighWeak正–x5RainyCoolNormalWeak正–x6RainyCoolNormalStrong负–x7OvercastCoolNormalStrong正–x8SunnyMildHighWeak负–x9SunnyCoolNormalWeak正–x10RainyMildNormalWeak正–x11SunnyMildNormalStrong正–x12OvercastMildHighStrong正–x13OvercastHotNormalWeak正–x14RainyMildHighStrong负MachineLearning决策树学习的搜索空间和搜索策略•ID3搜索的假设空间是所有可能的决策树的集合.•ID3搜索的目的是构造与训练数据一致的一棵决策树（即能够对训练例进行正确分类的一棵决策树）.•ID3的搜索策略是爬山法，在构造决策树时从简单到复杂，用信息赢取作为指导爬山法的评价函数.MachineLearning决策树学习的搜索空间和搜索策略(续)•优点–搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险。–整体使用训练数据，而不是象候选剪除算法一个一个地考虑训练例。能抵抗噪音（个例中的错误数据）。•缺点:–搜索中只维持一个解，不能象候选剪除算法那样返回所有可能的与训练例集一致的假设，也不能通过查询新例来优化获得的收敛于目标函数的解。–搜索过程无回溯。如同一般的无回溯爬山搜索一样，它可能收敛于局部最优解而丢掉全局最优解。–因为不是一个一个地考虑训练例，不容易象候选剪除算法那样使用新例步进式地改进决策树。MachineLearning决策树学习的归纳偏向•ID3的搜索策略–优先选择较短的树–选择那些信息增益高的属性离根节点较近的树–很难准确刻画ID3的归纳偏向•近似的ID3的归纳偏向–较短的树比较长的树优先–近似在于ID3得到局部最优，而不一定是全局最优–一个精确具有这个归纳偏向的算法，BFS-ID3•更贴切近似的归纳偏向–较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先MachineLearning候选消除算法ID3搜索范围不完整的假设空间,全搜完整的假设空间,但不全搜归纳偏置假设表示的表达能力,限制性(语言)偏向搜索策略排序,优先性(搜索)偏向限定偏向和优选偏向第一章讲的计算机下跳棋问题则综合运用两种偏向：将棋盘评价函数定为线性函数是一种语言偏向，而在调节系数时使用的最小均方系数调整规则（LMS系数调整规则）是一种搜索偏向。MachineLearning为什么短的假设优先•ID3的短树优先于长树的偏向是所谓Occam（奥卡姆）剃刀原理的一种体现。•Occam剃刀原理的一般表达为：偏向于与数据一致的最简单假设,即优先选择拟合数据的最简单的假设。•为什么呢?一般的解释是，与数据一致的简单假设的数量大大少于与数据一致的复杂假设的数量，所以简单假设与数据统计巧合的机会比复杂假设要小得多，从而选取简单假设更为保险。MachineLearning决策树学习的常见问题--与训练例过分吻合问题•过度拟合–对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例.–定义：给定一个假设空间H。若存在两个假设hH和h’H，如果在训练例上h比h’的错误少，但在全部实例上h’比h的错误少，则称假设hH与训练例过分吻合.MachineLearning•导致过度拟合的原因–一种可能原因是训练样例含有随机错误或噪声.•x15SunnyHotNormalStrong负(加一个分类错误的训练例)–当训练数据没有噪声时，过度拟合也有可能发生，特别是当与叶节点对应训练例的数量太小时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系.MachineLearning假设h’A1A3A4SORHNSW(1,2,8)(9,11)(3,7,12,13)(6,14)(4,5,10)A1A3A4SORHNSWA2假设hCMH(9)(11)(15)事例MachineLearning避免过度拟合数据•避免过度拟合的方法–及早停止树增长–后修剪法•两种方法的特点–第一种方法更直观，但精确地估计何时停止树增长很困难–第二种方法被证明在实践中更成功MachineLearning•避免过度拟合的关键：–使用什么样的准则来确定最终正确树的规模•解决方法：–使用与训练例互相独立的另一组实例，评价后剪除的效果(训练集与验证集分离)，来评估通过后修剪方法从树上修剪节点的效用。–使用所有可用数据进行训练，但用统计方法（χ2测试）来估计一个节点的加入或剪除是否对训练例以外的数据分类有所改进。–对训练例和决策树编码复杂度进行度量，当编码复杂度达到最小时停止树的增长（最小描述长度原理）。MachineLearning减错剪除•将树上的每一个中间节点(决策节点）作为修剪的候选对象•修剪步骤–删除以此节点为根的子树，使它成为叶节点–将它标记为与它相关的那些训练例的最常见分类•节点剪除的标准是：剪除后的决策树在验证样例上的分类效果不低于原来的树–节点剪除是一个重复过程，总是选取对验证例分类的精度改进贡献最大的节点先删除–当进一步剪除有害时（降低对验证例分类的精度），节点剪除的过程终止•如果有大量的数据可供使用，那么使用分离的数据集合来进行修剪.•数据分成3个子集–训练，形成树;验证，修剪树;测试，精度的无偏估计MachineLearning规则后修剪•从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生•将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则•通过删除任何能导致估计精度提高的前件来修剪每一条规则(一般化)，直到继续删除将降低估计精度为止•按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例MachineLearning连续型属性问题•ID3被限制为取离散值的属性1.学到的决策树要预测的目标属性必须是离散的2.树的决策节点的属性也必须是离散的•简单删除上面第2个限制的方法–通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合.–“动态”是指在ID3算法执行中，