第机器学习 决策树

会计学1第机器学习决策树上节课程内容回顾明天太阳会升起吗?他在一个袋子放了黑白各一个颗弹子。（太阳升起的概率？）第一天第二天太阳升起了，他加了一个白弹子在袋子里。（太阳升起的概率？）第三天太阳升起了，他又加了一个白弹子在袋子里。（太阳升起的概率？）。。。。。。。结论几乎可以肯定，太阳总会升起。第1页/共102页主要内容4.6.5决策树的假设空间搜索4.6.4最佳分类属性判定4.6.3决策树的基本算法4.6.2决策树学习的适用问题4.6.1决策树的概念4.6.8决策树算法的PROLOG实现4.6.7决策树的优缺点4.6.6决策树的常见问题第2页/共102页什么是决策树?从管理学的角度定义决策树是指使用系统分析方法，把各种决策方案及出现结果的可能性进行分组排列，然后确定最佳方案的决策过程。

4.6.1什么是决策树？第3页/共102页举例:渔民投资决策点新船旧船好鱼情(0.7)坏鱼情(0.3)好鱼情(0.7)坏鱼情(0.3)$90000-$10000$80000$200004.6.1什么是决策树？第4页/共102页什么是决策树?从机器学习的角度定义决策树是运用于分类的一种树结构。4.6.1什么是决策树？第5页/共102页决策树的表示方法每个内部节点（internalnode）代表对某个属性的一次测试。一条边代表一个测试结果。叶子（leaf）代表某个类（class）或者类的分布（classdistribution）。最上面的节点是根结点。4.6.1什么是决策树？第6页/共102页举例假设用一个决策树表示一个关心电子产品的用户是否会购买PC的知识，然后用它来预测某条记录（某个人）的购买意向。4.6.1什么是决策树？第7页/共102页举例年龄?学生?信用状况?否是是是否<=3030-40>40否

是很好一般4.6.1什么是决策树？第8页/共102页举例类别：buys_computers=yes和buys_computers=no）。样本向量为（age,student,credit_rating;buys_computers）被决策数据的格式为（age,student,credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。4.6.1什么是决策树？第9页/共102页决策树分类过程决策树通过把实例从根结点排列（sort）到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性（attribute）的测试，并且该结点的每一个后继分支对应于该属性的一个可能值。4.6.1什么是决策树？第10页/共102页决策树分类过程（续）分类实例的方法是从这棵树的根结点开始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。4.6.1什么是决策树？问题：实例怎么表达？第11页/共102页决策树与规则表达的转换通常决策树代表实例属性值约束的合取（conjunction）的析取式（disjunction）。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。(Buys_computer=age<=30∧Student)∨(Buys_computer=age=30-40)∨(Buys_computer=age>40∧Credit_rating=excellent)4.6.1什么是决策树？第12页/共102页决策树学习的适用问题实例由“属性-值”对（pair）表示

--实例是用一系列固定的属性和它们的值来描述的。

--最简单的决策树学习中，每一个属性取少数的分离的值。

--扩展的算法允许处理值域为实数的属性（例如，数字表示的温度）。4.6.2决策树学习的适用问题第13页/共102页决策树学习的适用问题目标函数具有离散的输出值

--上面举例的决策树给每个实例赋予一个布尔型的分类（例如，yes或no）。

--决策树方法很容易扩展到学习有两个以上输出值的函数。

--一种更强有力的扩展算法允许学习具有实数值输出的函数，尽管决策树在这种情况下的应用不太常见。4.6.2决策树学习的适用问题第14页/共102页决策树学习的适用问题可能需要析取的描述

--决策树很自然地代表了析取表达式。

4.6.2决策树学习的适用问题第15页/共102页决策树学习的适用问题训练数据可以包含缺少属性值的实例

--决策树学习对错误有很好的鲁棒性，无论是训练样例所属的分类错误还是描述这些样例的属性值错误。

4.6.2决策树学习的适用问题已经发现有很多实际的问题符合这些特征，所以决策树学习已经被应用到很多问题中。例如：根据拖欠支付的可能性分类贷款申请；根据起因分类设备故障。它们的核心任务就是要把样例分类到各可能的离散值对应的类别中。第16页/共102页已有的决策树学习算法4.6.3基本的决策树学习算法大多数已开发的决策树学习算法都是一种核心算法的变体。ID3(QUINLAN1986)及其后继的C4.5第17页/共102页ID34.6.3基本的决策树学习算法基本的ID3算法通过自顶向下构造决策树来进行学习。第18页/共102页ID3算法的构造过程

