3决策树学习.ppt

2024/5/6 周一1第三章决策树学习第三章决策树学习3.13.1简介简介3.23.2决策树表示法决策树表示法3.33.3决策树学习的适用范围决策树学习的适用范围3.43.4基本的决策树学习算法基本的决策树学习算法3.53.5决策树学习中的假设空间搜索决策树学习中的假设空间搜索3.63.6决策树学习的归纳偏置决策树学习的归纳偏置3.73.7决策树学习的常见问题决策树学习的常见问题3.83.8小结小结2024/5/6 周一2 3.1 3.1简介简介与前一章概念学习对比了解以下内容：与前一章概念学习对比了解以下内容：决策树学习是应用最广泛的决策树学习是应用最广泛的归纳学习归纳学习算法之一。算法之一。决策树学习是一种决策树学习是一种逼近离散值目标函数逼近离散值目标函数的方法，它学习到的方法，它学习到的目标函数的目标函数(概念概念)被表示为被表示为一棵决策树一棵决策树。学习到的决策树学习到的决策树(目标函数）目标函数）对应一组对应一组属性测试的合取的属性测试的合取的析取析取。该方法。该方法搜索完整表示的假设空间，避免受限假设空搜索完整表示的假设空间，避免受限假设空间的不足。间的不足。学习得到的决策树学习得到的决策树(目标）目标）也能再被也能再被表示为多个表示为多个if-thenif-then的的规则规则，以提高可读性。，以提高可读性。决策树学习方法对噪声数据有决策树学习方法对噪声数据有较好的健壮性较好的健壮性。决策树学习的决策树学习的归纳偏置归纳偏置是是优先选择较小（低）的树优先选择较小（低）的树。2024/5/6 周一33.23.2决策树表示法（决策树表示法（1/31/3）决策树学习后得到一棵决策树。决策树学习后得到一棵决策树。n决策树的结构决策树的结构:树上的每一个树上的每一个叶子结点叶子结点即为实例即为实例所属的分类所属的分类.内部结点内部结点指定了对实例的某个指定了对实例的某个属性的测试属性的测试，并且该结点的，并且该结点的每一个后继分支每一个后继分支对应于该对应于该属性的一个可能值属性的一个可能值。n决策树分类决策树分类(新新)实例的方法实例的方法是：是：首先，从这棵树的根结点开始，测试这个结点指定的首先，从这棵树的根结点开始，测试这个结点指定的属性。属性。然后，按照给定实例的该属性值对应的树枝向下移动。然后，按照给定实例的该属性值对应的树枝向下移动。最后，这个过程在以新结点为根的子树上重复，直到最后，这个过程在以新结点为根的子树上重复，直到到达叶子节点，得到该实例的正确分类。到达叶子节点，得到该实例的正确分类。2024/5/6 周一53.23.2决策树表示法（决策树表示法（2/32/3）X:上面决策树预测这个实例上面决策树预测这个实例x x的目标的目标PLayTennisPLayTennis=No=No下面决策树根据天气情况分类下面决策树根据天气情况分类“星期六上午是否适合打网球星期六上午是否适合打网球”2024/5/6 周一63.23.2决策树表示法（决策树表示法（3/33/3）n通常决策树代表通常决策树代表实例属性值约束的合取实例属性值约束的合取（根到某个叶子对（根到某个叶子对应的路径）应的路径）的析取式的析取式(树的所有分支树的所有分支):):从树根到树叶的每一条路径对应一组属性测试的从树根到树叶的每一条路径对应一组属性测试的合取。合取。树本身对应这些合取的树本身对应这些合取的析取析取。n例如，图例如，图3-13-1表示的决策树对应于以下表达式表示的决策树对应于以下表达式:(Outlook=(Outlook=SunnySunny HumidityHumidity=Normal)=Normal)V V(Outlook(Outlook=Overcast)=Overcast)V V(Outlook(Outlook=Rain=Rain Wind=Weak)Wind=Weak)2024/5/6 周一73.33.3决策树学习的适用范围决策树学习的适用范围n实例是由实例是由“属性一值属性一值”对表示的对表示的:在最简单的决策树学习中，在最简单的决策树学习中，每一个属性取少数的离散的值例（如，每一个属性取少数的离散的值例（如，Hot,Mild,Cold)Hot,Mild,Cold)。然而，扩展的算法也允许处理值域为实数的属性。然而，扩展的算法也允许处理值域为实数的属性。n目标函数具有离散的输出值目标函数具有离散的输出值:决策树方法很容易扩展到学习决策树方法很容易扩展到学习有有两个以上输出值两个以上输出值(目标值目标值)的函数。的函数。n可能需要析取的描述可能需要析取的描述:决策树很自然地代表了析取表达式。决策树很自然地代表了析取表达式。n训练数据可以包含错误训练数据可以包含错误:决策树学习对错误有很好的健壮性。决策树学习对错误有很好的健壮性。n训练数据可以包含缺少属性值的实例训练数据可以包含缺少属性值的实例:决策树学习甚至可以决策树学习甚至可以在有未知属性值的训练样例中使用。在有未知属性值的训练样例中使用。2024/5/6 周一83.43.4基本的决策树学习算法基本的决策树学习算法n 基本的基本的ID3ID3算法算法通过自顶向下构造决策树通过自顶向下构造决策树进行学习进行学习。构造过。构造过程是从程是从“哪一个属性将在树的根结点被测试哪一个属性将在树的根结点被测试?”这个问题开始这个问题开始的。的。首先，首先，使用统计测试使用统计测试来确定每一个实例属性单独分类训练样来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的例的能力。分类能力最好的属性被选作树的根结点的测试。根结点的测试。然后，为根结点属性的然后，为根结点属性的每个可能值产生一个分支每个可能值产生一个分支，并把训练，并把训练样例排列到适当的分支样例排列到适当的分支(也就是，样例的该属性值对应的分支也就是，样例的该属性值对应的分支)之下。之下。重复重复整个过程，整个过程，用每个分支结点关联的全部训练样例用每个分支结点关联的全部训练样例来选取来选取在该点被测试的最佳属性。在该点被测试的最佳属性。2024/5/6 周一9 专用于专用于学习布尔函数学习布尔函数的的ID3ID3算法概要算法概要ID3(Examples,Target-attribute,Attributes)ID3(Examples,Target-attribute,Attributes)ExamplesExamples即训练样例集。即训练样例集。Target-attributeTarget-attribute是目标属性。是目标属性。AttributesAttributes是属性列表。返是属性列表。返回一棵能正确分类给定回一棵能正确分类给定ExamplesExamples的决策树的决策树.创建树的创建树的RootRoot结点结点如果如果ExamplsExampls都为正，那么返回都为正，那么返回label=+label=+的单结点树的单结点树RootRoot如果如果ExamplsExampls都为反，那么返回都为反，那么返回label=label=一的单结点树一的单结点树RootRoot如果如果AttributesAttributes为空，那么返回单结点树为空，那么返回单结点树Root,labelRoot,label=Examples=Examples中中最普遍的最普遍的Target-attributeTarget-attribute值值否则开始否则开始 A A Attributes Attributes中中分类分类ExamplesExamples能力最好的属性能力最好的属性 RootRoot的决策属性的决策属性 A A 对于对于A A的每个可能值的每个可能值v vi i:在在RootRoot下加一个新的分支对应测试下加一个新的分支对应测试A=vA=vi i:令令ExamplesExamplesvivi为为ExamplesExamples中满足中满足A A属性值为属性值为v vi i的子集的子集 如果如果ExamplesExamplesvivi为空为空 则在这个新分支下加一个叶子结点，结点的则在这个新分支下加一个叶子结点，结点的label=Exampleslabel=Examples中最普遍中最普遍的的Target-attributeTarget-attribute值值 否则在这个新分支下加一个子树否则在这个新分支下加一个子树ID3(ExampleID3(Examplevi,vi,Target-attribute,Target-attribute,AttributesAttributes一一A)A)结束结束返回返回RootRoot2024/5/6 周一10 3.4 3.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（1 1）n ID3ID3算法的核心问题算法的核心问题是选取在树的每个结点要测试的属性。是选取在树的每个结点要测试的属性。n“信息增益信息增益”(information gain)(information gain)，用来衡量给定的属性区，用来衡量给定的属性区分训练样例的能力。分训练样例的能力。nID3ID3算法在增长树的每一步使用这个信息增益标准算法在增长树的每一步使用这个信息增益标准从候选属性从候选属性中选择属性中选择属性。2024/5/6 周一113.43.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（2 2）1.用熵度量样例的用熵度量样例的均一性均一性 为了精确地定义为了精确地定义信息增益信息增益，先定义信息论中广泛使用的一个，先定义信息论中广泛使用的一个度量标准，称为度量标准，称为熵熵(entropy)(entropy)，它刻画了任意样例集的，它刻画了任意样例集的纯度纯度(purity)(purity)。给定包含关于某个目标概念的正反样例的样例集。给定包含关于某个目标概念的正反样例的样例集S S，那么那么S S相对这个布尔型分类的熵相对这个布尔型分类的熵为为:2024/5/6 周一123.43.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（3 3）例，假设例，假设s s是一个关于某布尔概念的有是一个关于某布尔概念的有1414个样例个样例的集合，它包的集合，它包括括9 9个正例和个正例和5 5个反例个反例(我们采用记号我们采用记号9 9十，十，5 5一来概括这样一来概括这样的数据样例的数据样例)。那么。那么S S相对于这个布尔分类的熵相对于这个布尔分类的熵为为:注意注意，如果如果s s的所有成员属于同一类，那么的所有成员属于同一类，那么s s的熵为的熵为0;(0;(最纯净最纯净)当集合中正反样例的数量相等时，熵为当集合中正反样例的数量相等时，熵为1;1;（均一性最强均一性最强）如果集合中正反例的数量不等时，熵介于如果集合中正反例的数量不等时，熵介于0 0和和1 1之间。之间。2024/5/6 周一133.43.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（4 4）图中画出了随着正例所占比例图中画出了随着正例所占比例P 从从0到到1熵函数变化的曲线熵函数变化的曲线图图3-2关于某布尔分类的的关于某布尔分类的的熵熵函数函数2024/5/6 周一143.43.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（5 5）n 信息论中熵的一种解释：信息论中熵的一种解释：熵确定了要编码集合熵确定了要编码集合s s中任意成员中任意成员(即以均匀的概率随机抽即以均匀的概率随机抽出的一个成员出的一个成员)的分类所需要的最少二进制位数。的分类所需要的最少二进制位数。n举例：举例：如果如果P P 是是1 1，接收者知道抽出的样例必为正，所以不必发任何，接收者知道抽出的样例必为正，所以不必发任何消息，此时的熵为消息，此时的熵为0 0。另一方面，如果另一方面，如果P P 是是0.50.5，必须用一个二进制位来说明抽出的，必须用一个二进制位来说明抽出的样例是正还是负。样例是正还是负。如果如果P P 是是0.80.8，那么对所需的消息编码方法是赋予正例集合较，那么对所需的消息编码方法是赋予正例集合较短的编码，可能性较小的反例集合较长的编码。短的编码，可能性较小的反例集合较长的编码。2024/5/6 周一153.43.4基本的决策树学习算法基本的决策树学习算法3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（6 6）前面讨论了目标分类是前面讨论了目标分类是布尔型布尔型的情况下的熵。更一般的，的情况下的熵。更一般的，如果目标属性具有如果目标属性具有c c个不同的值个不同的值，那么那么s s相对于相对于c c个状态的分类个状态的分类的熵定义为的熵定义为:其中，其中，P Pi i是是S S中属于类别中属于类别i i的比例。的比例。请注意请注意对数的底数仍然为对数的底数仍然为2 2，原因是熵是以二进制位的个数来，原因是熵是以二进制位的个数来度量编码长度的。度量编码长度的。同时注意同时注意，如果目标属性具有，如果目标属性具有c c个可能值，那么熵最大可能为个可能值，那么熵最大可能为loglog2 2 c c。2024/5/6 周一163.43.4基本的决策树学习算法基本的决策树学习算法 3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（7 7）2.2.用信息增益度量期望熵的降低（用信息增益度量期望熵的降低（1 1）一个属性的一个属性的信息增益信息增益就是由于使用这个属性分割样例而导就是由于使用这个属性分割样例而导致的期望致的期望熵熵降低（纯度的增加）。一个属性降低（纯度的增加）。一个属性A A相对样例集合相对样例集合S S的的信息增益信息增益Gain(S,A)Gain(S,A)被定义为被定义为:其中，其中，Values(A)Values(A)是属性是属性A A所有可能值的集合，所有可能值的集合，S Sv v是是S S中属性中属性A A的值为的值为v v的的子集子集(即，即，S Sv v=s s S|A(sS|A(s)=)=v)v)GainGain(S,A)(S,A)是由于给定属性是由于给定属性A A的值而得到的关于目标函数值的值而得到的关于目标函数值的信息。当对的信息。当对S S的一个任意成员的目标值编码时，的一个任意成员的目标值编码时，Gain(SGain(S,A),A)的的值是在知道属性值是在知道属性A A的值后可以节省的二进制位数。的值后可以节省的二进制位数。2024/5/6 周一173.43.4基本的决策树学习算法基本的决策树学习算法 3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（8 8）例：例：假定假定S S是一套有关天气的训练样例，描述它的属性为可具有是一套有关天气的训练样例，描述它的属性为可具有WeakWeak和和StrongStrong两个值的两个值的WindWind。假定假定S S包含包含1414个样例（个样例（9 9十，十，5 5一）。一）。在这在这1414个样例中，假定正例中的个样例中，假定正例中的6 6个和反例中的个和反例中的2 2个有个有Wind=WeakWind=Weak，其他的有，其他的有Wind=StrongWind=Strong。2024/5/6 周一18Day Outlook Temperature Humidity Wind PlayTennisD1 Sunny Hot High Weak NoD2 Sunny Hot High Strong NoD3 Overcast Hot High Weak YesD4 Rain Mild High Weak YesDS Rain Cool Normal Weak YesD6 Rain Cool Normal Strong NoD7 Overcast Cool Normal Strong YesD8 Sunny Mild High Weak NoD9 Sunny Cool Normal Weak YesD10 Rain Mild Normal Weak YesD11 Sunny Mild Normal Strong YesD12 Overcast Mild High Strong YesD13 Overcast Hot Normal Weak YesD14 Rain Mild High Strong No表表3-23-2目标概念目标概念PlayTennisPlayTennis的训练样例的训练样例2024/5/6 周一193.43.4基本的决策树学习算法基本的决策树学习算法 3.4.13.4.1哪个属性是最佳的分类属性（哪个属性是最佳的分类属性（9 9）按照属性按照属性Wind分类分类14个样例得到的信息增益可以计算如下：个样例得到的信息增益可以计算如下：2024/5/6 周一203.43.4基本的决策树学习算法基本的决策树学习算法 3.4.13.4.1哪个属性是最佳的分类属性哪个属性是最佳的分类属性（1010）信息增益正是信息增益正是ID3ID3增长树的每一步中选取最佳属性的度量标准增长树的每一步中选取最佳属性的度量标准 前面的例子中，哪一个属性是最佳的分类属性前面的例子中，哪一个属性是最佳的分类属性?计算属性的信息增益计算属性的信息增益2024/5/6 周一213.43.4基本的决策树学习算法基本的决策树学习算法3.4.23.4.2举例（举例（1 1）为了演示为了演示ID3ID3算法的具体操作，考虑表算法的具体操作，考虑表3-23-2的训练数据所代的训练数据所代表的学习任务。所有四个属性的信息增益为表的学习任务。所有四个属性的信息增益为:Gain(S Gain(S，Outlook)=0.246Outlook)=0.246 Gain(S Gain(S，Humidity)=0.151Humidity)=0.151 Gain(S Gain(S，Wind)=0.048Wind)=0.048 Gain(S Gain(S，Temperature)=0.029Temperature)=0.029其中，其中，S S表示来自表表示来自表3-23-2的训练样例的集合。的训练样例的集合。2024/5/6 周一223.43.4基本的决策树学习算法基本的决策树学习算法3.4.23.4.2举例（举例（3 3）哪一个属性应在这里被测试哪一个属性应在这里被测试?Ssunny=D1,D2,D8,D9,D11 Gain(Ssunny,Humidity)=.970一一(3/5)0.0一一(2/5)0.0=970 Gain(Ssunny Temperature)=.970一一(2/5)0.0一一(2/5)1.0一一(1/5)0.0=.570 Gain(Ssunny,Wind)=.970一一(2/5)1.0一一(3/5).918=.019ID3ID3算法第一步后形成的部分决策树算法第一步后形成的部分决策树2024/5/6 周一233.53.5决策树学习中的假设空间搜索决策树学习中的假设空间搜索(1)(1)n与其他的归纳学习算法一样，与其他的归纳学习算法一样，决策树学习过程也是一个启发决策树学习过程也是一个启发式搜索过程式搜索过程，算法，算法ID3ID3可以被描述为可以被描述为从一个假设空间中搜索从一个假设空间中搜索一个拟合训练样例的假设一个拟合训练样例的假设。n被被ID3ID3算法搜索的假设空间就是算法搜索的假设空间就是可能的决策树的集合。可能的决策树的集合。nID3ID3算法以一种从算法以一种从简单到复杂的无回溯爬山算法简单到复杂的无回溯爬山算法遍历这个假遍历这个假设空间：设空间：从空树开始，然后逐步考虑更加复杂的假设，从空树开始，然后逐步考虑更加复杂的假设，目的是搜目的是搜索到一个正确分类训练数据的决策树。索到一个正确分类训练数据的决策树。引导这种爬山搜索的引导这种爬山搜索的评估函数（启发函数）是评估函数（启发函数）是信息增益度量信息增益度量。2024/5/6 周一243.53.5决策树学习中的假设空间搜索决策树学习中的假设空间搜索(2)(2)被被ID3ID3算法搜索的假设空间就是可能的决策树的集合。算法搜索的假设空间就是可能的决策树的集合。ID3搜索的假设空间2024/5/6 周一253.53.5决策树学习中的假设空间搜索决策树学习中的假设空间搜索(3)(3)ID3ID3算法的算法的优势和不足优势和不足:n当遍历决策树空间时，当遍历决策树空间时，ID3ID3仅维护单一的当前假设（与候仅维护单一的当前假设（与候选消除不同）。选消除不同）。例如，它不能判断有多少个其他的决策树例如，它不能判断有多少个其他的决策树也是与现有的训练数据一致的，或者使用新的实例查询来也是与现有的训练数据一致的，或者使用新的实例查询来最优地区分这些竞争假设。最优地区分这些竞争假设。n基本的基本的ID3ID3算法在搜索中不进行回溯。每当在树的某一层算法在搜索中不进行回溯。每当在树的某一层次选择了一个属性进行测试，它不会再回溯重新考虑这个次选择了一个属性进行测试，它不会再回溯重新考虑这个选择。所以，它易受无回溯的爬山搜索中的常见风险影响选择。所以，它易受无回溯的爬山搜索中的常见风险影响:收敛到局部最优的答案，而不是全局最优的。收敛到局部最优的答案，而不是全局最优的。2024/5/6 周一263.53.5决策树学习中的假设空间搜索决策树学习中的假设空间搜索(4)(4)nID3ID3算法中的算法中的假设空间包含所有的决策树（决策树能表假设空间包含所有的决策树（决策树能表示全部假设）示全部假设），它是关于现有属性的有限离散值函数，它是关于现有属性的有限离散值函数的一个的一个完整空间完整空间。ID3ID3算法算法避免避免了搜索不完整假设空间了搜索不完整假设空间的一个主要风险的一个主要风险:假设空间可能不包含目标函数。假设空间可能不包含目标函数。nID3ID3算法在搜索的每一步都使用当前的算法在搜索的每一步都使用当前的所有训练样例所有训练样例，以统计为基础决定怎样精化当前的假设。使用所有样以统计为基础决定怎样精化当前的假设。使用所有样例的统计属性例的统计属性(例如，信息增益例如，信息增益)的一个的一个优点优点是大大降是大大降低了对个别训练样例错误的敏感性。低了对个别训练样例错误的敏感性。n通过修改通过修改ID3ID3算法的终止准则以算法的终止准则以接受接受不完全拟合训练数不完全拟合训练数据的假设，它还可以被很容易地扩展到处理含有噪声据的假设，它还可以被很容易地扩展到处理含有噪声的训练数据。的训练数据。2024/5/6 周一273.63.6决策树学习的归纳偏置决策树学习的归纳偏置(1)(1)ID3ID3的搜索策略为的搜索策略为:(a)(a)优先选择优先选择较短较短的树而不是较长的的树而不是较长的;(b)(b)选择选择那些信息增益高的属性离根结点较近的树。（提高分那些信息增益高的属性离根结点较近的树。（提高分类效率）类效率）ID3ID3算法使用贪婪的启发式搜索策略，具有近似的算法使用贪婪的启发式搜索策略，具有近似的“较短的树较短的树比较长的树优先比较长的树优先”归纳偏置归纳偏置 。ID3ID3归纳偏置的更归纳偏置的更贴切贴切近似近似:较短的树比较长的树优先较短的树比较长的树优先。那些。那些信息增益高的属性更靠近根结点的树优先信息增益高的属性更靠近根结点的树优先。2024/5/6 周一283.63.6决策树学习的归纳偏置决策树学习的归纳偏置(2)(2)3.6.13.6.1限定偏置和优选偏置限定偏置和优选偏置nID3ID3的搜索范围的搜索范围是一个完整的假设空间是一个完整的假设空间(例如，能表示任何有例如，能表示任何有限的离散值函数的空间限的离散值函数的空间)。但它不彻底地搜索这个空间，从简。但它不彻底地搜索这个空间，从简单的假设到复杂的假设，直到遇到终止条件，单的假设到复杂的假设，直到遇到终止条件，它的归纳偏置它的归纳偏置完全是搜索策略排序假设的结果。它的假设空间没有引入额完全是搜索策略排序假设的结果。它的假设空间没有引入额外的偏置。外的偏置。n 变型空间候选消除算法的搜索范围变型空间候选消除算法的搜索范围是不完整的假设空间是不完整的假设空间(即即一个仅能表示潜在可教授概念子集的空间，如：所有属性值一个仅能表示潜在可教授概念子集的空间，如：所有属性值个合取个合取)，但它彻底地搜索这个空间，查找，但它彻底地搜索这个空间，查找所有所有与训练数据一与训练数据一致的假设。致的假设。它的归纳偏置完全是假设表示的表达能力的结果。它的归纳偏置完全是假设表示的表达能力的结果。它的搜索策略并没有引入额外的偏置。它的搜索策略并没有引入额外的偏置。n简单地讲，简单地讲，ID3ID3的归纳偏置的归纳偏置来自它的搜索策略，而来自它的搜索策略，而候选消除候选消除算法的归纳偏置算法的归纳偏置来自它对搜索空间的定义。来自它对搜索空间的定义。2024/5/6 周一293.63.6决策树学习的归纳偏置决策树学习的归纳偏置(2)(2)3.6.13.6.1限定偏置和优选偏置限定偏置和优选偏置nID3ID3的归纳偏置的归纳偏置是对某种假设是对某种假设(例如，对于较短的假设例如，对于较短的假设)胜胜过其他假设的一种优选过其他假设的一种优选(preference)(preference)，它对最终可列举的，它对最终可列举的假设没有硬性限制。这种类型的偏置通常被称为假设没有硬性限制。这种类型的偏置通常被称为优选偏置优选偏置或叫或叫搜索偏置搜索偏置(search bias)(search bias)。n候选消除算法的偏置候选消除算法的偏置是对待考虑假设的一种限定是对待考虑假设的一种限定(restriction(restriction）。这种形式的偏置通常被称为）。这种形式的偏置通常被称为限定偏置限定偏置(或者叫或者叫语言偏置语言偏置(language bias(language bias）。2024/5/6 周一303.63.6决策树学习的归纳偏置决策树学习的归纳偏置(2)(2)3.6.13.6.1限定偏置和优选偏置限定偏置和优选偏置 应该优先考虑应该优先考虑哪种形式的归纳偏置哪种形式的归纳偏置:优选偏置还是限优选偏置还是限定偏置定偏置?n通常，通常，优选偏置比限定偏置更符合需要优选偏置比限定偏置更符合需要，因为它允许学，因为它允许学习器工作在完整的假设空间上，这习器工作在完整的假设空间上，这保证保证了未知的目标函了未知的目标函被包含在内。被包含在内。n相反，限定偏置严格地相反，限定偏置严格地限制限制了假设集合的潜在空间，通了假设集合的潜在空间，通常不是我们希望的，因为它同时常不是我们希望的，因为它同时引入引入了把未知的目标函了把未知的目标函数排除在外的可能性。数排除在外的可能性。nID3ID3采用纯粹的优选偏置，而候选消除算法采用纯粹的采用纯粹的优选偏置，而候选消除算法采用纯粹的限定偏置，一些学习系统限定偏置，一些学习系统综合综合了这两者了这两者。2024/5/6 周一313.63.6决策树学习的归纳偏置决策树学习的归纳偏置(2)(2)3.6.23.6.2为什么短的假设优先为什么短的假设优先奥坎姆剃刀奥坎姆剃刀:优先选择拟合数据的最简单的假设。优先选择拟合数据的最简单的假设。一种解释一种解释是短假设的数量少于长假设的数量是短假设的数量少于长假设的数量(基于简单基于简单的参数组合的参数组合)，所以找到一个短的但同时与训练数据拟合的，所以找到一个短的但同时与训练数据拟合的假设的可能性较小。相反，常常有很多非常复杂的假设拟合假设的可能性较小。相反，常常有很多非常复杂的假设拟合当前的训练数据，但却无法正确地泛化到后来的数据（过度当前的训练数据，但却无法正确地泛化到后来的数据（过度拟合）。拟合）。例如考虑决策树假设例如考虑决策树假设。500500个结点的决策树比个结点的决策树比5 5个结点的个结点的决策树多得多。如果给定一个决策树多得多。如果给定一个2020个训练样例的集合，可以预个训练样例的集合，可以预期能够找到很多期能够找到很多500500个结点的决策树与训练数据一致，而如个结点的决策树与训练数据一致，而如果一个果一个5 5个结点的决策树可以完美地拟合这些数据则是出乎个结点的决策树可以完美地拟合这些数据则是出乎意料的。所以我们会相信意料的。所以我们会相信5 5个结点的树不太可能是统计巧合，个结点的树不太可能是统计巧合，因而优先选择这个假设，而不选择因而优先选择这个假设，而不选择500500个结点的。个结点的。2024/5/6 周一323.73.7决策树学习的常见问题决策树学习的常见问题 决策树学习的决策树学习的实际（进一步）问题实际（进一步）问题包括包括:确定决策树增长的确定决策树增长的深度深度;处理处理连续值连续值的属性的属性;选择一个适当的属性筛选度量选择一个适当的属性筛选度量标准标准;处理属性值处理属性值不完整不完整的训练数据的训练数据;处理处理不同代价不同代价的属性，提高计算效率。的属性，提高计算效率。2024/5/6 周一333.73.7决策树学习的常见问题决策树学习的常见问题3.7.13.7.1避免过度拟合数据避免过度拟合数据过度拟合：过度拟合：定义定义:给定一个假设空间给定一个假设空间H H，一个假设，一个假设h h H H，如果存在其，如果存在其他的假设他的假设h h H H，使得在训练样例上，使得在训练样例上h h的错误率比的错误率比h h小，小，但在整个实例分布上但在整个实例分布上h h的错误率比的错误率比h h小，那么就说假设小，那么就说假设h h过度拟合过度拟合(overfitoverfit)训练数据。训练数据。2024/5/6 周一34决策树学习中的过度拟合决策树学习中的过度拟合3.73.7决策树学习的常见问题决策树学习的常见问题3.7.13.7.1避免过度拟合数据避免过度拟合数据2024/5/6 周一35训练样例中的训练样例中的随机噪声随机噪声会导致过度拟合会导致过度拟合。训练样例中的随。训练样例中的随机噪声导致树机噪声导致树h h比树比树h h更好地拟合训练样例，但对于后来的更好地拟合训练样例，但对于后来的实例实例h h却表现更差。却表现更差。当训练数据当训练数据没有噪声没有噪声时，时，过度拟合也有可能发生过度拟合也有可能发生，特别是，特别是当少量的样例被关联到叶子结点时。这种情况下，很可能出当少量的样例被关联到叶子结点时。这种情况下，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。一旦这样巧合的规律性存但却与实际的目标函数并无关系。一旦这样巧合的规律性存在，就有过度拟合的风险。（训练样例的分布与实例的实际在，就有过度拟合的风险。（训练样例的分布与实例的实际分布不一致时）分布不一致时）导致过度拟合的原因导致过度拟合的原因2024/5/6 周一36决策树学习的常见问题的解决决策树学习的常见问题的解决 有几种途径可被用来有几种途径可被用来避免决策树学习中的过度拟合避免决策树学习中的过度拟合。它们可被分为两类它们可被分为两类:n及早停止树增长及早停止树增长，在，在ID3ID3算法完美分类训练数据之前就停算法完美分类训练数据之前就停止树增长止树增长;n后修剪法后修剪法(post-prune(post-prune），即允许树过度拟合数据，然后），即允许树过度拟合数据，然后对这个树进行后修剪。对这个树进行后修剪。2024/5/6 周一37n“错误率降低修剪方法错误率降低修剪方法”是考虑将树上的每一个结点作为修是考虑将树上的每一个结点作为修剪的候选对象。按以下剪的候选对象。按以下步骤步骤修剪一个结点修剪一个结点:1 1）当修剪后的树对于验证集合的性能不比原来的树差时才）当修剪后的树对于验证集合的性能不比原来的树差时才删删除除以某结点为根的子树以某结点为根的子树;使它成为叶子结点使它成为叶子结点;把和该结点关联的把和该结点关联的训练样例的训练样例的最常见分类赋给它最常见分类赋给它。这样便使因为训练集合的巧合。这样便使因为训练集合的巧合规律性而加入的结点很可能被删除，因为同样的巧合不大会发规律性而加入的结点很可能被删除，因为同样的巧合不大会发生在验证集合中。生在验证集合中。2 2）反复地修剪结点）反复地修剪结点，每次总是选取那些删除后可以最大提高，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的结点。继续修剪结点决策树在验证集合上的精度的结点。继续修剪结点直到直到进一步进一步的修剪是有害的为止的修剪是有害的为止(也就是降低了在验证集合上的精度也就是降低了在验证集合上的精度)n以上方法涉及到假设的评估问题。以上方法涉及到假设的评估问题。1.1.错误率降低修剪错误率降低修剪2024/5/6 周一381.1.错误率降低修剪错误率降低修剪2024/5/6 周一39规则后修剪规则后修剪包括下面的步骤包括下面的步骤:1)1)从训练集合从训练集合推导出决策树推导出决策树，增长决策树直到尽可能好地，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生。拟合训练数据，允许过度拟合发生。2)2)将决策树将决策树转化转化为等价的规则集合，方法是为从根结点到为等价的规则集合，方法是为从根结点到叶子结点的每一条路径创建一条规则。叶子结点的每一条路径创建一条规则。3)3)通过通过删除删除任何能导致估计精度提高的任何能导致估计精度提高的前件前件来修剪来修剪(泛化泛化)每一条规则。（比较规则每一条规则。（比较规则IF AIF A B THEN C B THEN C 与规则与规则IF A IF A THEN CTHEN C的泛化性）的泛化性）4)4)按照修剪过的规则的估计精度对它们进行按照修剪过的规则的估计精度对它们进行排序排序，并按这，并按这样的顺序应用这些规则来分类后来的实例。样的顺序应用这些规则来分类后来的实例。2.2.规则后修剪规则后修剪2024/5/6 周一40 修剪之前要把决策树转化成规则集有修剪之前要把决策树转化成规则集有三个好处三个好处:转化为规则集可以区分决策结点使用的不同上下文。转化为规则集可以区分决策结点使用的不同上下文。因为因为贯贯穿决策结点的每条不同路径产生一条不同的规则，所以穿决策结点的每条不同路径产生一条不同的规则，所以对于不对于不同路径同路径，关于一个属性测试的修剪决策可以不同（在一条路径，关于一个属性测试的修剪决策可以不同（在一条路径上可以删除上可以删除A A属性，而在另一条路径上可能删除属性，而在另一条路径上可能删除B B属性）。相反，属性）。相反，如果直接修剪树本身，只有两个选择，要么完全删除决策结点，如果直接修剪树本身，只有两个选择，要么完全删除决策结点，要么保留它的本来状态。要么保留它的本来状态。转化为规则集转化为规则集消除消除了根结点附近的属性测试和叶结点附近的了根结点附近的属性测试和叶结点附近的属性测试的区别。于是避免了零乱的记录问题，比如，若是根属性测试的区别。于是避免了零乱的记录问题，比如，若是根结点被修剪了但保留它下面的部分子树时如何重新组织这棵树。结点被修剪了但保留它下面的部分子树时如何重新组织这棵树。转化为规则以提高可读性。对人来说，规则总是更转化为规则以提高可读性。对人来说，规则总是更容易理解容易理解。2.2.规则后修剪规则后修剪2024/5/6 周一413.73.7决策树学习的常见问题决策树学习的常见问题 3.7.2 3.7.2 合并连续值属性合并连续值属性二、合并连续值属性二、合并连续值属性 要把连续值的决策属性加入到决策树中，可以通过连续要把连续值的决策属性加入到决策树中，可以通过连续实行的离散化，即动态地实行的离散化，即动态地定义新的离散值属性定义新的离散值属性来实现，即先来实现，即先把连续值属性的值域分割为离散的区间集合。