Clementine-第四讲

分类预测：决策树（一）主要内容决策树算法概述从学习角度看，决策树属有指导学习算法目标：用于分类和回归C5.0算法及应用分类回归树及应用模型的对比分析决策树算法概述：基本概念得名其分析结论的展示方式类似一棵倒置的树•根节点•叶节点•中间节点•2叉树和多叉树决策树算法概述：特点体现了对样本数据的不断分组过程决策树分为分类树和回归树体现了输入变量和输出变量取值的逻辑关系逻辑比较形式表述的是一种推理规则每个叶节点都对应一条推理规则对新数据对象的分类预测决策树算法概述：几何理解决策树建立的过程就是决策树各个分枝依次形成的过程决策树的每个分枝在一定规则下完成对n维特征空间的区域划分决策树建立好后，n维特征空间会被划分成若干个小的边界平行或垂直于坐标轴的矩形区域确定每一步特征空间划分标准时，都同时兼顾由此将形成的两个区域，希望划分形成的两个区域所包含的样本点尽可能同时“纯正”决策树算法概述：核心问题第一，决策树的生长利用训练样本集完成决策树的建立过程第二，决策树的剪枝利用测试样本集对所形成的决策树进行精简决策树算法概述：树生长决策树的生长是对训练样本集的不断分组分枝准则的确定涉及：•第一，如何从众多的输入变量中选择一个当前最佳的分组变量•第二，如何从分组变量的众多取值中找到一个最佳的分割点决策树算法概述：树剪枝树剪枝的原因：完整的决策树对训练样本特征的捕捉“过于精确”---过拟和（Overfitting）常用的修剪技术：预修剪（pre-pruning）：用来限制决策树的充分生长。策略：事先指定决策树生长的最大深度事先指定树节点样本量的最小值后修剪（post-pruning）：待决策树充分生长完毕后再进行剪枝决策树算法概述：树剪枝后修剪：待决策树生长完毕，根据一定规则，剪去不具一般代表性的子树。策略：事先指定允许的最大误差值通常依据测试样本集剪枝C5.0算法C5.0是在ID3(JRQuinlan,1979)基础上发展起来。C5.0是C4.5算法的商业化版本特点：C5.0用于建立多叉分类树输入变量是分类型或数值型，输出变量应为分类型以信息增益率确定最佳分组变量和分割点C5.0算法：熵信息熵是信息论(C.E.Shannon,1948)中的基本概念。信息论主要用于解决信息传递过程中的问题，也称统计通信理论信息论的基本出发点认为：信息传递通过由信源、信道和信宿组成的传递系统实现信道信源(发送端)信宿(接收端)C5.0算法：熵信息论的基本出发点认为：传递系统存在于一个随机干扰环境之中将发送的信息记为U，接收的信息记为V，那么信道可看作为信道模型，记为P(U|V)信道信源(发送端)Uu1,u2,..ur信宿(接收端)Vv1,v2,..vqP(U|V)C5.0算法：熵信道模型是一个条件概率矩阵P(U|V)，称为信道传输概率矩阵P(ui|vj)是信宿收到vj而信源发出ui的概率，且信源也同样被看做是某种随机过程，有：)|(....)|()|(..........)|(....)|()|()|(....)|()|(212222111211qrqqrrvuPvuPvuPvuPvuPvuPvuPvuPvuP),...,2,1(1)|(rivuPji),...,2,1(1)(riuPiC5.0算法：熵例如：二元信道模型2212211122211211)|()|()|()|(PPPPvuPvuPvuPvuPC5.0算法：熵先验不确定性：通信发生前，信宿对信源的状态具有不确定性后验不确定性：通信发生后，信宿收到发自信源的信息，先验不确定性部分被消除，信宿对信源仍有一定程度的不确定性后验不确定性等于先验不确定性，表示信宿没有收到信息；后验不确定性等于零，表示信宿收到了全部信息信息是用来消除随机不确定性的，信息量的大小可由所消除的不确定性大小来计量C5.0算法：熵信息量的数学定义：信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵。信息熵的数学定义：信息熵等于0，表示只存在唯一的信息发送可能，P(ui)=1，没有发送的不确定性；如果信源的k个信号有相同的发送概率，P(ui)=1/k，则信息发送的不确定性最大，信息熵达到最大P(ui)差别小，信息熵大，平均不确定性大；反之)(log)(1log)(22iiiuPuPuI)(log)()(1log)()(22iiiiiiuPuPuPuPUEntC5.0算法：信息增益已知信号U的概率分布P(U)且收到信号V=vj，发出信号的概率分布为P(U|vj)，信源的平均不确定性：称为后验熵。后验熵的期望(条件熵或信道疑义度)：信息增益信息消除随机不确定性的程度)|(log)|()|(1log)|()|(22jiijiijijijvuPvuPvuPvuPvUEnt))|(log)|(()()|(1log)|()()|(22jiijijjijijijjvuPvuPvPvuPvuPvPVUEnt)|()(),(VUEntUEntVUGainsC5.0：生长算法如何从众多输入变量中选择一个最佳分组变量：C5.0以信息增益率为标准。例如：决策树建立之前：940.0)145(log145)149(log149)(log)()(1log)()(2222iiiiiiuPuPuPuPUEnt决策树建立过程中，考察输入变量，如T1：694.0))52(log52)53(log53(145))40(log40)44(log44(144))53(log53)52(log52(145))1|(log)1|(()1()1|(2222222jiijijjtuPtuPtPTUEnt246.0694.0940.0)1|()()1,(TUEntUEntTUGains048.0892.0940.0)3|()()3,(TUEntUEntTUGains问题：类别值多的输入变量比类别值少的输入变量有更多的机会成为当前最佳分组变量686867.0))52(log52)53(log53(145))40(log40)44(log44(144))21(log21)21(log21(142))32(log32)31(log31(143))1|(log)1|(()1()1|(222222222jiijijjtuPtuPtPTUEnt253133.069686867.0940.0)1|()()1,(TUEntUEntTUGains信息增益率：如何评价数值型输入变量消除平均不确定性的能力首先分箱：Clementine的C5.0节点包含了MDLP分箱算法然后再根据上述方法判定)(/),(),(VEntVUGainVUGainsR156.0577.1/246.0))145(log145)144(log144)145(log145/(246.0)1,(222TUGainsR049.0985.0/048.0))148(log148)146(log146/(048.0)3,(22TUGainsRC5.0：生长算法如何从分组变量的众多取值中找到最佳分割点默认策略：对分类型分组变量：有k个类别，将样本分成k组，形成树的k个分支对数值型分组变量：以MDLP分箱所得的最小组限值为界，将小于组限的样本划为一组，大于的划为另一组，形成两个分叉其他策略：ChiMerge分箱法，合并分组变量的多个类别后再分支C5.0：生长算法ChiMerge分箱：有指导的分箱方法，基本思路：将输入变量按变量值升序排序定义初始区间，将输入变量值分成若干组C5.0：生长算法ChiMerge分箱基本思路：计算输入变量相邻两组与输出变量的列联表在列联表的基础上计算卡方观测值观测值小于临界值，输入变量在该相邻区间上的划分对输出变量取值没有显著影响，应合并。首先合并卡方观测值最小的区间。重复以上，直到任何两个相临组无法合并，即卡方观测值都不小于临界为止。C5.0：剪枝算法采用后修剪方法，从叶节点向上逐层剪枝，关键：误差的估计、剪枝标准的设置误差估计：利用统计学置信区间的估计方法，直接在训练样本集上估计误差Clementine中1-默认75%。置信度用于控制剪枝的程度，决定了所允许的误差上限1|)|)1((2zNffefPiiiiiiiiiiNffzfe)1(2C5.0：剪枝算法剪枝标准：“减少－误差（reduce-error）”法k为待剪子树中叶节点的个数，pi为第i个叶节点所含样本占子树所含样本的比例，ei为第i个叶节点的估计误差，e为父节点的估计误差),...,2,1(1kieepkiiiC5.0：剪枝算法例：能否剪掉C节点下的3个叶节点（E、F、G）•估计3个节点的误差：0.55、0.91、0.55•加权求和：•计算C节点的误差估计：0.50•可剪掉叶节点E、F、G60.014655.014291.014655.0第一个数字是本节点所含样本量N，第二个数为错判样本数EC5.0的应用举例以Students.xls为例，目标：研究哪些因素是显著影响学生是否参与社会公益活动的因素变量重要性的测度(Calculatevariableimportance)PropensityScores(validonlyforflagtargets)：计算变量的倾向性得分Calculaterawpropensityscores：基于训练样本集计算分类模型给出预测值为真的概率iiiiPPEvaluaton)1(1置信度：经拉普拉斯调整后的结果jjjjyyAxPyyxPyyPyesyAxPyesyxPyesyPAxxyesyP)|()|1()()|()|1()(),1|(212121jjjjyyAxPyyxPyyPnoyAxPnoyxPnoyPAxxnoyP)|()|1()()|()|1()(),1|(212121ktNkptNij)()(ktNtNj)(1)(N(t)是节点t包含的样本量Nj(t)是节点t包含第j类的样本量k是输出变量的类别个数kiiiABPAPABPAPBPABPAPBPABPBAP1)|()()|()()()|()()()()|(C5.0的推理规则集决策树对逻辑关系的表述并非是最简洁的IFaANDbTHENyesELSEIFcANDdTHENyesOTHERWISEno推理规则集的生成算法PRISM（PatientRuleInductionSpaceMethod，Cendrowska，1987），“覆盖”算法，规则在训练样本集上100％正确基本思路：确定输出变量的某个类别为期望类别在当前样本范围内，寻找能最大限度“覆盖”期望类别样本的推理规则在M个样本范围内，按照正确覆盖率最大原则确定附加条件，得到一个再小些的样本范围，直到推理规则不再“覆盖”属于期望类别外的样本从当前样本集合中剔除已经被正确“覆盖”的样本，检查剩余样本中是否还有属于期望类别的样本。如果有则回到第一步。否则结束。年龄段=A(2/5)，年龄段=B(4/4)，年龄段=C(3/5)，性别=0(6/8)，性别=1(3/6)，推理规则为：IF年龄段=BTHEN是否购买=yes。剔除已被正确覆盖的4个样本年龄段=A(2/5)，年龄段=C(3/5)，性别=0(4/6)，性别=1(1/4)，推理规则为：IF性别=0THEN是否购买=yes需附加逻辑与条件，样本范围为表中灰色部分。年龄段=A(1/3)，年龄段=C(3/3)。推理规则修正为：IF性别=0AND年龄段=CTHEN是否购买=yesYes为期望类