决策树算法及应用拓展.ppt

1、决策树算法及应用拓展,内容简介： 概述 预备知识 决策树生成(Building Decision Tree) 决策树剪枝(Pruning Decision Tree) 捕捉变化数据的挖掘方法 小结,概述(一),传统挖掘方法的局限性 只重视从数据库中提取规则，忽视了库中数据的变化 挖掘所用的数据来自稳定的环境，人为干预较少,概述(二),捕捉新旧数据变化的目的： 挖掘出变化的趋势 例：啤酒尿布 阻止/延缓不利变化的发生 例：金融危机银行的信贷策略 差异挖掘算法的主要思想： 合理比较新/旧数据的挖掘结果，并清晰的描述其变化部分,预备知识一(Building Tree),基本思想： 用途：提取分类规则

2、，进行分类预测,使用决策树进行分类,决策树 一个树性的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布 决策树生成算法分成两个步骤 树的生成 开始，数据都在根节点 递归的进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到一个叶子节点,决策树算法,基本算法（贪心算法） 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如, informati

3、on 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 in

4、dex (IBM IntelligentMiner) 能够适用于种类和数值字段,信息增益度度量(ID3/C4.5),任意样本分类的期望信息： I(s1,s2,sm)=Pi log2(pi) (i=1.m) 其中，数据集为S，m为S的分类数目， Pi Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分类Ci上的样本数 由A划分为子集的熵： E(A)= (s1j+ +smj)/s * I(s1j+ +smj) A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,sm) E(A),训练集(举例),ID3算法,使用信息增益进行属性选择,Class P: buys_comp

5、uter = “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,=30,40,no,no,yes,yes,yes,30.40,基尼指数 Gini Index (IBM IntelligentMiner),集合T包含N个类别的记录，那么其Gini指标就是 pj 类别j出现的频率

6、 如果集合T分成两部分 N1 and N2 。那么这个分割的Gini就是 提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).,预备知识二(Pruning Tree),目的： 消除决策树的过适应(OverFitting)问题 实质：消除训练集中的异常和噪声 两种方法： 先剪枝法(Public 算法) 后剪枝法(Sprint 算法),两种剪枝标准,最小描述长度原则(MDL) 思想：最简单的解释最期望的 做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树” 期望错误率最小原则 思想：选择期望错误率最小的子树进行剪枝

7、对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍,Cost of Encoding Data Records,对n条记录进行分类编码的代价(2种方法) n 记录数，k 类数目，ni属于类i的记录数,Cost of Encoding Tree,编码树结构本身的代价 编码每个分裂节点的代价 确定分类属性的代价 确定分类属性值的代价 & 其中，v是该节点上不同属性值的个数 编码每个树叶上的记录分类的代价,剪枝算法,设N为欲计算其最小代价的节点 两种情形： N是叶结点C(S)+1 Cost1 N是内部节点，有两个子节点N1、N2 已剪去N1、N2，N成为叶子节点 Cost1 计算

8、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 ch

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

10、界 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个分裂点的子树代价的下界(

11、包括确定分裂节点属性的代价) Public(V) V split value 同上，还包括确定分裂节点值的代价,Public(S)算法(一),相关概念,Public(S)算法(二),定理： 任何以N为根结点且有S个分裂点的子树的代价至少是2*S+1+S*log a+ ni i=s+2.k 证明： 编码树结构代价 2*S+1 确定节点分裂属性的代价 S*log a 编码S+1个叶子结点的代价 ni i=s+2.k,Public(S)算法(证明一),证明：编码S+1个叶子节点的代价至少为 ni i=s+2.k 相关概念： 1.主要类(Majority Class):if , 有 ，则Ci为主要类

12、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) nij 编码具有类 i 且位于叶子节点 j 的记录的代价是nij 所有少数类的代价 Cost= ni i少数类,计算minCost_S的代码,Procedure computeMinCostS(Node N) If k=1 return (C(S)+1) S=1 tmpCost=2*S+1+S*log

13、 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)示例,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)算法,计算

14、分类节点值的代价： 编码叶子节点记录的代价 i=1.k (1) 在所有内部节点编码分裂节点值的代价 (2) 总代价 (1)+(2) 其中，Cj是叶子节点j上的主要类；M是S+1个叶子节点上的主要类的集合,算法比较,Sprint: 传统的二阶段“构造剪枝”算法 Public(1):用保守的估计值1取代欲扩展节点的代价下界 Public(S):考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界 Public(V):比前者准确，需计算确定结点上属性值的代价下界,实验数据(Real-life),实验结果(一),产生的节点数目,实验结果(二),执行时间(S),算法结果分析,总体上，比Spri

15、nt算法有较大改进 相对于最后的剪枝树仍有多余的结点，有待改进 挖掘效率与数据分布及噪声有关,言归正传捕捉数据变化的挖掘方法,新生成一棵决策树 与旧树完全没有关系 生成一棵相关的树 未达到旧树中叶节点的深度 超出了旧树中相应节点的深度 相同的属性，最好的划分(best cut) 相同的属性，相同的划分,方法三的对应算法,使新树与旧树有相同的属性和划分，且能及早停止 测试在旧树中每个叶子节点的错误变化的情况 进一步生成新的树 剪枝移除那些无预测特性的分枝 比较新、旧树，识别变化部分,标识几种不同的变化类型,区域的连接：旧树中的划分不必要 边界的移动：旧树中的划分移到了新的位置 进一步细化(Refinement):旧树中的叶结点不足以描述新生成数据 类标号变化：旧树中的节点类标号发生了变化 错误率的变化 覆盖率的变化：某个节点具有的数据量的比率,小结,Building Decision Tree算法 Pruning Decision Tree算法 Public