第三周决策树和Boosting-ToStu

1分类:基本概念分类:基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结2什么是分类？分类，分类器银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全的”；医学研究人员分析癌症数据，以便选择治疗方案数据分析任务都是分类，都需要构造一个分类器来预测类标号数值预测，预测器销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱数据分析任务就是数值预测，所构造的模型（预测器）预测一个连续值函数或有序值，而不是类标号3分类预测类标号(离散的或标称的)基于训练集和类标号构建分类器，并对新的数据进行分类数值预测所构造的模型预测一个连续值函数，而不是类标号典型应用信用卡/贷款批准:医疗诊断:肿瘤是良性的还是恶性的欺诈检测:一次交易是否是欺诈的网页分类:属于哪一类预测问题:分类与数值预测4分类—一个两阶段过程两阶段：学习阶段（构建分类模型）和分类阶段（使用模型预测给定数据的类标号）分类模型构建(学习阶段):描述预先定义的类假设每个元组都属于一个预先定义的类，由类标号属性确定，类标号属性是离散值的和无序的用于模型构建的元组集合称为训练集模型用分类规则，决策树，或数学公式表示模型使用(分类阶段):用于分类未知对象评估模型的准确性检验样本的已知标签与模型的分类结果比较准确率是被模型正确分类的检验样本所占的百分比检验集是独立于训练集的(否则过分拟合)如果准确性是可接受的，则使用模型来分类新的数据5监督和无监督学习监督学习(分类)监督:提供了每个训练元组的类标号即分类器的学习在被告知每个训练元组属于哪个类的“监督”下进行的新的数据基于训练集被分类无监督学习(聚类)每个训练元组的类标号是未知的要学习的类的个数或集合也可能事先不知道6阶段(1):模型构建训练数据NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’分类器(模型)学习：用分类算法分析训练数据7阶段(2):使用模型预测分类器检验数据NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes新数据(Jeff,Professor,4)Tenured?分类：检验数据用于评估分类规则的准确率8分类:基本概念分类:基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结9决策树从有类标号的训练元组中学习决策树树结构每个内部结点（非树叶结点）表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶结点存放一个类标号树的最顶层结点是根结点如何使用决策树分类？给定一个类标号未知的元组X，在决策树上测试该元组的属性值。跟踪一条由根到叶结点的路径，该叶结点就存放着该元组的类预测。10决策树归纳:一个例子age?overcaststudent?creditrating?=3040noyesyesyes31..40fairexcellentyesnoageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno训练数据集: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和Asplit_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划分的信息增益)(log)(21imiippDInfo)(||||)(1jvjjADInfoDDDInfo(D)InfoInfo(D)Gain(A)APi用|Ci,D|/|D|估计15属性选择:信息增益ClassP:buys_computer=“yes”ClassN:buys_computer=“no”意思为14个样本中有5个“age=30”的人，其中2个为“Yes”,3个为“No”.因此类似地,agepiniI(pi,ni)=30230.97131…4040040320.971694.0)2,3(145)0,4(144)3,2(145)(IIIDInfoage048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain246.0)()()(DInfoDInfoageGainageageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno)3,2(145I940.0)145(log145)149(log149)5,9()(22IDInfo16计算连续值属性的信息增益假设A是一个连续值属性必须确定A的最佳分裂点首先将A的值按递增顺序排序每对相邻值的中点被看做可能的分裂点(ai+ai+1)/2是A的值ai和ai+1之间的中点对于A的每个可能分裂点,计算InfoA(D),具有最小期望信息需求的点选做A的分裂点分裂:D1是满足A≤split-point的元组集合,而D2是满足Asplit-point的元组集合.17属性选择:增益率(C4.5)信息增益度量倾向于选择具有大量值的属性C4.5(ID3的后继)采用增益率来克服这个问题(规范化信息增益)GainRatio(A)=Gain(A)/SplitInfo(A)Ex.gain_ratio(income)=0.029/1.557=0.019具有最大增益率的属性作为分裂属性)||||(log||||)(21DDDDDSplitInfojvjjA18基尼指数(CART)如果一个数据集D包含n个类，则D的基尼指数定义为其中pj是D中元组属于类j的概率,并用|Ci,D|/|D|估计如果数据集D基于属性A被划分成两个子集D1和D2,则基尼指数定义为不纯度降低:对于离散值属性,选择该属性产生最小基尼指数的子集作为它的分裂子集；对于连续值属性，选择产生最小基尼指数的点作为分裂点；产生最小基尼指数（或最大不纯度降低）的属性选为分裂属性njpjDgini121)()(||||)(||||)(2211DginiDDDginiDDDginiA)()()(DginiDginiAginiA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}上划分,因为它的基尼指数最小459.01451491)(22Dgini)(144)(1410)(21},{DGiniDGiniDginimediumlowincom