咨询工具：决策树算法及应用拓展

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,决策树算法及应用拓展,内容简介：,概述,预备知识,决策树生成(,Building Decision Tree),决策树剪枝(,Pruning Decision Tree),捕捉变化数据的挖掘方法,小结,概述(一),传统挖掘方法的局限性,只重视从数据库中提取规则，忽视了库中数据的变化,挖掘所用的数据来自稳定的环境，人为干预较少,概述(二),捕捉新旧数据变化的目的：,挖掘出变化的趋势,例：啤酒尿布,阻止/延缓不利变化的发生,例：金融危机银行的信贷策略,差异挖掘算法的主要思想：,合理,比较新/旧数据的挖掘结果，并清晰的描述其变化部分,预备知识一(,Building Tree),基本思想：,用途：提取分类规则，进行分类预测,判定树分类算法,output,训练集,决策树,input,使用决策树进行分类,决策树,一个树性的结构,内部节点上选用一个属性进行分割,每个分叉都是分割的一个部分,叶子节点表示一个分布,决策树生成算法分成两个步骤,树的生成,开始，数据都在根节点,递归的进行数据分片,树的修剪,去掉一些可能是噪音或者异常的数据,决策树使用:对未知数据进行分割,按照决策树上采用的分割属性逐层往下，直到一个叶子节点,决策树算法,基本算法（贪心算法）,自上而下分而治之的方法,开始时，所有的数据都在根节点,属性都是种类字段(如果是连续的，将其离散化),所有记录用所选属性递归的进行分割,属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain,),停止分割的条件,一个节点上的数据都是属于同一个类别,没有属性可以再用于对数据进行分割,伪代码(,Building Tree),Procedure,BuildTree,(S),用数据集,S,初始化根节点,R,用根结点,R,初始化队列,Q,While Q is not Empty do,取出队列,Q,中的第一个节点,N,if N,不纯(,Pure),for,每一个属性,A,估计该节点在,A,上的信息增益,选出最佳的属性，将,N,分裂为,N1、N2,属性选择的统计度量,信息增益,Information gain,(ID3/C4.5),所有属性假设都是种类字段,经过修改之后可以适用于数值字段,基尼指数,Gini,index,(IBM,IntelligentMiner,),能够适用于种类和数值字段,信息增益度度量(,ID3,/,C4.5),任意样本分类的期望信息：,I(s,1,s,2,s,m,)=P,i,log,2,(p,i,)(i=1.m),其中，数据集为,S，m,为,S,的分类数目，,P,i,Ci,为某分类标号，,P,i,为任意样本属于,Ci,的概率，,s,i,为分类,Ci,上的样本数,由,A,划分为子集的熵：,E(A)=(,s,1j,+,s,mj,)/,s*,I(,s,1j,+,s,mj,),A,为属性，具有,V,个不同的取值,信息增益：,Gain(A)=I(s,1,s2,sm,)E(A),训练集(举例),ID3,算法,使用信息增益进行属性选择,Class P:buys_computer=“yes”,Class N:buys_computer=“no”,I(p,n)=I(9,5)=0.940,Compute the entropy for,age,:,Hence,Similarly,Decision Tree(,结果输出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,基尼指数,Gini,Index(IBM,IntelligentMiner,),集合,T,包含,N,个类别的记录，那么其,Gini,指标就是,p,j,类别,j,出现的频率,如果集合,T,分成两部分,N,1,and,N,2,。,那么这个分割的,Gini,就是,提供最小,Gini,split,就被选择作为分割的标准(,对于每个属性都要遍历所有可以的分割方法,).,预备知识二(,Pruning Tree),目的：,消除决策树的过适应(,OverFitting,),问题,实质：消除训练集中的异常和噪声,两种方法：,先剪枝法(,Public,算法),后剪枝法(,Sprint,算法),两种剪枝标准,最小描述长度原则(,MDL),思想：最简单的解释最期望的,做法：对,Decision-Tree,进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”,期望错误率最小原则,思想：选择期望错误率最小的子树进行剪枝,对树中的,内部节点,计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍,Cost of Encoding Data Records,对,n,条记录进行分类编码的代价(2种方法),n,记录数，,k,类数目，,n,i,属于类,i,的记录数,Cost of Encoding Tree,编码树结构本身的代价,编码每个分裂节点的代价,确定分类属性的代价,确定分类属性值的代价,&,其中，,v,是,该节点上不同属性值的个数,编码每个树叶上的记录分类的代价,剪枝算法,设,N,为欲计算其最小代价的节点,两种情形：,N,是叶结点,C(S)+1,Cost1,N,是内部节点，有两个子节点,N1、N2,已剪去,N1、N2，N,成为叶子节点,Cost1,计算,N,节点及其子树的代价，使用递归过程,Csplit,(N)+1+minCost1+minCost2 ,Cost2,比较,Cost1,和,Cost2，,选取,代价较小者,作为返回值,计算最小子树代价的伪代码,Procedure,ComputeCost,&Prune(Node N),if N,是叶子节点，,return(C(S)+1),minCost1=,Compute&Prune(Node N1),minCost2=,Compute&Prune(Node N2),minCostN,=minC(S)+1,Csplit,(N)+1+minCost1,+minCost2,if,minCostN,=C(S)+1 Prune child nodes N1 and N2,return,minCostN,引入,Public,算法,一般做法：先建树，后剪枝,Public,算法：建树的同时进行剪枝,思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝,存在的问题：可能高估(,Over-Estimate),被剪节点的值,改进：采纳低估(,Under-Estimate),节点代价的策略,具体思路,三种叶节点：,有待扩展：需计算子树代价下界,不能扩展(纯节点,),剪枝后的结点,C(S)+1,改进算法的伪代码,Procedure,ComputCoste,&Prune(Node N),If N,是仍待扩展的结点，,return N,节点的代价下界,If N,是纯节点或不可扩展的叶节点,，,return(C(S)+1),两个子节点,N1、N2,minCost1=,Compute&Prune(Node N1),minCost2=,Compute&Prune(Node N2),minCostN,=minC(S)+1,Csplit,(N)+1+minCost1,+minCost2,if,minCostN,=C(S)+1 Prune child nodes N1 and N2,return,minCostN,计算子树代价下界,Public(1),假设节点,N,的代价至少是1,Public(S)S split,计算以,N,为根且包含,S,个分裂点的子树代价的下界(包括确定分裂节点属性的代价),Public(V)V split value,同上，还包括确定分裂节点值的代价,Public(S),算法(一,),相关概念,Public(S),算法(二,),定理：,任何以,N,为根结点且有,S,个分裂点的子树的代价至少是2*,S+1+S*log a+,n,i,i=s+2.k,证明：,编码树结构代价 2*,S+1,确定节点分裂属性的代价,S*log a,编码,S+1,个叶子结点的代价,n,i,i=s+2.k,Public(S),算法(证明一),证明：编码,S+1,个叶子节点的代价至少为,n,i,i=s+2.k,相关概念：,1.主要类(,Majority Class):if ,有 ，则,Ci,为主要类,2.少数类(,Minority Class):if then,Cj,为少数类,Public(S),算法(证明二),题设：子树,N,有,S,个分裂点(,Split),K,个类,S+1,个叶子节点,至多有,S+1,个主要类,至少有,K-S-1,个少数类,取,Ci,为某少数类,C(,Sj,),为编码叶子节点,j,上记录的代价,又有,C(S),n,ij,编码具有类,i,且位于叶子节点,j,的记录的代价是,n,ij,所有少数类的代价,Cost=,n,i,i,少数类,计算,minCost,_S,的代码,Procedure,computeMinCostS,(Node N),If k=1 return(C(S)+1),S=1,tmpCost,=2*S+1+S*log a+,i,ni,i=s+2.k,While s+12+log a do,tmpCost,=,tmpCost,+2+log a-ns+2,S+,Return minC(S)+1,tmpCost,Public(S),示例,age,Car type,label,16,truck,high,24,sports,high,32,sports,Medi,34,truck,low,65,family,low,16,truck,high,24,sports,high,1+,log2,1+1,1,N,65,family,low,34,truck,low,32,sports,medi,N,1+,log2,1+,log2,1,1,16,truck,high,24,sports,high,32,sports,medi,65,family,low,34,truck,low,1,Public(V),算法,计算分类节点值的代价：,编码叶子节点记录的代价,i=1.k (1),在所有内部节点编码分裂节点值的代价,(2),总代价 (1)+(2),其中，,Cj,是叶子节点,j,上的主要类；,M,是,S+1,个叶子节点上的主要类的集合,算法比较,Sprint:,传统的二阶段“构造剪枝”算法,Public(1):,用,保守的估计值1取代欲扩展节点的代价下界,Public(S):,考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界,Public(V):,比前者准确，需计算确定结点上属性值的代价下界,实验数据(,Real-life),DataSet,Canner,Car,Letter,Satimage,shuttle,vehicle,yeast,NO_CA,0,6,0,0,0,0,0,NO_NA,9,0,16,36,9,18,8,N_Class,2,4,26,7,5,4,10,N_R(Te),214,567,6632,2000,14500,559,1001,N_R(,Tr,),496,1161,13368,4435,43500,559,1001,实验结果(一),Dateset,DS1,DS2,DS3,DS4,DS5,DS6,DS7,Sprint,21,97,3265,657,53,189,325,Public1,17,83,3215,565,53,141,237,PublicS,15,71,2979,457,53,115,169,PublicV,15,65,2875,435,53,107,163,Max rat,40%,48%,14%,51%,0%,77%,99%,Nodes,9,37,1991,185,51,35,43,产生的节点数目,实验结果(二),Dateset,DS1,DS2,D