（问题：哪一个属性将在树的根结点被测试？）4.6.3基本的决策树学习算法使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根结点的测试。为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是，样例的该属性值对应的分支）之下。

重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。第19页/共102页专用于学习布尔函数的ID3算法4.6.3基本的决策树学习算法ID3是一种自顶向下增长树的贪婪(greedy)算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或者所有的属性都使用过了。见复印资料。第20页/共102页专用于学习布尔函数的ID3算法4.6.3基本的决策树学习算法什么是衡量属性价值的定量标准？第21页/共102页信息熵4.6.4哪个属性是最佳的分类属性？信息论中广泛使用的一个度量标准（ClaudeElwoodShannon），称为熵（entropy），它刻画了任意样例集的纯度（purity）。

第22页/共102页信息熵4.6.4哪个属性是最佳的分类属性？给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：

Entropy(S)-plog2p

-pΘlog2pΘ

其中，p是在S中正例的比例，pΘ是在S中负例的比例。在有关熵的所有计算中我们定义0log0为0。

第23页/共102页举例4.6.4哪个属性是最佳的分类属性？假设S是一个关于某布尔概念的有14个样例的集合，它包括9个正例和5个反例（用记号[9+，5-]来表示）。那么S相对于这个布尔分类的熵（Entropy）为：第24页/共102页注意4.6.4哪个属性是最佳的分类属性？如果S的所有成员属于同一类，那么S的熵为0。例如，如果所有的成员是正的（p=1），那么pΘ就是0，那么

Entropy(S)=0。第25页/共102页注意4.6.4哪个属性是最佳的分类属性？当集合中正反样例的数量相等时熵为1。如果集合中正反例的数量不等时，熵介于0和1之间。1.00,00.50.51.0某布尔分类的熵函数P随着从0到1变化的曲线第26页/共102页信息论中熵的解释4.6.4哪个属性是最佳的分类属性？熵确定了集合S中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少二进制位数。第27页/共102页信息论中熵的解释4.6.4哪个属性是最佳的分类属性？如果P是1，接收者知道抽出的样例必为正，所以不必发任何消息，此时的熵为0。如果是P0.5，必须用一个二进制位来说明抽出的样例是正还是负。如果是P0.8，那么对所需的消息编码方法是赋给正例集合较短的编码，可能性较小的反例集合较长的编码，平均每条消息的编码少于1个二进制位。第28页/共102页通用信息熵的定义4.6.4哪个属性是最佳的分类属性？如果目标属性具有c个不同的值，那么S相对于c个状态（c-wise）的分类的熵定义为： 第29页/共102页通用信息熵的定义4.6.4哪个属性是最佳的分类属性？为什么对数的底数是2?熵的最大可能值是多少?第30页/共102页信息增益(InformationGain)4.6.4哪个属性是最佳的分类属性？一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。第31页/共102页信息增益(InformationGain)4.6.4哪个属性是最佳的分类属性？一个属性A相对样例集合S的信息增益Gain(S,A)被定义为:第32页/共102页信息增益(InformationGain)4.6.4哪个属性是最佳的分类属性？Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。第33页/共102页举例4.6.4哪个属性是最佳的分类属性？例如，假定S是一套有关天气的训练样例，描述它的属性包括可能是具有Weak和Strong两个值的Wind。假定S包含14个样例，[9+，5-]。在这14个样例中，假定正例中的6个和反例中的2个有Wind=Weak，其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下。第34页/共102页举例4.6.4哪个属性是最佳的分类属性？第35页/共102页举例4.6.4哪个属性是最佳的分类属性？第36页/共102页信息增益与ID34.6.4哪个属性是最佳的分类属性？信息增益正是ID3算法增长树的每一步中选取最佳属性的度量标准。第37页/共102页举例4.6.4哪个属性是最佳的分类属性？

见复印材料。课堂练习:画出该示例的决策树。第38页/共102页Outlook??yesSunnyOvercastRain?举例4.6.4哪个属性是最佳的分类属性？[D1,D2,D3….,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]第39页/共102页举例4.6.4哪个属性是最佳的分类属性？Ssunny=[D1,D2,D8,D9,D11]Gain(Ssunny,Humidity)=0.97-(3/5)0.0-(2/5)0.0=0.97Gain(Ssunny,Temperature)=0.97-(2/5)0.0-(2/5)1.0

