第4章分类基本概念、决策树与模型评估

第4章分类：基本概念、决策树与模型评估4.1预备知识4.2解决分类问题的一般方法4.3决策树归纳4.4模型的过分拟合4.5评估分类器的性质4.6比较分类器的方法分类任务：确定对象属于哪个预定义的目标类例子：1、根据电子邮件的标题和内容检查出垃圾邮件。2、根据星系的形状对它们分类。螺旋状的星系椭圆状的星系分类任务的输入数据是记录的集合。每条记录也称实例或者样例，用元组（x,y）表示，其中x是属性的集合，而y是一个特殊的属性，指出样例的类标号（也成为分类属性或目标属性）。分类？回归？分类（classification）通过学习得到一个目标函数（targetfunction），也成为分类模型（classificationmodel），把每个属性集x映射到一个预先定义的类标号y。f目的：1、描述性建模分类模型可以作为解释性的工具，用于区分不同类中的对象。2、预测性建模分类模型还可以用于预测未知记录的类标号。名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号毒蜥冷血鳞片否否否是是？输入属性集（x）分类模型输出类标号（y）分类器的任务：根据输入属性集x确定类标号y分类技术非常适合预测或描述二元或标称类型的数据集，对序数分类不太有效，因为分类技术不考虑隐含在目标类中的序关系。分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术这些技术都使用一种学习算法确定分类模型，修改这个模型能够很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好地拟合输入数据，还要能够正确地预测未知样本的类标号。训练算法的目标：建立具有很好的泛化能力的模型。ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSet训练集：由类标号已知的记录构成检验集：由类标号未知的记录构成预测的类类=1类=0实际的类类=1类=000f01f10f11f二类问题的混淆矩阵ijfij表中每个表项表示实际类标号为但是被预测为类的记录数。被分类模型正确预测的样本总数是，而被错误预测的样本总数是。0011ff0110ff虽然混淆矩阵提供衡量分类模型的信息，但是用一个数汇总这些信息更便于比较不同模型的性能。为实现这一目的，可以使用性能度量（performancemetric），如准确率（accuracy），其定义如下：同样，分类模型的性能也可以用错误率（errorrate）来表示，其定义如下：000110110110ffffff预测总数错误预测数错误率目标：寻求最高的准确率或者最低的错误率000110110011ffffff预测总数正确预测数准确率1、什么是决策树？类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个叶节点代表类或类分布3、决策树的使用：对未知样本进行分类通过将样本的属性值与决策树相比较2、决策树的生成由两个阶段组成决策树构建开始时，所有的训练样本都在根节点递归通过选定的属性，来划分样本（必须是离散值）树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝根结点（rootnode）：它没有入边，但是有零条或多条出边。内部结点（internalnode）：恰好有一条入边和两条或多条出边。叶节点（leafnode）或终结点（terminalnode）：恰好有一条入边，但没有出边。叶结点根结点内部结点体温胎生非哺乳动物哺乳动物非哺乳动物恒温否冷血是一旦构造了决策树，对检验记录进行分类就很容易。从树的根结点开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该分支或者到达另一个内部结点，使用新的测试条件，或者到达一个叶结点。到达叶结点之后，叶结点的类标号就被赋值给该检验记录。名字体温胎生……类标号火烈鸟恒温否……？体温胎生非哺乳动物哺乳动物非哺乳动物恒温否冷血是如何建立决策树对于给定的属性集，可以构造的决策树的数目达指数级。尽管某些决策树比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树在计算上是不可行的。尽管如此，人们还是开发了一些有效的算法，能够在合理的时间内构造出具有一定准确率的次最优决策树。这些算法通常都采用贪心策略。有许多决策树算法:Hunt算法信息增益——Informationgain（ID3）增益比率——Gainration（C4.5）基尼指数——Giniindex(SLIQ，SPRINT)在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。设是与结点t相关联的训练记录集，而是类标号，Hunt算法的递归定义如下。tD},,,{21cyyyy（1）如果中所有记录都属于同一个类，则t是叶结点，用标记。tytDty（2）如果中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。tDtDHunt算法Tid有房者婚姻状况年收入拖欠贷款者1是单身125k否2否已婚100k否3否单身70k否4是已婚120k否5否离异95k是6否已婚60k否7是离异220k否8否单身85k是9否已婚75k否10否单身90k是拖欠贷款者=否拖欠贷款者=否拖欠贷款者=否有房者拖欠贷款者=否有房者拖欠贷款者=否婚姻状况年收入拖欠贷款者=是拖欠贷款者=否(b)(c)(d)(a)拖欠贷款者=否有房者拖欠贷款者=否婚姻状况拖欠贷款者=是是是否否否是单身离异单身离异已婚已婚80k=80kHunt算法构造决策树如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设太苛刻了，因此，需要附加的条件来处理以下的情况：（1）算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关联的记录。如果没有一个训练记录包含这样的结点相关联的属性值组合，这种情形就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记录中的多数类。（2）在第二步，如果与相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点，其标号为与该结点相关联的训练记录中的多数类。tD决策树归纳的设计问题（1）如何分裂训练记录？（2）如何停止分裂过程？树增长过程的每个递归步骤都必须选择一个属性测试条件，将记录划分成较小的子集。为了实现这个步骤。算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量。决策树需要有结束条件，以终止决策树的生长过程。一个可能的策略是分裂结点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。表示属性测试条件的方法1、二元属性二元属性的测试条件产生两个可能的输出。体温恒温冷血二元属性的测试条件2、标称属性由于标称属性有多个属性值，它的测试条件可以用两种方法表示。婚姻状况单身已婚离异婚姻状况已婚单身，离异婚姻状况离异单身，已婚婚姻状况单身已婚，离异多路划分二元划分（通过属性值分组）3、序数属性序数属性也可以产生二元或多路划分，只要不违背序数属性值的有序性，就可以对属性值进行分组。衬衣尺码小号，中号大号，加大号衬衣尺码小号中号，加大号衬衣尺码小号，大号中号，加大号（a）（b）（c）4、连续属性对于连续属性来说，测试条件可以是具有二元输出的比较测试或也可以是具有形如输出的范围查询。)(vA)(vA),,2,1(1kivAvii年收入80k（a）（b）年收入是否10k{10k,25k}10k{25k,50k}{50k,80k}连续属性的测试条件有很多度量可以用来确定划分记录的最佳方法，这些度量用划分前和划分后的记录的类分布定义。选择最佳划分的度量设表示给定结点t中属于类i的记录所占的比例，有时，我们省略结点t，直接用表示该比例。在两类问题中，任意结点的类分布都可以记作其中。)|(tip),(10pp011ppip性别男女车型家用运动豪华C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）C0:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顾客IDv1v10v20v11（c）……选择最佳划分的度量通常是根据划分后子女结点不纯性的度量。不纯的程度越低，类分布就越倾斜。例如（0,1）的结点具有零不纯性，而均衡分布（0.5,0.5）的结点具有最高的不纯性。不纯性度量的例子包括：102)|(log)|()(citiptiptEntropy102)]|([1)(citiptGini)]|([max1)(_Ctipterrorionlassificati熵：基尼指数：分类误差：其中c是类的个数，并且在计算熵时，00log2O结点N1计数类=00类=16结点N3计数类=03类=13结点N2计数类=01类=150)6/6()6/0(122Gini0)6/6(log)6/6()6/0(log)6/0(22Entropy0]6/6,6/0max[1Error278.0)6/5()6/1(122Gini650.0)6/5(log)6/5()6/1(log)6/1(22Entropy167.0]6/5,6/1max[1Error5.0)6/3()6/3(122Gini1)6/3(log)6/3()6/3(log)6/3(22Entropy5.0]6/3,6/3max[1Error二元分类问题不纯性度量之间的比较不同的不纯性度量是一致的，但是作为测试条件的属性选择仍然因不纯性度量的选择而异。00.10.20.30.40.50.60.70.80.9100.10.20.30.40.50.60.70.80.91p熵Gini分类误差为确定测试条件的效果，我们需要比较父结点（划分前）的不纯性程度和子女结点（划分后）的不纯性程度，它们的差越大，测试条件的效果就越好。增益是一种可以用来确定划分效果的标准：kjjjvINvNparentI1)()()()(I其中，是给定结点的不纯性度量，N是父结点上的记录总数，k是属性值的个数，是与子女结点相关联的记录个数。)(jvNjv决策树算法选择最大化增益的测试条件。B是否结点N1结点N2A是否结点N1结点N2父结点C06C16Gini=0.500N1N2C042C133Gini=0.486N1N2C015C142Gini=0.3711、二元属性的划分2、标称属性的划分车型{运动，豪华}{家用}C091C173Gini0.468车型{运动}{家用，豪华}C082C1010Gini0.167车型{家用}{运动}{豪华}C0181C1307Gini0.163（a）二元划分(b)多路划分标称属性可以产生二元划分或者多路划分3、连续属性的划分1.使用二元划分2.划分点v选择N个记录中所有属性值作为划分点3.对每个划分进行类计数,Av和Av4.计算每个候选点v的Gini指标，并从中选择具有最小值的候选划分点5.时间复杂度为O(n2)类NoNoNoYesYesYesNoNoNoNo年收入排序后的值607075859095100120125220划分点556