决策树算法及应用拓展

决策树算法及应用拓展内容简介：概述预备知识决策树生成(BuildingDecisionTree)决策树剪枝(PruningDecisionTree)捕捉变化数据的挖掘方法小结概述(一)传统挖掘方法的局限性只重视从数据库中提取规则，忽视了库中数据的变化挖掘所用的数据来自稳定的环境，人为干预较少概述(二)捕捉新旧数据变化的目的：挖掘出变化的趋势例：啤酒——尿布阻止/延缓不利变化的发生例：金融危机——银行的信贷策略差异挖掘算法的主要思想：合理比较新/旧数据的挖掘结果，并清晰的描述其变化部分预备知识一(BuildingTree)基本思想：用途：提取分类规则，进行分类预测判定树分类算法output训练集决策树input使用决策树进行分类决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割伪代码(BuildingTree)ProcedureBuildTree(S)用数据集S初始化根节点R用根结点R初始化队列QWhileQisnotEmptydo{取出队列Q中的第一个节点NifN不纯(Pure){for每一个属性A估计该节点在A上的信息增益选出最佳的属性，将N分裂为N1、N2}}属性选择的统计度量信息增益——Informationgain(ID3/C4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段基尼指数——Giniindex(IBMIntelligentMiner)能够适用于种类和数值字段信息增益度度量(ID3/C4.5)任意样本分类的期望信息：I(s1,s2,……,sm)=－∑Pilog2(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)||||SSi训练集(举例)ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno30…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentnoID3算法使用信息增益进行属性选择ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarlyagepiniI(pi,ni)=30230.97130…4040040320.971971.0)2,3(145)0,4(144)3,2(145)(IIIageE048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGainDecisionTree(结果输出)age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..40基尼指数GiniIndex(IBMIntelligentMiner)集合T包含N个类别的记录，那么其Gini指标就是pj类别j出现的频率如果集合T分成两部分N1andN2。那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).njpjTgini121)()()()(2211TginiNNTginiNNTginisplit预备知识二(PruningTree)目的：消除决策树的过适应(OverFitting)问题实质：消除训练集中的异常和噪声两种方法：先剪枝法(Public算法)后剪枝法(Sprint算法)两种剪枝标准最小描述长度原则(MDL)思想：最简单的解释最期望的做法：对Decision-Tree进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”期望错误率最小原则思想：选择期望错误率最小的子树进行剪枝对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍CostofEncodingDataRecords对n条记录进行分类编码的代价(2种方法)n——记录数，k——类数目，ni——属于类i的记录数!!1!log)11log(nknnkkn)2/(log2log21log*)(2/knknniniSCkiΓπCostofEncodingTree编码树结构本身的代价编码每个分裂节点的代价确定分类属性的代价确定分类属性值的代价&其中，v是该节点上不同属性值的个数编码每个树叶上的记录分类的代价)22log(v)1log(v剪枝算法设N为欲计算其最小代价的节点两种情形：N是叶结点——C(S)+1——Cost1N是内部节点，有两个子节点N1、N2已剪去N1、N2，N成为叶子节点——Cost1计算N节点及其子树的代价，使用递归过程Csplit(N)+1+minCost1+minCost2——Cost2比较Cost1和Cost2，选取代价较小者作为返回值计算最小子树代价的伪代码ProcedureComputeCost&Prune(NodeN)ifN是叶子节点，return(C(S)+1)minCost1=Compute&Prune(NodeN1)minCost2=Compute&Prune(NodeN2)minCostN=min{C(S)+1,Csplit(N)+1+minCost1+minCost2}ifminCostN=C(S)+1PrunechildnodesN1andN2returnminCostN引入Public算法一般做法：先建树，后剪枝Public算法：建树的同时进行剪枝思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝存在的问题：可能高估(Over-Estimate)被剪节点的值改进：采纳低估(Under-Estimate)节点代价的策略具体思路三种叶节点：有待扩展：需计算子树代价下界不能扩展(纯节点)剪枝后的结点C(S)+1改进算法的伪代码ProcedureComputCoste&Prune(NodeN)IfN是仍待扩展的结点，returnN节点的代价下界IfN是纯节点或不可扩展的叶节点，return(C(S)+1)两个子节点N1、N2minCost1=Compute&Prune(NodeN1)minCost2=Compute&Prune(NodeN2)minCostN=min{C(S)+1,Csplit(N)+1+minCost1+minCost2}ifminCostN=C(S)+1PrunechildnodesN1andN2returnminCostN计算子树代价下界Public(1)假设节点N的代价至少是1Public(S)S——split计算以N为根且包含S个分裂点的子树代价的下界(包括确定分裂节点属性的代价)Public(V)V——splitvalue同上，还包括确定分裂节点值的代价Public(S)算法(一)相关概念Public(S)算法(二)定理：任何以N为根结点且有S个分裂点的子树的代价至少是2*S+1+S*loga+∑nii=s+2..k证明：编码树结构代价2*S+1确定节点分裂属性的代价S*loga编码S+1个叶子结点的代价∑nii=s+2..kPublic(S)算法(证明一)证明：编码S+1个叶子节点的代价至少为∑nii=s+2..k相关概念：1.主要类(MajorityClass):if,有，则Ci为主要类2.少数类(MinorityClass):ifthenCj为少数类CiCCkkjijnnmajorityCCjPublic(S)算法(证明二)题设：子树N有S个分裂点(Split),K个类S+1个叶子节点至多有S+1个主要类至少有K-S-1个少数类取Ci为某少数类,C(Sj)为编码叶子节点j上记录的代价又有C(S)∑nij编码具有类i且位于叶子节点j的记录的代价是nij所有少数类的代价Cost=∑nii∈少数类ijijijijijijnnnnnSjEnSjClog**)(*)(2jijnin计算minCost_S的代码ProcedurecomputeMinCostS(NodeN)Ifk=1return(C(S)+1)S=1tmpCost=2*S+1+S*loga+∑inii=s+2..kWhiles+1kandns+22+logado{tmpCost=tmpCost+2+loga-ns+2S++}Returnmin{C(S)+1,tmpCost}}Public(S)示例ageCartypelabel16truckhigh24sportshigh32sportsMedi34trucklow65familylow[16,truck,high][24,sports,high]1+log21+11N[65,family,low][34,truck,low][32,sports,medi]N1+log21+log211[16,truck,high][24,sports,high][32,sports,medi][65,family,low][34,truck,low]1Public(V)算法计算分类节点值的代价：编码叶子节点记录的代价i=1..k(1)在所有内部节点编码分裂节点值的代价(2)总代价(1)+(2)其中，Cj是叶子节点j上的主要类；M是S+1个叶子节点上的主要类的集合11||SjjMiiMiijScnn}11:)(min{)(11SjjScVjScVjSj算法比较Sprint:传统的二阶段“构造－剪枝”算法Public(1):用保守的估计值1取代欲扩展节点的代价下界Public(S):考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界Public(V):比前者准确，需计算确定结点上属性值的代价下界实验数据(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001实