Clementine文档资料

1、1分类预测：决策树（一）分类预测：决策树（一）2主要内容n决策树算法概述决策树算法概述n从学习角度看，决策树属有指导学习算法从学习角度看，决策树属有指导学习算法n目标：用于分类和回归目标：用于分类和回归nc5.0c5.0算法及应用算法及应用n分类回归树及应用分类回归树及应用n模型的对比分析模型的对比分析3决策树算法概述：基本概念n得名其分析结论的展示方式类似一棵倒置的树得名其分析结论的展示方式类似一棵倒置的树根节点根节点叶节点叶节点中间节点中间节点2 2叉树和多叉树和多叉树叉树4决策树算法概述：特点n体现了对样本数据的不断分组过程体现了对样本数据的不断分组过程n决策树分为分类树和回归树决策树分

2、为分类树和回归树n体现了输入变量和输出变量取值的逻辑关系体现了输入变量和输出变量取值的逻辑关系n逻辑比较形式表述的是一种推理规则逻辑比较形式表述的是一种推理规则n每个叶节点都对应一条推理规则每个叶节点都对应一条推理规则n对新数据对象的分类预测对新数据对象的分类预测5决策树算法概述：几何理解n决策树建立的过程就是决策树各个分枝依次形成决策树建立的过程就是决策树各个分枝依次形成的过程的过程n决策树的每个分枝在一定规则下完成对决策树的每个分枝在一定规则下完成对n n维特征维特征空间的区域划分空间的区域划分n决策树建立好后，决策树建立好后，n n维特征空间会被划分成若干维特征空间会被划分成若干个小的边

3、界平行或垂直于坐标轴的矩形区域个小的边界平行或垂直于坐标轴的矩形区域6确定每一步特征空间划分标准时，都同时兼顾由此将确定每一步特征空间划分标准时，都同时兼顾由此将形成的两个区域，希望划分形成的两个区域所包含的形成的两个区域，希望划分形成的两个区域所包含的样本点尽可能同时样本点尽可能同时“纯正纯正”7决策树算法概述：核心问题n第一，决策树的生长第一，决策树的生长n利用训练样本集完成决策树的建立过程利用训练样本集完成决策树的建立过程n第二，决策树的剪枝第二，决策树的剪枝n利用测试样本集对所形成的决策树进行精简利用测试样本集对所形成的决策树进行精简8决策树算法概述：树生长n决策树的生长是对训练样本集

4、的不断分组决策树的生长是对训练样本集的不断分组分枝准则的确定涉及：分枝准则的确定涉及：第一，如何从众多的输入第一，如何从众多的输入变量中选择一个当前最佳的变量中选择一个当前最佳的分组变量分组变量第二，如何从分组变量的第二，如何从分组变量的众多取值中找到一个最佳的众多取值中找到一个最佳的分割点分割点9决策树算法概述：树剪枝n树剪枝的原因：完整的决策树对训练样本特征的树剪枝的原因：完整的决策树对训练样本特征的捕捉捕捉“过于精确过于精确”- 过拟和（过拟和（overfittingoverfitting）n常用的修剪技术：常用的修剪技术：n预修剪（预修剪（pre-pruningpre-pruning）

5、：用来限制决策树的）：用来限制决策树的充分生长。策略：充分生长。策略：n事先指定决策树生长的最大深度事先指定决策树生长的最大深度n事先指定树节点样本量的最小值事先指定树节点样本量的最小值n后修剪（后修剪（post-pruningpost-pruning）：待决策树充分生）：待决策树充分生长完毕后再进行剪枝长完毕后再进行剪枝10决策树算法概述：树剪枝n后修剪：待决策树生长完毕，根据一定规则，剪后修剪：待决策树生长完毕，根据一定规则，剪去不具一般代表性的子树。策略：去不具一般代表性的子树。策略：n事先指定允许的事先指定允许的最大误差值最大误差值n通常依据测试样通常依据测试样本集剪枝本集剪枝11c5

6、.0算法nc5.0c5.0是在是在id3(j r quinlan,1979)id3(j r quinlan,1979)基础上发展起基础上发展起来。来。c5.0c5.0是是c4.5c4.5算法的商业化版本算法的商业化版本n特点：特点：nc5.0c5.0用于建立多叉分类树用于建立多叉分类树n输入变量是分类型或数值型，输出变量应为分输入变量是分类型或数值型，输出变量应为分类型类型n以信息增益率确定最佳分组变量和分割点以信息增益率确定最佳分组变量和分割点12c5.0算法：熵n信息熵是信息论信息熵是信息论( (c.e.shannon,1948c.e.shannon,1948) )中的基本概中的基本概念。

