决策树基本概念教程课件.ppt

1、1分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结2什么是分类？什么是分类？n分类，分类器n银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全的”；医学研究人员分析癌症数据，以便选择治疗方案n数据分析任务都是分类，都需要构造一个分类器来预测类标号n数值预测，预测器n销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱n数据分析任务就是数值预测，所构造的模型（预测器）预测一个连续值函数或有序值，而不是类标号3n分类n预测类标号(离散的或标称的)n基于训练集和类标号构建分类器，并对新的数据进行分类n数值预测n所构造的模型预

2、测一个连续值函数，而不是类标号n典型应用n信用卡/贷款批准:n医疗诊断:肿瘤是良性的还是恶性的n欺诈检测:一次交易是否是欺诈的n网页分类:属于哪一类预测问题预测问题:分类与数值预测分类与数值预测4分类分类一个两阶段过程一个两阶段过程n两阶段：学习阶段（构建分类模型）和分类阶段（使用模型预测给定数据的类标号）n分类模型构建(学习阶段):描述预先定义的类n假设每个元组都属于一个预先定义的类，由类标号属性类标号属性确定，类标号属性是离散值的和无序的n用于模型构建的元组集合称为训练集训练集n模型用分类规则，决策树，或数学公式表示n模型使用(分类阶段):用于分类未知对象n评估模型的准确性n检验样本的已知

3、标签与模型的分类结果比较n准确率是被模型正确分类的检验样本所占的百分比n检验集是独立于训练集的(否则过分拟合)n如果准确性是可接受的，则使用模型来分类新的数据5监督和无监督学习监督和无监督学习n监督学习(分类)n监督:提供了每个训练元组的类标号n即分类器的学习在被告知每个训练元组属于哪个类的“监督”下进行的n新的数据基于训练集被分类n无监督学习(聚类)n每个训练元组的类标号是未知的n要学习的类的个数或集合也可能事先不知道6阶段阶段(1):模型构建模型构建训练数据NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBi

4、ll Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分类算法IF rank=professorOR years 6THEN tenured=yes 分类器(模型)学习：用分类算法分析训练数据7阶段阶段(2):使用模型预测使用模型预测分类器检验数据NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes新数据(Jeff,Prof

5、essor,4)Tenured?分类：检验数据用于评估分类规则的准确率8分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结9决策树决策树n从有类标号的训练元组中学习决策树n树结构n每个内部结点（非树叶结点）表示在一个属性上的测试n每个分枝代表该测试的一个输出n每个树叶结点存放一个类标号n树的最顶层结点是根结点n如何使用决策树分类？n给定一个类标号未知的元组X，在决策树上测试该元组的属性值。跟踪一条由根到叶结点的路径，该叶结点就存放着该元组的类预测。10决策树归纳决策树归纳:一个例子一个例子age?overcaststudent?cred

6、it rating?40noyesyesyes31.40nofairexcellentyesnoq训练数据集:Buys_computerq决策树:11决策树归纳算法决策树归纳算法n基础算法(贪心算法)n决策树以自顶向下递归的分治方式构造n从训练元组集和它们相关联的类标号开始构造决策树n所有属性是具有类别的(如果是连续数值型的，则它们需要事先离散化)n基于选择的属性对元组进行递归划分n测试属性基于统计学度量来选择(例如,信息增益)n停止划分的条件n给定结点的所有元组都属于同一个类n没有剩余属性可以用来进一步划分元组n给定的分枝没有元组算法基本策略算法基本策略n三个参数：D为数据分区，开始时，它是

7、训练元组和它们相应类标号的完全集。参数attribute_list是描述元组属性的列表。参数Attribute_selection_method用来选择可以按类“最好地”区分给定元组的属性，该过程使用一种属性选择度量（信息增益或基尼指数）。n树从单个结点N开始，N代表D中的训练元组n如果D中的元组都为同一类，则结点N变成树叶，并用该类标记它n否则，算法调用Attribute_selection_method确定分裂准则。分裂准则指定分裂属性，并且也指出分裂点或分裂子集n对分裂准则的每个输出，由结点N生长一个分枝。根据分裂属性A的类型，有三种可能的情况nA是离散值的:结点N的测试输出直接对应于A