-(1/5)0.0=0.57Gain(Ssunny,Wind)=0.97-(2/5)1.0-(3/5)0.918=0.19第40页/共102页决策树学习中的假设空间搜索4.6.5决策树学习中的假设空间搜索ID3算法可以被描述为从一个假设空间中搜索一个拟合训练样例的假设。被ID3算法搜索的假设空间就是可能的决策树的集合。ID3算法以一种从简单到复杂的爬山算法遍历这个假设空间，从空的树开始，然后逐步考虑更加复杂的假设，目的是搜索到一个正确分类训练数据的决策树。引导这种爬山搜索的评估函数是信息增益度量。第41页/共102页决策树学习中的误区4.6.5决策树学习中的假设空间搜索树的深度应尽量小。但贪婪搜索可能无法找到最小树，顶层结点可能不是高区分度的。第42页/共102页计算复杂度4.6.5决策树学习中的假设空间搜索最坏情况是构造出一棵完全树，每条路径都测试了所有特征。

第43页/共102页计算复杂度4.6.5决策树学习中的假设空间搜索各层i要对剩下的|A|-i个属性计算最佳分割。

一般来说，性能与属性个数成线性关系。D就是样本集第44页/共102页决策树学习的归纳偏置4.6.6决策树学习的归纳偏置归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例的分类。第45页/共102页决策树学习的归纳偏置4.6.6决策树学习的归纳偏置归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例的分类。第46页/共102页决策树学习的归纳偏置4.6.6决策树学习的归纳偏置如果给定一个训练样例的集合，那么通常有很多决策树与这些样例一致。所以，要描述ID3算法的归纳偏置，应找到它从所有一致的假设中选择一个的根据。第47页/共102页决策树学习的归纳偏置4.6.6决策树学习的归纳偏置ID3从这些决策树中选择哪一个呢？它选择在使用简单到复杂的爬山算法遍历可能的树空间时遇到的第一个可接受的树。第48页/共102页ID3的搜索策略4.6.6决策树学习的归纳偏置优先选择较短的树而不是较长的。选择那些信息增益高的属性离根结点较近的树。第49页/共102页存在的问题4.6.6决策树学习的归纳偏置在ID3中使用的选择属性的启发式规则和它遇到的特定训练样例之间存在着微妙的相互作用。由于这一点，很难准确地刻划出ID3的归纳偏置。然而我们可以近似地把它的归纳偏置描述为一种对短的决策树的偏好。第50页/共102页近似的ID3算法归纳偏置

4.6.6决策树学习的归纳偏置BFS-ID3：较短的树比较长的优先宽度优先搜索？深度优先搜索？第51页/共102页近似的ID3算法归纳偏置

4.6.6决策树学习的归纳偏置BFS-ID3：原理/过程它从一个空的树开始广度优先（breadthfirst）搜索逐渐复杂的树，先考虑所有深度为1的树，然后所有深度为2的，……。一旦它找到了一个与训练数据一致的决策树，它返回搜索深度的最小的一致树（例如，具有最少结点的树）。这种广度优先搜索称为BFS-ID3。BFS-ID3寻找最短的决策树，因此精确地具有“较短的树比较长的得到优先”的偏置。ID3可被看作BFS-ID3的一个有效近似，它使用一种贪婪的启发式搜索企图发现最短的树，而不用进行完整的广度优先搜索来遍历假设空间。

第52页/共102页近似的ID3算法归纳偏置

4.6.6决策树学习的归纳偏置ID3归纳偏置的更贴切近似：较短的树比较长的得到优先。那些信息增益高的属性更靠近根结点的树得到优先。第53页/共102页为什么ID3中选择短的假设优先？4.6.6决策树学习的归纳偏置ID3算法中优选较短决策树的归纳偏置，是不是从训练数据中泛化的可靠基础？哲学家们以及其他学者已经对这样的问题争论几个世纪了，而且这个争论至今还未解决。威廉·奥坎姆大约在1320年提出类似的论点，是最早讨论这个问题的人之一，所以这个偏置经常被称为“奥坎姆剃刀”（Occam’srazor）。第54页/共102页Occam’srazor4.6.6决策树学习的归纳偏置奥卡姆剃刀（Occam'sRazor,Ockham'sRazor）是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉（WilliamofOccam）提出的一个原理。第55页/共102页Occam’srazor4.6.6决策树学习的归纳偏置Entitiesshouldnotbemultipliedunnecessarily．（“如无必要，勿增实体”。）第56页/共102页Occam’srazor4.6.6决策树学习的归纳偏置威廉使用这个原理证明了许多结论，包括“通过思辨不能得出上帝存在的结论”。这使他不受罗马教皇的欢迎。第57页/共102页Occam’srazor4.6.6决策树学习的归纳偏置许多科学家接受或者（独立的）提出了奥卡姆剃刀原理，例如莱布尼兹的“不可观测事物的同一性原理”和牛顿提出的一个原则：如果某一原因既真又足以解释自然事物的特性，则我们不应当接受比这更多的原因。第58页/共102页Occam’srazor4.6.6决策树学习的归纳偏置对于科学家，这一原理最常见的形式是：当你有两个处于竞争地位的理论能得出同样的结论，那么简单的那个更好。第59页/共102页Occam’srazor

