数据挖掘算法-决策树算法及应用扩展

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,决策树算法及应用拓展,内容简介：,概述,预备知识,决策树生成(Building Decision Tree),决策树剪枝(Pruning Decision Tree),捕捉变化数据的挖掘方法,小结,1,概述(一),传统挖掘方法的局限性,只重视从数据库中提取规则，忽视了库中数据的变化,挖掘所用的数据来自稳定的环境，人为干预较少,2,概述(二),捕捉新旧数据变化的目的：,挖掘出变化的趋势,例：啤酒尿布,阻止/延缓不利变化的发生,例：金融危机银行的信贷策略,差异挖掘算法的主要思想：,合理,比较新/旧数据的挖掘结果，并清晰的描述其变化部分,3,预备知识一(Building Tree),基本思想：,用途：提取分类规则，进行分类预测,判定树分类算法,output,训练集,决策树,input,4,使用决策树进行分类,决策树,一个树性的结构,内部节点上选用一个属性进行分割,每个分叉都是分割的一个部分,叶子节点表示一个分布,决策树生成算法分成两个步骤,树的生成,开始，数据都在根节点,递归的进行数据分片,树的修剪,去掉一些可能是噪音或者异常的数据,决策树使用: 对未知数据进行分割,按照决策树上采用的分割属性逐层往下，直到一个叶子节点,5,决策树算法,基本算法（贪心算法）,自上而下分而治之的方法,开始时，所有的数据都在根节点,属性都是种类字段 (如果是连续的，将其离散化),所有记录用所选属性递归的进行分割,属性的选择是基于一个启发式规则或者一个统计的度量 (如,information gain,),停止分割的条件,一个节点上的数据都是属于同一个类别,没有属性可以再用于对数据进行分割,6,伪代码(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,7,属性选择的统计度量,信息增益Information gain,(ID3/C4.5),所有属性假设都是种类字段,经过修改之后可以适用于数值字段,基尼指数Gini index,(IBM IntelligentMiner),能够适用于种类和数值字段,8,信息增益度度量(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),9,训练集(举例),ID3算法,10,使用信息增益进行属性选择,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,11,Decision Tree (结果输出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,12,基尼指数 Gini,Index (IBM IntelligentMiner),集合T包含N个类别的记录，那么其Gini指标就是,p,j,类别j出现的频率,如果集合T分成两部分,N,1,and,N,2,。那么这个分割的Gini就是,提供最小Gini,split,就被选择作为分割的标准(,对于每个属性都要遍历所有可以的分割方法,).,13,预备知识二(Pruning Tree),目的：,消除决策树的过适应(OverFitting)问题,实质：消除训练集中的异常和噪声,两种方法：,先剪枝法(Public 算法),后剪枝法(Sprint 算法),14,两种剪枝标准,最小描述长度原则(MDL),思想：最简单的解释最期望的,做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”,期望错误率最小原则,思想：选择期望错误率最小的子树进行剪枝,对树中的,内部节点,计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍,15,Cost of Encoding Data Records,对n条记录进行分类编码的代价(2种方法),n 记录数，k 类数目，n,i,属于类i的记录数,16,Cost of Encoding Tree,编码树结构本身的代价,编码每个分裂节点的代价,确定分类属性的代价,确定分类属性值的代价,&,其中，v是该节点上不同属性值的个数,编码每个树叶上的记录分类的代价,17,剪枝算法,设N为欲计算其最小代价的节点,两种情形：,N是叶结点C(S)+1 Cost1,N是内部节点，有两个子节点N1、N2,已剪去N1、N2，N成为叶子节点 ,Cost1,计算N节点及其子树的代价，使用递归过程,Csplit(N)+1+minCost1+minCost2 ,Cost2,比较Cost1和Cost2，选取,代价较小者,作为返回值,18,计算最小子树代价的伪代码,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,19,引入Public算法,一般做法：先建树，后剪枝,Public算法：建树的同时进行剪枝,思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝,存在的问题：可能高估(Over-Estimate)被剪节点的值,改进：采纳低估(Under-Estimate)节点代价的策略,20,具体思路,三种叶节点：,有待扩展：需计算子树代价下界,不能扩展(纯节点),剪枝后的结点,C(S)+1,21,改进算法的伪代码,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,22,计算子树代价下界,Public(1),假设节点N的代价至少是1,Public(S) S split,计算以N为根且包含S个分裂点的子树代价的下界(包括确定分裂节点属性的代价),Public(V) V split value,同上，还包括确定分裂节点值的代价,23,Public(S)算法(一),相关概念,24,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,25,Public(S)算法(证明一),证明：编码S+1个叶子节点的代价至少为, n,i,i=s+2.k,相关概念：,1.主要类(Majority Class):if ,有 ，则Ci为主要类,2.少数类(Minority Class): if then,Cj为少数类,26,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少数类,27,计算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,28,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,29,Public(V)算法,计算分类节点值的代价：,编码叶子节点记录的代价,i=1.k (1),在所有内部节点编码分裂节点值的代价,(2),总代价 (1)+(2),其中，Cj是叶子节点j上的主要类；M是S+1个叶子节点上的主要类的集合,30,算法比较,Sprint: 传统的二阶段“构造剪枝”算法,Public(1):用保守的估计值1取代欲扩展节点的代价下界,Public(S):考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界,Public(V):比前者准确，需计算确定结点上属性值的代价下界,31,实验数据(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,32,实验结果(一),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,产生的节点数目,33,实验结果(二),Dateset,DS1,DS2,DS3,DS4,DS5,DS6,DS7,Sprint,0.87,1.59,334.9,177.65,230.62,11.98,6.65,Public1,0.82,1.51,285.56,167.78,229.21,10.58,5.55,PublicS,0.83,1.44,289.70,166.44,230.26,9.81,4.94,PublicV,0.81,1.45,300.48,159.83,227.26,9.64,4.89,Max rat,9%,0%,17%,11%,2%,2%,3%,执行时间(S),34,算法结果分析,总体上，比Sprint算法有较大改进,相对于最后的剪枝树仍有多余的结点，有待改进,挖掘效率与数据分布及噪声有关,35,言归正传捕捉数据变化的挖掘方法,新生成一棵决策树,与旧树完全没有关系,生成一棵相关的树,未达到旧树中叶节点的深度,超出了旧树中相应节点的深度,相同的属性，最好的划分(best cut),相同的属性，相同的划分,36,方法三的对应算法,使新树与旧树有相同的属性和划分，且能及早停止,测试在旧树中每个叶子节点的错误变化的情况,进一步生成新的树,剪枝移除那些无预测特性的分枝,比较新、旧树，识别变化部分,37,标识几种不同的变化类型,区域的连接：旧树中的划分不必要,边界的移动：旧树中的划分移到了新的位置,进一步细化(Refinement):旧树中的叶结点不足以描述新生成数据,类标号变化：旧树中的节点类标号发生了变化,错误率,的变化,覆盖率,的变化：某个节点具有的数据量的比率,38,小结,Building Decision Tree算法,Pruning Decision Tree算法,Public 算法,Public(1)算法,Public(s)算法,Public(v)算法,识别数据变化的挖掘算法,39,个人观点,40,计算分裂点属性代价下界的算法代码,Procedure ComputeMinCostS(Node N),If K=1 return (C(S)+1),S=1,tmpCost=2*S+1+S*log a +,n,i i=s+1.k,While S+12+log a do,tmpCost=tmpCost+2+log a ,s+ ,Return min C(S)+1,tmpCost ,41,