3-决策树学习

2020/6/301第三章决策树学习3.1简介3.2决策树表示法3.3决策树学习的适用范围3.4基本的决策树学习算法3.5决策树学习中的假设空间搜索3.6决策树学习的归纳偏置3.7决策树学习的常见问题3.8小结2020/6/3023.1简介与前一章概念学习对比了解以下内容：决策树学习是应用最广泛的归纳学习算法之一。决策树学习是一种逼近离散值目标函数的方法，它学习到的目标函数(概念)被表示为一棵决策树。学习到的决策树(目标函数）对应一组属性测试的合取的析取。该方法搜索完整表示的假设空间，避免受限假设空间的不足。学习得到的决策树(目标）也能再被表示为多个if-then的规则，以提高可读性。决策树学习方法对噪声数据有较好的健壮性。决策树学习的归纳偏置是优先选择较小（低）的树。2020/6/3033.2决策树表示法（1/3）决策树学习后得到一棵决策树。决策树的结构:树上的每一个叶子结点即为实例所属的分类.内部结点指定了对实例的某个属性的测试，并且该结点的每一个后继分支对应于该属性的一个可能值。决策树分类(新)实例的方法是：首先，从这棵树的根结点开始，测试这个结点指定的属性。然后，按照给定实例的该属性值对应的树枝向下移动。最后，这个过程在以新结点为根的子树上重复，直到到达叶子节点，得到该实例的正确分类。2020/6/3053.2决策树表示法（2/3）X:Outlook=Sunny，Temperature=Hot，Humidity=High，Wind=Strong上面决策树预测这个实例x的目标PLayTennis=No下面决策树根据天气情况分类“星期六上午是否适合打网球”2020/6/3063.2决策树表示法（3/3）通常决策树代表实例属性值约束的合取（根到某个叶子对应的路径）的析取式(树的所有分支):从树根到树叶的每一条路径对应一组属性测试的合取。树本身对应这些合取的析取。例如，图3-1表示的决策树对应于以下表达式:(Outlook=SunnyHumidity=Normal)V(Outlook=Overcast)V(Outlook=RainWind=Weak)2020/6/3073.3决策树学习的适用范围实例是由“属性一值”对表示的:在最简单的决策树学习中，每一个属性取少数的离散的值例（如，Hot,Mild,Cold)。然而，扩展的算法也允许处理值域为实数的属性。目标函数具有离散的输出值:决策树方法很容易扩展到学习有两个以上输出值(目标值)的函数。可能需要析取的描述:决策树很自然地代表了析取表达式。训练数据可以包含错误:决策树学习对错误有很好的健壮性。训练数据可以包含缺少属性值的实例:决策树学习甚至可以在有未知属性值的训练样例中使用。2020/6/3083.4基本的决策树学习算法基本的ID3算法通过自顶向下构造决策树进行学习。构造过程是从“哪一个属性将在树的根结点被测试?”这个问题开始的。首先，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根结点的测试。然后，为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支(也就是，样例的该属性值对应的分支)之下。重复整个过程，用每个分支结点关联的全部训练样例来选取在该点被测试的最佳属性。2020/6/309专用于学习布尔函数的ID3算法概要ID3(Examples,Target-attribute,Attributes){Examples即训练样例集。Target-attribute是目标属性。Attributes是属性列表。返回一棵能正确分类给定Examples的决策树.}创建树的Root结点如果Exampls都为正，那么返回label=+的单结点树Root如果Exampls都为反，那么返回label=一的单结点树Root如果Attributes为空，那么返回单结点树Root,label=Examples中最普遍的Target-attribute值否则开始AAttributes中分类Examples能力最好的属性Root的决策属性A对于A的每个可能值vi:在Root下加一个新的分支对应测试A=vi:令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空则在这个新分支下加一个叶子结点，结点的label=Examples中最普遍的Target-attribute值否则在这个新分支下加一个子树ID3(Examplevi,Target-attribute,Attributes一{A})结束返回Root2020/6/30103.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（1）ID3算法的核心问题是选取在树的每个结点要测试的属性。“信息增益”(informationgain)，用来衡量给定的属性区分训练样例的能力。ID3算法在增长树的每一步使用这个信息增益标准从候选属性中选择属性。2020/6/30113.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（2）1.用熵度量样例的均一性为了精确地定义信息增益，先定义信息论中广泛使用的一个度量标准，称为熵(entropy)，它刻画了任意样例集的纯度(purity)。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为:ppppSEntropy22loglog)(2020/6/30123.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（3）例，假设s是一个关于某布尔概念的有14个样例的集合，它包括9个正例和5个反例(我们采用记号「9十，5一」来概括这样的数据样例)。那么S相对于这个布尔分类的熵为:注意，•如果s的所有成员属于同一类，那么s的熵为0;(最纯净)•当集合中正反样例的数量相等时，熵为1;（均一性最强）•如果集合中正反例的数量不等时，熵介于0和1之间。2020/6/30133.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（4）图中画出了随着正例所占比例P从0到1熵函数变化的曲线图3-2关于某布尔分类的的熵函数2020/6/30143.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（5）信息论中熵的一种解释：熵确定了要编码集合s中任意成员(即以均匀的概率随机抽出的一个成员)的分类所需要的最少二进制位数。举例：如果P是1，接收者知道抽出的样例必为正，所以不必发任何消息，此时的熵为0。另一方面，如果P是0.5，必须用一个二进制位来说明抽出的样例是正还是负。如果P是0.8，那么对所需的消息编码方法是赋予正例集合较短的编码，可能性较小的反例集合较长的编码。2020/6/30153.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（6）前面讨论了目标分类是布尔型的情况下的熵。更一般的，如果目标属性具有c个不同的值，那么s相对于c个状态的分类的熵定义为:其中，Pi是S中属于类别i的比例。请注意对数的底数仍然为2，原因是熵是以二进制位的个数来度量编码长度的。同时注意，如果目标属性具有c个可能值，那么熵最大可能为log2c。2020/6/30163.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（7）2.用信息增益度量期望熵的降低（1）一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低（纯度的增加）。一个属性A相对样例集合S的信息增益Gain(S,A)被定义为:其中，Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集(即，Sv={sS|A(s)=v})Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。2020/6/30173.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（8）例：假定S是一套有关天气的训练样例，描述它的属性为可具有Weak和Strong两个值的Wind。假定S包含14个样例（9十，5一）。在这14个样例中，假定正例中的6个和反例中的2个有Wind=Weak，其他的有Wind=Strong。2020/6/3018DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesDSRainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo表3-2目标概念PlayTennis的训练样例2020/6/30193.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（9）按照属性Wind分类14个样例得到的信息增益可以计算如下：2020/6/30203.4基本的决策树学习算法3.4.1哪个属性是最佳的分类属性（10）信息增益正是ID3增长树的每一步中选取最佳属性的度量标准前面的例子中，哪一个属性是最佳的分类属性?计算属性的信息增益2020/6/30213.4基本的决策树学习算法3.4.2举例（1）为了演示ID3算法的具体操作，考虑表3-2的训练数据所代表的学习任务。所有四个属性的信息增益为:Gain(S，Outlook)=0.246Gain(S，Humidity)=0.151Gain(S，Wind)=0.048Gain(S，Temperature)=0.029其中，S表示来自表3-2的训练样例的集合。2020/6/30223.4基本的决策树学习算法3.4.2举例（3）哪一个属性应在这里被测试?Ssunny={D1,D2,D8,D9,D11}Gain(Ssunny,Humidity)=.970一(3/5)0.0一(2/5)0.0=970Gain(SsunnyTemperature)=.970一(2/5)0.0一(2/5)1.0一(1/5)0.0=.570Gain(Ssunny,Wind)=.970一(2/5)1.0一(3/5).918=.019ID3算法第一步后形成的部分决策树2020/6/30233.5决策树学习中的假设空间搜索(1)与其他的归纳学习算法一样，决策树学习过程也是一个启发式搜索过程，算法ID3可以被描述为从一个假设空间中搜索一个拟合训练样例的假设。被ID3算法搜索的假设空间就是可能的决策树的集合。ID3算法以一种从简单到复杂的无回溯爬山算法遍历这个假设空间：从空树开始，然后逐步考虑更加复杂的假设，目的是搜索到一个正确分类训练数据的决策树。引导这种爬山搜索的评估函数（启发函数）是信息增益度量。2020/6/30243.5决策树学习中的假设空间搜索(2)被ID3算法搜索的假设空间就是可能的决策树的集合。ID3搜索的假设空间2020/6/30253.5决策树学习中的假设空间搜索(3)ID3算法的优势和不足:当遍历决策树空间时，ID3仅维护单一的当前假设（与候选消除不同）。例如，它不能判断有多少个其他的决策树也是与现有的训练数据一致的，或者使用新的实例查询来最优地区分这些竞争假设。基本的ID3算法在搜索中不进行回溯。每当在树的某一层次选择了一个属性进行测试，它不会再回溯重新考虑这个选择。所以，它易受无回溯的爬山搜索中的常见风险影响:收敛到局部最优的答案，而不是全局最优的。2020/6/30263.5决策树学习中的假设空间搜索(4)ID3算法中的假设空间包含