机器学习之决策树学习ppt课件.ppt

《机器学习之决策树学习ppt课件.ppt》由会员分享，可在线阅读，更多相关《机器学习之决策树学习ppt课件.ppt（49页珍藏版）》请在三一办公上搜索。

1、1,机器学习 决策树学习,2,决策树学习概述决策树学习的适用问题决策树建树算法决策树学习中的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,3,决策树学习概述,决策树归纳是归纳学习算法中最简单也是最成功的算法之一好的入门 决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)一般是二值分类(真或假)，是一种逼近离散值函数的方法,4,决策树学习示例,例子：星期六上午是否适合打网球属性=outlook，Temperature, humidity，wind属性值=sunny, overcast, rain, hot, mild, cool, high, norma

2、l, strong, weak,5,决策树学习示例训练样例,返回,6,决策树学习示例决策树表示,决策树通过把实例从根节点排列到某个叶子节点来分类实例叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值,High Normal Strong Weak,Outlook,Wind,Humidity,Sunny,Overcast,Rain,Yes,No,Yes,No,Yes,7,Outlook,Wind,Humidity,Sunny,Overcast,Rain,High Normal Strong Weak,Yes,No,Yes,No,Yes,决

3、策树学习示例决策树,未见实例: ,8,决策树学习示例决策树表示,决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取,High Normal Strong Weak,Outlook,Wind,Humidity,Sunny,Overcast,Rain,Yes,No,Yes,No,Yes,9,High Normal Strong Weak,Outlook,Wind,Humidity,Sunny,Overcast,Rain,Yes,No,Yes,No,Yes,决策树学习示例决策树表示,上面决策树对应于以下表达式: （Outlook=sunn

4、yHumidity=normal） （Outlook=overcast) （Outlook=rainWind=weak),10,决策树学习概述决策树学习的适用问题决策树建树算法决策树学习中的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,11,决策树学习的适用问题,决策树适合具有以下特征的学习：实例是由“属性-值”对表示的固定的属性+离散或连续的取值目标函数具有离散的输出值析取表达式训练数据可以包含错误决策树学习的鲁棒性好训练数据可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障分类问题核心任务是把样例分类到各可能的离散值对应的类别,12,决策树学习概述

5、决策树学习的适用问题决策树建树算法决策树学习中的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,13,决策树建树算法,决策树学习包括2个步骤：从实例中归纳出决策树(建立决策树)利用决策树对新实例进行分类判断如何建立决策树：大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表,14,决策树建树算法（1）,ID3算法的基本思想：自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力,15,决策树建树算法（2）,ID3算法的构造过程初始时，决策树根节点包括所有的训练样例

