数据挖掘——第四章分类.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1.,提名,(Nominations),2006,年,9,月在,香港举办的国际会议,ICDM,会议上,邀请,ACM KDD,创新大奖,(Innovation Award),和,IEEE ICDM,研究贡献奖,(Research Contributions Award),的获奖者们来参与数据挖掘,10,大算法的选举,每人提名,10,种他认为最重要的算法,。,除一人未参与外,其他获奖者均给出了算法的提名,。,每个提名中均需同时给出以下信息：,-,(a),算法名称,-,(b),提名理由摘要,-,(c),算法的代表性论文,每个提名算法都应该被相关领域的研究者广泛引用和使用，每位提名者给出的同类算法应该是数据挖掘重要应用领域的代表,。,2.,审核,(Verification),在,2006,年,10,月,通过,Google Scholar,对每个提名算法的引用情况进行了审核,从候选名单中删除了低于,50,篇论文引用的算法,最终剩下,18,种提名算法通过了审核,它们分属,10,类数据挖掘主题,邀请更多的专业人士来从这些候选算法中投票选出,10,大算法，他们包括,-,(a)KDD-06,、,ICDM 06,和,SDM 06,的程序委员会成员,(Program Committee members),-,(b)ACM KDD,创新大奖和,IEEE ICDM,研究贡献奖的获奖者们,根据票数排名筛选出,10,大算法,(,如果票数相同，则按字母顺序进行排名,),3.,投票,(Voting),数据挖掘,10,大算法,产生过程,三步鉴定流程,18,种通过审核的候,选,算法,算法陈述,数据挖掘,10,大算法：一览,1,2,3,4,开放式讨论,5,C4.5,CART,Nave Bayes,kNN,SVM,EM,Apriori,FP-Tree,18,种通过审核的候选算法,分类,(Classification),C4.5,Quinlan,J.R.1993.C4.5:Programs for Machine Learning.Morgan Kaufmann Publishers Inc.,CART,:L.Breiman,J.Friedman,R.Olshen,and C.Stone.Classification and Regression Trees.Wadsworth,Belmont,CA,1984.,K Nearest Neighbours(kNN),:Hastie,T.and Tibshirani,R.1996.Discriminant Adaptive Nearest Neighbor Classification.IEEE Trans.Pattern Anal.Mach.Intell.(TPAMI).18,6(Jun.1996),607-616.,Naive Bayes,Hand,D.J.,Yu,K.,2001.Idiots Bayes:Not So Stupid After All?Internat.Statist.Rev.69,385-398.,统计学习,(Statistical Learning),SVM,:Vapnik,V.N.1995.The Nature of Statistical Learning Theory.Springer-Verlag New York,Inc.,EM,:McLachlan,G.and Peel,D.(2000).Finite Mixture Models.J.Wiley,New York.,关联分析,(Association Analysis),Apriori,:Rakesh Agrawal,Ramakrishnan Srikant.Fast Algorithms for Mining Association Rules.In VLDB 94.,FP-Tree,:Han,J.,Pei,J.,and Yin,Y.2000.Mining frequent patterns without candidate generation.In SIGMOD 00.,十大经典算法,1.,C4.5,（,ID3,算法）,2.,The k-means algorithm,即,K-Means,算法,3.,Support vector machines,4.,The Apriori algorithm,5.,最大期望,(EM),算法,6.,PageRank,7.,AdaBoost,8.,kNN:k-nearest neighbor classification,9.,Naive Bayes,10.,CART:,分类与回归树,决策树基础,女孩家长,安排相亲,女孩,不厌其烦,女孩,提出决策树,父母筛选,候选男士,决策树基础,实例,No.,头痛,肌肉痛体温,患流感,1,是,(1),是,(1),正常,(0),N(0),2,是,(1),是,(1),高,(1),Y(1),3,是,(1),是,(1),很高,(2),Y(1),4,否,(0),是,(1),正常,(0),N(0),5,否,(0),否,(0),高,(1),N(0),6,否,(0),是,(1),很高,(2),N(1),7,是,(1),否,(0),高,(1),Y(1),生活工作中的决策（做？不做？）,总是优先选取最具有决定性意义的,辅助条件进行判定,如,打不打室外羽毛球？,刮风是最具有决定意义的因素,主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,决策树,决策树基本概念,关于分类问题,分类（,Classification,）任务就是通过学习获得一个目标函数,（,Target Function,）,f,将每个属性集,x,映射到一个预先定义好的类,标号,y,。,分类任务的输入数据是纪录的集合，每条记录也称为实例,或者样例。用元组,(X,y),表示，其中，,X,是属性集合，,y,是一个,特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）,决策树分类的步骤,12,数据库,2025/10/14 周二,训练样本,(training samples),建立模型,测试样本,(testing samples),评估模型,决策树,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题,一般包括两个步骤：,1,、模型构建（归纳）,通过对训练集合的归纳，建立分类模型。,2,、预测应用（推论）,根据建立的分类模型，对测试集合进行测试。,决策树,决策树基本概念,解决分类问题的一般方法,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,？,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,决策树,决策树基本概念,决策树,决策树是一种典型的分类方法，首先对数据进行处理，利用,归纳算法生成可读的规则和决策树，然后使用决策对新数据进行,分析。本质上决策树是通过一系列规则对数据进行分类的过程。,决策树,决策树基本概念,决策树的优点,1,、推理过程容易理解，决策推理过程可以表示成,If Then,形式；,2,、推理过程完全依赖于属性变量的取值特点；,3,、可自动忽略目标变量没有贡献的属性变量，也为判断属性,变量的重要性，减少变量的数目提供参考。,决策树,决策树基本概念,关于归纳学习,(1),决策树技术发现数据模式和规则的核心是归纳算法。,归纳是从特殊到一般的过程。归纳推理从若干个事实中表,征出的特征、特性和属性中，通过比较、总结、概括而得出一,个规律性的结论。,归纳推理试图从对象的一部分或整体的特定的观察中获得,一个完备且正确的描述。即从特殊事实到普遍性规律的结论。,归纳对于认识的发展和完善具有重要的意义。人类知识的增长,主要来源于归纳学习。,决策树,决策树基本概念,关于归纳学习,(2),归纳学习的过程就是寻找一般化描述的过程。这种一般性,描述能够解释给定的输入数据，并可以用来预测新的数据。,锐角三角形内角和等于,180,度；,钝角三角形内角和等于,180,度；三角形内角和,直角三角形内角和等于,180,度；等于,180,度,已知三角形,ABC,，,A,角等于,76,度，,B,角等于,89,度，则其,C,角等于,15,度,归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：,任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。,决策树,决策树基本概念,关于归纳学习,(3),主要内容,决策树基本概念,决策树算法,决策树研究问题,主要参考文献,决策树,决策树算法,与决策树相关的重要算法,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,决策树基础,女孩家长,安排相亲,女孩,不厌其烦,女孩,提出决策树,父母筛选,候选男士,决策树基础,有向无环 二叉,/,多叉树,父节点：没有子节点的节点,内部节点：有父节点、子节点的节点,叶节点：有父节点没有子节点的节点,父节点,内部节点,叶节点,分割属性,+,判断规则,类别标识,决策树基础,父节点,内部节点,叶节点,（类别标识）,（分割属性,+,判断规则）,决策树基础,训练集：,数据的集合，用于生成树（模型）,测试集：,用于测试树（模型）的性能,决策树作用：,通过训练集,算法指导下,生成决策树,新数据进行划分,否则是,“三拍”,决策,训练集,算法,决策树,新数据,决策,决策树基础,实例,No.,头痛,肌肉痛,体温,患流感,1,是,(1),是,(1),正常,(0),N(0),2,是,(1),是,(1),高,(1),Y(1),3,是,(1),是,(1),很高,(2),Y(1),4,否,(0),是,(1),正常,(0),N(0),5,否,(0),否,(0),高,(1),N(0),6,否,(0),是,(1),很高,(2),N(1),7,是,(1),否,(0),高,(1),Y(1),决策树怎么做？谁是父节点？,谁是下一层子节点？为什么是它？,头,-,肌肉,-,体温,头,-,体温,-,肌肉,肌肉,-,头,-,体温,肌肉,-,体温,-,头,体温,-,头,-,肌肉,体温,-,肌肉,-,头,三 拍 决 策,决策树,决策树算法,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？,即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？,又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,谁在买计算机？,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树的用途,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,谁在买计算机？,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树的用途,决策树算法,决策树,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树中最上面的结点称为根结点。,是整个决策树的开始。每个分支是一,个新的决策结点，或者是树的叶子。,每个决策结点代表一个问题或者决策,.,通常对应待分类对象的属性。,每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个,测试。对每个结点上问题的不同测试输出导致不同的分枝，最后,会达到一个叶子结点这一过程就是利用决策树进行分类的过程，,利用若干个变量来判断属性的类别,决策树,决策树算法,CLS,（,Concept Learning System,）算法,CLS,算法是早期的决策树学习算法。它是许多决策树学习算法,的基础。,CLS,基本思想,从一棵空决策树开始，选择某一属性（分类属性）作为测试,属性。该测试属性对应决策树中的决策结点。根据该属性的值的,不同，可将训练样本分成相应的子集，如果该子集为空，或该子,集中的样本属于同一个类，则该子集为叶结点，否则该子集对应,于决策树的内部结点，即测试结点，需要选择一个新的分类属性,对该子集进行划分，直到所有的子集都为空或者属于同一类。,决策树,人员,眼睛颜色,头发颜色,所属人种,1,黑色,黑色,黄种人,2,蓝色,金色,白种人,3,灰色,金色,白种人,4,蓝色,红色,白种人,5,灰色,红色,白种人,6,黑色,金色,混血,7,灰色,黑色,混血,8,蓝色,黑色,混血,决策树算法,CLS,算法,决策树,人员,眼睛颜色,头发颜色,所属人种,1,黑色,黑色,黄种人,2,蓝色,金色,白种人,3,灰色,金色,白种人,4,蓝色,红色,白种人,5,灰色,红色,白种人,6,黑色,金色,混血,7,灰色,黑色,混血,8,蓝色,黑色,混血,决策树算法,CLS,算法,-,决策树的构建,眼睛颜色,1,，,6,2,，,4,，,8,3,，,5,，,7,黑色,兰色,灰色不属于同一类，非叶结点,决策树,眼睛颜色,头发颜色,头发颜色,头发颜色,黑色,兰色,灰色,决策树算法,CLS,算法,黄种人,1,混血,6,白种人,2,白种人,4,混血,8,白种人,3,白种人,5,混血,7,黑色,金色,金色,红色,黑色,金色,红色,黑色,决策树,决策树算法,CLS,算法,1,生成一颗空决策树和一张训练样本属性集,;,2,若训练样本集,T,中所有的样本都属于同一类,则生成结点,T,并终止学习算法,;,否则,3,根据,某种策略,从训练样本属性表中选择属性,A,作为测试属性,生成测试结点,A,4,若,A,的取值为,v1,v2,vm,则根据,A,的取值的,不同,将,T,划分成,m,个子集,T1,T2,Tm;,5,从训练样本属性表中删除属性,A;,6,转步骤,2,对每个子集递归调用,CLS;,决策树,CLS,算法问题,在步骤,3,中，根据某种策略从训练样本属性表中选择属性,A,作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。,举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中,1,表示包含食物，,0,表示不包含,决策树算法,决策树,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,不缺钙,学生膳食结构和缺钙调查表,决策树,CLS,算法问题,决策树算法,采用不同的测试属性及其先后顺序将会生成不同的决策树,鸡肉,猪肉,猪肉,牛肉,牛肉,牛肉,不缺钙（,2,）,缺钙（,3,，,6,）,不缺钙（,4,）,不缺钙（,10,）,缺钙（,5,）,不缺钙（,1,）,鱼肉,缺钙（,5,）,不缺钙（,7,，,9,）,是,否,是,否,否,否,否,否,否,是,是,是,是,是,决策树,牛奶,不缺钙,（,1,，,2,，,4,，,7,，,9,，,10,）,缺钙,（,3,，,5,，,6,，,8,）,CLS,算法问题,决策树算法,在上例中，显然生成的两种决策树的复杂性和分类意义相差,很大由此可见，选择测试属性是决策树学习算法中需要研究的重,要课题。,决策树,ID3,决策树算法,ID3,算法主要针对属性选择问题。是决策树学习方法中最,具影响和最为典型的算法。,该方法使用信息增益度选择测试属性。,当获取信息时，将不确定的内容转为确定的内容，因此信,息伴着不确定性。,从直觉上讲，小概率事件比大概率事件包含的信息量大。,如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的,信息量大。,如何度量信息量的大小？,决策树基础,C4.5,算法,ID3,算法,决策树基础,信息论基础,选哪个？,怎么生成好的？,Next One!,香农的信息论,1948,年，香农提出了“信息熵”,(shng),的概念，解决了对信息的量化问题。,信息量的大小，由其所消除的,不确定性大小来衡量！,例,你已经确知的东西，别人告诉你，,你会觉得信息量不大。,信息论之父,C.E.Shannon,信息的定量描述,衡量信息多少的物理量称为,信息量,。,若概率很大，受信者事先已有所估计，则该消息信息量就很小；,若概率很小，受信者感觉很突然，该消息所含信息量就很大。,信息量的定义,根据客观事实和人们的习惯概念，函数,f,(,p,),应满足以下条件：,f,(,p,),应是概率,p,的严格单调递减函数，即当,p,1,p,2,，,f,(,p,1,),f,(,p,2,),；,当,p,=1,时，,f,(,p,)=0,；,当,p,=0,时，,f,(,p,)=,；,两个独立事件的联合信息量应等于它们分别的信息量之和。,对信息量的认识理解,信息量的定义,若一个消息,x,出现的概率为,p,，则这一消息所含的信息量为,其中，对数的底大于,1,信息量单位,以,2,为底时，单位为,bit,（,binary unit,，比特）,以,e,为底时，单位为,nat,（,natural unit,，奈特）,以,10,为底时，单位为,hart,（,Hartley,，哈特）,抛一枚均匀硬币，出现正面与反面的信息量是多少？,解：出现正面与反面的概率均为,0.5,，它们的信息量是,I,(,正,)=-lb,p,(,正,)=-lb0.5=1b,I,(,反,)=-lb,p,(,反,)=-lb0.5=1b,抛一枚畸形硬币，出现正面与反面的概率分别是,1/4，3/4，,出现正面与反面时的信息量是多少？,解：出现正面与反面的概率分别是,1/4，3/4,，它们的信息量是I,(,正,)=-lb,p,(,正,)=-lb1/4=2b,I,(,反,)=-lb,p,(,反,)=-lb3/4=0.415b,信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息,熵,，是指每个符号所含信息量的统计平均值。,m,种符号的平均信息量为,抛一枚均匀硬币的信息,熵,是多少？,解：出现正面与反面的概率均为,0.5,，信息,熵,是,抛一枚畸形硬币，出现正面与反面的概率分别是,1/4，3/4，,出现正面与反面时的信息量是多少？,解：出现正面与反面的概率分别是,1/4，3/4,，信息,熵,是,例：气象预报,52,条件自信息量,在事件,y,j,出现的条件下，随机事件,x,i,发生的条件概率为,p,(,x,i,|,y,j,),，则它的条件自信息量定义为条件概率对数的负值：,53,条件熵,在给定,y,j,条件下，,x,i,的条件自信息量为,I,(,x,i,|,y,j,),X,集合的条件熵,H(,X,|,y,j,),为,在给定,Y,(,即各个,y,j,),条件下,X,集合的,条件熵,H,(,X,|,Y,),条件熵,H,(,X,|,Y,),表示已知,Y,后，,X,的不确定度,活动,天气,是否进行垒球活动,进行,取消,晴,阴,雨,晴,阴,雨,活动,进行,取消,活动的熵,活动,有,2,个属性值，,进行,，,取消,。其熵为：,H,(,活动,)=-(9/14)*log,(9/14)-(5/14)*log,(5/14)=,0.94,活动,进行,取消,已知,户外,的,天气情况下活动,的,条件,熵,户外,有三个属性值，晴，阴和雨。其熵分别为：,H,(,活动,|,户外,=,晴,)=-(2/5)*log,2,(2/5)-(3/5)*log,2,(3/5)=0.971,H,(,活动,|,户外,=,阴,)=-(4/4)*log,2,(4/4)=0,H,(,活动,|,户外,=,雨,)=-(3/5)*log,2,(3/5)-(2/5)*log,2,(2/5)=0.971,活动,天气,进行,取消,晴,阴,雨,已知,户外,时,活动,的,条件,熵,H,(,活动,|,户外)=5/14*,H,(,活动,|,户外,=,晴,)+4/14*,H,(,活动,|,户外,=,阴,)+5/14*,H,(,活动,|,户外,=,雨,),=(5/14)*0.971+(4/14)*0+(5/14)*0.971,=0.693,晴,阴,雨,平均互信息,I,(,活动,;,户外,)=,H,(,活动,),-,H,(,活动,|,户外,),=0.94-0.693,=0.246,是否适合打垒球的决策表,天气,温度,湿度,风速,活动,晴,炎热,高,弱,取消,晴,炎热,高,强,取消,阴,炎热,高,弱,进行,雨,适中,高,弱,进行,雨,寒冷,正常,弱,进行,雨,寒冷,正常,强,取消,阴,寒冷,正常,强,进行,晴,适中,高,弱,取消,晴,寒冷,正常,弱,进行,雨,适中,正常,弱,进行,晴,适中,正常,强,进行,阴,适中,高,强,进行,阴,炎热,正常,弱,进行,雨,适中,高,强,取消,活动的熵,H,(,活动,)=-(9/14)*lb,(9/14)-(5/14)*lb,(5/14)=,0.94,天气,温度,湿度,风速,活动,阴,炎热,高,弱,进行,雨,适中,高,弱,进行,雨,寒冷,正常,弱,进行,阴,寒冷,正常,强,进行,晴,寒冷,正常,弱,进行,雨,适中,正常,弱,进行,晴,适中,正常,强,进行,阴,适中,高,强,进行,阴,炎热,正常,弱,进行,晴,炎热,高,弱,取消,晴,炎热,高,强,取消,雨寒冷,正常,强,取消,晴,适中,高,弱,取消,雨,适中,高,强,取消,已知天气时活动的条件熵,H,(,活动,|,天气,)=5/14*,H,(,活动,|,天气,=,晴,)+4/14*,H,(,活动,|,天气,=,阴,)+5/14*,H,(,活动,|,天气,=,雨,),=(5/14)*0.971+(4/14)*0+(5/14)*0.971,=0.693,温度,湿度,风速,天气,活动,寒冷,正常,弱,晴,进行,适中,正常,强,晴,进行,炎热,高,弱,晴,取消,炎热,高,强,晴,取消,适中,高,弱,晴,取消,炎热,高,弱,阴,进行,寒冷,正常,强,阴,进行,适中,高,强,阴,进行,炎热,正常,弱,阴进行,适中,高,弱,雨,进行,寒冷,正常,弱,雨,进行,适中,正常,弱,雨,进行,寒冷,正常,强,雨,取消,适中,高,强,雨,取消,天气,湿度,风速,温度,活动,阴,高,弱,炎热,进行,阴,正常,弱,炎热,进行,晴,高,弱,炎热,取消,晴,高,强,炎热,取消,雨,高,弱,适中,进行,雨,正常,弱,适中,进行,晴,正常,强,适中,进行,阴,高,强,适中,进行,晴,高,弱,适中,取消,雨,高,强,适中,取消,雨,正常,弱,寒冷,进行,阴,正常,强,寒冷,进行,晴,正常,弱,寒冷,进行,雨,正常,强,寒冷,取消,已知,温度,时,活动,的条件熵,H,(,活动,|,温度,),=0.911,天气,温度,风速,湿度,活动,阴,炎热,弱,高,进行,雨,适中,弱,高,进行,阴,适中,强,高,进行,晴,炎热,弱,高,取消,晴,炎热,强,高,取消,晴,适中,弱,高,取消,雨,适中,强,高,取消,雨,寒冷,弱,正常,进行,阴,寒冷,强,正常,进行,晴,寒冷,弱,正常,进行,雨,适中,弱,正常,进行,晴,适中,强,正常,进行,阴,炎热,弱,正常,进行,雨,寒冷,强,正常,取消,H,(,活动,|,湿度,),=0.789,已知,湿度,时,活动,的条件熵,天气,温度,湿度,风速,活动,阴,寒冷,正常,强,进行,晴,适中,正常,强,进行,阴,适中,高,强,进行,晴,炎热,高,强,取消,雨,寒冷,正常,强,取消,雨适中,高,强,取消,阴,炎热,高,弱,进行,雨,适中,高,弱,进行,雨,寒冷,正常,弱,进行,晴,寒冷,正常,弱,进行,雨,适中,正常,弱,进行,阴,炎热,正常,弱,进行,晴,炎热,高,弱,取消,晴,适中,高,弱,取消,H,(,活动,|,风速,),=0.892,已知,风速,时,活动,的条件熵,各互信息量,I,(,活动,;,天气,)=,H,(,活动,)-,H,(,活动,|,天气,)=0.94-0.693=0.246,I,(,活动,;,温度,)=,H,(,活动,)-,H,(,活动,|,温度,)=0.94-0.911=0.029,I,(,活动,;,湿度,)=,H,(,活动,)-,H,(,活动,|,湿度,)=0.94-0.789=0.151,I,(,活动,;,风速,)=,H,(,活动,)-,H,(,活动,|,风速,)=0.94-0.892=0.048,天气,温度,湿度,风速,活动,晴,炎热,高,弱,取消,晴,炎热,高,强,取消,阴,炎热,高,弱,进行,雨,适中,高,弱,进行,雨,寒冷,正常,弱,进行,雨,寒冷,正常,强,取消,阴,寒冷,正常,强,进行,晴,适中,高,弱,取消,晴,寒冷,正常,弱,进行,雨,适中,正常,弱,进行,晴,适中,正常,强,进行,阴,适中,高,强,进行,阴,炎热,正常,弱,进行,雨,适中,高,强,取消,温度,湿度,风速,活动,寒冷,正常,弱,进行,适中,正常,强,进行,炎热,高,弱,取消,炎热,高,强,取消,适中,高,弱,取消,温度,湿度,风速,活动,适中,高,弱,进行,寒冷,正常,弱,进行,适中,正常,弱,进行,寒冷,正常,强,取消,适中,高,强,取消,温度,湿度,风速,活动,炎热,高,弱,进行,寒冷,正常,强,进行,适中,高,强,进行,炎热,正常,弱,进行,阴,晴,雨,天气,温度,湿度,风速,活动,晴,寒冷,正常,弱,进行,晴,适中,正常,强,进行,晴,炎热,高,弱,取消,晴,炎热,高,强,取消,晴,适中,高,弱,取消,阴,炎热,高,弱,进行,阴,寒冷,正常,强,进行,阴,适中,高,强,进行,阴,炎热,正常,弱,进行,雨,适中,高,弱,进行,雨,寒冷正常,弱,进行,雨,适中,正常,弱,进行,雨,寒冷,正常,强,取消,雨,适中,高,强,取消,ID3算法生成的决策树,决策规则（产生式规则）,天气,=,阴,进行,天气,=,晴,湿度,=,正常,进行,天气,=,晴,湿度,=,高,取消,天气,=,雨,风速,=,强,取消,天气,=,雨,风速,=,弱,进行,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,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,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2,步计算条件属性的熵,条件属性共有,4,个。分别是年龄、,收入、学生、信誉。,分别计算不同属性的信息增益。,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,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,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,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,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,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,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,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,）,决策树算法,决策树,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,