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