决策树算法及科学应用拓展

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

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

3、到一个叶子节点 决策树算法及科学应用拓展 决策树算法 n基本算法（贪心算法） n自上而下分而治之的方法 n开始时，所有的数据都在根节点 n属性都是种类字段 (如果是连续的，将其离散化) n所有记录用所选属性递归的进行分割 n属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain) n停止分割的条件 n一个节点上的数据都是属于同一个类别 n没有属性可以再用于对数据进行分割 决策树算法及科学应用拓展 伪代码(Building Tree) Procedure BuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q While Q is not

4、Empty do 取出队列Q中的第一个节点N if N 不纯 (Pure) for 每一个属性 A 估计该节点在A上的信息增益 选出最佳的属性，将N分裂为N1、N2 决策树算法及科学应用拓展 属性选择的统计度量 n信息增益Information gain (ID3/C4.5) n所有属性假设都是种类字段 n经过修改之后可以适用于数值字段 n基尼指数Gini index (IBM IntelligentMiner) n能够适用于种类和数值字段 决策树算法及科学应用拓展 信息增益度度量(ID3/C4.5) n任意样本分类的期望信息： nI(s1,s2,sm)=Pi log2(pi) (i=1.m)

5、 n其中，数据集为S，m为S的分类数目， Pi nCi为某分类标号，Pi为任意样本属于Ci的概率， si为分类Ci上的样本数 n由A划分为子集的熵： nE(A)= (s1j+ +smj)/s * I(s1j+ +smj) nA为属性，具有V个不同的取值 n信息增益：Gain(A)= I(s1,s2,sm) E(A) | | S Si 决策树算法及科学应用拓展 训练集(举例) ageincome studentcredit_ratingbuys_computer =30highnofairno 40mediumnofairyes 40lowyesfairyes 40lowyesexcellent

6、no 3140 lowyesexcellentyes =30mediumnofairno 40mediumyesfairyes 40mediumnoexcellentno ID3算法 决策树算法及科学应用拓展 使用信息增益进行属性选择 gClass P: buys_computer = “yes” gClass N: buys_computer = “no” gI(p, n) = I(9, 5) =0.940 gCompute the entropy for age: Hence Similarly agepiniI(pi, ni) 40320.971 971.0)2, 3( 14 5 )0