（奥卡姆剃刀的强形式）4.6.6决策树学习的归纳偏置如果你有两个原理，它们都能解释观测到的事实，那么你应该使用简单的那个，直到发现更多的证据。对于现象最简单的解释往往比较复杂的解释更正确。第60页/共102页Occam’srazor

（奥卡姆剃刀的强形式）4.6.6决策树学习的归纳偏置如果你有两个类似的解决方案，选择最简单的。需要最少假设的解释最有可能是正确的……或者以这种自我肯定的形式出现：让事情保持简单！第61页/共102页Occam’srazor

（奥卡姆剃刀的强形式）4.6.6决策树学习的归纳偏置严格的说，它们应该被称为吝啬定律，或者称为朴素原则。爱因斯坦说:“万事万物应该尽量简单，而不是更简单。”第62页/共102页Occam’srazor

（奥卡姆剃刀的强形式）4.6.6决策树学习的归纳偏置当然给出一个归纳偏置的名字不等于证明了它。决策树假设,500个结点的决策树比5个结点的决策树多得多。如果给定一个20个训练样例的集合，可以预期能够找到很多500个结点的决策树与训练数据一致，而如果一个5结点的决策树可以完美地拟合这些数据则是出乎意外的。所以我们会相信5个结点的树不太可能是统计巧合，因而优先选择这个假设，而不选择500个结点的。第63页/共102页Occam’srazor

（奥卡姆剃刀的强形式）4.6.7决策树的常见问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率ID3扩展为C4.5第64页/共102页避免过度拟合（Overfitting）4.6.7决策树的常见问题通过学习训练数据来构造分类树，可能无法达到最好的泛化性能。噪声数据的影响某些决策仅基于少量数据，与客观事实不符合第65页/共102页避免过度拟合（Overfitting）4.6.7决策树的常见问题基本ID3算法描述增长树的每一个分支的深度，直到恰好能对训练样例完美地分类。数据中有噪声。训练数据太少以至于不能产生目标函数的有代表性的采样时。在以上任一种情况发生时，这个简单的算法产生的树会过度拟合训练样例。第66页/共102页避免过度拟合（Overfitting）4.6.7决策树的常见问题对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布（也就是包含训练集合以外的实例）上表现的却更好时，我们说这个假设过度拟合（overfit）训练样例。第67页/共102页避免过度拟合4.6.7决策树的常见问题定义：给定一个假设空间H，一个假设hH，如果存在其他的假设h´H，使得在训练样例上h的错误率比h´小，但在整个实例分布上h´的错误率比h小，那么就说假设h过度拟合训练数据。第68页/共102页避免过度拟合4.6.7决策树的常见问题第69页/共102页过度拟合与噪声4.6.7决策树的常见问题分类或属性噪声都会导致过度拟合

增加噪声实例<<medium,green,circle>,+>（实际为-）。第70页/共102页过度拟合与噪声4.6.7决策树的常见问题第71页/共102页过度拟合与噪声4.6.7决策树的常见问题噪声也会直接导致样本的冲突(相同描述，不同分类)。应将叶结点标号为主要的分类

<<big,red,circle>,->(实际上为+)。若属性不完备且不足以判别分类时，也可能导致样本的冲突。第72页/共102页避免过度拟合的方法—剪枝4.6.7决策树的常见问题预修剪：支持度不够则停止树的增长。后修剪：置信度不够则修剪掉该分支。第73页/共102页哪种方法被实践证明更有效？原因是什么？避免过度拟合的方法—剪枝4.6.7决策树的常见问题预修剪中精确地估计何时停止增长树很困难。第74页/共102页无论是通过预修剪还是后修剪来得到正确大小的树，一个关键的问题是使用什么样的准则来确定最终正确树的大小。

