决策树_ID3算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第 6,章 决策树,1,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,2,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,3,第6章 决策树,决策树基本概念,关于分类问题,分类（Classification）任务就是通过学习获得一个目标函数,（Target Function）f, 将每个属性集x映射到一个预先定义好的类,标号y。,分类任务的输入数据是纪录的集合，每条记录也称为实例,或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个,特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）,4,第6章 决策树,决策树基本概念,关于分类问题,名称,体温,表皮覆盖,胎生,水生动物,飞行动物,有腿,冬眠,类标号,人类,恒温,毛发,是,否,否,是,否,哺乳动物,海龟,冷血,鳞片,否,半,否,是,否,爬行类,鸽子,恒温,羽毛,否,否,是,是,否,鸟类,鲸,恒温,毛发,是,是,否,否,否,哺乳类,X,y,分类与回归,分类目标属性y是离散的，回归目标属性y是连续的,5,第6章 决策树,决策树基本概念,解决分类问题的一般方法,分类技术是一种根据输入数据集建立分类模型的系统方法。,分类技术一般是用一种学习算法确定分类模型，该模型可以很好,地拟合输入数据中类标号和属性集之间的联系。学习算法得到的,模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的,类标号。因此，训练算法的主要目标就是要建立具有很好的泛化,能力模型，即建立能够准确地预测未知样本类标号的模型。,分类方法的实例包括：决策树分类法、基于规则的分类法、,神经网络、支持向量级、朴素贝叶斯分类方法等。,6,第6章 决策树,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题,一般包括两个步骤：,1、模型构建（归纳）,通过对训练集合的归纳，建立分类模型。,2、预测应用（推论）,根据建立的分类模型，对测试集合进行测试。,7,第6章 决策树,决策树基本概念,解决分类问题的一般方法,TID,A1,A2,A3,类,1,Y,100,L,N,2,N,125,S,N,3,Y,400,L,Y,4,N,415,M,N,学习算法,学习模型,模型,应用模型,TID,A1,A2,A3,类,1,Y,100,L,？,2,N,125,S,？,3,Y,400,L,？,4,N,415,M,？,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,8,第6章 决策树,决策树基本概念,决策树,决策树是一种典型的分类方法，首先对数据进行处理，利用,归纳算法生成可读的规则和决策树，然后使用决策对新数据进行,分析。本质上决策树是通过一系列规则对数据进行分类的过程。,9,第6章 决策树,决策树基本概念,决策树的优点,1、推理过程容易理解，决策推理过程可以表示成If Then形式；,2、推理过程完全依赖于属性变量的取值特点；,3、可自动忽略目标变量没有贡献的属性变量，也为判断属性,变量的重要性，减少变量的数目提供参考。,10,第6章 决策树,决策树基本概念,关于归纳学习(1),决策树技术发现数据模式和规则的核心是归纳算法。,归纳是从特殊到一般的过程。归纳推理从若干个事实中表,征出的特征、特性和属性中，通过比较、总结、概括而得出一,个规律性的结论。,归纳推理试图从对象的一部分或整体的特定的观察中获得,一个完备且正确的描述。即从特殊事实到普遍性规律的结论。,归纳对于认识的发展和完善具有重要的意义。人类知识的增长,主要来源于归纳学习。,11,第6章 决策树,决策树基本概念,关于归纳学习(2),归纳学习的过程就是寻找一般化描述的过程。这种一般性,描述能够解释给定的输入数据，并可以用来预测新的数据。,锐角三角形内角和等于180度；,钝角三角形内角和等于180度； 三角形内角和,直角三角形内角和等于180度； 等于180度,已知三角形ABC，A角等于76度，,B角等于89度，则其C角等于,15度,12,归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：,任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。,第6章 决策树,决策树基本概念,关于归纳学习(3),13,第6章 决策树,决策树基本概念,关于归纳学习(4),归纳过程就是在描述空间中进行搜索的过程。归纳可分为自,顶向下，自底向上和双向搜索三种方式。,自底向上法一次处理一个输入对象。将描述逐步一般化。直,到最终的一般化描述。,自顶向下法对可能的一般性描述集进行搜索，试图找到一些,满足一定要求的最优的描述。,14,第6章 决策树,决策树基本概念,从机器学习看分类及归纳推理等问题（1）,从特殊的训练样例中归纳出一般函数是机器学习的中心问题；,从训练样例中进行学习通常被视为归纳推理。每个例子都是一个,对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。,学习过程将产生对目标函数f的不同逼近。F的每一个逼近都,叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过,调整假设的表示，学习过程将产生出假设的不同变形。在表示中,通常需要修改参数（如a, b）。,15,第6章 决策树,决策树基本概念,从机器学习看分类及归纳推理等问题（2）,从这些不同的变形中选择最佳的假设（或者说权值集合）。,一般方法如定义为使训练值与假设值 预测出的值之间的误差平方,和E最小为最佳。,学习是在假设空间上的一个搜索。概念学习也可以看作是一,个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与,训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以,利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。,16,第6章 决策树,决策树基本概念,从机器学习看分类及归纳推理等问题（3）,分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数,进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，二元,分类问题混淆矩阵如下：,实际,的类,类1,f11,类0,f01,f10,f00,类1,类0,预测的类,准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00),差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00),17,归纳学习假设,机器学习的任务是在整个实例集合X上确定与目标概念c相同,的假设 。一般H表示所有可能假设。H中每个假设h表,示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上,的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟,合。若没有更多的信息，只能假定对于未见实例最好的假设就是,训练数据最佳拟合的假设。,定义 归纳学习假设：任一假设如果在足够大的训练样例中很,好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。,（Function Approximation）。,第6章 决策树,决策树基本概念,从机器学习看分类及归纳推理等问题（4）,18,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,19,第6章 决策树,决策树算法,与决策树相关的重要算法,1、Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。,2、1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。,3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。,4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。,1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。,5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。,CLS, ID3，C4.5，CART,20,第6章 决策树,决策树算法,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？,即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？,又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,21,第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章 决策树,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树中最上面的结点称为根结点。,是整个决策树的开始。每个分支是一,个新的决策结点，或者是树的叶子。,每个决策结点代表一个问题或者决策.,通常对应待分类对象的属性。,每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个,测试。对每个结点上问题的不同测试输出导致不同的分枝，最后,会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，,利用若干个变量来判断属性的类别,24,第6章 决策树,决策树算法,CLS（Concept Learning System）算法,CLS算法是早期的决策树学习算法。它是许多决策树学习算法,的基础。,CLS基本思想,从一棵空决策树开始，选择某一属性（分类属性）作为测试,属性。该测试属性对应决策树中的决策结点。根据该属性的值的,不同，可将训练样本分成相应的子集，如果该子集为空，或该子,集中的样本属于同一个类，则该子集为叶结点，否则该子集对应,于决策树的内部结点，即测试结点，需要选择一个新的分类属性,对该子集进行划分，直到所有的子集都为空或者属于同一类。,25,第6章 决策树,人员,眼睛颜色,头发颜色,所属人种,1,黑色,黑色,黄种人,2,蓝色,金色,白种人,3,灰色,金色,白种人,4,蓝色,红色,白种人,5,灰色,红色,白种人,6,黑色,金色,混血,7,灰色,黑色,混血,8,蓝色,黑色,混血,决策树算法,CLS算法,26,第6章 决策树,人员,眼睛颜色,头发颜色,所属人种,1,黑色,黑色,黄种人,2,蓝色,金色,白种人,3,灰色,金色,白种人,4,蓝色,红色,白种人,5,灰色,红色,白种人,6,黑色,金色,混血,7,灰色,黑色,混血,8,蓝色,黑色,混血,决策树算法,CLS算法-决策树的构建,眼睛颜色,1，6,2，4，8,3，5，7,黑色,兰色,灰色,不属于同一类，非叶结点,27,第6章 决策树,眼睛颜色,头发颜色,头发颜色,头发颜色,黑色,兰色,灰色,决策树算法,CLS算法,黄种人1,混血6,白种人2,白种人4,混血8,白种人3,白种人5,混血7,黑色,金色,金色,红色,黑色,金色,红色,黑色,28,第6章 决策树,决策树算法,CLS算法,1 生成一颗空决策树和一张训练样本属性集;,2 若训练样本集T 中所有的样本都属于同一类,则生成结点T , 并终止学习算法;否则,3 根据,某种策略,从训练样本属性表中选择属性,A 作为测试属性, 生成测试结点A,4 若A的取值为v1,v2,vm, 则根据A 的取值的,不同,将T 划分成 m个子集T1,T2,Tm;,5 从训练样本属性表中删除属性A;,6 转步骤2, 对每个子集递归调用CLS;,29,第6章 决策树,CLS算法问题,在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。,举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含,决策树算法,30,第6章 决策树,CLS算法问题,决策树算法,学生,鸡肉,猪肉,牛肉,羊肉,鱼肉,鸡蛋,青菜,番茄,牛奶,健康情况,1,0,1,1,0,1,0,1,0,1,不缺钙,2,0,0,0,0,1,1,1,1,1,不缺钙,3,1,1,1,1,1,0,1,0,0,缺钙,4,1,1,0,0,1,1,0,0,1,不缺钙,5,1,0,0,1,1,1,0,0,0,缺钙,6,1,1,1,0,0,1,0,1,0,缺钙,7,0,1,0,0,0,1,1,1,1,不缺钙,8,0,1,0,0,0,1,1,1,1,缺钙,9,0,1,0,0,0,1,1,1,1,不缺钙,10,1,0,1,1,1,1,0,1,1,不缺钙,学生膳食结构和缺钙调查表,31,第6章 决策树,CLS算法问题,决策树算法,采用不同的测试属性及其先后顺序将会生成不同的决策树,鸡肉,猪肉,猪肉,牛肉,牛肉,牛肉,不缺钙（2）,缺钙（3，6）,不缺钙（4）,不缺钙（10）,缺钙（5）,不缺钙（1）,鱼肉,缺钙（5）,不缺钙（7，9）,是,否,是,否,否,否,否,否,否,是,是,是,是,是,32,第6章 决策树,牛奶,不缺钙,（1，2，4，,7，9，10）,缺钙,（3，5，6，8）,CLS算法问题,决策树算法,在上例中，显然生成的两种决策树的复杂性和分类意义相差,很大由此可见，选择测试属性是决策树学习算法中需要研究的重,要课题。,33,第6章 决策树,ID3,决策树算法,ID3算法主要针对属性选择问题。是决策树学习方法中最,具影响和最为典型的算法。,该方法使用信息增益度选择测试属性。,当获取信息时，将不确定的内容转为确定的内容，因此信,息伴着不确定性。,从直觉上讲，小概率事件比大概率事件包含的信息量大。,如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的,信息量大。,如何度量信息量的大小？,34,第6章 决策树,ID3 信息量大小的度量,决策树算法,Shannon1948年提出的信息论理论。事件a,i,的信息量I（ a,i,）可,如下度量：,其中p(a,i,)表示事件a,i,发生的概率。,假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个,发生，则其平均的信息量可如下度量：,35,第6章 决策树,ID3 信息量大小的度量,决策树算法,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。,通常取2，并规定当p(ai)=0时 =0,公式1,36,在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本,划分为n个不同的类C1,C2,.Cn，这些类的大小分别标记为|C1|，,|C2|，.,|Cn|。则任意样本S属于类Ci的概率为：,第6章 决策树,ID3 信息量大小的度量,决策树算法,Entropy（S，A）=（|Sv|/|S|）* Entropy（Sv）公式2,是属性A的所有可能的值v,Sv是属性A有v值的S子集,|Sv|是Sv 中元素的个数；|S|是S中元素的个数。,37,第6章 决策树,ID3 信息量大小的度量,决策树算法,Gain（S，A）是属性A在集合S上的信息增益,Gain（S，A）= Entropy（S） -Entropy（S，A） 公式3,Gain（S，A）越大，说明选择测试属性对分类提供的信息越多,38,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,决策树算法,39,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第1步计算决策属性的熵,决策属性“买计算机？”。该属性分,两类：买/不买,S1(买)=641,S2（不买）= 383,S=S1+S2=1024,P1=641/1024=0.6260,P2=383/1024=0.3740,I(S1,S2)=I(641,383),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9537,决策树算法,40,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、,收入、学生、信誉。,分别计算不同属性的信息增益。,决策树算法,41,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第2-1步计算年龄的熵,年龄共分三个组：,青年、中年、老年,青年买与不买比例为128/256,S1(买)=128,S2（不买）= 256,S=S1+S2=384,P1=128/384,P2=256/384,I(S1,S2)=I(128,256),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9183,决策树算法,42,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第2-2步计算年龄的熵,年龄共分三个组：,青年、中年、老年,中年买与不买比例为256/0,S1(买)=256,S2（不买）= 0,S=S1+S2=256,P1=256/256,P2=0/256,I(S1,S2)=I(256，0),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0,决策树算法,43,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第2-3步计算年龄的熵,年龄共分三个组：,青年、中年、老年,老年买与不买比例为125/127,S1(买)=125,S2（不买）=127,S=S1+S2=252,P1=125/252,P2=127/252,I(S1,S2)=I(125，127),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9157,决策树算法,44,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第2-4步计算年龄的熵,年龄共分三个组：,青年、中年、老年,所占比例,青年组 384/1025=0.375,中年组 256/1024=0.25,老年组 384/1024=0.375,计算年龄的平均信息期望,E（年龄）=0.375*0.9183+,0.25*0+,0.375*0.9157,=0.6877,G（年龄信息增益）,=0.9537-0.6877,=0.2660,（1）,决策树算法,45,第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),决策树算法,46,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,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）,决策树算法,47,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第5步计算信誉的熵,信誉分二个组：,良好，优秀,E（信誉）= 0.9048,信誉信息增益=0.9537-0.9048,=0.0453,（4）,决策树算法,48,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第6步计算选择节点,年龄信息增益=0.9537-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）,决策树算法,49,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,年龄,青年,中年,老年,买/,不买,买,买/,不买,叶子,决策树算法,50,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,青年买与不买比例为128/256,S1(买)=128,S2（不买）= 256,S=S1+S2=384,P1=128/384,P2=256/384,I(S1,S2)=I(128,256),=-P1Log2P1-P2Log2P2,=-(P1Log2P1+P2Log2P2),=0.9183,决策树算法,51,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,如果选择收入作为节点,分高、中、低,平均信息期望（加权总和）：,E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592,Gain(收入) =,I(128, 256),- E(收入)=,0.9183, 0.4592 = 0.4591,I(0,128)=0,比例: 128/384=0.3333,I(64,128)=0.9183,比例: 192/384=0.5,I(64,0)=0,比例: 64/384=0.1667,注意,决策树算法,52,第6章 决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/,不买,买,叶子,叶子,叶子,决策树算法,53,第6章 决策树,ID3 决策树建立算法,1 决定分类属性；,2 对目前的数据表，建立一个节点N,3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上,标出所属的类,4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少,数服从多数的原则在树叶上标出所属类别,5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作,为节点N的测试属性,6 节点属性选定后，对于该属性中的每个值：,从N生成一个分支，并将数据表中与该分支有关的数据收集形,成分支节点的数据表，在表中删除节点属性那一栏,如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,54,第6章 决策树,决策树的数据准备,原始表,决策树算法,55,第6章 决策树,整理后的数据表,决策树的数据准备,Data cleaning,删除/减少noise，,补填missing values,Data transformation,数据标准化（data normalization）,数据归纳（generalize data to higher-level,concepts using concept,hierarchies）,例如：年龄归纳为老、中、青三类,控制每个属性的可能值不超过七种,（最好不超过五种）,Relevance analysis,对于与问题无关的属性：删,对于属性的可能值大于七种,又不能归纳的属性：删,决策树算法,56,第6章 决策树,决策树的数据准备,决策树算法,处理连续属性值,决策树算法比较适合处理离散数值的属性。实际应用中,属性是连续的或者离散的情况都比较常见。,在应用连续属性值时，在一个树结点可以将属性Ai的值,划分为几个区间。然后信息增益的计算就可以采用和离散值,处理一样的方法。原则上可以将Ai的属性划分为任意数目的,空间。C4.5中采用的是二元分割（Binary Split）。需要找出,一个合适的分割阈值。,参考C4.5算法 Top 10 algorithms in data mining,Knowledge Information System 2008 14:137,57,第6章 决策树,决策树算法,ID3算法小结,ID3算法是一种经典的决策树学习算法，由Quinlan于1979年,提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节,点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值,变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节,点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于,同一类。,58,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（1）,通过ID3算法来实现客户流失的预警分析，找出客户流失的,特征，以帮助电信公司有针对性地改善客户关系，避免客户流失,利用决策树方法进行数据挖掘，一般有如下步骤：,数据预处,理、决策树挖掘操作,，模式评估和应用。,电信运营商的客户流失有三方面的含义：一是指客户从一个,电信运营商转网到其他电信运营商，这是流失分析的重点。二是,指客户月平均消费量降低，从高价值客户成为低价值客户。三、,指客户自然流失和被动流失。,在客户流失分析中有两个核心变量：财务原因非财务原因、,主动流失被动流失。,客户流失可以相应分为四种类型：其中非财务原因主动流失,的客户往往是高价值的客户。他们会正常支付服务费用，并容易,对市场活动有所响应。这种客户是电信企业真正需要保住的客户。,59,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（2）,数据预处理,数据挖掘的处理对象是大量的数据，这些数据一般存储在数,据库系统中（该用户相关数据存储在其CRM中），是长期积累的,结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般,包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、,归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃,至正确性都有关键性的影响。,该公司经过多年的电脑化管理，已有大量的客户个人基本信息,(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名,用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间,（竣工时间）、地址、职业、用户类别、客户流失（用户状态）,等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面,向属性的归纳等方法去掉不相关或弱相关属性。,60,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（3）,属性删除：将有大量不同取值且无概化操作符的属性或者可用其,它属性来代替它的较高层概念的那些属性删除。比如客户信息表,中的用户标识、身份证号码等，它们的取值太多且无法在该取值,域内找到概化操作符，应将其删除，得到表1。,表1 客户信息表,年龄,学历,职业,缴费方式,在网时长,费用变化率,客户流失,58,大学,公务员,托收,13,10%,NO,47,高中,工人,营业厅缴费,9,42%,NO,26,研究生,公务员,充值卡,2,63%,YES,28,大学,公务员,营业厅缴费,5,2.91%,NO,32,初中,工人,营业厅缴费,3,2.3%,NO,42,高中,无业人员,充值卡,2,100%,YES,68,初中,无业人员,营业厅缴费,9,2.3%,NO,61,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（4）,属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻,进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含,中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分,共分3类：Z1一Z3；,缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。,连续型属性概化为区间值：表中年龄、费用变化率和在网时间为,连续型数据，由于建立决策树时，用离散型数据进行处理速度最,快，因此对连续型数据进行离散化处理，根据专家经验和实际计,算信息增益，在“在网时长”属性中，通过检测每个划分，得到在,阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则,这个属性的范围就变为5：H1,H2。而在“年龄”属性中，,信息增益有两个锋值，分别在40和50处，因而该属性的范围变为,40-50即变为青年，中年，老年：N1,N2,N3；费,用变化率：指（当月话费近3个月的平均话费）/近3个月的平,均话费）0，F1:30%，F2：30%-99%, F3:100%变为,F1,F2,F3。,62,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（5）,63,YES,NO,年 龄,职 业,YES,缴费方式,YES,YES,NO,YSES,NO,NO,在网时长,NO,F1,F2,F3,N1,N2,N3,T1,T2,T3,Z1,Z2,Z3,H1,H2,费用变化率,第6章 决策树,决策树算法,ID3算法实际应用-在电信行业应用实例（6）,在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率,为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客,户一般不会流失，费用变化率在30%99%的客户有可能流失，其中年龄在4050岁之间,的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较,短的客户容易流失；年龄较大的客户，则工人容易流失。,64,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,65,第6章 决策树,决策树研究问题,理想的决策树有三种：,(1)叶子结点数最少；,(2)叶子结点深度最小；,(3)叶子结点数最少且叶子结点深度最小。,然而，洪家荣等人已经证明了要找到这种最优的决策树是NP难,题。因此，决策树优化的目的就是要找到尽可能趋向于最优的,决策树。,66,第6章 决策树,关于过渡拟合,上述的决策树算法增长树的每一个分支的深度，直到恰好能,对训练样例比较完美地分类。实际应用中，当数据中有噪声或训练,样例的数量太少以至于不能产生目标函数的有代表性的采样时，该,策略可能会遇到困难。,在以上情况发生时，这个简单的算法产生的树会过渡拟合训练,样例（过渡拟合：Over Fitting）.,决策树研究问题,67,关于过渡拟合,第6章 决策树,对于一个假设，当存在其它的假设对训练样例的拟合比它差，,但事实上在实例的整个分布上（包含训练集合以外的实例）表现得,却更好时，则称该假设过度拟合训练样例。,过度拟合：给定一个假设空间H，一个假设hH，如果存在其,它的假设h1,H ,使得在训练样例上h的错误率比h1小，但在整个实,例发布上h1的错误率比h小，则称假设h过度拟合训练数据,过度拟合产生的原因：噪声，训练样例太小等,决策树研究,问题,68,关于过渡拟合,第6章 决策树,对学习算法是否成功的真正测试是看它对于训练中未见到的,数据的执行性能。,训练过程应该包含训练样本和验证样本。验证样本用于测试,训练后的性能。如果验证结果差，则需要考虑采用不同的结构重,新进行训练，例如使用更大的样本集，或者改变从连续值到离散,值得数据转换等。,通常应该建立一个验证过程，在训练最终完成后用来检测训,练结果的泛化能力。,决策树研究,问题,69,关于过渡拟合,第6章 决策树,分类模型的误差,一般可以将分类模型的误差分为：,1、训练误差（Training Error）；,2、泛化误差（Generalization Error）,决策树研究问题,70,关于过渡拟合,第6章 决策树,分类模型的误差,训练误差是在训练记录上误分类样本比例；,泛化误差是模型在未知记录上的期望误差；,一个好的模型不仅要能够很好地拟合训练数据，而且对未知,样本也要能够准确地分类。,一个好的分类模型必须具有低的训练误差和泛化误差。因为,一个具有低训练误差的模型，其泛化误差可能比具有较高训练误,差的模型高。（训练误差低，泛化误差高，称为过渡拟合）,决策树研究,问题,71,关于过渡拟合,第6章 决策树,模型过渡拟合的潜在因素,（1）噪声导致的过渡拟合；,错误的类别值/类标签，属性值等,（2）缺乏代表性样本所导致的过渡拟合,根据少量训练记录作出的分类决策模型容易受过渡拟合的,影响。由于训练样本缺乏代表性的样本，在没有多少训练,记录的情况下，学习算法仍然继续细化模型就会导致过渡,拟合。,决策树研究,问题,72,关于过渡拟合,第6章 决策树,模型过渡拟合的潜在因素,名称,体温,胎生,4条腿,冬眠,哺乳动物,蝾螈,冷血,N,Y,Y,N,虹鳉,冷血,Y,N,N,N,鹰,恒温,N,N,N,N,弱夜鹰,恒温,N,N,Y,N,鸭嘴兽,恒温,Y,Y,Y,Y,哺乳动物分类的训练样例,体温,恒温,冷血,冬眠,N,Y,N,N,4条腿,Y,N,N,Y,名称,体温,胎生,4条腿,冬眠,哺乳动物,人,恒温,Y,N,N,Y,大象,恒温,Y,Y,N,Y,鸽子,恒温,N,N,N,N,哺乳动物分类的训练样例,按照训练模型。人和大象都不是,哺乳动物。决策树作出这样的判,断是因为只有一个训练样例具有,这些特点（鹰，恒温，不冬眠）,被划分为非哺乳动物。,该例清楚表明，当决策树的叶节,点没有足够的代表性时，可能会,预测错误。,决策树研究,问题,73,关于过渡拟合,第6章 决策树,解决过度拟合的手段：,1 及早停止树增长；,2 后修剪法。,决策树研究,问题,74,关于过渡拟合,第6章 决策树,1 及早停止树增长,由于决策树学习要从候选集合众选择满足给定标准的,最大化属性，并且不回溯，也就是我们常说的爬山策略，其,选择往往会是局部最优而不是全局最优。树结构越复杂，则,过渡拟合发生的可能性越大。因此，要选择简单的模型。,Occan法则（又称Occan剃刀 Occan Razor）:具有相同,泛化误差的两个模型，较简单的模型比复杂的模型更可取。,决策树研究,问题,75,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）,在训练过程中允许对数据的过渡拟合，然后再对树进行修剪,该方法称为后剪枝法。,决策树研究,问题,76,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,一棵通过,训练集合,学好的决策树,决策树研究,问题,77,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,对以上的决策树通过右侧的,验证集合进行测试，发现其,有5个错分类。,决策树研究,问题,78,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,18，19，20,1，2，3，4,5，,6，7，8,9，10，11，12,13，14,，15，16，17,错分类5个，6，7，8，13，14,决策树研究,问题,79,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,第1步 将决策树规则化,规则1 IF A=Y AND B=Y,THEN +,规则2 IF A=Y AND B=N AND C=Y,THEN +,规则3 IF A=Y AND B=N AND C=N,THEN ,规则4 IF A=N,THEN -,A,B,负,C,正,正,负,Y,Y,Y,N,N,N,决策树研究,问题,80,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,规则1 IF A=Y AND B=Y,THEN +,规则2 IF A=Y AND B=N AND C=Y,THEN +,规则3 IF A=Y AND B=N AND C=N,THEN ,规则4 IF A=N,THEN -,规则,分类正确的数目,分类错误的数目,精度,1,5,3,5/8,2,4,0,4/4,3,3,2,3/5,4,3,0,3/3,第2步 规则精度的计算,决策树研究,问题,81,规则2与规则4精度为100%，保留,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,规则,分类正确的数目,分类错误的数目,精度,1,5,3,5/8,2,4,0,4/4,3,3,2,3/5,4,3,0,3/3,第3步 对规则进行修剪,决策树研究,问题,?,82,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,第3步 对规则进行修剪-最终规则集合为,规则1 IF A=Y,AND B=Y,THEN +,规则2 IF A=Y AND B=N AND C=Y,THEN +,规则3 IF,A=Y AND B=N AND,C=N,THEN ,规则4 IF A=N,THEN -,原始规则集合,规则1 IF A=Y,THEN +,规则2 IF A=Y AND B=N AND C=Y,THEN +,规则3 IF C=N,THEN ,规则4 IF A=N,THEN -,最终规则集合,决策树研究,问题,83,关于过渡拟合,第6章 决策树,后修剪法（后剪枝法）例,第4步 根据精度和泛化能力对对规则进行排序,IF A=N THEN - 18，19，20,IF A=Y AND B=N AND C=Y THEN + 9,10,11,12,IF C=N THEN 6,7,8,13,14,15,16,17,IF A=Y THEN +1,2,3,4,5,尽管13，14仍然被错分，但整个模型的精度提高了,决策树研究,问题,84,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,85,第6章 决策树,主要参考文献,几个数据,万方数据库中查询涉及决策树的学位论文；,时间跨度是2005-2009；,查询结果是245篇（硕士论文居多）,按照以下三个领域分类：,1 利用决策树解决实际问题；,2 利用决策树与其它数据挖掘（机器学习）结合改进；,3 有关决策树的改进方法。,约150篇,约100篇,86,第6章 决策树,主要参考文献,几个数据,万方数据库中查询涉及决策树的期刊论文,时间跨度是2005-2009；,查询结果是982篇,按照以下三个领域分类：,1 利用决策树解决实际问题；,2 利用决策树与其它数据挖,掘（机器学习）结合改进；,3 有关决策树的改进方法。,约600篇,约400篇,非计算机领域占相当部分,计算机领域的主要期刊没有,一篇,以研究与发展为例，前100篇中有4篇,初略估计1000篇中有40篇，平均每年,8篇，该期刊每年发表文章360篇，,占比8/360=2.2%.研究与发展录用率,约8-10%。可以初略推算出每年收到,的关于决策树方面的论文约80-100篇,87,第6章 决策树,主要参考文献,几个数据,以上几个关于决策树的数据也许能够表明，尽管决策树非常古老，,但目前仍然有相当部分的研究人员和研究项目和工程项目。仍然,是硕士研究生可以加以研究的主要方向。,另外，通过对这些数据的分析，我也想告诉大家，数据是非常宝贵,的。特别是学校科研项目多数是研究项目，对海量数据集合的获得,非常不容易。而目前数据挖掘研究和应用往往和大数据集合有关。,像网络日志、万方数据、国外数据挖掘通用数据集合（一般都比较,小）等都是我们可以利用的数据集合。,88,