6、分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支，训练样例排列到适当的分支对于每一个分支，重复上面的过程算法的终止条件：所有的属性已经被这条路经包括；与这个节点关联的所有训练样例都具有相同的目标属性值（即它们的熵为0）,16,决策树建树算法（3）,ID3(Examples, Target_attribute, Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Targe

7、t_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（ Examplesvi,Target_attribute,Attributes-A）结束返回root,17,属性选择,决策树中的每个节点都代表一定的属性，这些属性如何在决策树中排布是值得认真研

8、究的决策树建树算法中的属性选择方案的目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例在决策树算法中，属性排序以信息论中的熵概念为理论基础属性提供的期望信息量,18,熵与不确定性,信息论中用熵表示事物的不确定性，同时也是信息含量的表示熵值越大，表示不确定性越大，同时信息量越多；反之则不确定性越小，信息量越小,19,熵和决策树,Quinlan于1983年提出决策树算法ID3时使用熵的概念来提高决策树分类的效率：开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减

9、小了到达叶子节点，分类完成，此时不确定性为零,20,要提高决策树的分类效率，就相当于要求熵值下降的更快 / 这样，ID3算法的实质就是构造一棵熵值下降平均最快的决策树熵值下降表明不确定性减小的思想可以应用到许多情况，例如：自然语言中的各种歧义是一种不确定性，而从不确定性走向确定性就是歧义减小 / 如果不确定性消失也就是熵值为零，则说明已经消除了歧义，选择了某个明确的符号表示 / 因此可以应用决策树算法来消歧,熵和决策树（2）,21,熵和决策树（3）,用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为更一般地，如果目标属性具有

10、c个不同的值，那么S相对于c个状态的分类的熵定义为,其中，p1是在S 中正例的比例，p0是在S 中反例的比例,22,熵和决策树（4）,熵值计算举例：例如：“PlayTennis”中S是一个关于某布尔概念的14个样例的集合，包括9个正例和5个反例9+，5-。那么S相对于这个布尔分类的熵为：训练数据集,23,熵和决策树熵函数变化曲线,熵值分析：如果S的所有成员属于同一类，那么S的熵为0如果S中正反样例的数量相等时（或者：S中各类样例等比例时），熵值为1如果S集合中正反例的数量不等时，熵介于0和1之间,24,信息增益,用信息增益度量期望的熵降低属性的信息增益（属性分类训练数据的能力的度量标准），由于

11、使用这个属性分割样例而导致的期望熵降低一个属性A相对样例集合S的信息增益Gain(S,A)为：,其中，Values(A)是属性A所有可能值得集合，Sv是S 中属性A的值为v的子集上述等式中：第一项为原集合S的熵，第二项是用A分类S后熵的期望值即每个子集的熵的加权和。,25,上式中第二项的值应该越小越好，因为越小说明S相对于属性A作分解以后而造成的熵下降越快（根据前面的解释，熵下降越快就是不确定性减少越快），换句话说Gain(S,A)越大越好 决策树建树算法的要点是在构造决策树的每一层次时，从尚未检测的属性中选择信息增益Gain(S,A)大的属性进行分解,信息增益（1）,26,举例PlayTen

12、nis,学习任务：星期六上午是否适合打网球目标函数PlayTennis具有yes和no两个值，我们将根据其它属性来预测这个目标函数值决策树建树算法第一步，创建决策树的最顶端节点：哪个属性在树上第一个被测试呢？ ID3算法计算每一个候选属性（Outlook, Temperature, Humidity和Wind）的信息增益，然后选择信息增益最高的一个。,27,举例PlayTennis（1）,计算属性Wind的信息增益Values(Wind) = Weak, Strong S = 9+,5- Sweak = 6+,2- Sstrong = 3+,3-信息增益,= Entropy(S)- (8/14

13、)Entropy(Sweak)- (6/14)Entropy(Sstrong),=0.940- (8/14)0.811- (6/14)1.00 =0.048,S:9+, 5 E=0.940 wind,weak strong6+, 2 3+, 3E=0.811 E=1.00,Gain(S,Wind)=0.940(8/14)0.811(6/14)1.0,28,举例PlayTennis（2）,同理，其它属性的信息增益Gain (S, Outlook) = 0.246Gain (S, Humidity) = 0.151Gain (S, Wind) = 0.048Gain (S, Temperature

14、) = 0.029,根据信息增益标准，属性Outlook在训练样例上提供了对目标函数PlayTennis的最好预测。所以，Outlook被选作根节点的决策属性，并为它的每一个可能值在根节点下创建分支。,29,举例PlayTennis（3）,D1,D2,D14S:9+, 5,Outlook,Sunny,Overcast,Rain,D3,D7,D12,D134+, 0,D1,D2,D8,D9,D112+, 3,D4,D5,D6,D10,D143+, 2,?,哪一个属性应在这里被测试,Yes,?,Ssunny=D1,D2,D8,D9,D11Gain (Ssunny, Humidity) = 0.97

15、0-(3/5)0.0-(2/5)0.0=0.970Gain (Ssunny, Temperature) = 0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570Gain (Ssunny, Wind) = 0.970-(2/5)1.0-(3/5)0.918=0.019,30,举例PlayTennis（4）,上述决策树构建的终止条件：所有的属性已经被这条路经包括；与这个节点关联的所有训练样例都具有相同的目标属性值（即它们的熵为0）,31,练习,著名的隐形眼镜例子(Cendrowska给出)对于是否可配戴隐形眼镜，可把人们分为3类：类1：适于配戴硬性隐形眼镜；类2：适于配戴软

16、性隐形眼镜；类3：不适于配戴隐形眼镜为了判断一个人是否适合配戴隐形眼镜，需要检查以下4种属性：属性a：配戴者年龄，取值a=属性b：配戴者的视力缺陷，取值b=属性c：配戴者是否有散光，取值c=属性d：配戴者泪腺分泌情况，取值d=,32,隐形眼镜例子（1）,上述属性和人群分类一律按顺序用数字1, 2表示，可以假设根据属性a、b、c、d有如下表的分类(纯属虚拟),33,决策树学习概述决策树学习的适用问题决策树建树算法决策树学习中的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,34,决策树学习中的假设空间搜索,观察ID3的搜索空间和搜索策略，认识到这个算法的优势和不足假设空间包

17、含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设（不同于第二章的变型空间候选消除算法）不进行回溯，可能收敛到局部最优每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强,35,决策树学习概述决策树学习的适用问题决策树建树算法决策树学习中的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,36,决策树学习的归纳偏置,ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先,37,限定偏置和优选偏置,

18、ID3和候选消除算法的比较ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义,38,限定偏置和优选偏置,优选偏置ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制限定偏置候选消除算法的偏置是对待考虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的需要优选偏置和限定偏置的结合例如：第一章中描述的下棋程序,39,决策树学习概述决策树学习的适用问题决策树建树算法决策树学习中

19、的假设空间搜索决策树学习的归纳偏置决策树学习的常见问题,OUTLINE,40,决策树学习的常见问题,确定决策树增长的深度处理连续值的属性处理属性值不完整的训练数据,41,问题1：避免过度拟和数据,过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。,42,问题1：避免过度拟和数据（1）,导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练

20、数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。例如：见下页,43,问题1：避免过度拟和数据（1）,High Normal Strong Weak,Outlook,Wind,Humidity,Sunny,Overcast,Rain,Yes,No,Yes,No,Yes,训练样例集中加入一条训练正例，但被错误标示为反例: ,44,问题1：避免过度拟和数据（2）,避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观，但是精确地估计何时停止树增长很困难第二种方法被证明

21、在实践中更成功,45,问题1：避免过度拟和数据（3）,后修剪法：错误率降低修剪该方法考虑将树上的每一个节点作为修剪的候选对象。修剪一个节点的步骤：1 删除此节点为根的子树，使它成为叶子节点2 把和该节点关联的训练样例的最常见分类赋给它。仅当修剪后的树对于测试集合的性能不比原来的树差时才删除该节点,46,问题2：合并连续值属性,ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合。例如：对于属性，动态创建一新的布尔属性Ac if Ac Ac

22、= true else Ac = false,阈值c的选择：产生最大信息增益的c,47,问题2：合并连续值属性（1）,选择阈值c的方法按照连续属性A排序样例，然后确定目标分类不同的相邻样例，于是可以产生一组候选阈值，他们的值是相应的A值之间的中间值(48+60/2)和(80+90/2)计算每一个候选属性Temperature54和Temperature85的信息增益，并选择最好的,48,问题3：缺少属性值的训练样例,为了评估属性是否是决策节点的最佳测试属性，要计算Gain(S,A)。训练样例, 测试属性A的值A(x)未知处理方法：赋予A(x)节点的训练样例中该属性的最常见值;赋予A(x)节点的被分类为c(x)的训练样例中该属性的最常见值;为的每个可能值赋予一个概率e.g. A(x) = 0 is 0.4 and A(x)=1 is 0.6,49,对噪声数据有很好的健壮性 能够学习析取表达式 搜索一个完整表示的假设空间 归纳偏置是优先选择较小的树 决策树表示了多个if-then规则,总结,