分类的决策树算法ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,决策树,决策树基本概念,决策树算法,决策树决策树基本概念决策树算法,1,主要内容,决策树基本概念,决策树算法,主要内容决策树基本概念决策树算法,2,决策树基本概念,关于分类问题,分类（,Classification,）任务就是通过学习获得一个目标函数,（,Target Function,）,f,将每个属性集,x,映射到一个预先定义好的类,标号,y,。,分类任务的输入数据是纪录的集合，每条记录也称为实例,或者样例。用元组,(X,y),表示，其中，,X,是属性集合，,y,是一个,特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）,决策树基本概念关于分类问题 分类（Classi,3,决策树基本概念,关于分类问题,名称,体温,表皮覆盖,胎生,水生动物,飞行动物,有腿,冬眠,类标号,人类,恒温,毛发,是,否,否,是,否,哺乳动物,海龟,冷血,鳞片,否,半,否,是,否,爬行类,鸽子,恒温,羽毛,否,否,是,是,否,鸟类,鲸,恒温,毛发,是,是,否,否,否,哺乳类,X,y,分类与回归,分类目标属性,y,是离散的，回归目标属性,y,是连续的,决策树基本概念关于分类问题名称体温表皮覆盖胎生水生动物飞行动,4,决策树基本概念,解决分类问题的一般方法,分类技术是一种根据输入数据集建立分类模型的系统方法。,分类技术一般是用一种学习算法确定分类模型，该模型可以很好,地拟合输入数据中类标号和属性集之间的联系。学习算法得到的,模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的,类标号。因此，训练算法的主要目标就是要建立具有很好的泛化,能力模型，即建立能够准确地预测未知样本类标号的模型。,分类方法的实例包括：决策树分类法、基于规则的分类法、,神经网络、支持向量级、朴素贝叶斯分类方法等。,决策树基本概念解决分类问题的一般方法 分类技术,5,决策树基本概念,解决分类问题的一般方法,通过以上对分类问题一般方法的描述，可以看出分类问题,一般包括两个步骤：,1,、模型构建（归纳）,通过对训练集合的归纳，建立分类模型。,2,、预测应用（推论）,根据建立的分类模型，对测试集合进行测试。,决策树基本概念解决分类问题的一般方法 通过以上,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,？,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y,7,决策树基本概念,决策树,决策树是一种典型的分类方法，首先对数据进行处理，利用,归纳算法生成可读的规则和决策树，然后使用决策对新数据进行,分析。本质上决策树是通过一系列规则对数据进行分类的过程。,决策树基本概念决策树 决策树是一种典型的分类方,8,决策树基本概念,决策树的优点,1,、推理过程容易理解，决策推理过程可以表示成,If Then,形式；,2,、推理过程完全依赖于属性变量的取值特点；,3,、可自动忽略目标变量没有贡献的属性变量，也为判断属性,变量的重要性，减少变量的数目提供参考。,决策树基本概念决策树的优点,9,主要内容,决策树基本概念,决策树算法,主要内容决策树基本概念决策树算法,10,决策树算法,与决策树相关的重要算法,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,决策树算法与决策树相关的重要算法1、Hunt,Marin和S,11,决策树算法,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？,即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？,又：你需要多少有关这位客人的信息才能回答这个问题？,决策树的用途,决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不,12,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,谁在买计算机？,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树的用途,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,13,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,谁在买计算机？,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树的用途,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,14,决策树算法,决策树的表示,决策树的基本组成部分：决策结点、分支和叶子。,年龄？,学生？,信誉？,买,青,中,老,否,是,优,良,不买,买,买,不买,决策树中最上面的结点称为根结点。,是整个决策树的开始。每个分支是一,个新的决策结点，或者是树的叶子。,每个决策结点代表一个问题或者决策,.,通常对应待分类对象的属性。,每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个,测试。对每个结点上问题的不同测试输出导致不同的分枝，最后,会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，,利用若干个变量来判断属性的类别,决策树算法决策树的表示决策树的基本组成部分：决策结点、分支和,15,ID3,决策树算法,ID3,算法主要针对属性选择问题。是决策树学习方法中最,具影响和最为典型的算法。,该方法使用信息增益度选择测试属性。,当获取信息时，将不确定的内容转为确定的内容，因此信,息伴着不确定性。,从直觉上讲，小概率事件比大概率事件包含的信息量大。,如果某件事情是“百年一见”则肯定比“习以为常”的事件包含,的信息量,大。,如何度量信息量的大小？,ID3 决策树算法 ID3算法主要针对属性选择,16,ID3 ,信息量大小的度量,决策树算法,Shannon1948,年提出的信息论理论。事件,a,i,的信息量,I,（,a,i,）可,如下度量：,其中,p(a,i,),表示事件,a,i,发生的概率。,假设有,n,个互不相容的事件,a1,a2,a3,.,an,它们中有且仅有一个,发生，则其平均的信息量可如下度量：,ID3 信息量大小的度量决策树算法Shannon1948年,17,ID3 ,信息量大小的度量,决策树算法,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。,通常取,2,，并规定当,p(ai)=0,时,=0,ID3 信息量大小的度量决策树算法上式，对数底数可以为任何,18,信息增益,用来衡量给定的属性区分训练样例的能力，,中间（间接）表示属性,ID3,算法在生成 树的每一步使用,信息增益,从候选属性中选择属性,用熵度量样例的均一性,决策树算法,信息增益决策树算法,19,/ 34,信息增益,用熵度量样例的均一性,熵刻画了任意样例集合,S,的纯度,给定包含关于某个目标概念的正反样例的样例集,S,，那么,S,相对这个布尔型分类（函数）的熵为,信息论中对熵的一种解释：,熵,确定了,要编码集合,S,中任意成员的分类所需要的最少二进制位数；熵值越大，需要的位数越多,。,更一般地，如果目标属性具有,c,个不同的值，那么,S,相对于,c,个状态的分类的熵定义为,决策树算法,信息增益决策树算法,20,/ 34,用,信息增益,度量,熵的降低程度,属性,A,的,信息增益,，使用属性,A,分割样例集合,S,而导致的熵的降低程度,Gain (,S, A,),是,在知道属性,A,的值后可以节省的二进制位数,例子，注意是对当前样例集合计算上式,用信息增益度量熵的降低程度,21,/ 34,理解信息熵,1,、,信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么它出现的各种情况也就越多，也就是包含的内容多，我们要描述它就需要付出更多的表达才可以，也就是需要更多的信息才能确定这个变量,。,2,、,信息熵是随机变量的期望。度量信息的不确定程度。信息的熵越大，信息就越不容易搞清楚（杂乱）,。,3,、,一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵也可以说是系统有序化程度的一个度量,。,4,、,信息熵用以表示一个事物的非确定性，如果该事物的非确定性越高，你的好奇心越重，该事物的信息熵就越高,。,5,、,熵是整个系统的平均消息量。 信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高,。,6,、,处理信息就是为了把信息搞清楚，实质上就是要想办法让信息熵变小。,理解信息熵1、信息熵是用来衡量一个随机变量出现的期望值，一个,22,/ 34,理解信息增益,熵,：表示随机变量的不确定性。,条件熵,：在一个条件下，随机变量的不确定性。,信息,增益：熵,-,条件熵。表示在一个条件下，信息不确定性减少的程度。,例如,：,假设,X(,明天下雨,),的信息熵为,2,（不确定明天是否下雨,），,Y,(,如果是阴天则下雨）的条件熵为,0.01,（因为如果是阴天就下雨的概率很大，信息就少了,）,信息增益,=2-0.01=1.99,。信息增益很大。说明在获得阴天这个信息后，明天是否下雨的信息不确定性减少了,1.99,，是很多的，所以信息增益大。也就是说阴天这个信息对下雨来说是很重要的,。,理解信息增益熵：表示随机变量的不确定性。,23,/ 34,ID3 ,信息量大小的度量,决策树算法,Gain,（,S,，,A,）是属性,A,在集合,S,上的信息增益,Gain,（,S,，,A,）,= Entropy,（,S,）,-Entropy,（,S,，,A,）,Gain,（,S,，,A,）越大，说明选择测试属性对分类提供的信息越多,ID3 信息量大小的度量决策树算法Gain（S，A）是属性,24,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,25,计数,年龄,收入,学生,信誉,归类：买计算机？,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青高,26,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2,步计算条件属性的熵,条件属性共有,4,个。分别是年龄、,收入、学生、信誉。,分别计算不同属性的信息增益。,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,27,计数,年龄,收入,学生,信誉,归类：买计算机？,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青高,28,计数,年龄,收入,学生,信誉,归类：买计算机？,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青高,29,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2-3,步计算年龄的熵,年龄共分三个组：,青年、中年、老年,老年买与不买比例,为,257/127,S1(,买,)=257,S2,（不买）,=127,S=S1+S2=384,P1=257,/,384,P2=127/384,I(S1,S2,)=,I(257,，,127),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9157,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,30,计数,年龄,收入,学生,信誉,归类：买计算机？,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青高,31,计数,年龄,收入,学生,信誉,归类：买计算机？,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),决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,32,计数,年龄,收入,学生,信誉,归类：买计算机？,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,）,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,33,计数,年龄,收入,学生,信誉,归类：买计算机？,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,）,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,34,计数,年龄,收入,学生,信誉,归类：买计算机？,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,）,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,35,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,年龄,青年,中年,老年,买,/,不买,买,买,/,不买,叶子,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,36,计数,年龄,收入,学生,信誉,归类：买计算机？,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,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,37,计数,年龄,收入,学生,信誉,归类：买计算机？,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,注意,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,38,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买,/,不买,买,叶子,叶子,叶子,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,39,ID3,决策树建立算法,1,决定分类属性；,2,对目前的数据表，建立一个节点,N,3,如果数据库中的数据都属于同一个类，,N,就是树叶，在树叶上,标出所属的类,4,如果数据表中没有其他属性可以考虑，则,N,也是树叶，按照少,数服从多数的原则在树叶上标出所属类别,5,否则，根据平均信息期望值,E,或,GAIN,值选出一个最佳属性作,为节点,N,的测试属性,6,节点属性选定后，对于该属性中的每个值：,从,N,生成一个分支，并将数据表中与该分支有关的数据收集形,成分支节点的数据表，在表中删除节点属性那一栏,如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,ID3 决策树建立算法决策树算法,40,决策树的数据准备,姓名,年龄,收入,学生,信誉,电话,地址,邮编,买计算机,张三,23,4000,是,良,281-322-0328,2714 Ave. M,77388,买,李四,34,2800,否,优,713-239-7830,5606 Holly Cr,78766,买,王二,70,1900,否,优,281-242-3222,2000 Bell Blvd.,70244,不买,赵五,18,900,是,良,281-550-0544,100 Main Street,70244,买,刘兰,34,2500,否,优,713-239-7430,606 Holly Ct,78566,买,杨俊,27,8900,否,优,281-355-7990,233 Rice Blvd.,70388,不买,张毅,38,9500,否,优,281-556-0544,399 Sugar Rd.,78244,买,。,。,。,原始表,决策树算法,决策树的数据准备姓名年龄收入学生信誉电话地址邮编买计算机张三,41,计数,年龄,收入,学生,信誉,归类：买计算机？,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,。,整理后的数据表,决策树的数据准备,Data cleaning,删除,/,减少,noise,，,补填,missing values,Data transformation,数据标准化（,data normalization,）,数据归纳（,generalize data to higher-level,concepts using concept,hierarchies,）,例如：年龄归纳为老、中、青三类,控制每个属性的可能值不超过七种,（最好不超过五种）,Relevance analysis,对于与问题无关的属性：删,对于属性的可能值大于七种,又不能归纳的属性：删,决策树算法,计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高,42,决策树的数据准备,决策树算法,处理连续属性值,决策树算法比较适合处理离散数值的属性。实际应用中,属性是连续的或者离散的情况都比较常见。,在应用连续属性值时，在一个树结点可以将属性,Ai,的值,划分为几个区间。然后信息增益的计算就可以采用和离散值,处理一样的方法。原则上可以将,Ai,的属性划分为任意数目的,空间。,C4.5,中采用的是二元分割（,Binary Split,）。需要找出,一个合适的分割阈值。,参考,C4.5,算法,Top 10 algorithms in data mining,Knowledge Information System 2008 14:137,决策树的数据准备决策树算法处理连续属性值 决策,43,决策树算法,ID3,算法小结,ID3,算法是一种经典的决策树学习算法，由,Quinlan,于,1979,年,提出。,ID3,算法的基本思想是，以信息熵为度量，用于决策树节,点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值,变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节,点处的熵值为,0,。此时，每个叶子节点对应的实例集中的实例属于,同一类。,决策树算法ID3算法小结 ID3算法是一种经典,44,决策树算法,ID3,算法实际应用,-,在电信行业应用实例（,1,）,通过,ID3,算法来实现客户流失的预警分析，找出客户流失的,特征，以帮助电信公司有针对性地改善客户关系，避免客户流失,利用决策树方法进行数据挖掘，一般有如下步骤：,数据预处,理、决策树挖掘操作,，模式评估和应用。,电信运营商的客户流失有三方面的含义：一是指客户从一个,电信运营商转网到其他电信运营商，这是流失分析的重点。二是,指客户月平均消费量降低，从高价值客户成为低价值客户。三、,指客户自然流失和被动流失。,在客户流失分析中有两个核心变量：财务原因非财务原因、,主动流失被动流失。,客户流失可以相应分为四种类型：其中非财务原因主动流失,的客户往往是高价值的客户。他们会正常支付服务费用，并容易,对市场活动有所响应。这种客户是电信企业真正需要保住的客户。,决策树算法ID3算法实际应用-在电信行业应用实例（1）,45,决策树算法,ID3,算法实际应用,-,在电信行业应用实例（,2,）,数据预处理,数据挖掘的处理对象是大量的数据，这些数据一般存储在数,据库系统中（该用户相关数据存储在其,CRM,中），是长期积累的,结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般,包括数据的选择,(,选择相关的数据,),、净化,(,消除冗余数据,),、转换、,归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃,至正确性都有关键性的影响。,该公司经过多年的电脑化管理，已有大量的客户个人基本信息,(,文中简称为客户信息表,),。在客户信息表中，有很多属性，如姓名,用户号码、用户标识、用户身份证号码,(,转化为年龄,),、在网时间,（竣工时间）、地址、职业、用户类别、客户流失（用户状态）,等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面,向属性的归纳等方法去掉不相关或弱相关属性。,决策树算法ID3算法实际应用-在电信行业应用实例（2）数据预,46,决策树算法,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,决策树算法ID3算法实际应用-在电信行业应用实例（3）属性删,47,决策树算法,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,。,决策树算法ID3算法实际应用-在电信行业应用实例（4）属性概,48,表,2,转化后的客户信息表,年龄,学历,职业,缴费方式,开户时间,费用变化率,客户流失,N3,W3,Z1,T1,H2,F1,NO,N2,W2,Z2,T2,H2,F2,NO,N1,W3,Z1,T3,H1,F2,YES,N1,W3,Z1,T2,H1,F1,NO,N1,W1,Z2,T2,H1,F1,NO,N2,W2,Z3,T3,H1,F3,YES,N3,W1,Z3,T1,H2,F1,NO,决策树算法,ID3,算法实际应用,-,在电信行业应用实例（,5,）,表2 转化后的客户信息表年龄学历职业缴费方式开户时间费用变,49,YES,NO,年 龄,职 业,YES,缴费方式,YES,YES,NO,YSES,NO,NO,在网时长,NO,F1,F2,F3,N1,N2,N3,T1,T2,T3,Z1,Z2,Z3,H1,H2,费用变化率,决策树算法,ID3,算法实际应用,-,在电信行业应用实例（,6,）,在图中，,NO,表示客户不流失，,YES,表示客户流失。从图可以看出，客户费用变化率,为,100%,的客户肯定已经流失；而费用变化率低于,30%,的客户；即每月资费相对稳定的客,户一般不会流失，费用变化率在,30%,99%,的客户有可能流失，其中年龄在,40,50,岁之间,的客户流失的可能性非常大，而年龄低于,40,岁的客户，用充值卡缴费的客户和在网时间较,短的客户容易流失；年龄较大的客户，则工人容易流失。,步骤1：生成训练集和测试集,生成训练集iris.train=iris2*(1:75)-1, （意思是返回原数据集1、3、5、7、8。、149奇数行行所有列的数据）,生成测试集iris.test= iris2*(1:75), （意思是返回原数据集2、4、6、8、10、。、150偶数行所有列的数据）,步骤2：生成决策树模型,model - rpart(Species Sepal.Length + Sepal.Width + Petal.Length + Petal.Width, data = iris.train, method=class)绘制决策树fancyRpartPlot(model)步骤3：对测试集进行预测iris.rp3=predict(model, iris.test,-5, type=class) 注释：iris.test,-5的意思是去掉原测试集第5列后的数据步骤4：查看预测结果并对结果进行分析，计算出该决策树的accuracy（分类正确的样本数除以总样本数）,table(iris.test,5,iris.rp3) 注释：iris.test,5的意思是取出测试集第5列的数据R语言中使用table(data)进行频数统计,iris.rp3 setosa versicolor virginica setosa 25 0 0 versicolor 0 24 1 virginica 0 3 22accuracy=（25+24+22）/75=94.67%步骤5：生成规则,asRules(model),YESNO年 龄职 业YES缴费方式YESYESNOYS,50,步骤,1,：生成训练集和测试集,生成训练集,iris.train=iris2*(1:75)-1,（意思是返回原数据集,1,、,3,、,5,、,7,、,8,。、,149,奇数行行所有列的数据）,生成测试集,iris.test= iris2*(1:75),（意思是返回原数据集,2,、,4,、,6,、,8,、,10,、。、,150,偶数行所有列的数据）,步骤,2,：生成决策树模型,model - rpart(Species Sepal.Length + Sepal.Width + Petal.Length + Petal.Width, data = iris.train, method=class),绘制决策树,fancyRpartPlot(model),步骤,3,：对测试集进行预测,iris.rp3=predict(model, iris.test,-5, type=class),注释：,iris.test,-5,的意思是去掉原测试集第,5,列后的数据步骤,4,：查看预测结果并对结果进行分析，计算出该决策树的,accuracy,（分类正确的样本数除以总样本数）,table(iris.test,5,iris.rp3),注释：,iris.test,5,的意思是取出测试集第,5,列的数据,R,语言中使用,table(data),进行频数统计,iris.rp3 setosa versicolor virginica setosa 25 0 0 versicolor 0 24 1 virginica 0 3 22accuracy=,（,25+24+22,）,/75=94.67%,步骤,5,：生成规则,asRules(model),步骤1：生成训练集和测试集,51,/ 34,