决策树学习培训和科学决策与信息分析

第3章决策树学习决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合更深入的话题决策树学习是一种归纳学习方法，它的特点有：是一种学习离散值目标函数的近似表达的方法。函数表示形式:决策树，易写为if-then

规则。实用性强，许多著名的学习系统（ID3,C4.5,ASSISTANT等）皆基于此方法，并成功应用到许多实际领域（学习疾病的诊断，信贷风险的评价，等）。能较好地抵抗噪音。能学习析取表达式。搜索完全的假设空间。它的归纳偏向是小树优先于大树。决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。决策树代表一个假设:(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)

设输入的属性集为｛A1,A2,...,An｝，则决策树可写成：所有以yes结束的路i（(A1=v1i)(A2=v2i)...(An=vni)）OutlookHumidityWindSunnyOvercastRainHighNormalStrongWeakNoYesYesNoYes适用问题特征训练例的对象由属性-值的对序列表示，具有确定个数的属性，属性可取若干离散值（取值个数越小越好）.目标函数具有离散型输出值。最常见的是布尔型目标函数.可能需要析取表达式描述的问题。显然决策树可自然地表达逻辑析取式.训练例有噪音。决策树学习对训练数据中的噪音具有抵抗力。噪音包括：训练例的分类错、训练例的属性值错、训练例的属性值不全等.基本的决策树学习算法大多数决策树学习算法都是ID3核心算法的一种变体,它采用自顶向下的贪婪搜索遍历可能的决策树空间.ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程ID3的简化描述:

输入：Es:训练例集,

c:目标概念,

As:属性列表

输出：能够正确判别Es的决策树递归算法：ID3(Es,c,As)建立决策树的根节点root若Es均为正例，则返回单节点树root，root标记+若Es均为负例，则返回单节点树root，root标记-若As为空，则返回单节点树root，root标记为Es中占多数的c值root的决策属性

As中可对Es进行最佳分类的属性A对A的每一可能的值v

从root射出一条弧，代表测试A=vEsv

Es中属性A取值为v的那些例子组成的子集若Esv为空则在此弧下加一节点，并标记为Es中占多数的c值否则在此弧下加一子树ID3(Esv,c,As-{A})返回以root为根的决策树最佳分类属性的确定？关键：确定As中可对Es进行最佳分类的属性A，即在树的每一个节点上确定一个候选属性，它的测试对训练例的分类最有利。

训练例分类纯度的度量熵:信息论中度量一组实例在某方面的纯度的方法。给定训练例集Es，其中正例的比例为p+，负例的比例为p-=1-p+。Es的关于这个布尔分类的纯度可用熵定义为：性质：实例集在目标分类方面越模糊、越杂乱、越无序，它的熵就越高；实例集在目标分类方面越清晰、越纯洁、越有序，它的熵就越低。熵刻画了任意样例集的纯度.一种解释：熵为Es中的任意实例的分类结果进行编码所需的最少比特数

.更一般地，如果目标属性具有c个不同的值，那么Es相对于c个状态的分类的熵定义为:预计熵减弱的度量信息赢取

设Es当前的熵为E，若用一个属性A将Es分组（A=v的实例分在同一组Esv），E将会降低（从无序向有序）。预计熵降低的数量称为属性A相对于实例集Es的信息赢取Gain(Es,A)，定义为：解释：由于了解分析A的值而1.引起的熵减弱（有序化）→2.获得的关于目标分类的信息→3.节省的为Es中的任意实例的分类结果进行编码所需的比特数,信息赢取越大的属性对训练例的分类越有利.如何确定As中可对Es进行最佳分类的属性？原则:信息赢取越大的属性对训练例的分类越有利;操作:算法在每一步选取“As中可对Es进行最佳分类的属性;可见,计算各个属性的信息赢取并加以比较是ID3算法的关键操作。ID3算法举例对象：日子目标概念：适合打网球：日子集D

Bool训练例：日子属性表A1A2A3A4正/负例阴晴气温湿度风力