8、的已知值nA是连续值的:结点N的测试有两个可能的输出，分别对应于条件Asplit_point,其中split_point是分裂点nA是离散值并且必须产生二叉树:在结点N的测试形如“A SA？”，其中SA是A的分裂子集算法算法:Generate_decision_tree。由数据分区D中的训练元组产生决策树。输入:n数据分区D,训练元组和他们对应类标号的集合nattribute_list,候选属性的集合。nAttribute_selection_method,一个确定“最好地”划分数据元组为个体类的分裂准则的过程。这个准则由分裂属性(splitting_attribute)和分裂点或划分子集组成

9、。输出:一棵决策树。方法:(1)创建一个结点N；(2)if D中的元组都在同一类C中 then(3)返回N作为叶结点,以类C标记;(4)if attribute_list为空 then(5)返回N作为叶结点,标记为D中的多数类;/多数表决(6)使用Attribute_selection_method(D,attribute_list),找出“最好的”splitting_criterion;(7)用splitting_criterion标记结点N;(8)if splitting_attribute是离散值的，并且允许多路划分 then /不限于二叉树(9)从attribute_list中删除分裂

10、属性；(10)for splitting_criterion的每个输出 j /划分元组并对每个分区产生子树(11)设Dj是D中 满足输出 j 的数据元组的集合；/一个分区(12)if Dj为空 then(13)加一个树叶到结点N,标记为D中的多数类；(14)else 加一个由Generate_decision_tree(Dj,attribute_list)返回的结点到N；endfor(15)返回N；14属性选择度量属性选择度量:信息增益信息增益(ID3/C4.5)n符号定义：设数据分区D为标记类元组的训练集。假定类标号属性具有m个不同值，定义m个不同类。设Ci,D是D中Ci类元组的集合。n选择