7、信息论主要用于解决信息传递过程中的问题念。信息论主要用于解决信息传递过程中的问题，也称统计通信理论，也称统计通信理论n信息论的基本出发点认为：信息论的基本出发点认为：n信息传递通过由信源、信道和信宿组成的传递信息传递通过由信源、信道和信宿组成的传递系统实现系统实现信道信道信源信源( (发送端发送端) )信宿信宿( (接收端接收端) )13c5.0算法：熵n信息论的基本出发点认为：信息论的基本出发点认为：n传递系统存在于一个随机干扰环境之中传递系统存在于一个随机干扰环境之中n将发送的信息记为将发送的信息记为u u，接收的信息记为，接收的信息记为v v，那么，那么信道可看作为信道模型，记为信道可看

8、作为信道模型，记为p(u|v)p(u|v)信道信道信源信源( (发送端发送端) )u uu1,u2,.uru1,u2,.ur信宿信宿( (接收端接收端) )v vv1,v2,.vqv1,v2,.vqp(u|v)p(u|v)14c5.0算法：熵n信道模型是一个条件概率矩阵信道模型是一个条件概率矩阵p(u|v)p(u|v)，称为信道，称为信道传输概率矩阵传输概率矩阵np(ui|vj)是信宿收到是信宿收到vj而信源发出而信源发出ui的概率的概率 ，且，且n信源也同样被看做是某种随机过程，有：信源也同样被看做是某种随机过程，有：)|(. )|( )|(. . . .)|( . )|( )|()|( .

9、 )|( )|(212222111211qrqqrrvupvupvupvupvupvupvupvupvup),.,2 , 1( 1)|(rivupji),.,2 , 1( 1)(riupi15c5.0算法：熵n例如：二元信道模型例如：二元信道模型2212211122211211 )|( )|()|( )|(ppppvupvupvupvup16c5.0算法：熵n先验不确定性：通信发生前，信宿对信源的状态具先验不确定性：通信发生前，信宿对信源的状态具有不确定性有不确定性n后验不确定性：通信发生后，信宿收到发自信源的后验不确定性：通信发生后，信宿收到发自信源的信息，先验不确定性部分被消除，信宿对信源

10、仍有信息，先验不确定性部分被消除，信宿对信源仍有一定程度的不确定性一定程度的不确定性n后验不确定性等于先验不确定性，表示信宿没有后验不确定性等于先验不确定性，表示信宿没有收到信息；收到信息；n后验不确定性等于零，表示信宿收到了全部信息后验不确定性等于零，表示信宿收到了全部信息n信息是用来消除随机不确定性的，信息量的大小信息是用来消除随机不确定性的，信息量的大小可由所消除的不确定性大小来计量可由所消除的不确定性大小来计量17c5.0算法：熵n信息量的数学定义：信息量的数学定义：n信息熵是信息量的数学期望，是信源发出信息前的信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵。信息

11、熵的数学定义：平均不确定性，也称先验熵。信息熵的数学定义：n信息熵等于信息熵等于0，表示只存在唯一的信息发送可能表示只存在唯一的信息发送可能，p(ui)=1，没有发送的不确定性没有发送的不确定性；n如果信源的如果信源的k个信号有相同的发送概率个信号有相同的发送概率，p(ui)=1/k，则信息发送的不确定性最大，信息熵达到最大则信息发送的不确定性最大，信息熵达到最大np(ui)差别小，信息熵大，平均不确定性大；反之差别小，信息熵大，平均不确定性大；反之)(log)(1log)(22iiiupupui)(log)()(1log)()(22iiiiiiupupupupuent18c5.0算法：信息增

12、益n已知信号已知信号u的概率分布的概率分布p(u)且收到信号且收到信号v=vj，发出信发出信号的概率分布为号的概率分布为p(u|vj)，信源的平均不确定性：信源的平均不确定性：n称为后验熵。后验熵的期望称为后验熵。后验熵的期望( (条件熵或信道疑义条件熵或信道疑义度度) )：n信息增益信息增益n信息消除随机不确定性的程度信息消除随机不确定性的程度)|(log)|()|(1log)|()|(22jiijiijijijvupvupvupvupvuent)|(log)|( )()|(1log)|()()|(22jiijijjijijijjvupvupvpvupvupvpvuent)|()(),(vu

13、entuentvugains19c5.0：生长算法n如何从众多输入变量中选择一个最佳分组变量：如何从众多输入变量中选择一个最佳分组变量：nc5.0c5.0以信息增益率为标准。例如：以信息增益率为标准。例如：n决策树建立之前：决策树建立之前：940. 0)145(log145)149(log149)(log)()(1log)()(2222iiiiiiupupupupuent20n决策树建立过程中，考察输入变量，如决策树建立过程中，考察输入变量，如t1t1：694. 0)52(log52)53(log53(145 )40(log40)44(log44(144 )53(log53)52(log52(

14、145)1|(log)1|( )1() 1|(2222222jiijijjtuptuptptuent246. 0694. 0940. 0) 1|()() 1,(tuentuenttugains048. 0892. 0940. 0)3|()()3,(tuentuenttugains21n问题：类别值多的输入变量比类别值少的输入变量问题：类别值多的输入变量比类别值少的输入变量有更多的机会成为当前最佳分组变量有更多的机会成为当前最佳分组变量686867. 0)52(log52)53(log53(145 )40(log40)44(log44(144 )21(log21)21(log21(142)32(

15、log32)31(log31(143)1|(log)1|( )1() 1|(222222222jiijijjtuptuptptuent253133. 069686867. 0940. 0) 1|()() 1,(tuentuenttugains22n信息增益率：信息增益率：n如何评价数值型输入变量消除平均不确定性的能力如何评价数值型输入变量消除平均不确定性的能力n首先分箱：首先分箱： clementine clementine的的c5.0c5.0节点包含了节点包含了mdlpmdlp分箱算法分箱算法n然后再根据上述方法判定然后再根据上述方法判定)(/ ),(),(ventvugainvugains

16、r156. 0577. 1/246. 0)145(log145)144(log144)145(log145/(246. 0) 1,(222tugainsr049. 0985. 0/048. 0)148(log148)146(log146/(048. 0)3,(22tugainsrc5.0：生长算法23n如何从分组变量的众多取值中找到最佳分割点如何从分组变量的众多取值中找到最佳分割点n默认策略默认策略：n对分类型分组变量：有对分类型分组变量：有k个类别，将样本分成个类别，将样本分成k组，形成树的组，形成树的k个分支个分支n对数值型分组变量：以对数值型分组变量：以mdlpmdlp分箱所得的最小分箱

17、所得的最小组限值为界，将小于组限的样本划为一组，组限值为界，将小于组限的样本划为一组，大于的划为另一组，形成两个分叉大于的划为另一组，形成两个分叉n其他策略其他策略：nchimerge分箱法，合并分组变量的多个类别分箱法，合并分组变量的多个类别后再分支后再分支c5.0：生长算法24nchimergechimerge分箱：有指导的分箱方法，基本思路：分箱：有指导的分箱方法，基本思路：n将输入变量按变量值升序排序将输入变量按变量值升序排序n定义初始区间，将输入变量值分成若干组定义初始区间，将输入变量值分成若干组c5.0：生长算法25nchimergechimerge分箱基本思路：分箱基本思路：n计

18、算输入变量相邻两组与输出变量的列联表计算输入变量相邻两组与输出变量的列联表n在列联表的基础上计算卡方观测值在列联表的基础上计算卡方观测值n观测值小于临界值，输入变量在该相邻区间上的划分观测值小于临界值，输入变量在该相邻区间上的划分对输出变量取值没有显著影响，应合并。首先合并卡对输出变量取值没有显著影响，应合并。首先合并卡方观测值最小的区间。方观测值最小的区间。n重复以上，直到任何两个相临组无法合并，即卡重复以上，直到任何两个相临组无法合并，即卡方观测值都不小于临界为止。方观测值都不小于临界为止。26c5.0：剪枝算法n采用后修剪方法，从叶节点向上逐层剪枝，关键：采用后修剪方法，从叶节点向上逐层

19、剪枝，关键：n误差的估计、剪枝标准的设置误差的估计、剪枝标准的设置n误差估计：利用统计学置信区间的估计方法，直接误差估计：利用统计学置信区间的估计方法，直接在训练样本集上估计误差在训练样本集上估计误差nclementineclementine中中1-1- 默认默认75%75%。置信度用于控制剪枝。置信度用于控制剪枝的程度，决定了所允许的误差上限的程度，决定了所允许的误差上限1|)|)1 (2znffefpiiiiiiiiiinffzfe)1 (227c5.0：剪枝算法n剪枝标准：剪枝标准：“减少误差（减少误差（reduce -errorreduce -error）”法法nk为待剪子树中叶节点的

20、个数为待剪子树中叶节点的个数，pi为第为第i个叶节点个叶节点所含样本占子树所含样本的比例所含样本占子树所含样本的比例，ei为第为第i个叶节个叶节点的估计误差点的估计误差，e为父节点的估计误差为父节点的估计误差),.,2 , 1(1kieepkiii28c5.0：剪枝算法n例：能否剪掉例：能否剪掉c c节点下的节点下的3 3个叶节点（个叶节点（e e、f f、g g）估计估计3 3个节点的误差：个节点的误差：0.550.55、0.910.91、0.550.55加权求和：加权求和：计算计算c c节点的误差估计：节点的误差估计：0.500.50可剪掉叶节点可剪掉叶节点e e、f f、g g60. 0

21、14655. 014291. 014655. 0第一个数字是本节点所含样第一个数字是本节点所含样本量本量n，第二个数为错判样第二个数为错判样本数本数e29c5.0的应用举例n以以students.xlsstudents.xls为例，目标：研究哪些因素是显著为例，目标：研究哪些因素是显著影响学生是否参与社会公益活动的因素影响学生是否参与社会公益活动的因素n变量重要性的测度变量重要性的测度( (calculate variable importance) )npropensity scores(valid only for flag targets)：计算计算变量的倾向性得分变量的倾向性得分nca

22、lculate raw propensity scores：基于训练样本基于训练样本集计算分类模型给出预测值为真的概率集计算分类模型给出预测值为真的概率iiiippevaluaton)1 (130n置信度：经拉普拉斯调整后的结果置信度：经拉普拉斯调整后的结果jjjjyyaxpyyxpyypyesyaxpyesyxpyesypaxxyesyp)|()|1()()|()|1()(), 1|(212121jjjjyyaxpyyxpyypnoyaxpnoyxpnoypaxxnoyp)|()|1()()|()|1()(), 1|(212121ktnkptnij)()(ktntnj)(1)(n(t)n(t

23、)是节点是节点t t包含的样本量包含的样本量nj(t) nj(t) 是节点是节点t t包含第包含第j j类的样本量类的样本量k k是输出变量的类别个数是输出变量的类别个数kiiiabpapabpapbpabpapbpabpbap1)|()()|()()()|()()()()|(31c5.0的推理规则集n决策树对逻辑关系的表述并非是最简洁的决策树对逻辑关系的表述并非是最简洁的if a and b then yeselse if c and d then yesotherwise no32推理规则集的生成算法nprismprism（patient rule induction space meth

24、odpatient rule induction space method，cendrowskacendrowska，19871987），），“覆盖覆盖”算法，规则在训练样算法，规则在训练样本集上本集上100100正确正确n基本思路：确定输出变量的某个类别为期望类别基本思路：确定输出变量的某个类别为期望类别n在当前样本范围内，寻找能最大限度在当前样本范围内，寻找能最大限度“覆盖覆盖”期望类别期望类别样本的推理规则样本的推理规则n在在m m个样本范围内，按照正确覆盖率最大原则确定附加条个样本范围内，按照正确覆盖率最大原则确定附加条件，得到一个再小些的样本范围，直到推理规则不再件，得到一个再小些的

25、样本范围，直到推理规则不再“覆盖覆盖”属于期望类别外的样本属于期望类别外的样本n从当前样本集合中剔除已经被正确从当前样本集合中剔除已经被正确“覆盖覆盖”的样本，检的样本，检查剩余样本中是否还有属于期望类别的样本。如果有则查剩余样本中是否还有属于期望类别的样本。如果有则回到第一步。否则结束。回到第一步。否则结束。33年龄段年龄段=a(2/5)=a(2/5)，年龄段，年龄段=b(4/4)=b(4/4)，年龄段，年龄段=c(3/5)=c(3/5)，性别，性别=0(6/8)=0(6/8)，性别，性别=1(3/6)=1(3/6)，推理规则为：，推理规则为：if if 年龄段年龄段=b then =b t

26、hen 是否是否购买购买=yes=yes。剔除已被正确覆盖的。剔除已被正确覆盖的4 4个样本个样本年龄段年龄段=a(2/5)=a(2/5)，年龄段，年龄段=c(3/5)=c(3/5)，性别，性别=0(4/6)=0(4/6)，性别，性别=1(1/4)=1(1/4)，推理规则为：，推理规则为：if if 性别性别=0 then =0 then 是否购买是否购买=yes=yes需附加逻辑与条件，样本范围为表中灰色部分。需附加逻辑与条件，样本范围为表中灰色部分。年龄段年龄段=a(1/3)=a(1/3)，年龄段，年龄段=c(3/3)=c(3/3)。推理规则修正为：。推理规则修正为：if if 性别性别=

27、0 and =0 and 年龄段年龄段=c then =c then 是否购买是否购买=yes=yesyes为期望类别为期望类别34c5.0其他：损失矩阵n不同错误类型所造成的实际损失可能不同，置信度不同错误类型所造成的实际损失可能不同，置信度会影响决策，错判损失同样会影响决策会影响决策，错判损失同样会影响决策n损失矩阵损失矩阵n使用损失矩阵的策略：使用损失矩阵的策略：n数据建模型阶段使用损失矩阵数据建模型阶段使用损失矩阵n样本预测时使用损失矩阵样本预测时使用损失矩阵35c5.0其他：损失矩阵nc5.0c5.0对损失矩阵的使用对损失矩阵的使用n剪枝时采用剪枝时采用“减少损失减少损失”法，判断待

28、剪子树中法，判断待剪子树中叶节点的加权损失是否大于父层节点的损失，如叶节点的加权损失是否大于父层节点的损失，如果大于则可以剪掉果大于则可以剪掉),.,2 , 1(1kieccepkiiii36c5.0其他：损失矩阵n损失矩阵对预测的影响：损失矩阵对预测的影响：nc(i|j)是损失矩阵中将是损失矩阵中将j类错判为类错判为i类的损失类的损失，p(j|t)是被节点是被节点t判为判为j类的归一化概率，定义为：类的归一化概率，定义为：n例如：例如：) )|()|(min jitjpjicjtjjnntjptjptjptjp,),(,),(),()|(预测值123实际值1c(2|1)c(3|1)2c(1|

29、2)c(3|2)3c(1|3)c(2|3)37c5.0其他：n折交叉验证n偏差和方差：预测的差异性来自两个方面，定义输偏差和方差：预测的差异性来自两个方面，定义输出变量出变量y y的均方误差（的均方误差（mean squared errormean squared error）为：）为：n模型复杂度是导致偏差大小的重要因素：模型复杂度是导致偏差大小的重要因素：n常数预测和复杂模型的预测常数预测和复杂模型的预测n方差较大的预测仍是无法令人满意的方差较大的预测仍是无法令人满意的n方差测度了模型对训练样本的敏感程度方差测度了模型对训练样本的敏感程度n偏差总是未知的，方差的测度显得较为重要偏差总是未知

30、的，方差的测度显得较为重要nn n折交叉验证：估计模型参数的方差，估计预测精度折交叉验证：估计模型参数的方差，估计预测精度的方差的方差222)() ()(yeyeyeeyeymseyy38c5.0其他n偏差和方差的存在，使建立在一组训练样本集上的偏差和方差的存在，使建立在一组训练样本集上的一个模型，所给出的预测往往缺乏稳健性一个模型，所给出的预测往往缺乏稳健性n数据挖掘中的策略数据挖掘中的策略nbaggingbagging技术技术nboostingboosting技术技术n均包括建模和投票两个阶段均包括建模和投票两个阶段39c5.0应用其他：bagging技术建模过程（输入：训练样本集建模过程

31、（输入：训练样本集t t，训练次数，训练次数k k；输出：；输出：多个决策树模型多个决策树模型c1,c2,ck)c1,c2,ck)for i=1,2,k dofor i=1,2,k do 从从t t中随机有放回抽取样本，形成有相同样本中随机有放回抽取样本，形成有相同样本容量的样本集合容量的样本集合titi 以以titi为训练集构造模型为训练集构造模型ciciend forend for40c5.0其他：bagging技术决策过程（输入：新数据决策过程（输入：新数据x x，多个决策树模型，多个决策树模型c1,c2,ckc1,c2,ck；输出：分类预测结果；输出：分类预测结果c(x) c(x) ）for i=1,2,k dofor i=1,2,k do 根据根据cici对对x x做预测，结果为做预测，结果为ci(x)ci(x)end forend for统计各类别得票，得票数最高的为统计各类别得票，得票数最高的为c(x)c(x)，或计算平，或计算平均值均值 如果将投票改进为：输出概率而非简单的分类结果，如果将投票改进为：输出概率而非简单的分类结果