《{决策管理}3第三章决策树》由会员分享，可在线阅读，更多相关《{决策管理}3第三章决策树（45页珍藏版）》请在金锄头文库上搜索。
1、1,决策树(Decision Tree),2020/7/29,2,1、分类的意义,数据库,了解类别属性与特征,分类模型 决策树,分类模型 聚类,一、分类(Classification),2020/7/29,3,数据库,分类标记,2020/7/29,2、分类的技术,（1）决策树,4,（2）聚类,2020/7/29,3、分类的程序,5,模型建立(Model Building) 模型评估(Model Evaluation) 使用模型(Use Model),2020/7/29,决策树分类的步骤,6,数据库,2020/7/29,训练样本(training samples),建立模型,测试样本(testi
2、ng samples),评估模型,例：,7,错误率为66.67%,2020/7/29,4、分类算法的评估,8,预测的准确度：指模型正确地预测新的或先前未见过的数据的类标号的能力。 训练测试法(training-and-testing) 交叉验证法(cross-validation) 例如，十折交叉验证。即是将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10倍交叉验证求均值，例如10次10倍交叉验证，更精确一点。,2020/7/29,2020/7/29,9,速度：指产生和使用模型的计算花费。 建模的速度、预测的速度 强壮性：指给定噪声
3、数据或具有缺失值的数据，模型正确预测的能力。 可诠释性：指模型的解释能力。,10,2020/7/29,决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。 贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。,二、决策树(Decision Tree),（一）决策树的结构,11,根部节点(root nod
4、e),中间节点(non-leaf node) (代表测试的条件),分支(branches) (代表测试的结果),叶节点(leaf node) (代表分类后所获得的分类标记),2020/7/29,2020/7/29,12,（二）决策树的形成,例：,13,根部节点 中间节点 停止分支,？,2020/7/29,（三）ID3算法(C4.5,C5.0),14,2020/7/29,Quinlan(1979)提出，以Shannon(1949)的信息论为依据。 ID3算法的属性选择度量就是使用信息增益，选择最高信息增益的属性作为当前节点的测试属性。 信息论：若一事件有k种结果，对应的概率为Pi。则此事件发生后
5、所得到的信息量I(视为Entropy)为：I=-(p1*log2(p1)+ p2*log2(p2)+ pk*log2(pk),Example 1： 设 k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25 I=-(.25*log2(.25)*4)=2 Example 2： 设k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1 Example 3： 设 k=4p1=1,p2=0,p3=0,p4=0 I=-(1*log2(1)=0,2020/7/29,15,2020/7/29,16,信息增益,17,Example(Gain),n=16 n1
6、=4,I(16,4)=(4/16)*log2(4/16)+(12/16)*log2(12/16)=0.8113,E(年龄)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946 Gain(年龄)=I(16,4)-E(年龄)=0.0167,Gain(年龄)=0.0167,Max:作为第一个分类依据,2020/7/29,Gain(性别)=0.0972,Gain(家庭所得)=0.0177,Example(续),18,Gain(家庭所得)=0.688,I(7,3)=-(3/7)*log2(3/7)+(4/7)*log2(4/7)=0.9852,Gain(年龄)=0.9852,Gai
7、n(年龄)=0.2222,I(9,1)=-(1/9)*log2(1/9)+(8/9)*log2(8/9)=0.5032,Gain(家庭所得)=0.5032,2020/7/29,Example(end)ID3算法,19,分类规则： IF性别=Female AND家庭所得= 低所得THEN购买RV房车=否 IF性别=Female AND家庭所得= 小康THEN购买RV房车=否 IF性别=Female AND家庭所得= 高所得THEN购买RV房车=是 IF性别=Male AND年龄35 THEN购买RV房车=否 IF性别=Male AND年龄35 THEN购买RV房车=是,资料,Decision T
8、ree,2020/7/29,（四）Decision Tree的建立过程,20,1、决策树的停止 决策树是通过递归分割(recursive partitioning)建立而成，递归分割是一种把数据分割成不同小的部分的迭代过程。 如果有以下情况发生，决策树将停止分割： 该群数据的每一笔数据都已经归类到同一类别。 该群数据已经没有办法再找到新的属性来进行节点分割。 该群数据已经没有任何尚未处理的数据。,2020/7/29,2、决策树的剪枝(pruning),21,决策树学习可能遭遇模型过度拟合（over fitting）的问题，过度拟合是指模型过度训练，导致模型记住的不是训练集的一般性，反而是训练集
9、的局部特性。 如何处理过度拟合呢？对决策树进行修剪。 树的修剪有几种解决的方法，主要为先剪枝和后剪枝方法。,2020/7/29,（1）先剪枝方法,22,在先剪枝方法中，通过提前停止树的构造（例如，通过决定在给定的节点上不再分裂或划分训练样本的子集）而对树“剪枝”。一旦停止，节点成为树叶。 确定阀值法：在构造树时，可将信息增益用于评估岔的优良性。如果在一个节点划分样本将导致低于预定义阀值的分裂，则给定子集的进一步划分将停止。 测试组修剪法：在使用训练组样本产生新的分岔时，就立刻使用测试组样本去测试这个分岔规则是否能够再现，如果不能，就被视作过度拟合而被修剪掉，如果能够再现，则该分岔予以保留而继续
10、向下分岔。,2020/7/29,（2）后剪枝方法,23,后剪枝方法是由“完全生长”的树剪去分枝。通过删除节点的分枝，剪掉叶节点。 案例数修剪是在产生完全生长的树后，根据最小案例数阀值，将案例数小于阀值的树节点剪掉。 成本复杂性修剪法是当决策树成长完成后，演算法计算所有叶节点的总和错误率，然后计算去除某一叶节点后的总和错误率，当去除该叶节点的错误率降低或者不变时，则剪掉该节点。反之，保留。,2020/7/29,应用案例：在农业中的应用,2020/7/29,24,第一步：属性离散化,2020/7/29,25,第二步：概化（泛化）,2020/7/29,26,第三步：计算各属性的期望信息,2020/7
11、/29,27,=(17/30)*LOG(17/30),2)+(10/30)*LOG(10/30),2)+(3/30)*LOG(3/30),2),计算各属性的信息增益,2020/7/29,28,第四步：决策树,2020/7/29,29,案例2：银行违约率,2020/7/29,30,2020/7/29,31,案例3 对电信客户的流失率分析,2020/7/29,32,数据仓库,条件属性,类别属性,客户是否流失,案例4：在银行中的应用,2020/7/29,33,案例5：个人信用评级,2020/7/29,34,个人信用评级决策树,（五）其他算法,35,C4.5与C5.0算法 Gini Index算法 C
12、ART算法 PRISM算法 CHAID算法,2020/7/29,1、C4.5与C5.0算法,36,C5.0算法则是C4.5算法的修订版 ，适用在处理大数据集，采用Boosting（提升）方式提高模型准确率，又称为Boosting Trees，在软件上的计算速度比较快，占用的内存资源较少。,2020/7/29,类别属性的信息熵,2、Gini Index算法,37,ID3 and PRISM适用于类别属性的分类方法。 Gini Index能数值型属性的变量来做分类。着重解决当训练集数据量巨大，无法全部放人内存时，如何高速准确地生成更快的，更小的决策树。,2020/7/29,集合T包含N个类别的记录
13、，那么其Gini指标就是 如果集合T分成两部分N1 和 N2。则此分割的Gini就是 提供最小Gini split就被选择作为分割的标准(对于每个属性都要经过所有可以的分割方法)。,Gini Index算法,38,2020/7/29,案例：在汽车销售中的应用,2020/7/29,39,2020/7/29,40,2020/7/29,41,N,N,Y,Y,Y,N,Y,Y,Y,N,N,N,3、CART算法,42,由Friedman等人提出，1980年以来就开始发展，是基于树结构产生分类和回归模型的过程，是一种产生二元树的技术。 CART与C4.5/C5.0算法的最大的区别是：其在每一个节点上都是采用二分法，也就是一次只能够有两个子节点，C4.5/5.0则在每一个节点上可以产生不同数量的分枝。,2020/7/29,2020/7/29,43,构建树的步骤：,2020/7/29,44,2020/7/29,45,