x1SunnyHotHighWeak负x2SunnyHotHighStrong负x3OvercastHotHighWeak正x4RainyMildHighWeak正x5RainyCoolNormalWeak正x6RainyCoolNormalStrong负x7OvercastCoolNormalStrong正x8SunnyMildHighWeak负x9SunnyCoolNormalWeak正x10RainyMildNormalWeak正x11SunnyMildNormalStrong正x12OvercastMildHighStrong正x13OvercastHotNormalWeak正x14RainyMildHighStrong负决策树学习的搜索空间和搜索策略ID3搜索的假设空间是所有可能的决策树的集合.ID3搜索的目的是构造与训练数据一致的一棵决策树（即能够对训练例进行正确分类的一棵决策树）.ID3的搜索策略是爬山法，在构造决策树时从简单到复杂，用信息赢取作为指导爬山法的评价函数.决策树学习的搜索空间和搜索策略(续)优点搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险。整体使用训练数据，而不是象候选剪除算法一个一个地考虑训练例。能抵抗噪音（个例中的错误数据）。缺点:搜索中只维持一个解，不能象候选剪除算法那样返回所有可能的与训练例集一致的假设，也不能通过查询新例来优化获得的收敛于目标函数的解。搜索过程无回溯。如同一般的无回溯爬山搜索一样，它可能收敛于局部最优解而丢掉全局最优解。因为不是一个一个地考虑训练例，不容易象候选剪除算法那样使用新例步进式地改进决策树。决策树学习的归纳偏向ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏向近似的ID3的归纳偏向较短的树比较长的树优先近似在于ID3得到局部最优，而不一定是全局最优一个精确具有这个归纳偏向的算法，BFS-ID3更贴切近似的归纳偏向较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先候选消除算法ID3搜索范围不完整的假设空间,全搜完整的假设空间,但不全搜归纳偏置假设表示的表达能力,限制性(语言)偏向搜索策略排序,优先性(搜索)偏向限定偏向和优选偏向第一章讲的计算机下跳棋问题则综合运用两种偏向：将棋盘评价函数定为线性函数是一种语言偏向，而在调节系数时使用的最小均方系数调整规则（LMS系数调整规则）是一种搜索偏向。为什么短的假设优先ID3的短树优先于长树的偏向是所谓Occam（奥卡姆）剃刀原理的一种体现。Occam剃刀原理的一般表达为：偏向于与数据一致的最简单假设,即优先选择拟合数据的最简单的假设。为什么呢?一般的解释是，与数据一致的简单假设的数量大大少于与数据一致的复杂假设的数量，所以简单假设与数据统计巧合的机会比复杂假设要小得多，从而选取简单假设更为保险。决策树学习的常见问题

--与训练例过分吻合问题

过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例.定义：给定一个假设空间H。若存在两个假设hH和h’H，如果在训练例上h比h’的错误少，但在全部实例上h’比h的错误少，则称假设hH与训练例过分吻合.导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声.x15SunnyHotNormalStrong负(加一个分类错误的训练例)当训练数据没有噪声时，过度拟合也有可能发生，特别是当与叶节点对应训练例的数量太小时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系.假设h’A1A3A4SORHNSW(1,2,8)(9,11)(3,7,12,13)(6,14)(4,5,10)A1A3A4SORHNSWA2假设hCMH(9)(11)(15)事例避免过度拟合数据避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观，但精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功避免过度拟合的关键：使用什么样的准则来确定最终正确树的规模解决方法：使用与训练例互相独立的另一组实例，评价后剪除的效果(训练集与验证集分离)，来评估通过后修剪方法从树上修剪节点的效用。使用所有可用数据进行训练，但用统计方法（χ2测试）来估计一个节点的加入或剪除是否对训练例以外的数据分类有所改进。对训练例和决策树编码复杂度进行度量，当编码复杂度达到最小时停止树的增长（最小描述长度原理）

