1、决策树算法及应用拓展n内容简介：n概述n预备知识n决策树生成(Building Decision Tree)n决策树剪枝(Pruning Decision Tree)n捕捉变化数据的挖掘方法n小结决策树算法及应用拓展教材ppt决策树算法及应用拓展教材ppt概述(一)n传统挖掘方法的局限性n只重视从数据库中提取规则，忽视了库中数据的变化n挖掘所用的数据来自稳定的环境，人为干预较少概述(二)n捕捉新旧数据变化的目的：n挖掘出变化的趋势n例：啤酒尿布n阻止/延缓不利变化的发生n例：金融危机银行的信贷策略n差异挖掘算法的主要思想：n合理合理比较新/旧数据的挖掘结果，并清晰的描述其变化部分预备知识一(B
2、uilding Tree)n基本思想：n用途：提取分类规则，进行分类预测判定树分类算法output训练集决策树input使用决策树进行分类n决策树 n一个树性的结构n内部节点上选用一个属性进行分割n每个分叉都是分割的一个部分n叶子节点表示一个分布n决策树生成算法分成两个步骤n树的生成n开始，数据都在根节点n递归的进行数据分片n树的修剪n去掉一些可能是噪音或者异常的数据n决策树使用:对未知数据进行分割n按照决策树上采用的分割属性逐层往下，直到一个叶子节点决策树算法n基本算法（贪心算法）n自上而下分而治之的方法n开始时，所有的数据都在根节点n属性都是种类字段(如果是连续的，将其离散化)n所有记录用
3、所选属性递归的进行分割n属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain)n停止分割的条件n一个节点上的数据都是属于同一个类别n没有属性可以再用于对数据进行分割伪代码(Building Tree)Procedure BuildTree(S)用数据集S初始化根节点R 用根结点R初始化队列QWhile Q is not Empty do 取出队列Q中的第一个节点Nif N 不纯(Pure)for 每一个属性 A估计该节点在A上的信息增益 选出最佳的属性，将N分裂为N1、N2属性选择的统计度量n信息增益Information gain(ID3/C4.5)n所有属
4、性假设都是种类字段n经过修改之后可以适用于数值字段n基尼指数Gini index(IBM IntelligentMiner)n能够适用于种类和数值字段信息增益度度量(ID3/C4.5)n任意样本分类的期望信息：nI(s1,s2,sm)=Pi log2(pi)(i=1.m)n其中，数据集为S，m为S的分类数目，PinCi为某分类标号，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)|SSi训练集(举例)ageincome st
5、udentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoID3算法使用信息增益进行属性选择gClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I(9,5)=0.940gCompute the entropy for age:Hen
6、ceSimilarlyagepiniI(pi,ni)40320.971971.0)2,3(145)0,4(144)3,2(145)(IIIageE048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGainDecision Tree(结果输出结果输出)age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.40基尼指数 Gini Index(IBM IntelligentMiner)n集合T包含N个类别的记录，那
7、么其Gini指标就是pj 类别j出现的频率n如果集合T分成两部分 N1 and N2。那么这个分割的Gini就是n提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).njpjTgini121)()()()(2211TginiNNTginiNNTginisplit预备知识二(Pruning Tree)n目的：n消除决策树的过适应(OverFitting)问题n实质：消除训练集中的异常和噪声n两种方法：n先剪枝法(Public 算法)n后剪枝法(Sprint 算法)两种剪枝标准n最小描述长度原则(MDL)n思想：最简单的解释最期望的n做法：对Decisio
8、n-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”n期望错误率最小原则n思想：选择期望错误率最小的子树进行剪枝n对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍Cost of Encoding Data Recordsn对n条记录进行分类编码的代价(2种方法)nn 记录数，k 类数目，ni属于类i的记录数!1!log)11log(nknnkkn)2/(log2log21log*)(2/knknniniSCkiCost of Encoding Treen编码树结构本身的代价n编码每个分裂节点的代价n确定分类属性的代价n确定分类属性值的代价&其中，v是该节
9、点上不同属性值的个数n编码每个树叶上的记录分类的代价)22log(v)1log(v剪枝算法n设N为欲计算其最小代价的节点n两种情形：nN是叶结点C(S)+1 Cost1nN是内部节点，有两个子节点N1、N2n已剪去N1、N2，N成为叶子节点 Cost1n计算N节点及其子树的代价，使用递归过程 Csplit(N)+1+minCost1+minCost2 Cost2 比较Cost1和Cost2，选取代价较小者代价较小者作为返回值计算最小子树代价的伪代码Procedure ComputeCost&Prune(Node N)if N 是叶子节点，return(C(S)+1)minCost1=Compu
10、te&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算法n一般做法：先建树，后剪枝nPublic算法：建树的同时进行剪枝n思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝n存在的问题：可能高估(Over-Estimate)被剪节点的值n改进：采纳低估(Under-Estimate)节点代价的策略
11、具体思路n三种叶节点：n有待扩展：需计算子树代价下界n不能扩展(纯节点)n剪枝后的结点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
12、 child nodes N1 and N2 return minCostN计算子树代价下界nPublic(1)n假设节点N的代价至少是1nPublic(S)S splitn计算以N为根且包含S个分裂点的子树代价的下界(包括确定分裂节点属性的代价)nPublic(V)V split valuen同上，还包括确定分裂节点值的代价Public(S)算法(一)n相关概念Public(S)算法(二)n定理：n任何以N为根结点且有S个分裂点的子树的代价至少是2*S+1+S*log a+ni i=s+2.k n证明：n编码树结构代价 2*S+1n确定节点分裂属性的代价 S*log a n编码S+1个叶子结
13、点的代价 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 thenCj为少数类CiCCkkjijnn majorityCCjPublic(S)算法(证明二)n题设：子树N有S个分裂点(Split),K个类n S+1个叶子节点n 至多有S+1个主要类n 至少有K-S-1个少数类n 取Ci为某少数类,C(Sj)为编码叶子节点j上记录的代价n n 又有 C(S)nij n 编码具有类 i 且位于叶子
14、节点 j 的记录的代价是nijn 所有少数类的代价 Cost=ni i少数类ijijijijijijnnnnnSjEnSjClog*)(*)(2jijnin计算minCost_S的代码Procedure computeMinCostS(Node N)If k=1 return(C(S)+1)S=1tmpCost=2*S+1+S*log a+i ni i=s+2.k While s+12+log a dotmpCost=tmpCost+2+log a-ns+2S+Return minC(S)+1,tmpCostPublic(S)示例 ageCar type label 16 truck high
15、 24 sports high 32 sportsMedi 34 truck low 65 family low16,truck,high24,sports,high1+log21+11N65,family,low34,truck,low32,sports,mediN1+log21+log21116,truck,high24,sports,high32,sports,medi65,family,low34,truck,low1Public(V)算法n计算分类节点值的代价：n编码叶子节点记录的代价 i=1.k (1)n在所有内部节点编码分裂节点值的代价 (2)总代价 (1)+(2)其中，Cj是叶
16、子节点j上的主要类；M是S+1个叶子节点上的主要类的集合11|SjjMiiMiijScnn11:)(min)(11SjjScVjScVjSj算法比较nSprint:传统的二阶段“构造剪枝”算法nPublic(1):用保守的估计值1取代欲扩展节点的代价下界nPublic(S):考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界nPublic(V):比前者准确，需计算确定结点上属性值的代价下界实验数据(Real-life)DataSet Canner CarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Cla
17、ss242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001实验结果(一)Dateset DS1DS2DS3DS4DS5DS6DS7Sprint 2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV 1565287543553107163Max rat40%48%14%51%0%77%99%Nodes9371991185513543产生的节点数目产生的节点数目实验结果(二)Dateset DS1
18、DS2DS3DS4DS5DS6DS7Sprint0.871.59334.9177.65230.6211.986.65Public10.821.51285.56 167.78229.2110.585.55PublicS0.831.44289.70 166.44230.269.814.94PublicV 0.811.45300.48 159.83227.269.644.89Max rat9%0%17%11%2%2%3%执行时间执行时间(S)决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材算法结果分析n总体上，比Sprint
19、算法有较大改进n相对于最后的剪枝树仍有多余的结点，有待改进n挖掘效率与数据分布及噪声有关决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材言归正传捕捉数据变化的挖掘方法n新生成一棵决策树n与旧树完全没有关系n生成一棵相关的树n未达到旧树中叶节点的深度n超出了旧树中相应节点的深度n相同的属性，最好的划分(best cut)n相同的属性，相同的划分决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材方法三的对应算法n使新树与旧树有相同的属性和划分，且能及
20、早停止n测试在旧树中每个叶子节点的错误变化的情况n进一步生成新的树n剪枝移除那些无预测特性的分枝n比较新、旧树，识别变化部分决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材标识几种不同的变化类型n区域的连接：旧树中的划分不必要n边界的移动：旧树中的划分移到了新的位置n进一步细化(Refinement):旧树中的叶结点不足以描述新生成数据n类标号变化：旧树中的节点类标号发生了变化n错误率的变化n覆盖率的变化：某个节点具有的数据量的比率决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材p
21、pt优秀课件精品课件培训课件培训教材小结nBuilding Decision Tree算法nPruning Decision Tree算法nPublic 算法nPublic(1)算法nPublic(s)算法nPublic(v)算法n识别数据变化的挖掘算法决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材个人观点决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材计算分裂点属性代价下界的算法代码2sn2snProcedure ComputeMinCostS(Node N)If K=1 return(C(S)+1)S=1tmpCost=2*S+1+S*log a+ni i=s+1.kWhile S+12+log a do tmpCost=tmpCost+2+log a s+Return min C(S)+1,tmpCost 决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材决策树算法及应用拓展教材ppt优秀课件精品课件培训课件培训教材