11、具有最高信息增益的属性A作为结点N的分裂属性n对D中的元组分类所需要的期望信息由下式给出:n基于按A划分对D的元组分类所需要的期望信息:n按属性A划分的信息增益)(log)(21imiippDInfo)(|)(1jvjjADInfoDDDInfo(D)InfoInfo(D)Gain(A)APi用|Ci,D|/|D|估计15属性选择属性选择:信息增益信息增益gClass P:buys_computer=“yes”gClass N:buys_computer=“no”意思为14个样本中有5个“age=30”的人，其中2个为“Yes”,3个为“No”.因此类似地,694.0)2,3(145)0,4(

12、144)3,2(145)(IIIDInfoage048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentno

13、)3,2(145I940.0)145(log145)149(log149)5,9()(22 IDInfo16计算连续值属性的信息增益计算连续值属性的信息增益n假设A是一个连续值属性n必须确定A的最佳分裂点n首先将A的值按递增顺序排序n每对相邻值的中点被看做可能的分裂点n(ai+ai+1)/2 是A的值ai 和 ai+1 之间的中点n对于A的每个可能分裂点,计算InfoA(D),具有最小期望信息需求的点选做A的分裂点n分裂:nD1 是满足A split-point的元组集合,而 D2 是满足A split-point的元组集合.17属性选择属性选择:增益率增益率(C4.5)n信息增益度量倾向于选

14、择具有大量值的属性nC4.5(ID3的后继)采用增益率来克服这个问题(规范化信息增益)nGainRatio(A)=Gain(A)/SplitInfo(A)nEx.ngain_ratio(income)=0.029/1.557=0.019n具有最大增益率的属性作为分裂属性)|(log|)(21DDDDDSplitInfojvjjA18基尼指数基尼指数(CART)n如果一个数据集D包含n个类，则D的基尼指数定义为 其中 pj 是D中元组属于类 j 的概率,并用|Ci,D|/|D|估计n如果数据集D基于属性 A 被划分成两个子集D1 和 D2,则基尼指数定义为n不纯度降低:n对于离散值属性,选择该属

15、性产生最小基尼指数的子集作为它的分裂子集；对于连续值属性，选择产生最小基尼指数的点作为分裂点；产生最小基尼指数（或最大不纯度降低）的属性选为分裂属性njpjDgini121)()(|)(|)(2211DginiDDDginiDDDginiA)()()(DginiDginiAginiA19基尼指数的计算基尼指数的计算n例如数据集D 有 9 个buys_computer=“yes”的元组和 5 个“no”的元组n假设按income属性子集low,medium将数据集划分为D1(10个元组)和D2(4个元组)Ginilow,high 是 0.458;Ginimedium,high 是 0.450.因

16、此在income的子集 low,medium上划分,因为 它的基尼指数 最小459.01451491)(22Dgini)(144)(1410)(21,DGiniDGiniDginimediumlowincome20过分拟合与树剪枝过分拟合与树剪枝n过分拟合:树创建时，由于数据中的噪声和离群点，会过分拟合训练数据n有很多分枝，一些是由于噪声和离群点导致的异常n预测准确率下降n两种方法来避免过分拟合n先剪枝:如果划分一个结点后的元组低于预定义阈值，则提前停止树的构建n选取一个适当的阈值是困难的n后剪枝:由“完全生长”的树剪去子树用回溯方式去除树的一些点nUse a set of data diff

17、erent from the training data to decide which is the“best pruned tree”21分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结22使用使用IF-THEN 规则分类规则分类n以 IF-THEN 规则的形式表示学习得到的模型R:IF age=youth AND student=yes THEN buys_computer=yesn“IF”部分称为规则前件或前提,“THEN”部分称为规则的结论n在规则前件，条件由一个或多个用逻辑连接词AND连接的属性测试组成；规则的结论包含一个

18、类预测n对于给定的元组，如果规则前件中的条件都成立，则规则覆盖覆盖了该元组n规则的评价:覆盖率和准确率nncovers 表示规则R覆盖的元组数nncorrect 表示规则R正确分类的元组数coverage(R)=ncovers/|D|/*D:训练数据集*/accuracy(R)=ncorrect/ncovers23使用使用IF-THEN 规则分类规则分类n如何使用基于规则的分类来预测给定元组X的类标号？n如果规则被X满足，则称该规则被触发。例如，X=(age=youth,income=medium,student=yes,credit_rating=fair)X满足规则R，触发该规则。n如果R

19、是唯一满足的规则，则该规则激活，返回X的类预测n注意，触发并不总意味激活，因为可能有多个规则被满足n如果多个规则被触发，则需要解决冲突解决冲突n规模序规模序:把最高优先权赋予具有“最苛刻”要求的被触发的规则(即,具有最多属性测试的)n规则序规则序:预先确定规则的优先次序。n基于类的序:按类的普遍性降序排序n基于规则的序(决策表决策表):根据规则质量的度量，规则被组织成一个优先权列表。最先出现在决策表中的被触发的规则具有最高优先权，因此激活它的类预测。24age?student?credit rating?40noyesyesyes31.40nofairexcellentyesnon例子:从 b

20、uys_computer 决策树提取规则R1:IF age=young AND student=no THEN buys_computer=noR2:IF age=young AND student=yes THEN buys_computer=yesR3:IF age=mid-age THEN buys_computer=yesR4:IF age=old AND credit_rating=excellent THEN buys_computer=noR5:IF age=old AND credit_rating=fair THEN buys_computer=yes由决策树提取规则由决策树

21、提取规则n与决策树相比，IF-THEN规则可能更容易理解，尤其是当决策树非常大时n对每条从根到树叶结点的路径创建一个规则n给定路径上的每个分裂准则的逻辑AND形成规则的前件(“IF”部分);存放类预测的树叶结点形成规则的后件(“THEN”部分)n规则是互斥的和穷举的25规则归纳规则归纳:顺序覆盖算法顺序覆盖算法n顺序覆盖算法:直接从训练集中提取规则n典型的顺序覆盖算法:FOIL,AQ,CN2,RIPPERn规则被顺序地学习,给定类的每个规则覆盖该类的许多元组（并且希望不覆盖其他类的元组）n步骤:n一次学习一个规则n每学习一个规则,就删除该规则覆盖的元组n在剩下的元组上重复该过程，直到满足终止条

22、件,例如,不再有训练元组，或返回规则的质量低于用户指定的阈值n与决策树对比:决策树归纳是同时学习一组规则26基本顺序覆盖算法基本顺序覆盖算法算法算法：顺序覆盖顺序覆盖。学习一组IF-THEN分类规则。输入输入：D，类标记元组的数据集合。Att-vals,所有属性与它们可能值的集合。输出输出：IF-THEN规则的集合。方法方法：Rule_set=;/学习的规则集初始为空for每个类c do repeat Rule=Learn_One_Rule(D,Att-vals,c);从D中删除被Rule覆盖的元组；until 终止条件满足；Rule_set=Rule_set+Rule /将新规则添加到规则集

23、endfor返回Rule_set;27如何如何Learn-One-Rule?n从最一般的规则开始:condition=empty(条件为空)n通过采用一种贪心的深度优先策略添加新的属性n选择最能提高规则质量的属性n规则质量度量:同时考虑覆盖率和准确率nFoil-gain(in FOIL&RIPPER):用下式估计扩展条件而获得的信息n偏向于具有高准确率并且覆盖许多正元组的规则)log(log_22negposposnegposposposGainFOIL28分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结29贝叶斯定理贝叶斯定理:基础

24、基础n贝叶斯定理:nX 表示数据元组:类标号未知nH为某种假设，如数据元组X属于某个特定类 C n分类是确定P(H|X)(即后验概率):在条件X下，H的后验概率，例如，X是一位35岁的顾客，其收入为4万美元。令H为某种假设，如顾客将购买计算机，则则P(H|X)反映当我们知道顾客的年龄和收入时，顾客X将购买计算机的概率。nP(H)(先验概率):H的先验概率n如,任意给定顾客将购买计算机的概率nP(X):X的先验概率，如顾客集合中的年龄为35岁并且收入为4万美元的概率nP(X|H):在条件H下，X的后验概率n例如,已知顾客X将购买计算机，该顾客是35岁并且收入为4万美元的概率)(/)()|()()

