决策树基本概念教材

1分类:基本概念分类:基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结2什么是分类？分类，分类器银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全的”；医学研究人员分析癌症数据，以便选择治疗方案数据分析任务都是分类，都需要构造一个分类器来预测类标号数值预测，预测器销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱数据分析任务就是数值预测，所构造的模型（预测器）预测一个连续值函数或有序值，而不是类标号3分类预测类标号(离散的或标称的)基于训练集和类标号构建分类器，并对新的数据进行分类数值预测所构造的模型预测一个连续值函数，而不是类标号典型应用信用卡/贷款批准:医疗诊断:肿瘤是良性的还是恶性的欺诈检测:一次交易是否是欺诈的网页分类:属于哪一类预测问题:分类与数值预测4分类—一个两阶段过程两阶段：学习阶段（构建分类模型）和分类阶段（使用模型预测给定数据的类标号）分类模型构建(学习阶段):描述预先定义的类假设每个元组都属于一个预先定义的类，由类标号属性确定，类标号属性是离散值的和无序的用于模型构建的元组集合称为训练集模型用分类规则，决策树，或数学公式表示模型使用(分类阶段):用于分类未知对象评估模型的准确性检验样本的已知标签与模型的分类结果比较准确率是被模型正确分类的检验样本所占的百分比检验集是独立于训练集的(否则过分拟合)如果准确性是可接受的，则使用模型来分类新的数据5监督和无监督学习监督学习(分类)监督:提供了每个训练元组的类标号即分类器的学习在被告知每个训练元组属于哪个类的“监督”下进行的新的数据基于训练集被分类无监督学习