避免过度拟合的方法—剪枝4.6.7决策树的常见问题第75页/共102页修剪方法4.6.7决策树的常见问题使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修剪结点的效用。第76页/共102页修剪方法4.6.7决策树的常见问题使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的结点是否有可能改善在训练集合外的实例上的性能。例如，Quinlan（1986）使用一种卡方（chi-square）测试来估计进一步扩展结点是否能改善在整个实例分布上的性能，还是仅仅改善了在当前的训练数据上的性能。第77页/共102页修剪方法4.6.7决策树的常见问题使用一个明确的标准来衡量训练样例和决策树编码的复杂度，当这个编码的长度最小时停止增长树。这个方法基于一种启发式规则，被称为最小描述长度（MinimumDescriptionLength）的准则。第78页/共102页训练和验证集法4.6.7决策树的常见问题AllavailabledataTrainingSetGrowingSetPruningSetTestSet第79页/共102页训练和验证集法的动机4.6.7决策树的常见问题即使学习器可能会被训练集合中的随机错误和巧合规律性所误导，但验证集合不大可能表现出同样的随机波动。所以，验证集合可以用来对过度拟合训练集中的虚假特征提供一个防护检验。当然，很重要的一点，验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。第80页/共102页合并连续值属性4.6.7决策树的常见问题如何把连续值的决策属性加入到决策树中？以通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合。例如，对于连续值的属性A，算法可动态地创建一个新的布尔属性Ac，如果A<c，那么为Ac真，否则为假。唯一的问题是如何选取最佳的阈值c。第81页/共102页举例4.6.7决策树的常见问题对于与决策树的特定结点关联的训练样例，进一步假定其属性Temperature和目标属性PlayTennis的值如下：Temperature: 40 48 60 72 80 90PlayTennis: No No Yes Yes Yes No对属性Temprature，应该定义什么样的基于阈值的布尔属性呢？无疑，我们会选择产生最大信息增益的阈值c。第82页/共102页举例4.6.7决策树的常见问题对于与决策树的特定结点关联的训练样例，进一步假定其属性Temperature和目标属性PlayTennis的值如下：Temperature: 40 48 60 72 80 90PlayTennis: No No Yes Yes Yes No第83页/共102页举例4.6.7决策树的常见问题对属性Temprature，应该定义什么样的基于阈值的布尔属性呢？第84页/共102页举例4.6.7决策树的常见问题首先按照连续属性A排序样例，然后确定目标分类不同的相邻实例，于是我们可以产生一组候选阈值，它们的值是相应的A值之间的中间值。可以证明产生最大信息增益的c值必定位于这样的边界中。第85页/共102页举例4.6.7决策树的常见问题在当前的例子中，有两个候选阈值，它们对应于目标属性PlayTennis变化时属性Temperature的值：（48+60）/2和（80+90）/2。然后计算每一个候选属性——Temperature>54和Temperature>85的信息增益，并选择最好的（Temperature>54）。现在这个动态创建的布尔属性便可以和其他候选的离散值属性一同“竞争”，以用于增长决策树。第86页/共102页举例4.6.7决策树的常见问题如何把连续的属性分割成多个区间？第87页/共102页属性选择的其他度量标准4.6.7决策树的常见问题信息增益度量偏袒具有较多值的属性。举一个极端的例子，考虑属性Date，它有大量的可能值。它会在所有属性中有最大的信息增益。这是因为单独Date就可以完全预测训练数据的目标属性。第88页/共102页属性选择的其他度量标准4.6.7决策树的常见问题于是这个属性会被选作树的根结点的决策属性并形成一棵深度为一级但却非常宽的树，这棵树可以理想地分类训练数据。当然，这个决策树对于后来数据的性能会相当差，因为尽管它完美地分割了训练数据，但它不是一个好的预测器（predicator）。第89页/共102页举例4.6.7决策树的常见问题属性Date太多的可能值必然把训练样例分割成非常小的空间。因此，相对训练样例，它会有非常高的信息增益，尽管对于未见实例它是一个非常差的目标函数预测器。第90页/共102页增益比率4.6.7决策树的常见问题增益比率通过加入一个称作分裂信息（splitinformation）的项来惩罚类似Date的属性，分裂信息用来衡量属性分裂数据的广度和均匀性：其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。

第91页/共102页举例4.6.7决策树的常见问题分裂信息实际上就是S关于属性A的各值的熵。

ID3中熵是S关于学习到的树要预测的目标属性的值的熵。第92页/共102页