。减错剪除将树上的每一个中间节点(决策节点）作为修剪的候选对象修剪步骤删除以此节点为根的子树，使它成为叶节点将它标记为与它相关的那些训练例的最常见分类节点剪除的标准是：剪除后的决策树在验证样例上的分类效果不低于原来的树节点剪除是一个重复过程，总是选取对验证例分类的精度改进贡献最大的节点先删除当进一步剪除有害时（降低对验证例分类的精度），节点剪除的过程终止如果有大量的数据可供使用，那么使用分离的数据集合来进行修剪.数据分成3个子集训练，形成树;验证，修剪树;测试，精度的无偏估计规则后修剪从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则(一般化)，直到继续删除将降低估计精度为止按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例规则精度估计方法使用与训练集不相交的验证集基于训练集合本身(C4.5)使用一种保守估计来弥补训练数据有利于当前规则的估计偏向过程1.先计算规则在它应用的训练样例上的精度(观察)2.然后假定此估计精度为二项式分布，并计算它的标准差3.给定一个置信区间，采用与观察精度和标准差相关的下界估计作为规则性能的度量评论1.对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远2.不是统计有效（统计学上无根据），但是实践中发现有效连续型属性问题

ID3被限制为取离散值的属性1.学到的决策树要预测的目标属性必须是离散的2.树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合.“动态”是指在ID3算法执行中，每当连续值属性成为候选属性时，就要依据当时当地的情况将它离散化.“划分点”的确定则仍要根据最大信息赢取的原则.设在ID3算法的某一步，相关训练例集为Es，候选属性集As中有一个连续型属性A.将Es中实例按A值升序排列。找到此序列中实例的分类发生变动的地方，并用A值对(ai,ai+1)表示在A值从ai增加到ai+1时实例的正负发生了变化。(ai+ai+1)/2成为A的离散化的一个候选阈值c.(分类变动点及对应的候选阈值可能有多个)对每一个候选的阈值c定义一个二值离散属性Ac。对每一个新的离散属性计算它的信息赢取gain(Es,Ac)，然后选取信息赢取最大的属性Ac为原属性A离散化的结果.ID3让新选定的离散化属性Ac代替连续型属性A来与As中其他的离散属性竟争当前步骤的最佳分类属性.对C1定义一个二值属性AC1={不发烧,发烧},求Gain(Es,AC1)对C2定义一个二值属性AC2={不发烧,发烧},求Gain(Es,AC2)若Gain(Es,AC2)>Gain(Es,AC1),则用AC2代替A参加与其它决策属性的竞争+++++++++++++++------A体温3737.137.437.5C1=37.05C2=37.45示例属性选择的其他标准

信息增益度量存在一个内在偏向,即偏向具有较多值的属性,如DATE属性避免的方法，采用其他度量，如增益比率增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性.分离能力强,则该值大.

分裂信息项阻碍选择值为均匀分布的属性问题，当某个|Si||S|,分母接近于0。解决方法：采用一些启发式规则，比如仅对增益高过平均值的那些属性应用增益比率测试属性值丢失问题

设在ID3计算的某一步相应的实例集为Es，我们需要知道对象xEs的A属性的值A(x)，而这个值没有给出。这时可用A属性在Es中最常出现的值充当未见的A(x)。也可用A属性在Es中分类与x一样的那些实例中最常出现的值充当未见的A(x)。C4.5使用更复杂的方法：为属性A的各种取值赋以概率（此概率的计算基于当前训练例中各值的出现频率）。具有未知A值的实例x按概率值分成大小不等的碎片，沿相应A值的分支向树的下方分布。实例的碎片将用于计算信息赢取。这个实例碎片法在学习后，还可以用来对属性值不全的新实例进行分类。属性值的获取代价问题

实例的属性可能与代价相关优先选择尽可能使用低代价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性通过引入一个代价项到属性选择度量中，可以使ID3算法考虑属性代价,如不是仅根据信息赢取，而是根据信息赢取和属性代价的比值来选择最佳属性。机器学习文献中提出了许多不同的考虑代价因素的评价属性的公式。它们的共同特点是，需要用在某一领域的实用效果来说明所提出的公式的价值。抽象地争论那一个公式更好似乎没有意义.小结决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法ID3算法贪婪算法从根向下构建决策树搜索完整的假设空间归纳偏置:较小的树过度拟合问题ID3算法的扩展第3章科学决策与信息分析主要内容：信息分析在决策中的作用；各类型决策中的信息保障；信息分析的工作流程。基本要求：了解各类决策中信息利用的重要性；了解不同决策阶段信息服务的特点；理解决策对信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在决策中的作用3.1.1决策活动中的信息利用信息分析:是对情报进行定向浓集和科学抽象的一种科学劳动.信息在军事战略制定中的作用；信息在制定地区经济发展规划中的作用；信息在科学管理中的作用；信息在对外贸易中的作用；信息在制定生产计划中的作用；信息在提高产品质量、发展花色品种中的作用。3.1信息分析在决策中的作用决策阶段信息服务的内容与特点决策前（超前服务）促成决策及早完成（快）；有助于决策者掌握预测性信息（准）；有助于决策者更新知识、增强判断力（增）决策中（跟踪服务）确立目标阶段；决策方案准备阶段；选定决策方案阶段。决策后（反馈服务）跟踪反馈；循环反馈；同步追踪反馈。3.1.2不同决策阶段的信息服务3.1信息分析在决策中的作用3.1.3决策对信息的基本要求可靠性（可信度）——信息的真实性和准确性。信息源；信息获取手段；信息获取的条件。完整性（完全度）——包括决策对象全部的信息全面收集历史的、现实的和未来的信息；兼顾反映正面的和反面问题的信息。精确性（精确度）——反映事物特征的细微化程度。不同决策对信息的精确度要求不同；划定范围，确定上限和下限。3.2各类型决策中的信息保障3.2.1新产品研制的信息保障创意产生与筛选阶段的信息保障创意产生于对信息的收集、吸收和理解；创意孕育着新产品，要尽可能多的收集；筛选是从多个创意中选择出具有开发价值项目的过程，其要求是：新意；可行；实用；有效。3.2各类型决策中的信息保障3.2.1新产品研制的信息保障开发决策阶段的信息保障主要任务是针对经过初步筛选出的几个创意中的每一个新产品开发构