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

《数据挖掘算法决策树算法及应用扩展》由会员分享，可在线阅读，更多相关《数据挖掘算法决策树算法及应用扩展（41页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据挖掘算法决策树算法及应用扩展,*,数据挖掘算法决策树算法及应用扩展,2024/11/29,数据挖掘算法决策树算法及应用扩展,概述(一),传统挖掘方法的局限性,只重视从数据库中提取规则，忽视了库中数据的变化,挖掘所用的数据来自稳定的环境，人为干预较少,数据挖掘算法决策树算法及应用扩展,概述(二),捕捉新旧数据变化的目的：,挖掘出变化的趋势,例：啤酒尿布,阻止/延缓不利变化的发生,例：金融危机银行的信贷策略,差异挖掘算法的主要思想：,合理,比较新/旧数据的挖掘结果，并清晰的描述其变化部分,数据挖掘算法决策树

2、算法及应用扩展,预备知识一(Building Tree),基本思想：,用途：提取分类规则，进行分类预测,判定树分类算法,output,训练集,决策树,input,数据挖掘算法决策树算法及应用扩展,使用决策树进行分类,决策树,一个树性的结构,内部节点上选用一个属性进行分割,每个分叉都是分割的一个部分,叶子节点表示一个分布,决策树生成算法分成两个步骤,树的生成,开始，数据都在根节点,递归的进行数据分片,树的修剪,去掉一些可能是噪音或者异常的数据,决策树使用:对未知数据进行分割,按照决策树上采用的分割属性逐层往下，直到一个叶子节点,数据挖掘算法决策树算法及应用扩展,决策树算法,基本算法（贪心算法）,

3、自上而下分而治之的方法,开始时，所有的数据都在根节点,属性都是种类字段(如果是连续的，将其离散化),所有记录用所选属性递归的进行分割,属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain,),停止分割的条件,一个节点上的数据都是属于同一个类别,没有属性可以再用于对数据进行分割,数据挖掘算法决策树算法及应用扩展,伪代码(Building Tree),Procedure BuildTree(S),用数据集S初始化根节点R,用根结点R初始化队列Q,While Q is not Empty do,取出队列Q中的第一个节点N,if N 不纯(Pure),for 每一个属

4、性 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

5、,为任意样本属于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,

6、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,就被选择作为分割的标准(,对于每个属性都

7、要遍历所有可以的分割方法,).,数据挖掘算法决策树算法及应用扩展,预备知识二(Pruning Tree),目的：,消除决策树的过适应(OverFitting)问题,实质：消除训练集中的异常和噪声,两种方法：,先剪枝法(Public 算法),后剪枝法(Sprint 算法),数据挖掘算法决策树算法及应用扩展,两种剪枝标准,最小描述长度原则(MDL),思想：最简单的解释最期望的,做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”,期望错误率最小原则,思想：选择期望错误率最小的子树进行剪枝,对树中的,内部节点,计算其剪枝/不剪枝可能出现的期望错误率，比较后加以

8、取舍,数据挖掘算法决策树算法及应用扩展,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

9、、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+minCost

10、1,+minCost2,if minCostN=C(S)+1 Prune child nodes N1 and N2,return minCostN,数据挖掘算法决策树算法及应用扩展,引入Public算法,一般做法：先建树，后剪枝,Public算法：建树的同时进行剪枝,思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝,存在的问题：可能高估(Over-Estimate)被剪节点的值,改进：采纳低估(Under-Estimate)节点代价的策略,数据挖掘算法决策树算法及应用扩展,具体思路,三种叶节点：,有待扩展：需计算子树代价下界,不能扩展(纯节点),剪枝后的结点,C(S)+1

11、,数据挖掘算法决策树算法及应用扩展,改进算法的伪代码,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

12、,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+

13、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)为

14、编码叶子节点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,数据挖掘算法决策树算法及应

15、用扩展,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,数据挖掘算法决策树算法及应用扩

16、展,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,