1、第第 6 6 章章 决策树决策树主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献第6章 决策树决策树基本概念决策树基本概念关于分类问题关于分类问题 分类（Classification）任务就是通过学习获得一个目标函数（Target Function）f,将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是纪录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个特殊
2、的属性，指出样例的类标号（也称为分类属性或者目标属性）第6章 决策树决策树基本概念决策树基本概念关于分类问题关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类与回归分类目标属性分类目标属性y是离散的，回归目标属性是离散的，回归目标属性y是连续的是连续的第6章 决策树决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数
3、据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。第6章 决策树决策树基本概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法 通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。第6章 决策树决策树基本
4、概念决策树基本概念解决分类问题的一般方法解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）训练集（类标号已知）检验集（类标号未知）检验集（类标号未知）归纳推论第6章 决策树决策树基本概念决策树基本概念有指导的学习与无指导的学习有指导的学习与无指导的学习(有监督学习与无监督学习有监督学习与无监督学习)有指导的学习（有指导的学习（supervised learning 一般用于分类）一般用于分类）模型的学习在被告知每个训练样
5、本属于模型的学习在被告知每个训练样本属于“那个类那个类”的指导下的指导下进行。进行。新数据使用训练数据集中得到的规则进行分类。新数据使用训练数据集中得到的规则进行分类。无指导的学习（无指导的学习（unsupervised learning 一般用于聚类）一般用于聚类）每个训练样本的类编号是未知的，要学习的类集合和数量每个训练样本的类编号是未知的，要学习的类集合和数量也可能是事先未知的。也可能是事先未知的。通过一系列的度量、观察来建立数据中的类编号或进行聚类通过一系列的度量、观察来建立数据中的类编号或进行聚类第6章 决策树决策树基本概念决策树基本概念半监督学习（半监督学习（semi-superv
6、ised learning）传统的机器学习技术需要使用大量有标记训练样本进行学传统的机器学习技术需要使用大量有标记训练样本进行学习，但是在很多真实应用中，获取大量有标记训练样本相当困习，但是在很多真实应用中，获取大量有标记训练样本相当困难，但是很容易获得大量未标记训练样本。半监督学习致力于难，但是很容易获得大量未标记训练样本。半监督学习致力于利用未标记样本来提高学习性能。利用未标记样本来提高学习性能。半监督学习主要有三种学习方法：半监督学习主要有三种学习方法：自训练；自训练；协同训练；协同训练；Co-EM算法算法第6章 决策树决策树基本概念决策树基本概念半监督学习（半监督学习（semi-sup
7、ervised learning）自训练：先在较小的标识数据集上训练得到初始分类器，然后自训练：先在较小的标识数据集上训练得到初始分类器，然后 利用该分类器对未标识样本进行分类。将分类置信度利用该分类器对未标识样本进行分类。将分类置信度 较高的未标识数据作为新的训练样本，添加到原训练较高的未标识数据作为新的训练样本，添加到原训练 集中对模型进行更新。如此循环多次后，输出得到的集中对模型进行更新。如此循环多次后，输出得到的 分类器及其分类结果。分类器及其分类结果。特点：自训练的方法通过将训练得到的置信度高的未标识数据特点：自训练的方法通过将训练得到的置信度高的未标识数据作为训练样本，添加到训练集
8、重复训练的方法，增加了训练集作为训练样本，添加到训练集重复训练的方法，增加了训练集的数量，对未标识数据的信息进行了很好的利用，提高了分类的数量，对未标识数据的信息进行了很好的利用，提高了分类的性能。但要求分类器对未标识数据具有较高的分类精度。这的性能。但要求分类器对未标识数据具有较高的分类精度。这点对于较为复杂的分类尤其重要。点对于较为复杂的分类尤其重要。自训练方法及特点自训练方法及特点第6章 决策树半监督学习（半监督学习（semi-supervised learning）协同训练方法及特点协同训练方法及特点 协同训练是一种利用互补的分类器对未标识样本特征空间协同训练是一种利用互补的分类器对未
9、标识样本特征空间进行探索的半监督学习方法。进行探索的半监督学习方法。协同训练利用分类器之间的相互训练来提高分类性能。可协同训练利用分类器之间的相互训练来提高分类性能。可以弥补因一个分类器不准而对最终结果造成的影响。最终结果以弥补因一个分类器不准而对最终结果造成的影响。最终结果综合了两个分类器的结果得到。协同训练结果一般要优于自训综合了两个分类器的结果得到。协同训练结果一般要优于自训练。但也面临未知数据分类精度对最终结果的影响问题。练。但也面临未知数据分类精度对最终结果的影响问题。第6章 决策树半监督学习（半监督学习（semi-supervised learning）Co-EM算法及特点算法及特
10、点 Co-EM算法是协同训练的改进形式，它不是直接利用当算法是协同训练的改进形式，它不是直接利用当前分类器对未标识样本的分类，而利用分类后的后验概率进前分类器对未标识样本的分类，而利用分类后的后验概率进行分类。行分类。优点在于对数据前几轮中的预测标识可以通过后验概率优点在于对数据前几轮中的预测标识可以通过后验概率来改变。这样在初始分类器准确率不高的情况下优于协同训来改变。这样在初始分类器准确率不高的情况下优于协同训练。但其合理性和收敛性没有理论的保证。练。但其合理性和收敛性没有理论的保证。第6章 决策树半监督学习（半监督学习（semi-supervised learning）其它半监督学习方法
11、还包括：其它半监督学习方法还包括：生成式模型（生成式模型（generative models）;最大化分离（最大化分离（maximizing separation）;基于图的方法（基于图的方法（graph-based methods）.第6章 决策树决策树基本概念决策树基本概念决策树决策树 决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。第6章 决策树决策树基本概念决策树基本概念决策树的优点决策树的优点1、推理过程容易理解，决策推理过程可以表示成If Then形式；2、推理过程完
12、全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量的重要性，减少变量的数目提供参考。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(1)决策树技术发现数据模式和规则的核心是归纳算法。归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳
13、学习(2)归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。锐角三角形内角和等于180度；钝角三角形内角和等于180度；三角形内角和 直角三角形内角和等于180度；等于180度 已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度 归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。第6章 决策树决策树基本概念决策树基本概念关于归纳学习关于归纳学习(3)第6章 决策树决策
14、树基本概念决策树基本概念关于归纳学习关于归纳学习(4)归纳过程就是在描述空间中进行搜索的过程。归纳可分为自顶向下，自底向上和双向搜索三种方式。自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述。第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（1）从特殊的训练样例中归纳出一般函数是机器学习的中心问题；从训练样例中进行学习通常被视为归纳推理。每个例子都是一个对偶（序偶）（x,f(x)），对每个输入的x，都有确定的输出f(x)。学习过程将产生
15、对目标函数f的不同逼近。F的每一个逼近都叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过调整假设的表示，学习过程将产生出假设的不同变形。在表示中通常需要修改参数（如a,b）。第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（2）从这些不同的变形中选择最佳的假设（或者说权值集合）。一般方法如定义为使训练值与假设值 预测出的值之间的误差平方和E最小为最佳。amplestrainingexbVtrainbbVbVtrainE)(,2)()(学习是在假设空间上的一个搜索。概念学习也可以看作是一个搜索问题的过程。它在预定义的假设空
16、间中搜索假设，使其与训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（3）分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数进行评估。这些计数存储在混淆矩阵（进行评估。这些计数存储在混淆矩阵（Confusion Matrix）的表格中，二元）的表格中，二元分类问题混淆矩阵如下：分类问题混淆矩阵如下：实际实际的类的类类类1f11类类0f01f10f00类类
17、1类类0预测的类预测的类准确率准确率=正确的预测数正确的预测数/预测总数预测总数=（f11+f00）/(f11+f01+f10+f00)差错率差错率=错误的预测数错误的预测数/预测总数预测总数=（f10+f01）/(f11+f01+f10+f00)第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（4）混淆矩阵一般可以用于衡量分类器的精度。混淆矩阵一般可以用于衡量分类器的精度。例如例如 有有150个数据，分个数据，分3类，每类类，每类50个数据。个数据。分类结果的混淆矩阵如下分类结果的混淆矩阵如下类1类2类3类14352类22453类3
18、0149含义：第含义：第1行表示类行表示类1有有43个分类是正确的，个分类是正确的，5个错分为类个错分为类2,2个错分为类个错分为类3。其分类精度为。其分类精度为.43/50.其余类同其余类同上例的数据来自上例的数据来自 UCI Machine Learning Repository中的中的German Credit Dataset可以免费获取。可以免费获取。归纳学习假设 机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设 。一般H表示所有可能假设。H中每个假设h表示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟合。若
19、没有更多的信息，只能假定对于未见实例最好的假设就是训练数据最佳拟合的假设。定义 归纳学习假设：任一假设如果在足够大的训练样例中很好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。（Function Approximation）。)1,0:(xhh第6章 决策树决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（从机器学习看分类及归纳推理等问题（4）主要内容主要内容决策树基本概念决策树基本概念决策树算法决策树算法决策树研究问题决策树研究问题主要参考文献主要参考文献第6章 决策树决策树算法决策树算法与决策树相关的重要算法与决策树相关的重要算法1、Hunt,Marin和Stone
20、于1966年研制的CLS学习系统，用于学习单个概 念。2、1979年,J.R.Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。5、1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。6、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有
21、两个分枝，分别包括学习实例的正例与反例。CLS,ID3，C4.5，CART第6章 决策树决策树算法决策树算法计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买假定公司收集了左表数据，那么对假定公司收集了左表数据，那么对于任意给定的客人（测试样例），于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于即：你能
22、预测这位客人是属于“买买”计算机的那一类，还是属于计算机的那一类，还是属于“不买不买”计算机的那一类？计算机的那一类？又：你需要多少有关这位客人的信又：你需要多少有关这位客人的信息才能回答这个问题？息才能回答这个问题？决策树的用途决策树的用途第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买谁在买计算机？谁在买计算机？年龄？学生？信誉？买青中老否是优良不买
23、买买不买决策树的用途决策树的用途决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买归类：买计算机？计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买谁在买计算机？谁在买计算机？年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途决策树的用途决策树算法决策树算法第6章 决策树决策树算法决策树算法决策树的表示决策树的表示决策树的基本组成部分：决策结点、分支和叶子。决策树的基本组成部分：决策结点、分支
24、和叶子。年龄？学生？信誉？买青中老否是优良不买买买不买决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果 在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别第6章 决策树决策树算法决策树算法CLS（Concept Learning System）算法）算法 CLS算法是早期的决策树学习算法。它是许多决策树学习算法的
25、基础。CLS基本思想基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。第6章 决策树人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血决策树算法决策树算法CLS算法算法第6章 决策树人员眼睛颜色头发颜色所属人种
26、1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血决策树算法决策树算法CLS算法算法-决策树的构建决策树的构建眼睛颜色眼睛颜色1，62，4，83，5，7黑色黑色兰色兰色灰色灰色不属于同一类，非叶结点不属于同一类，非叶结点第6章 决策树眼睛颜色眼睛颜色头发颜色头发颜色头发颜色头发颜色头发颜色头发颜色黑色黑色兰色兰色灰色灰色决策树算法决策树算法CLS算法算法黄种人黄种人1混血混血6白种人白种人2白种人白种人4混血混血8白种人白种人3白种人白种人5混血混血7黑色黑色金色金色金色金色红色红色 黑色黑色金色金色红色红色黑色黑色第6章
27、 决策树决策树算法决策树算法CLS算法算法1 生成一颗空决策树和一张训练样本属性集;2 若训练样本集T 中所有的样本都属于同一类,则生成结点T,并终止学习算法;否则3 根据某种策略某种策略从训练样本属性表中选择属性 A 作为测试属性,生成测试结点A 4 若A的取值为v1,v2,vm,则根据A 的取值的 不同,将T 划分成 m个子集T1,T2,Tm;5 从训练样本属性表中删除属性A;6 转步骤2,对每个子集递归调用CLS;第6章 决策树CLS算法问题算法问题在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决
28、策树的学习具有举足轻重的影响。举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含决策树算法决策树算法第6章 决策树CLS算法问题算法问题决策树算法决策树算法学生鸡肉猪肉牛肉羊肉鱼肉鸡蛋青菜番茄牛奶健康情况1011010101不缺钙2000011111不缺钙3111110100缺钙4110011001不缺钙5100111000缺钙6111001010缺钙7010001111不缺钙8010001111缺钙9010001111不缺钙10101111011不缺钙学生膳食结构和缺钙调查表第6章 决策树CLS算法问题算法问题决策树算法决策树算法采用不同的测试属性及其先后
29、顺序将会生成不同的决策树鸡肉鸡肉猪肉猪肉猪肉猪肉牛肉牛肉牛肉牛肉牛肉牛肉不缺钙（不缺钙（2）缺钙（缺钙（3，6）不缺钙（不缺钙（4）不缺钙（不缺钙（10）缺钙（缺钙（5）不缺钙（不缺钙（1）鱼肉鱼肉缺钙（缺钙（5）不缺钙（不缺钙（7，9）是是否否是是否否否否否否否否否否否否是是是是是是是是是是第6章 决策树牛奶牛奶不缺钙不缺钙（1，2，4，7，9，10）缺钙缺钙（3，5，6，8）CLS算法问题算法问题决策树算法决策树算法 在上例中，显然生成的两种决策树的复杂性和分类意义相差很大由此可见，选择测试属性是决策树学习算法中需要研究的重要课题。第6章 决策树ID3 决策树算法决策树算法 ID3算法主要
30、针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。该方法使用信息增益度选择测试属性。当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小？第6章 决策树决策树算法决策树算法IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrue
31、TrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno例申请贷款例申请贷款的数据集合的数据集合第6章 决策树
32、决策树算法决策树算法上例可能的两种根节点上例可能的两种根节点Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3上例若采用Age或Own_house作为根节点。根节点可能值构成了根节点分支。对于每个分支，列出该分支上每个类（Yes或No）的训练数据的数目。(b)显然要比(a)好。因为从分类预测的观点来看，(b)比(a)犯错误的可能性要小。（a）（b）第6章 决策树决策树算法决策树算法Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:1Yes:4Own_ho
33、use？truefalseNo:0Yes:6No:6Yes:3（a）（b）选择(b)时，当Own_house=true时，每个样例都分配到yse类中。在Own_house=false时如果将它们都归类到No类中，则在整个分类中会有三个分类是错误的。选择(a)时，如果我们选择按照多数服从少数的方法，则会产生5个错误的分类。说明，节点的选择对结果是有影响的。说明，节点的选择对结果是有影响的。第6章 决策树ID3 信息量大小的度量信息量大小的度量决策树算法决策树算法Shannon1948年提出的信息论理论。事件ai的信息量I（ai）可如下度量：其中p(ai)表示事件ai发生的概率。假设有n个互不相容
34、的事件a1,a2,a3,.,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：niiiniinapapaIaaaI12121)(1log)()(),.,()(1log)()(2iiiapapaI第6章 决策树ID3 信息量大小的度量信息量大小的度量决策树算法决策树算法niiiniinapapaIaaaI12121)(1log)()(),.,(上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时 =0)(1log)()(2iiiapapaI公式公式1第6章 决策树决策树算法决策树算法例：假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例
35、类计算D中正例类和负例类在三种不同的组分下熵的变化情况。（1）D中包含有50%的正例和50%的负例。Entropy(D)=-0.5*log20.5-0.5*log20.5=1（2）D中包含有20%的正例和80%的负例。Entropy(D)=-0.2*log20.2-0.8*log20.8=0.722（3）D中包含有100%的正例和0%的负例。Entropy(D)=-1*log21-0*log20=0 从上述的结果可以看到一个趋势，当数据变得越来越纯净时，熵的值变得越来越小。事实上可以证明，当正例（0.5）,反例（0.5）时，熵取最大值。当D 中所有数据都只属于一个类时，熵得到最小值。显然，上可
36、以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中需要的。在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本划分为n个不同的类C1,C2,.Cn，这些类的大小分别标记为|C1|，|C2|，.,|Cn|。则任意样本S属于类Ci的概率为：|)(SCSpii第6章 决策树ID3 信息量大小的度量信息量大小的度量决策树算法决策树算法Entropy（S，A）=（|Sv|/|S|）*Entropy（Sv）公式）公式2 是属性A的所有可能的值v,Sv是属性A有v值的S子集|Sv|是Sv 中元素的个数；|S|是S中元素的个数。第6章 决策树ID3 信息量大小的度量信息量大小的度量决策树算法决策
37、树算法Gain（S，A）是属性）是属性A在集合在集合S上的信息增益上的信息增益Gain（S，A）=Entropy（S）-Entropy（S，A）公式公式3Gain（S，A）越大，说明选择测试属性对分类提供的信息越多）越大，说明选择测试属性对分类提供的信息越多第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策树算法决策树算法第6章 决策树计数年龄收入学生
38、信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第1步计算决策属性的熵步计算决策属性的熵决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641 S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2
39、P2)=0.9537决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2步计算条件属性的熵步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买6
40、4老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128 S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不
41、买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-2步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256 S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：
42、买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-3步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1(买)=125 S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9157决策树算法决策树算法第6章
43、 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-4步计算年龄的熵步计算年龄的熵年龄共分三个组：青年、中年、老年所占比例青年组 384/1024=0.375中年组 256/1024=0.25老年组 384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157 =0.6877G（年龄信息增益
44、）=0.9537-0.6877 =0.2660 （1）决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步计算收入的熵步计算收入的熵收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176(2)决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？6
45、4青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步计算学生的熵步计算学生的熵学生共分二个组：学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811 =0.1726 （3）决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买1
46、32老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第5步计算信誉的熵步计算信誉的熵信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048 =0.0453 （4）决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第6步计算选择节点步计算选择节点 年龄信息增益=0.9
47、537-0.6877 =0.2660 （1）收入信息增益=0.9537-0.9361 =0.0176 （2）学生信息增益=0.9537-0.7811 =0.1726 （3）信誉信息增益=0.9537-0.9048 =0.0453 （4）决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄年龄青年中年老年买/不买买买/不买叶子决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中
48、是优买青年买与不买比例为128/256S1(买)=128 S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2)=0.9183决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(
49、128,256)-E(收入)=0.9183 0.4592=0.4591I(0,128)=0 比例:128/384=0.3333I(64,128)=0.9183 比例:192/384=0.5I(64,0)=0比例:64/384=0.1667 注意决策树算法决策树算法第6章 决策树计数年龄收入学生信誉归类：买计算归类：买计算机？机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买年龄年龄青年中年老年学生买信誉叶子否否是是优
50、优良良买不买买/不买买叶子叶子叶子决策树算法决策树算法第6章 决策树ID3 决策树建立算法决策树建立算法1 决定分类属性；2 对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上 标出所属的类4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作 为节点N的测试属性6 节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏 如果分支数据表非空，则运用以上算法从该节点建立子树。