7、,4( 14 4 )3 ,2( 14 5 )( I IIageE 048. 0)_( 151. 0)( 029. 0)( ratingcreditGain studentGain incomeGain )(),()(ageEnpIageGain 决策树算法及科学应用拓展 Decision Tree (结果输出结果输出) age? overcast student?credit rating? noyesfairexcellent 40 nonoyesyes yes 30.40 决策树算法及科学应用拓展 基尼指数 Gini Index (IBM IntelligentMiner) n集合T包含N

8、个类别的记录，那么其Gini指标就是 pj 类别j出现的频率 n如果集合T分成两部分 N1 and N2 。那么这个分割的 Gini就是 n提供最小Ginisplit 就被选择作为分割的标准(对于每个 属性都要遍历所有可以的分割方法). n j p j Tgini 1 2 1)( )()()( 2 2 1 1 T gini N N T gini N N T gini split 决策树算法及科学应用拓展 预备知识二(Pruning Tree) n目的： n消除决策树的过适应(OverFitting)问题 n实质：消除训练集中的异常和噪声 n两种方法： n先剪枝法(Public 算法) n后剪枝

9、法(Sprint 算法) 决策树算法及科学应用拓展 两种剪枝标准 n最小描述长度原则(MDL) n思想：最简单的解释最期望的 n做法：对Decision-Tree 进行二进位编码， 编码所需二进位最少的树即为“最佳剪枝 树” n期望错误率最小原则 n思想：选择期望错误率最小的子树进行剪 枝 n对树中的内部节点计算其剪枝/不剪枝可能 出现的期望错误率，比较后加以取舍 决策树算法及科学应用拓展 Cost of Encoding Data Records n对n条记录进行分类编码的代价(2种方法) nn 记录数，k 类数目，ni属于 类i的记录数 !1 ! log) 1 1 log( nkn n k

10、 kn )2/( log 2 log 2 1 log*)( 2/ k nk n ni niSC k i 决策树算法及科学应用拓展 Cost of Encoding Tree n编码树结构本身的代价 n编码每个分裂节点的代价 n确定分类属性的代价 n确定分类属性值的代价 & 其中，v是该节点上不同属性值的个数 n编码每个树叶上的记录分类的代价 )22log( v ) 1log( v 决策树算法及科学应用拓展 剪枝算法 n设N为欲计算其最小代价的节点 n两种情形： nN是叶结点C(S)+1 Cost1 nN是内部节点，有两个子节点N1、N2 n已剪去N1、N2，N成为叶子节点 Cost1 n计算N

11、节点及其子树的代价，使用递归过程 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 minCos

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

13、法的伪代码 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 决策树算

14、法及科学应用拓展 计算子树代价下界 nPublic(1) n假设节点N的代价至少是1 nPublic(S) S split n计算以N为根且包含S个分裂点的子树代价 的下界(包括确定分裂节点属性的代价) nPublic(V) V split value n同上，还包括确定分裂节点值的代价 决策树算法及科学应用拓展 Public(S)算法(一) n相关概念 决策树算法及科学应用拓展 Public(S)算法(二) n定理： n任何以N为根结点且有S个分裂点的子树的 代价至少是2*S+1+S*log a+ ni i=s+2.k n证明： n编码树结构代价 2*S+1 n确定节点分裂属性的代价 S*l

15、og a n编码S+1个叶子结点的代价 ni i=s+2.k 决策树算法及科学应用拓展 Public(S)算法(证明一) n证明：编码S+1个叶子节点的代价至少 为 ni i=s+2.k n相关概念： 1.主要类(Majority Class):if , 有 ，则Ci为主要类 2.少数类(Minority Class): if then Cj为少数类 CiCCk kjijnn majorityCCj 决策树算法及科学应用拓展 Public(S)算法(证明二) n题设：子树N有S个分裂点(Split),K个类 n S+1个叶子节点 n 至多有S+1个主要类 n 至少有K-S-1个少数类 n 取C

16、i为某少数类,C(Sj)为编码叶子节点j上记录的代价 n n 又有 C(S) nij n 编码具有类 i 且位于叶子节点 j 的记录的代价是nij n 所有少数类的代价 Cost= ni i少数类 ij ij ij ij ijij n n n n nSjEnSjC log*)(*)( 2 j ij ni n 决策树算法及科学应用拓展 计算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

17、tmpCost=tmpCost+2+log a-ns+2 S+ Return minC(S)+1,tmpCost 决策树算法及科学应用拓展 Public(S)示例 ageCar type label 16 truck high 24 sports high 32 sportsMedi 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 11 16,truck,high 24,sports,h

18、igh 32,sports,medi65,family,low 34,truck,low 1 决策树算法及科学应用拓展 Public(V)算法 n计算分类节点值的代价： n编码叶子节点记录的代价 i=1.k (1) n在所有内部节点编码分裂节点值的代价 (2) 总代价 (1)+(2) 其中，Cj是叶子节点j上的主要类；M是S+1个叶子节 点上的主要类的集合 1 1 | S j j Mi i Mi ijScnn 11: )(min)( 1 1 SjjScVjScVj S j 决策树算法及科学应用拓展 算法比较 nSprint: 传统的二阶段“构造剪枝”算 法 nPublic(1):用保守的估计值

19、1取代欲扩展节 点的代价下界 nPublic(S):考虑具有分裂点的子树，同时 计算为确定分裂节点及其属性的代价下 界 nPublic(V):比前者准确，需计算确定结点 上属性值的代价下界 决策树算法及科学应用拓展 实验数据(Real-life) DataSet Canner CarLetterSatimageshuttlevehicleyeast NO_CA0600000 NO_NA9016369188 N_Class242675410 N_R(Te)21456766322000145005591001 N_R(Tr)4961161133684435435005591001 决策树算法及科学

20、应用拓展 实验结果(一) Dateset DS1DS2DS3DS4DS5DS6DS7 Sprint 2197326565753189325 Public11783321556553141237 PublicS1571297945753115169 PublicV 1565287543553107163 Max rat40%48%14%51%0%77%99% Nodes9371991185513543 产生的节点数目产生的节点数目 决策树算法及科学应用拓展 实验结果(二) Dateset DS1DS2DS3DS4DS5DS6DS7 Sprint0.871.59334.9177.65230.6211.986.65 Public10.821.51285.56 167.78229.2110.585.55 PublicS0.831.44289.70 166.44230.269.814.94 PublicV 0.811.4530