(聚类)每个训练元组的类标号是未知的要学习的类的个数或集合也可能事先不知道6阶段(1):模型构建训练数据分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类器(模型)学习：用分类算法分析训练数据7阶段(2):使用模型预测分类器检验数据新数据(Jeff,Professor,4)Tenured?分类：检验数据用于评估分类规则的准确率8分类:基本概念分类:基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结9决策树从有类标号的训练元组中学习决策树树结构每个内部结点（非树叶结点）表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶结点存放一个类标号树的最顶层结点是根结点如何使用决策树分类？给定一个类标号未知的元组X，在决策树上测试该元组的属性值。跟踪一条由根到叶结点的路径，该叶结点就存放着该元组的类预测。10决策树归纳纳:一个例子age?overcaststudent?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno训练数据集集:Buys_computer决策树:11决策树归纳纳算法基础算法(贪心算法)决策树以自顶向下递递归的分治治方式构造从训练元组组集和它们们相关联的的类标号开开始构造决决策树所有属性是是具有类别别的(如果是连续续数值型的的，则它们们需要事先先离散化)基于选择的的属性对元元组进行递递归划分测试属性基基于统计学学度量来选选择(例如,信息增益)停止划分的的条件给定结点的的所有元组组都属于同同一个类没有剩余属属性可以用用来进一步步划分元组组给定的分枝枝没有元组组算法基本策策略三个参数：：D为数据分区区，开始时，，它是训练练元组和它它们相应类类标号的完完全集。参参数attribute_list是描述述元组组属性性的列列表。参数数Attribute_selection_method用来选选择可可以按按类““最好好地””区分分给定定元组组的属属性，该过过程使使用一一种属属性选选择度度量（（信息息增益益或基基尼指指数））。树从单单个结结点N开始，，N代表D中的训训练元元组如果D中的元元组都都为同同一类类，则则结点点N变成树树叶，，并用用该类类标记记它否则，，算法法调用用Attribute_selection_method确定分分裂准准则。。分裂准准则指指定分分裂属属性，，并且且也指指出分分裂点点或分分裂子子集对分裂裂准则则的每每个输输出，，由结结点N生长一一个分分枝。。根据据分裂裂属性性A的类型型，有有三种种可能能的情情况A是离散散值的的:结点N的测试试输出出直接接对应应于A的已知知值A是连续续值的的:结点N的测试试有两两个可可能的的输出出，分分别对对应于于条件件A<=split_point和A>split_point,其中split_point是分裂裂点A是离散散值并并且必必须产产生二二叉树树:在结点点N的测试试形如如“A∈∈SA？”，，其中中SA是A的分裂裂子集集算法:Generate_decision_tree。由数数据分分区D中的训训练元元组产产生决决策树树。输入:数据分分区D,训练元元组和和他们们对应应类标标号的的集合合attribute_list,候选属属性的的集合合。Attribute_selection_method,一个确确定““最好好地””划分分数据据元组组为个个体类类的分分裂准准则的的过程程。这这个准准则由由分裂裂属性性(splitting_attribute)和分裂裂点或或划分分子集集组成成。输出:一棵决决策树树。方法:(1)创建一一个结结点N；(2)ifD中的元元组都都在同同一类类C中then(3)返回N作为叶叶结点点,以类C标记;(4)ifattribute_list为空then(5)返回N作为叶结点,标记为D中的多数类;//多数表决(6)使用Attribute_selection_method(D,attribute_list),找出“最好的的”splitting_criterion;(7)用splitting_criterion标记结点N;(8)ifsplitting_attribute是离散值的，，并且允许多多路划分then//不限于二叉树树(9)从attribute_list中删除分裂属属性；(10)forsplitting_criterion的每个输出j//划分元组并对对每个分区产产生子树(11)设Dj是D中满足输出出j的数据元组的的集合；//一个分区(12)ifDj为空then(13)加一个树叶到到结点N,标记为D中的多数类；；(14)else加一个由Generate_decision_tree(Dj,attribute_list)返回的结点到到N；endfor(15)返回N；14属性选择度量量:信息增益(ID3/C4.5)符号定义：：设数据分区区D为标记类元组组的训练集。。假定类标号号属性具有m个不同值，定定义m个不同类。设设Ci,D是D中Ci类元组的集合合。选择具有最高高信息增益的的属性A作为结点N的分裂属性对D中的元组分类类所需要的期望信息由下式给出:基于按A划分对D的元组分类所所需要的期望信息:按属性A划分的信息增益Pi用|Ci,D|/|D|估计15属性选择:信息增益ClassP:buys_computer=““yes”ClassN:buys_computer=““no”意思为14个样本中有5个“age<=30”的人，其中2个为“Yes”,3个为“No”.因此类似地,16计算连续值属属性的信息增增益假设A是一个连续值值属性必须确定A的最佳分裂点首先将A的值按递增顺顺序排序每对相邻值的的中点被看做做可能的分裂点(ai+ai+1)/2是A的值ai和ai+1之间的中点对于A的每个可能分分裂点,计算InfoA(D),具有最小期望信息息需求的点选做A的分裂点分裂:D1是满足A≤split-point的元组集合,而D2是满足A>split-point的元组集合.17属性选择:增益率(C4.5)信息增益度量量倾向于选择择具有大量值值的属性C4.5(ID3的后继)采用增益率来来克服这个问问题(规范化信息增增益)GainRatio(A)=Gain(A)/SplitInfo(A)Ex.gain_ratio(income)=0.029/1.557=0.019具有最大增益益率的属性作作为分裂属性性18基尼指数(CART)如果一个数据据集D包含n个类，则D的基尼指数定定义为其中pj是D中元组属于类类j的概率,并用|Ci,D|/|D|估计如果数据集D基于属性A被划分成两个个子集D1和D2,则基尼指数定定义为不纯度降低:对于离散值属性,选择该属性产产生最小基尼指数数的子集作为为它的分裂子子集；对于连续值属性，选择产生最小基尼指数数的点作为分分裂点；产生最小基尼指数数（或最大不纯纯度降低）的属性选为分分裂属性19基尼指数的计计算例如数据集D有9个buys_computer=““yes””的元组和5个“no”的元组假设按income属性子集{low,medium}将数据集划分分为D1(10个元组)和D2(4个元组)Gini{low,high}是0.458;Gini{medium,high}是0.450.因此在income的子集{low,medium}上划分,因为它的基尼指数数最小20过分拟合与树树剪枝过分拟合:树创建时，由由于数据中的的噪声和离群群点，会过分分拟合训练数数据有很多分枝，，一些是由于于噪声和离群群点导致的异异常预测准确率下下降两种方法来避避免过分拟合合先剪枝:如果划分一个个结点后的元元组低于预定定义阈值，则则提前停止树树的构建选取一个适当当的阈值是困困难的后剪枝:由“完全生长”的树剪去子树树——用回溯方式去去除树的一些些点Useasetofdatadifferentfromthetrainingdatatodecidewhichisthe“bestprunedtree”21分类:基本概念分类:基本概念决策树基于规则分分类贝叶斯分类类方法提高分类准准确率的技技术小结22使用IF-THEN规则分类以IF-THEN规则的形式式表示学习习得到的模模型R:IFage=youthANDstudent=yesTHENbuys_computer=yes“IF”部分称为规规则前件或或前提,“THEN”部分称为规规则的结论论在规则前件件，条件由由一个或多多个用逻辑辑连接词AND连接的属性性测试组成成；规则的的结论包含含一个类预预测对于给定的的元组，如如果规则前前件中的条条件都成立立，则规则则覆盖了该元组规则的评价价:覆盖率和准准确率ncovers表示规则R覆盖的元组组数ncorrect表示规则R正确分类的的元组数coverage(R)=ncovers/|D|/*D:训练数据集集*/accuracy(R)=ncorrect/ncovers23使用IF-THEN规则分类如何使用基基于规则的的分类来预预测给定元元组X的类标号？？如果规则被被X满足，则称称该规则被被触发。例如，X=(age=youth,income=medium,student=yes,credit_rating=fair)X满足规则R，触发该规规则。如果R是唯一满足足的规则，，则该规则则激活，返返回X的类预测注意，触发发并不总意意味激活，，因为可能能有多个规规则被满足足如果多个规规则被触发发，则需要要解决冲突规模序:把最高优先先权赋予具具有“最苛苛刻”要求求的被触发发的规则(即,具有最多属属性测试的的)规则序:预先确定规规则的优先先次序。基于类的序序:按类的普遍遍性降序排排序基于规则的的序(决策表):根据规则质质量的度量量，规则被被组织成一一个优先权权列表。最最先出现在在决策表中中的被触发发的规则具具有最高优优先权，因因此激活它它的类预测测。24age?student?creditrating?<=30>40noyesyesyes31..40nofairexcellentyesno例子:从buys_computer决策树提取取规则R1:IFage=youngANDstudent=noTHENbuys_computer=noR2:IFage=youngANDstudent=yesTHENbuys_computer=yesR3:IFage=mid-ageTHENbuys_computer=yesR4:IFage=oldANDcredit_rating=excellentTHENbuys_computer=noR5:IFage=oldANDcredit_rating=fairTHENbuys_computer=yes由决策树树提取规规则与决策树树相比，，IF-THEN规则可能能更容易易理解，，尤其是是当决策策树非常常大时对每条从从根到树树叶结点点的路径径创建一一个规则则给定路径径上的每每个分裂裂准则的的逻辑AND形成规则则的前件件(“IF”部分);存放类预预测的树树叶结点点形成规规则的后后件(“THEN””部分)规则是互互斥的和和穷举的的25规则归纳纳:顺序覆盖盖算法顺序覆盖盖算法:直接从训训练集中中提取规规则典型的顺顺序覆盖盖算法:FOIL,AQ,CN2,RIPPER规则被顺顺序地学学习,给定类的的每个规规则覆盖盖该类的的许多元元组（并并且希望望不覆盖盖其他类类的元组组）步骤:一次学习习一个规规则每学习一一个规则则,就删除该该规则覆覆盖的元元组在剩下的的元组上上重复该该过程，，直到满足终止止条件,例如,不再有训训练元组组，或返返回规则则的质量量低于用用户指定定的阈值值与决策树树对比:决策树归归纳是同同时学习习一组规规则26基本顺序序覆盖算算法算法：顺序覆盖盖。学习一一组IF-THEN分类规则则。输入：D，类标记记元组的的数据集集合。Att-vals,所有属性性与它们们可能值值的集合合。输出：IF-THEN规则的集集合。方法：Rule_set={};//学习的规规则集初初始为空空for每个类cdorepeatRule=Learn_One_Rule(D,Att-vals,c);从D中删除被被Rule覆盖的元元组；until终止条件件满足；；Rule_set=Rule_set+Rule//将新规则则添加到到规则集集endfor返回Rule_set;27如何Learn-One-Rule?从最一般般的规则则开始:condition=empty(条件为空空)通过采用用一种贪贪心的深深度优先先策略添添加新的的属性选择最能能提高规规则质量量的属性性规则质量量度量:同时考虑虑覆盖率率和准确确率Foil-gain(inFOIL&RIPPER):用下式估估计扩展展条件而而获得的的信息偏向于具具有高准准确率并并且覆盖盖许多正正元组的的规则28分类:基本概念念分类:基本概念念决策树基于规则则分类贝叶斯分分类方法法提高分类类准确率率的技术术小结29贝叶斯定定理:基础贝叶斯定定理:X表示数据据元组:类标号未未知H为某种假假设，如如数据元元组X属于某个个特定类类C分类是确确定P(H|X)(即后验概概率):在条件X下，H的后验概概率，例例如，X是一位35岁的顾客客，其收收入为4万美元。。令H为某种假假设，如如顾客将将购买计计算机，，则P(H|X)反映当我我们知道道顾客的的年龄和和收入时时，顾客客X将购买计计算机的的概率。。P(H)(先验概率率):H的先验概概率如,任意给定定顾客将将购买计计算机的的概率P(X):X的先验概概率，如如顾客集集合中的的年龄为为35岁并且收收入为4万美元的的概率P(X|H):在条件H下，X的后验概概率例如,已知顾客客X将购买计计算机，，该顾客客是35岁并且收收入为4万美元的的概率30分类就是是导出最最大后验验概率设D是训练元元组和它它们相关关联的类类标号的的集合。。每个元元组用一一个n维属性向向量X=(x1,x2,…,xn)表示假定有m个类C1,C2,…,Cm.分类法将预测测X属于具有最高高后验概率的的类,即,最大的P(Ci|X)。如果P(Ci|X)在所有k个类的P(Ck|X)中最大，则预预测X属于类Ci每个类的后验验概率可根据据以下贝叶斯斯定理计算得得到由于P(X)对所有类为常常数，所以只只需要最大化化31朴素贝叶斯分分类简单假定:属性有条件地地相互独立(即属性之间不不存在依赖关关系):如果Ak是分类属性,则P(xk|Ci)是D中属性Ak的值为xk的Ci类的元组数除除以D中Ci类的元组数|Ci,D|如果Ak是连续值属性性,P(xk|Ci)通常基于均值值μ和标准差σ的高斯分布计计算（假定连连续值属性服服从均值为μ、标准差为σ的高斯分布）），由下式定定义32朴素贝叶斯分分类Class:C1:buys_computer=‘yes’C2:buys_computer=‘no’待分类数据:X=(age<=30,Income=medium,Student=yes,Credit_rating=Fair)33朴素贝叶斯分分类:例子P(Ci):P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357为每个类计算算P(X|Ci)P(age=“<=30”|buys_computer=“yes”)=2/9=0.222P(age=“<=30”|buys_computer=“no”)=3/5=0.6P(income=““medium”|buys_computer=“yes”)=4/9=0.444P(income=““medium”|buys_computer=“no”)=2/5=0.4P(student=“yes”|buys_computer=““yes)=6/9=0.667P(student=“yes”|buys_computer=““no”)=1/5=0.2P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4X=(age<=30,income=medium,student=yes,credit_rating=fair)P(X|Ci):P(X|buys_computer=““yes”)=0.222x0.444x0.667x0.667=0.044P(X|buys_computer=““no”)=0.6x0.4x0.2x0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=““yes”)*P(buys_computer=“yes”)=0.028P(X|buys_computer=““no”)*P(buys_computer=““no”)=0.007因此,X属于类(“buys_computer=yes”)34避免零零概率率问题题朴素贝贝叶斯斯分类类预测测需要要每个个条件件概率率是非非零的的，否否则，，预测测概率率将会会为零零例如，，假设设一个个具有有1000个元组组的数数据集集,income=low(0),income=medium(990),和income=high(10)使用拉普拉拉斯校校准(或拉普普拉斯斯估计计法)每个组组元组组数加加1Prob(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003“校准准的””概率率估计计与对对应的的“未未校准准的””估计计很接接近35朴素贝贝叶斯斯分类类:评价优点易于实实施大部分分情况况下可可以获获得好好的结结果缺点假设:类条件件独立立，因因此损损失准准确性性实际中中,属性之之间经经常存存在依依赖性性属性之之间存存在依依赖的的情况况不能能通过过朴素素贝叶叶斯分分类建建模怎么处处理这这些依依赖性性?贝叶斯斯信念念网络络36分类:基本概概念分类:基本概概念决策树树基于规规则分分类贝叶斯斯分类类方法法提高分分类准准确率率的技技术小结组合方方法:提高分分类准准确率率组合方方法把k个学习习得到到的模模型,M1,M2,……,Mk,组合在在一起起，旨旨在创创建一个改改进的的复合合分类类模型型M*流行的的组合合方法法装袋:在一组组分类类器上上平均均预测测提升:基于一一组分分类器器的加加权表表决37给定一一个待待分类类元组组X，它收收集由由基分分类器器返回回的类类标号号预测测，并并输出出占多多数的的类。。装袋:自助聚聚集类似:基于多多个医医生多多数表表决的的诊断断训练每次迭迭代i，d个元组组的训训练集集Di采用有有放回回抽样样从原原始数数据集集D抽取从每个个训练练集Di学习一一个分分类器器模型型Mi分类:对一个个未知知元组组X分类每个分分类器器Mi返回它它的类类预测测装袋分分类器器M*统计得得票，，并将将得票票最高高的类类赋予予X预测:通过取取给定定元组组的每每个预预测的的平均均值，，装袋袋也可可以用用于连连续值值的预预测准确率率准确率率显著著高于于从原原训练练集D导出的的单个个分类类器的的准确确率对于噪噪声数数据:更鲁棒棒38装袋:自助聚聚集39算法：装袋袋。装装袋算算法——为学习习方案案创建建组合合分类类模型型，其其中每每个模模型给给出等等权重重预测测。输入：D：d个训练练元组组的集集合；；k:组合分分类器器中的的模型型数；；一种学学习方方案（（例如如，决决策树树算法法、后后向传传播等等）输出：组合合分类类器——复合模模型M*。方法：fori=1tokdo//创建k个模型型通过对对D有放回回抽样样，