1、上节课程内容回顾上节课程内容回顾n什么是机器学习？什么是机器学习？n机器学习的产生与发展机器学习的产生与发展n贝叶斯定理贝叶斯定理n贝叶斯分类算法贝叶斯分类算法上节课程内容回顾上节课程内容回顾明天太阳明天太阳会升起吗会升起吗? ?他在一个袋子放他在一个袋子放了黑白各一个颗弹子。了黑白各一个颗弹子。（太阳升起的概率？）（太阳升起的概率？）第一天第一天第二天第二天太阳升起了，太阳升起了，他加了一个白弹子在袋子里。他加了一个白弹子在袋子里。（太阳升起的概率？）（太阳升起的概率？）第三天第三天太阳升起了，太阳升起了，他又加了一个白弹子在袋子里。他又加了一个白弹子在袋子里。（太阳升起的概率？）（太阳升起
2、的概率？）。结论结论几乎可以肯定，几乎可以肯定，太阳总会升起。太阳总会升起。主要内容主要内容4.6.5 4.6.5 决策树的假设空间搜索决策树的假设空间搜索4.6.4 4.6.4 最佳分类属性判定最佳分类属性判定4.6.3 4.6.3 决策树的基本算法决策树的基本算法4.6.2 4.6.2 决策树学习的适用问题决策树学习的适用问题4.6.1 4.6.1 决策树的概念决策树的概念4.6.8 4.6.8 决策树算法的决策树算法的PROLOGPROLOG实现实现4.6.7 4.6.7 决策树的优缺点决策树的优缺点4.6.6 4.6.6 决策树的常见问题决策树的常见问题什么是决策树什么是决策树? n从
3、管理学的角度定义决策树是指使用系统分析决策树是指使用系统分析方法，把各种决策方案及方法，把各种决策方案及出现结果的可能性进行分出现结果的可能性进行分组排列，然后确定最佳方组排列，然后确定最佳方案的决策过程。案的决策过程。 4.6.1 什么是决策树？举例举例:渔民投资渔民投资决策点决策点新船新船旧船旧船好鱼情好鱼情(0.7)坏鱼情坏鱼情(0.3)好鱼情好鱼情(0.7)坏鱼情坏鱼情(0.3)$90000-$10000$80000$200004.6.1 什么是决策树？什么是决策树什么是决策树? n从机器学习的角度定义决策树是运用于分类决策树是运用于分类的一种树结构。的一种树结构。 4.6.1 什么是
4、决策树？决策树的表示方法决策树的表示方法n每个内部节点（每个内部节点（internal node）代表对某）代表对某个属性的一次测试。个属性的一次测试。n一条边代表一个测试结果。一条边代表一个测试结果。n叶子（叶子（leaf）代表某个类（）代表某个类（class）或者类）或者类的分布（的分布（class distribution）。）。n最上面的节点是根结点。最上面的节点是根结点。 4.6.1 什么是决策树？举例举例n假设用一个决策树表示一个关心电子产品假设用一个决策树表示一个关心电子产品的用户是否会购买的用户是否会购买PC的知识，然后用它来的知识，然后用它来预测某条记录（某个人）的购买意向。
5、预测某条记录（某个人）的购买意向。4.6.1 什么是决策树？举例举例年龄年龄? ?学生学生? ?信用状况信用状况? ?否否是是是是是是否否40否否 是是很好很好一般一般4.6.1 什么是决策树？举例举例n类别：类别：buys_computers=yesbuys_computers=yes和和buys_computers=nobuys_computers=no）。）。n样本向量为（样本向量为（age, student, credit_rating; age, student, credit_rating; buys_computersbuys_computers）n被决策数据的格式为（被决策数据
6、的格式为（age, student, age, student, credit_ratingcredit_rating）n输入新的被决策的记录，可以预测该记录隶属于输入新的被决策的记录，可以预测该记录隶属于哪个类。哪个类。4.6.1 什么是决策树？决策树分类过程决策树分类过程n决策树通过把实例从根结点排列（决策树通过把实例从根结点排列（sort）到某个叶子结点来分类实例，叶子结点即到某个叶子结点来分类实例，叶子结点即为实例所属的分类。为实例所属的分类。n树上的每一个结点指定了对实例的某个属树上的每一个结点指定了对实例的某个属性（性（attribute）的测试，并且该结点的每）的测试，并且该结点
7、的每一个后继分支对应于该属性的一个可能值。一个后继分支对应于该属性的一个可能值。4.6.1 什么是决策树？决策树分类过程（续）决策树分类过程（续）n分类实例的方法是从这棵树的根结点开始，分类实例的方法是从这棵树的根结点开始，测试这个结点指定的属性，然后按照给定测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。这实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。个过程再在以新结点为根的子树上重复。4.6.1 什么是决策树？问题：实例怎么表达？问题：实例怎么表达？决策树与规则表达的转换决策树与规则表达的转换通常决策树代表实例属性值约束的合取通常决策树代表实
8、例属性值约束的合取（conjunction）的析取式（）的析取式（disjunction）。）。从树根到树叶的每一条路径对应一组属性测从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。试的合取，树本身对应这些合取的析取。(Buys_computer=age=30 Student) (Buys_computer=age40 Credit_rating=excellent)(Buys_computer=age40 Credit_rating=excellent)4.6.1 什么是决策树？决策树学习的适用问题决策树学习的适用问题n实例由“属性-值”对（pair）表示 -实例是
9、用一系列固定的属性和它们的值来实例是用一系列固定的属性和它们的值来描述的。描述的。 -最简单的决策树学习中，每一个属性取少最简单的决策树学习中，每一个属性取少数的分离的值。数的分离的值。 -扩展的算法允许处理扩展的算法允许处理值域为实数值域为实数的属性的属性（例如，数字表示的温度）。（例如，数字表示的温度）。4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n目标函数具有离散的输出值 -上面举例的决策树给每个实例赋予一个布上面举例的决策树给每个实例赋予一个布尔型的分类（例如，尔型的分类（例如，yes或或no）。）。 -决策树方法很容易扩展到学习有两个以上决策树方法很容易扩
10、展到学习有两个以上输出值的函数。输出值的函数。 -一种更强有力的扩展算法允许学习具有实一种更强有力的扩展算法允许学习具有实数值输出的函数，尽管决策树在这种情况下数值输出的函数，尽管决策树在这种情况下的应用不太常见。的应用不太常见。4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n可能需要析取的描述 -决策树很自然地代表了析取表达式。决策树很自然地代表了析取表达式。 4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n训练数据可以包含缺少属性值的实例 -决策树学习对错误有很好的决策树学习对错误有很好的鲁棒性鲁棒性，无论，无论是训练样例所属的分类错误还
11、是描述这些样是训练样例所属的分类错误还是描述这些样例的属性值错误。例的属性值错误。 4.6.2 决策树学习的适用问题已经发现有很多实际的问题符合这些特征，所以决策树学习已经被应用到很多问题中。例如：根据拖欠支付的可能性分类贷款申请；根据起因分类设备故障。它们的核心任务就是它们的核心任务就是要把样例分类到各可能的离散值对应的类别中。要把样例分类到各可能的离散值对应的类别中。已有的决策树学习算法已有的决策树学习算法4.6.3 基本的决策树学习算法大多数已开发的大多数已开发的决策树学习算法都是决策树学习算法都是一种核心算法的变体。一种核心算法的变体。ID3(QUINLAN 1986)ID3(QUIN
12、LAN 1986)及其后继的及其后继的C4.5C4.5ID34.6.3 基本的决策树学习算法基本的基本的ID3ID3算法通过自顶向下构造决策算法通过自顶向下构造决策树来进行学习。树来进行学习。ID3算法的构造过程算法的构造过程（问题：哪一个属性将在树的根结点被测试？问题：哪一个属性将在树的根结点被测试？）4.6.3 基本的决策树学习算法使用统计测试来确定每一个实例属性单独分类训练样例的能力，使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根结点的测试。分类能力最好的属性被选作树的根结点的测试。 为根结点属性的每个可能值产生一个分支，并把训练样例排列到为根结点
13、属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是，样例的该属性值对应的分支）之下。适当的分支（也就是，样例的该属性值对应的分支）之下。 重复整个过程，用每个分支结点关联的训练样例来选取在该点被重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。测试的最佳属性。 专用于学习布尔函数的专用于学习布尔函数的ID3算法算法4.6.3 基本的决策树学习算法ID3ID3是一种是一种自顶向下增长树自顶向下增长树的贪婪的贪婪(greedy)(greedy)算法，算法，在每个结点选取能最好地分类样例的属性。在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树继续这个
14、过程直到这棵树能完美分类训练样例，能完美分类训练样例，或者所有的属性都使用过了。或者所有的属性都使用过了。 见复印资料。专用于学习布尔函数的专用于学习布尔函数的ID3算法算法4.6.3 基本的决策树学习算法什么是衡量属性价值的定量标准什么是衡量属性价值的定量标准？信息熵信息熵4.6.4 哪个属性是最佳的分类属性？n信息论中广泛使用的一个度量标准信息论中广泛使用的一个度量标准（Claude Elwood Shannon），称为熵），称为熵（entropy），它刻画了任意样例集的纯度），它刻画了任意样例集的纯度（purity）。）。 信息熵信息熵4.6.4 哪个属性是最佳的分类属性？n给定包含关于
15、某个目标概念的正反样例的给定包含关于某个目标概念的正反样例的样例集样例集S，那么，那么S相对这个布尔型分类的熵为：相对这个布尔型分类的熵为： Entropy(S) -p log2p -plog2p 其中，其中，p 是在是在S中正例的比例，中正例的比例，p是在是在S中负例的比例。在有关熵的所有计算中我们中负例的比例。在有关熵的所有计算中我们定义定义0log0为为0。 举例举例4.6.4 哪个属性是最佳的分类属性？n假设假设S是一个关于某布尔概念的有是一个关于某布尔概念的有14个样例个样例的集合，它包括的集合，它包括9个正例和个正例和5个反例（用记号个反例（用记号9+，5-来表示）。那么来表示）。
16、那么S相对于这个布尔分相对于这个布尔分类的熵（类的熵（Entropy）为：）为：94. 0)14/5(log)14/5( )14/9(log)14/9()5 ,9(22Entropy注意注意4.6.4 哪个属性是最佳的分类属性？n如果如果S的所有成员属于同一类，那么的所有成员属于同一类，那么S的熵的熵为为0。例如，如果所有的成员是正的。例如，如果所有的成员是正的（p =1），那么），那么p就是就是0，那么，那么 Entropy(S) = 0。注意注意4.6.4 哪个属性是最佳的分类属性？n当集合中正反样例的数量相等时熵为当集合中正反样例的数量相等时熵为1。如。如果集合中正反例的数量不等时，熵介
17、于果集合中正反例的数量不等时，熵介于0和和1之间。之间。 1.00,00.50.51.0某布尔分类的熵函数P随着从0到1变化的曲线信息论中熵的解释信息论中熵的解释4.6.4 哪个属性是最佳的分类属性？n熵确定了集合熵确定了集合S中任意成员（即以均匀的概中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最率随机抽出的一个成员）的分类所需要的最少二进制位数。少二进制位数。信息论中熵的解释信息论中熵的解释4.6.4 哪个属性是最佳的分类属性？n如果如果P 是是1，接收者知道抽出的样例必为，接收者知道抽出的样例必为正，所以不必发任何消息，此时的熵为正，所以不必发任何消息，此时的熵为0。n如果
18、是如果是P 0.5，必须用一个二进制位来说，必须用一个二进制位来说明抽出的样例是正还是负。明抽出的样例是正还是负。n如果是如果是P 0.8，那么对所需的消息编码方，那么对所需的消息编码方法是赋给正例集合较短的编码，可能性较小法是赋给正例集合较短的编码，可能性较小的反例集合较长的编码，平均每条消息的编的反例集合较长的编码，平均每条消息的编码少于码少于1个二进制位。个二进制位。 通用信息熵的定义通用信息熵的定义4.6.4 哪个属性是最佳的分类属性？n如果目标属性具有如果目标属性具有c个不同的值，那么个不同的值，那么S相对于相对于c个状态（个状态（c-wise）的分类的熵定义为：）的分类的熵定义为：
19、 ciiippSEntropy12log)(通用信息熵的定义通用信息熵的定义4.6.4 哪个属性是最佳的分类属性？为什么对数的底数是为什么对数的底数是2?熵的最大可能值是多少熵的最大可能值是多少?信息增益信息增益(Information Gain)4.6.4 哪个属性是最佳的分类属性？n一个属性的信息增益就是由于使用这个一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。属性分割样例而导致的期望熵降低。信息增益信息增益(Information Gain)4.6.4 哪个属性是最佳的分类属性？n一个属性一个属性A相对样例集合相对样例集合S的信息增益的信息增益Gain(S,A)被定义
20、为被定义为:)(|)(),()(AValuesvvvSEntropySSSEntropyASGain)(AValuesv信息增益信息增益(Information Gain)4.6.4 哪个属性是最佳的分类属性？nGain(S,A)是由于给定属性是由于给定属性A的值而得到的值而得到的关于目标函数值的信息。当对的关于目标函数值的信息。当对S的一个的一个任意成员的目标值编码时，任意成员的目标值编码时，Gain(S,A)的的值是在知道属性值是在知道属性A的值后可以节省的二进的值后可以节省的二进制位数。制位数。 举例举例4.6.4 哪个属性是最佳的分类属性？n例如，假定例如，假定S是一套有关天气的训练样
21、例，是一套有关天气的训练样例，描述它的属性包括可能是具有描述它的属性包括可能是具有Weak和和Strong两个值的两个值的Wind。假定。假定S包含包含14个样个样例，例，9+，5-。在这。在这14个样例中，假定正例个样例中，假定正例中的中的6个和反例中的个和反例中的2个有个有Wind =Weak，其其他的有他的有Wind=Strong。由于按照属性。由于按照属性Wind分类分类14个样例得到的信息增益可以计算如下。个样例得到的信息增益可以计算如下。举例举例4.6.4 哪个属性是最佳的分类属性？3 ,32 ,6,5-9StrongWeakSSSgWeak,Strond)Values(Win举例
22、举例4.6.4 哪个属性是最佳的分类属性？048. 000. 1 )14/6(811. 0)14/8(940. 0)()14/6()()14/8()()(|)(),(,StrongWeakStrongWeakvvvSEntropySEntropySEntropySEntropySSSEntropyWindSGain信息增益与信息增益与ID34.6.4 哪个属性是最佳的分类属性？n信息增益正是信息增益正是ID3算法增长树的每一步中选算法增长树的每一步中选取最佳属性的度量标准。取最佳属性的度量标准。 举例举例4.6.4 哪个属性是最佳的分类属性？ 见复印材料。见复印材料。课堂练习课堂练习: 画出该
23、示例的决策树。画出该示例的决策树。OutlookOutlook? ? ?yesSunnyOvercastRain?举例举例4.6.4 哪个属性是最佳的分类属性？D1,D2,D3.,D149+,5-D1,D2,D8,D9,D112+,3-D3,D7,D12,D134+,0-D4,D5,D6,D10,D143+,2-举例举例4.6.4 哪个属性是最佳的分类属性？Ssunny=D1,D2,D8,D9,D11Gain(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 -
24、(1/5)0.0=0.57Gain(Ssunny,Wind)=0.97-(2/5)1.0-(3/5)0.918=0.19决策树学习中的假设空间搜索4.6.5 决策树学习中的假设空间搜索nID3算法可以被描述为从一个假设空间中搜算法可以被描述为从一个假设空间中搜索一个拟合训练样例的假设。被索一个拟合训练样例的假设。被ID3算法搜算法搜索的假设空间就是可能的决策树的集合。索的假设空间就是可能的决策树的集合。nID3算法以一种从简单到复杂的爬山算法遍算法以一种从简单到复杂的爬山算法遍历这个假设空间，从空的树开始，然后逐步历这个假设空间，从空的树开始，然后逐步考虑更加复杂的假设，目的是搜索到一个正考虑
25、更加复杂的假设，目的是搜索到一个正确分类训练数据的决策树。确分类训练数据的决策树。n引导这种爬山搜索的评估函数是信息增益引导这种爬山搜索的评估函数是信息增益度量。度量。 决策树学习中的误区决策树学习中的误区4.6.5 决策树学习中的假设空间搜索n树的深度应尽量小。但贪婪搜索可能无法树的深度应尽量小。但贪婪搜索可能无法找到最小树，顶层结点可能不是高区分度的。找到最小树，顶层结点可能不是高区分度的。 计算复杂度计算复杂度4.6.5 决策树学习中的假设空间搜索n最坏情况是构造出一棵完全树，每条路径最坏情况是构造出一棵完全树，每条路径都测试了所有特征。都测试了所有特征。计算复杂度计算复杂度4.6.5
26、决策树学习中的假设空间搜索n各层各层i要对剩下的要对剩下的|A|-i个属性个属性计算最佳分割。计算最佳分割。n一般来说，性能与属性个数成线性关系。一般来说，性能与属性个数成线性关系。)(2) 1(2|1ADOAADDiAiD就是就是样本集样本集决策树学习的归纳偏置4.6.6 决策树学习的归纳偏置n归纳偏置是一系列前提，这些前提与训练归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例的分类。数据一起演绎论证未来实例的分类。决策树学习的归纳偏置4.6.6 决策树学习的归纳偏置n归纳偏置是一系列前提，这些前提与训练归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例的分类。数据一起
27、演绎论证未来实例的分类。决策树学习的归纳偏置4.6.6 决策树学习的归纳偏置n如果给定一个训练样例的集合，那么通常如果给定一个训练样例的集合，那么通常有很多决策树与这些样例一致。所以，要描有很多决策树与这些样例一致。所以，要描述述ID3算法的归纳偏置，应找到它从所有一算法的归纳偏置，应找到它从所有一致的假设中选择一个的根据。致的假设中选择一个的根据。 决策树学习的归纳偏置4.6.6 决策树学习的归纳偏置nID3从这些决策树中选择哪一个呢？它选择从这些决策树中选择哪一个呢？它选择在使用简单到复杂的爬山算法遍历可能的树在使用简单到复杂的爬山算法遍历可能的树空间时遇到的第一个可接受的树。空间时遇到的
28、第一个可接受的树。 ID3的搜索策略4.6.6 决策树学习的归纳偏置n优先选择较短的树而不是较长的。优先选择较短的树而不是较长的。n选择那些信息增益高的属性离根结点较近选择那些信息增益高的属性离根结点较近的树。的树。存在的问题4.6.6 决策树学习的归纳偏置n在在ID3中使用的选择属性的启发式规则和它中使用的选择属性的启发式规则和它遇到的特定训练样例之间存在着微妙的相互遇到的特定训练样例之间存在着微妙的相互作用。由于这一点，很难准确地刻划出作用。由于这一点，很难准确地刻划出ID3的归纳偏置。然而我们可以的归纳偏置。然而我们可以近似地把它的归纳偏置描述为一种对短的决策树的偏好。近似的ID3算法归
29、纳偏置 4.6.6 决策树学习的归纳偏置nBFS-ID3：较短的树比较长的优先宽度优先搜索？宽度优先搜索？深度优先搜索？深度优先搜索？近似的ID3算法归纳偏置 4.6.6 决策树学习的归纳偏置nBFS-ID3：原理/过程它从一个空的树开始广度优先（breadth first）搜索逐渐复杂的树，先考虑所有深度为1的树，然后所有深度为2的，。一旦它找到了一个与训练数据一致的决策树，它返回搜索深度的最小的一致树（例如，具有最少结点的树）。这种广度优先搜索称为BFS-ID3。BFS-ID3寻找最短的决策树，因此精确地具有“较短的树比较长的得到优先”的偏置。ID3可被看作BFS-ID3的一个有效近似，它
30、使用一种贪婪的启发式搜索企图发现最短的树，而不用进行完整的广度优先搜索来遍历假设空间。 近似的ID3算法归纳偏置 4.6.6 决策树学习的归纳偏置nID3归纳偏置的更贴切近似：较短的树比较较短的树比较长的得到优先。那些长的得到优先。那些信息增益高的属性更靠近的属性更靠近根结点的树得到优先。根结点的树得到优先。为什么为什么ID3中选择短的假设优先？中选择短的假设优先？4.6.6 决策树学习的归纳偏置nID3算法中优选较短决策树的归纳偏置，是算法中优选较短决策树的归纳偏置，是不是从训练数据中泛化的可靠基础？哲学家不是从训练数据中泛化的可靠基础？哲学家们以及其他学者已经对这样的问题争论几个们以及其他
31、学者已经对这样的问题争论几个世纪了，而且这个争论至今还未解决。世纪了，而且这个争论至今还未解决。n威廉威廉奥坎姆大约在奥坎姆大约在1320年提出类似的论点，年提出类似的论点，是最早讨论这个问题的人之一，所以这个偏是最早讨论这个问题的人之一，所以这个偏置经常被称为置经常被称为“奥坎姆剃刀奥坎姆剃刀”（Occams razor）。）。Occams razor4.6.6 决策树学习的归纳偏置n奥卡姆剃刀（奥卡姆剃刀（Occams Razor, Ockhams Razor）是由）是由14世纪逻辑学家、圣方济各会世纪逻辑学家、圣方济各会修士奥卡姆的威廉（修士奥卡姆的威廉（William of Occam
32、）提）提出的一个原理。出的一个原理。 Occams razor4.6.6 决策树学习的归纳偏置Entities should not be multiplied unnecessarily （“如无必要，勿增实如无必要，勿增实体体”。）。）Occams razor4.6.6 决策树学习的归纳偏置威廉使用这个原理证明了许多结论，包括威廉使用这个原理证明了许多结论，包括“通过思辨不能得出上帝存在的结论通过思辨不能得出上帝存在的结论”。这。这使他不受罗马教皇的欢迎。使他不受罗马教皇的欢迎。 Occams razor4.6.6 决策树学习的归纳偏置许多科学家接受或者（独立的）提出了奥卡许多科学家接受或
33、者（独立的）提出了奥卡姆剃刀原理，例如莱布尼兹的姆剃刀原理，例如莱布尼兹的“不可观测事不可观测事物的同一性原理物的同一性原理”和牛顿提出的一个原则：和牛顿提出的一个原则：如果某一原因既真又足以解释自然事物的特如果某一原因既真又足以解释自然事物的特性，则我们不应当接受比这更多的原因。性，则我们不应当接受比这更多的原因。 Occams razor4.6.6 决策树学习的归纳偏置对于科学家，这一原理最常见的形式是：对于科学家，这一原理最常见的形式是： 当当你有两个处于竞争地位的理论能得出同样的你有两个处于竞争地位的理论能得出同样的结论，那么简单的那个更好。结论，那么简单的那个更好。 Occams r
34、azor（奥卡姆剃刀的强形式）（奥卡姆剃刀的强形式）4.6.6 决策树学习的归纳偏置n如果你有两个原理，它们都能解释观测到如果你有两个原理，它们都能解释观测到的事实，那么你应该使用简单的那个，直到的事实，那么你应该使用简单的那个，直到发现更多的证据。发现更多的证据。n 对于现象最简单的解释往往比较复杂的解对于现象最简单的解释往往比较复杂的解释更正确。释更正确。Occams razor（奥卡姆剃刀的强形式）（奥卡姆剃刀的强形式）4.6.6 决策树学习的归纳偏置n如果你有两个类似的解决方案，选择最简如果你有两个类似的解决方案，选择最简单的。单的。n需要最少假设的解释最有可能是正确需要最少假设的解释
35、最有可能是正确的的n或者以这种自我肯定的形式出现：让事情或者以这种自我肯定的形式出现：让事情保持简单！保持简单！ Occams razor（奥卡姆剃刀的强形式）（奥卡姆剃刀的强形式）4.6.6 决策树学习的归纳偏置n严格的说，它们应该被称为吝啬定律，或严格的说，它们应该被称为吝啬定律，或者称为朴素原则。者称为朴素原则。 n爱因斯坦说爱因斯坦说: “万事万物应该尽量简单，而万事万物应该尽量简单，而不是更简单。不是更简单。”Occams razor（奥卡姆剃刀的强形式）（奥卡姆剃刀的强形式）4.6.6 决策树学习的归纳偏置n当然给出一个归纳偏置的名字不等于证明当然给出一个归纳偏置的名字不等于证明了
36、它。决策树假设了它。决策树假设,500个结点的决策树比个结点的决策树比5个结点的决策树多得多。如果给定一个个结点的决策树多得多。如果给定一个20个个训练样例的集合，可以预期能够找到很多训练样例的集合，可以预期能够找到很多500个结点的决策树与训练数据一致，而如个结点的决策树与训练数据一致，而如果一个果一个5结点的决策树可以完美地拟合这些结点的决策树可以完美地拟合这些数据则是出乎意外的。所以我们会相信数据则是出乎意外的。所以我们会相信5个个结点的树不太可能是统计巧合，因而优先选结点的树不太可能是统计巧合，因而优先选择这个假设，而不选择择这个假设，而不选择500个结点的。个结点的。 Occams
37、razor（奥卡姆剃刀的强形式）（奥卡姆剃刀的强形式）4.6.7 决策树的常见问题n确定决策树增长的深度确定决策树增长的深度n处理连续值的属性处理连续值的属性n选择一个适当的属性筛选度量标准选择一个适当的属性筛选度量标准n处理属性值不完整的训练数据处理属性值不完整的训练数据n处理不同代价的属性处理不同代价的属性n提高计算效率提高计算效率 ID3扩展为扩展为C4.5避免过度拟合（Overfitting）4.6.7 决策树的常见问题n通过学习训练数据来构造分类树，可能无通过学习训练数据来构造分类树，可能无法达到最好的泛化性能。法达到最好的泛化性能。噪声数据的影响噪声数据的影响某些决策仅基于少量数据
38、，与客观事实某些决策仅基于少量数据，与客观事实不符合不符合避免过度拟合（Overfitting）4.6.7 决策树的常见问题基本基本ID3ID3算法描述算法描述增长树的每一个分支增长树的每一个分支的深度，直到恰好的深度，直到恰好能对训练样例能对训练样例完美地分类。完美地分类。数据中有噪声。数据中有噪声。训练数据太少训练数据太少以至于不能产生以至于不能产生目标函数的有代目标函数的有代表性的采样时。表性的采样时。在以上任一种情况发生时，在以上任一种情况发生时，这个简单的算法产生的树会过度拟合训练样例。这个简单的算法产生的树会过度拟合训练样例。避免过度拟合（Overfitting）4.6.7 决策树
39、的常见问题决策树的常见问题n对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布（也就是包含训练集合以外的实例）上表现的却更好时，我们说这个假设过度拟合（overfit）训练样例。避免过度拟合4.6.7 决策树的常见问题n定义：定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。 避免过度拟合4.6.7 决策树的常见问题过度拟合与噪声过度拟合与噪声4.6.7 决策树的常见问题n分类或属性噪声都会导致过度拟合分类或属性噪声都会导致过度拟合增加噪声实例增加噪声
40、实例, +（实际为（实际为-）。）。过度拟合与噪声过度拟合与噪声4.6.7 决策树的常见问题过度拟合与噪声过度拟合与噪声4.6.7 决策树的常见问题n噪声也会直接导致样本的冲突噪声也会直接导致样本的冲突(相同描述，相同描述，不同分类不同分类)。应将叶结点标号为主要的分类。应将叶结点标号为主要的分类, - (实际上为实际上为+)。n若属性不完备且不足以判别分类时，也可若属性不完备且不足以判别分类时，也可能导致样本的冲突。能导致样本的冲突。避免过度拟合的方法避免过度拟合的方法剪枝剪枝4.6.7 决策树的常见问题n预修剪：支持度不够则停止树的增长。：支持度不够则停止树的增长。n后修剪：置信度不够则修
41、剪掉该分支。：置信度不够则修剪掉该分支。哪种方法被实践证明更有效？哪种方法被实践证明更有效？原因是什么？原因是什么？避免过度拟合的方法避免过度拟合的方法剪枝剪枝4.6.7 决策树的常见问题预修剪中精确地估计何时停止预修剪中精确地估计何时停止增长树很困难。增长树很困难。 无论是通过预修剪无论是通过预修剪还是后修剪来得到正确大小的树，还是后修剪来得到正确大小的树，一个关键的问题是一个关键的问题是使用什么样使用什么样的准则来确定的准则来确定最终正确树的大小。最终正确树的大小。 避免过度拟合的方法避免过度拟合的方法剪枝剪枝4.6.7 决策树的常见问题修剪方法修剪方法4.6.7 决策树的常见问题n使用与
42、训练样例截然不同的一套分离的样使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修剪结点例，来评估通过后修剪方法从树上修剪结点的效用。的效用。 修剪方法修剪方法4.6.7 决策树的常见问题n使用所有可用数据进行训练，但进行统计使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的结点测试来估计扩展（或修剪）一个特定的结点是否有可能改善在训练集合外的实例上的性是否有可能改善在训练集合外的实例上的性能。例如，能。例如，Quinlan （1986）使用一种卡方）使用一种卡方（chi-square）测试来估计进一步扩展结点）测试来估计进一步扩展结点是否能改善在整个实例分
43、布上的性能，还是是否能改善在整个实例分布上的性能，还是仅仅改善了在当前的训练数据上的性能。仅仅改善了在当前的训练数据上的性能。 修剪方法修剪方法4.6.7 决策树的常见问题n使用一个明确的标准来衡量训练样例和决使用一个明确的标准来衡量训练样例和决策树编码的复杂度，当这个编码的长度最小策树编码的复杂度，当这个编码的长度最小时停止增长树。这个方法基于一种启发式规时停止增长树。这个方法基于一种启发式规则，被称为最小描述长度（则，被称为最小描述长度（Minimum Description Length）的准则）的准则 。训练和验证集法训练和验证集法4.6.7 决策树的常见问题All available
44、 dataTraining SetGrowing SetPruning SetTest Set训练和验证集法的动机训练和验证集法的动机4.6.7 决策树的常见问题n即使学习器可能会被训练集合中的随机错即使学习器可能会被训练集合中的随机错误和巧合规律性所误导，但验证集合不大可误和巧合规律性所误导，但验证集合不大可能表现出同样的随机波动。所以，验证集合能表现出同样的随机波动。所以，验证集合可以用来对过度拟合训练集中的虚假特征提可以用来对过度拟合训练集中的虚假特征提供一个防护检验。当然，很重要的一点，验供一个防护检验。当然，很重要的一点，验证集合应该足够大，以便它本身可提供具有证集合应该足够大，以便
45、它本身可提供具有统计意义的实例样本。统计意义的实例样本。 合并连续值属性合并连续值属性 4.6.7 决策树的常见问题n如何把连续值的决策属性加入到决策树中？如何把连续值的决策属性加入到决策树中？以通过动态地定义新的离散值属性来实现，以通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间即先把连续值属性的值域分割为离散的区间集合。集合。n例如，对于连续值的属性例如，对于连续值的属性A，算法可动态，算法可动态地创建一个新的布尔属性地创建一个新的布尔属性Ac，如果，如果A54 和和Temperature85的的信息增益，并选择最好的信息增益，并选择最好的（Temperature
46、54）。现在这个动态创建）。现在这个动态创建的布尔属性便可以和其他候选的离散值属性的布尔属性便可以和其他候选的离散值属性一同一同“竞争竞争”，以用于增长决策树。，以用于增长决策树。 举例举例 4.6.7 决策树的常见问题如何把连续的属性分割成多个区间？如何把连续的属性分割成多个区间？属性选择的其他度量标准属性选择的其他度量标准 4.6.7 决策树的常见问题n信息增益度量偏袒具有较多值的属性。举信息增益度量偏袒具有较多值的属性。举一个极端的例子，考虑属性一个极端的例子，考虑属性Date，它有大量，它有大量的可能值。它会在所有属性中有最大的信息的可能值。它会在所有属性中有最大的信息增益。这是因为单
47、独增益。这是因为单独Date就可以完全预测训就可以完全预测训练数据的目标属性。练数据的目标属性。属性选择的其他度量标准属性选择的其他度量标准 4.6.7 决策树的常见问题n于是这个属性会被选作树的根结点的决策于是这个属性会被选作树的根结点的决策属性并形成一棵深度为一级但却非常宽的树，属性并形成一棵深度为一级但却非常宽的树，这棵树可以理想地分类训练数据。当然，这这棵树可以理想地分类训练数据。当然，这个决策树对于后来数据的性能会相当差，因个决策树对于后来数据的性能会相当差，因为尽管它完美地分割了训练数据，但它不是为尽管它完美地分割了训练数据，但它不是一个好的预测器（一个好的预测器（predicat
48、or）。）。举例举例 4.6.7 决策树的常见问题属性属性DateDate太多的可能值必然把太多的可能值必然把训练样例分割成非常小的空间。训练样例分割成非常小的空间。因此，相对训练样例，它会有非因此，相对训练样例，它会有非常高的信息增益，常高的信息增益，尽管对于未见实例它是一尽管对于未见实例它是一个非常差的目标函数预测器。个非常差的目标函数预测器。 增益比率增益比率4.6.7 决策树的常见问题n增益比率通过加入一个称作分裂信息增益比率通过加入一个称作分裂信息（split information）的项来惩罚类似）的项来惩罚类似Date的属性，分裂信息用来衡量属性分裂数据的的属性，分裂信息用来衡量
49、属性分裂数据的广度和均匀性：广度和均匀性： |log|),(21SSSSASmationSplitInforicii其中其中S S1 1到到ScSc是是c c个值的属性个值的属性A A分割分割S S而形成的而形成的c c个样例子集。个样例子集。 举例举例 4.6.7 决策树的常见问题分裂信息实际上分裂信息实际上就是就是S S关于属性关于属性A A的各值的熵。的各值的熵。 ID3ID3中熵是中熵是S S关于学习到的关于学习到的树要预测的目标属性的值的熵。树要预测的目标属性的值的熵。 增益比率增益比率4.6.7 决策树的常见问题n增益比率度量是用前面的增益度量和这里增益比率度量是用前面的增益度量和
50、这里的分裂信息度量来共同定义的，即：的分裂信息度量来共同定义的，即：),(),(),(ASmationSplitInforASGainASGainRatio处理缺少属性值的训练样例处理缺少属性值的训练样例 4.6.7 决策树的常见问题n例如，在医学领域我们希望根据多项化验例如，在医学领域我们希望根据多项化验指标预测患者的结果，然而可能仅有部分患指标预测患者的结果，然而可能仅有部分患者具有验血结果。在这种情况下，经常需要者具有验血结果。在这种情况下，经常需要根据此属性值已知的其他实例，来估计这个根据此属性值已知的其他实例，来估计这个缺少的属性值。缺少的属性值。 处理缺少属性值的训练样例处理缺少属
