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

决策树算法及应用拓展内容简介：概述预备知识决策树生成(BuildingDecisionTree)决策树剪枝(PruningDecisionTree)捕捉变化数据的挖掘方法小结概述(一)传统挖掘方法的局限性只重视从数据库中提取规则，忽视了库中数据的变化挖掘所用的数据来自稳定的环境，人为干预较少概述(二)捕捉新旧数据变化的目的：挖掘出变化的趋势例：啤酒——尿布阻止/延缓不利变化的发生例：金融危机——银行的信贷策略差异挖掘算法的主要思想：合理比较新/旧数据的挖掘结果，并清晰的描述其变化部分预备知识一(BuildingTree)基本思想：用途：提取分类规则，进行分类预测判定树分类算法output训练集决策树input使用决策树进行分类决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到一个叶子节点决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割伪代码(BuildingTree)ProcedureBuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q WhileQisnotEmptydo{ 取出队列Q中的第一个节点N ifN不纯(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的分类数目，PiCi为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数由A划分为子集的熵：E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A为属性，具有V个不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)训练集(举例)ID3算法使用信息增增益进行属属性选择ClassP:buys_computer=““yes”ClassN:buys_computer=““no””I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarlyDecisionTree(结果果输出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40基尼指数GiniIndex(IBMIntelligentMiner)集合T包含含N个类别别的记录，，那么其Gini指指标就是pj类别j出现现的频率如果集合T分成两部部分N1andN2。那么这个个分割的Gini就就是提供最小Ginisplit就被被选选择择作作为为分分割割的的标标准准(对于于每每个个属属性性都都要要遍遍历历所所有有可可以以的的分分割割方方法法).预备备知知识识二二(PruningTree)目的的：：消除除决决策策树树的的过过适适应应(OverFitting)问问题题实质质：：消消除除训训练练集集中中的的异异常常和和噪噪声声两种种方方法法：：先剪剪枝枝法法(Public算算法法)后剪剪枝枝法法(Sprint算算法法)两种种剪剪枝枝标标准准最小小描描述述长长度度原原则则(MDL)思想想：：最最简简单单的的解解释释最最期期望望的的做法法：：对对Decision-Tree进进行行二二进进位位编编码码，，编编码码所所需需二二进进位位最最少少的的树树即即为为““最最佳佳剪剪枝枝树树””期望望错错误误率率最最小小原原则则思想想：：选选择择期期望望错错误误率率最最小小的的子子树树进进行行剪剪枝枝对树树中中的的内部部节节点点计算算其其剪剪枝枝/不不剪剪枝枝可可能能出出现现的的期期望望错错误误率率，，比比较较后后加加以以取取舍舍CostofEncodingDataRecords对n条条记记录录进进行行分分类类编编码码的的代代价价(2种种方方法法)n————记记录录数数，，k————类类数数目目，，ni———属属于于类类i的的记记录录数数CostofEncodingTree编码码树树结结构构本本身身的的代代价价编码码每每个个分分裂裂节节点点的的代代价价确定定分分类类属属性性的的代代价价确定定分分类类属属性性值值的的代代价价&其中中，，v是是该该节节点点上上不不同同属属性性值值的的个个数数编码码每每个个树树叶叶上上的的记记录录分分类类的的代代价价剪枝枝算算法法设N为为欲欲计计算算其其最最小小代代价价的的节节点点两种种情情形形：：N是是叶叶结结点点————C(S)+1————Cost1N是是内内部部节节点点，，有有两两个个子子节节点点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的代代价至少少是1Public(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为少少数类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∈少数数类计算minCost_S的代代码ProcedurecomputeMinCostS(NodeN)Ifk=1return(C(S)+1)S=1tmpCost=2*S+1+S*loga+∑inii=s+2..kWhiles+1<kandns+2>2+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个叶子子节点上上的主要要类的集集合算法比较较Sprint:传统统的二阶阶段“构构造－剪剪枝”算算法Public(1):用保守守的估计计值1取取代欲扩扩展节点点的代价价下界Public(S):考虑具具有分裂裂点的子子树，同同时计算算为确定定分裂节节点及其其属性的的代价下下界Public(V):比前者者准确，，需计算算确定结结点上属属性值的的代价下下界实验数据据(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001实验结果果(一)DatesetDS1DS2DS3DS4DS5DS6DS7Sprint2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV1565287543553107163Maxrat40%48%14%51%0%77%99%Nodes9371991185513543产生的节节点数目目实验结果果(二)DatesetDS1DS2DS3DS4DS5DS6DS7Sprint0.871.59334.9177.65230.6211.986.65Public10.821.51285.56167.78229.2110.585.55PublicS0.831.44289.70166.44230.269.814.94PublicV0.811.45300.48159.83227.269.644.89Maxrat9%0%17%11%2%2%3%执行时间间(S)算法结果果分析总体上，，比Sprint算法法有较大大改进相对于最最后的剪剪枝树仍仍有多余余的结点点，有待待改进挖掘效率率与数据据分布及及噪声有有关言归正传传—捕捉捉数据变变化的挖挖掘方法法新生成一一棵决策策树与旧树完完全没有有关系生成一棵棵相关的的树未达到旧旧树中叶叶节点的的深度超出了