25、()|()|(XXXXXPHPHPPHPHPHP30分类就是导出最大后验概率分类就是导出最大后验概率n设D是训练元组和它们相关联的类标号的集合。每个元组用一个n维属性向量 X=(x1,x2,xn)表示n假定有m 个类C1,C2,Cm.n分类法将预测X属于具有最高后验概率的类,即,最大的P(Ci|X)。如果P(Ci|X)在所有k个类的P(Ck|X)中最大，则预测 X 属于类Cin每个类的后验概率可根据以下贝叶斯定理计算得到n由于P(X)对所有类为常数，所以只需要最大化)()()|()|(XXXPiCPiCPiCP)()|()|(iCPiCPiCPXX 31朴素贝叶斯分类朴素贝叶斯分类n简单假定:

26、属性有条件地相互独立(即属性之间不存在依赖关系):n如果 Ak 是分类属性,则P(xk|Ci)是D中属性Ak的值为xk的Ci类的元组数除以D中Ci类的元组数|Ci,D|n如果 Ak 是连续值属性,P(xk|Ci)通常基于均值 和标准差 的高斯分布计算（假定连续值属性服从均值为、标准差为 的高斯分布），由下式定义)|(.)|()|(1)|()|(21CixPCixPCixPnkCixPCiPnkX222)(21),(xexg),()|(iiCCkkxgCixP32朴素贝叶斯分类朴素贝叶斯分类Class:C1:buys_computer=yesC2:buys_computer=no待分类数据:X=

27、(age=30,Income=medium,Student=yes,Credit_rating=Fair)33朴素贝叶斯分类朴素贝叶斯分类:例子例子nP(Ci):P(buys_computer=“yes”)=9/14=0.643 P(buys_computer=“no”)=5/14=0.357n为每个类计算 P(X|Ci)P(age=“=30”|buys_computer=“yes”)=2/9=0.222 P(age=“=30”|buys_computer=“no”)=3/5=0.6 P(income=“medium”|buys_computer=“yes”)=4/9=0.444 P(inco

28、me=“medium”|buys_computer=“no”)=2/5=0.4 P(student=“yes”|buys_computer=“yes)=6/9=0.667 P(student=“yes”|buys_computer=“no”)=1/5=0.2 P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667 P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4n X=(age=30,income=medium,student=yes,credit_rating=fair)P(X|Ci):P

29、(X|buys_computer=“yes”)=0.222 x 0.444 x 0.667 x 0.667=0.044 P(X|buys_computer=“no”)=0.6 x 0.4 x 0.2 x 0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028 P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007因此因此,X 属于类属于类(“buys_computer=yes”)34避免零概率问题避免零概率问题n朴素贝叶斯分类预测需要每个条件概率是非

30、零的，否则，预测概率将会为零n例如，假设一个具有1000个元组的数据集,income=low(0),income=medium(990),和 income=high(10)n使用拉普拉斯校准拉普拉斯校准(或拉普拉斯估计法)n每个组元组数加1Prob(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003n“校准的”概率估计与对应的“未校准的”估计很接近nkCixkPCiXP1)|()|(35朴素贝叶斯分类朴素贝叶斯分类:评价评价n优点n易于实施n大部分情况下可以获得好的结果n缺点n假设:类条件独立，因此损失

31、准确性n实际中,属性之间经常存在依赖性n属性之间存在依赖的情况不能通过朴素贝叶斯分类建模n怎么处理这些依赖性?贝叶斯信念网络36分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结组合方法组合方法:提高分类准确率提高分类准确率n组合方法n把k个学习得到的模型,M1,M2,Mk,组合在一起，旨在创建 一个改进的复合分类模型M*n流行的组合方法n装袋:在一组分类器上平均预测n提升:基于一组分类器的加权表决37给定一个待分类元组X，它收集由基分类器返回的类标号预测，并输出占多数的类。装袋装袋:自助聚集自助聚集n类似:基于多个医生多数表决的诊断n

32、训练n每次迭代i，d个元组的训练集Di采用有放回抽样从原始数据集D抽取n从每个训练集Di学习一个分类器模型Min分类:对一个未知元组X分类n每个分类器Mi 返回它的类预测n装袋分类器M*统计得票，并将得票最高的类赋予Xn预测:通过取给定元组的每个预测的平均值，装袋也可以用于连续值的预测n准确率n准确率显著高于从原训练集D导出的单个分类器的准确率n对于噪声数据:更鲁棒38装袋装袋:自助聚集自助聚集39算法算法：装袋。装袋算法为学习方案创建组合分类模型，其中每个模型给出等权重预测。输入输入：D：d个训练元组的集合；k:组合分类器中的模型数；一种学习方案（例如，决策树算法、后向传播等）输出输出：组合

33、分类器复合模型M*。方法方法：for i=1 to k do /创建k个模型通过对D有放回抽样，创建自助样本Di;使用Di和学习方法导出模型Mi;endfor使用组合分类器对元组X分类：让k个模型都对X分类并返回多数表决;提升提升n类似:咨询多位医生，根据医生先前的诊断准确率，对每位医生的诊断赋予一个权重加权诊断的组合作为最终的诊断n提升?n权重权重被赋予每个训练元组n迭代地学习k个分类器n学习得到分类器Mi 之后,更新权重,使得其后的分类器使得其后的分类器Mi+1”更关注更关注”Mi 误分类的训练元组误分类的训练元组n最终提升的分类器M*组合每个个体分类器的表决组合每个个体分类器的表决,其中

34、每个分类器投票的权重是其准确率的函数n提升算法也可以用于数值预测n与装袋相比:提升有更高的准确率，但存在对数据过分拟合的危险4041Adaboost(Freund and Schapire,1997)n给定一个包含d 个类标记元组(X1,y1),(Xd,yd)的数据集Dn开始,对每个训练元组赋予相等的权重(1/d)nk轮产生k个分类器.在第 i 轮,n从D中元组有放回抽样,形成大小为d的训练集Di。n每个元组被选中的机会由它的权重决定n从训练集Di 导出分类器 Mi。n计算Mi的错误率n如果元组被不正确地分类,则它的权重 增加，否则 它的权重减少n错误率:err(Xj)是元组 Xj 的误分类误差的误分类误差.模型 Mi 的错误率是模型Mi误分类D中的每个元组的加权和:n分类器Mi的表决权重为)()(1logiiMerrorMerrordjjierrwMerror)()(jX42分类分类:基本概念基本概念n分类:基本概念n决策树n基于规则分类n贝叶斯分类方法n提高分类准确率的技术n小结小结小结n分类是一种提取模型的数据分析形式n有效的分类方法：决策树归纳,基于规则的分类,贝叶斯分类方法.n装袋和提升可用于提高整体的分类准确率43