数据挖掘导论第四章_924

第四章分类分类任务的输入数据数记录的集合。每条记录也称实例或者样例，用元祖（x,y）表示，其中x是属性的集合，而y是一个特殊的集合，支出样例的类标号（也称为分类属性或者是目标属性）。属性主要是离散的，但是属性也可以包含连续特征。但是类标号必须是离散属性，这正是区分分类与回归（regression）的关键特征。回归数一种预测建模任务，其中目标属性y是连续的。分类（calssification）分类的任务就是通过学习得到一个目标函数（targetfunction）f，把每个属性集x映射到一个预先定义的类标号y。目标函数也称分类模型（classification）。描述性建模分类模型可以作为解释性的工具，用于区分不同类中的对象预测性建模分类模型还可以用于未知记录的类标号。分类技术非常适合预测或者描述二元或标称类型的数据集，对于叙述分类（如把人类分为高收入、中收入低收入组），分类技术不太有效，因为分类技术不考虑隐含在目标类中的序关系。如子类与超类的关系（例如，人类和猿都是灵长类的动物，而灵长类是哺乳类的子类）也被忽略。决策树归纳决策树是有一种由节点和有向边组成的层次结构。书中包含三种节点.根节点(rootnode)，它没有入边，但有零条或多条出边。内部节点（internalnode），恰有一条入边和两条或多条出边。叶节点（leafnode）或终结点（reminalnode），桥由一条入边和两条或多条出边。图4-4哺乳动物分类问题决策时非哺乳动物非哺乳类体温胎生哺乳动物恒温冷血内部节点否是如何建立决策树Hunt算法在Hunt算法中，通过训练记录相机划分成较纯的子集，以递归方式建立决策树。设𝐷𝑡是与节点t相关联的训练记录集，而y={𝑦1𝑦2……𝑦𝑐}是类标号，Hunt算法的递归定义如下：（1）如果𝐷𝑡中所有的记录都属于同一个类𝑦𝑡，则t是叶节点，则用𝑦𝑡标记。（2）如果𝐷𝑡中包含属于多个类的记录，则选择一个属性测试条件（attributetestcondition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将𝐷𝑡中的记录分布到子女节点中，然后，对于每个子女节点，递归的调用该算法。如果属性值的每种组合都在训练数据中出现，并且美中组合都有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设都太苛刻了。因此徐福佳的条件来处理一下的情况。（1）算法的第二步所创建的子女节点可能为空，即不存在与这些相关联的记录。如果没有一个训练记录包含与这样的节点相关联的属性值组合，这种情形就肯能发生，这时该节点成为一个叶节点，类标号为其父节点上训练记录中的多数类。（2）在第二步，如果与𝐷𝑡相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该节点为叶节点，其标号与该节点相关联的训练记录中的多数类。决策树归纳的设计问题，决策树归纳必须解决以下两个问题：（1）如何分裂训练记录？树增长过程中的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。因此算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估美中测试条件的客观度量。（2）如何停止分裂过程？终止决策树生长的过程的两个策略：①分裂节点，知道所有记录都属于同一个类，或者所有记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但还是可以提前终止生长。选择最佳划分的度量选择最佳划分的度量通常是根据划分后子女节点不纯性的程度。不纯的程度越低，类分布就越倾斜。不纯性度量的例子包括：Entropy(t)=−∑𝑝(𝑖|𝑡)𝑙𝑜𝑔𝑧𝑝(𝑖|𝑡)𝑐−1𝑖=0Gini(t)=1-∑[𝑝(𝑖|𝑡)]2𝑐−1𝑖=0Classficationerror(t)=1-max[𝑝(𝑖|𝑡)]其中c是类的个数，并且在计算熵时，00log2O。以上三种方法都是在类均衡时达到最大值，当所有记录都属于同一类时，达到最小值。为了确定测试条件的效果，我们需要比较父结点（划分前）的不纯程度和子女结点（划分后）的不纯程度。它们的差越大，测试条件的效果就越好，带来的增益定义如下：kjjjvINvNparentI1)()()(其中，I(.)是给定结点的不纯性度量，N是父结点上的记录总数，k是属性值的个数。)(jvN是与子女结点jv相关联的记录的个数。对于所有的测试条件来说，I(parent)是一个不变值，所以最大化增益等价于最小化子女结点的不纯性度量的加权平均。当选择熵作为不纯性度量时，熵的差就是所谓信息增益（informationgain）info。二元属性划分：以下表为例计算。父结点C06C16Gini=0.5分类A分类BGini(A)=(7/12)*Gini(N1)+(5/12)*Gini(N2)Gini(B)=(5/12)*Gini(N1)+(7/12)*Gini(N2)Gini(N1)和Gini(N2)由2.4中的第二个公式计算标称属性的划分：与二元划分类似，只不过多计算一些结点而已。一般来说，多路划分的Gini指标比二元划分都小，因为二元划分实际上合并了多路划分的某些输出，自然降低了自己的纯度。连续属性的划分：总体思路是把连续属性划分为若干个区间，在套用1、2中的思路。但在这之前，如果先对训练记录按照分类属性进行排序，能够把时间复杂度从)(2NO降低至))log((NNO。其他还有一些可以考虑的优化方案：如仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点。N1N2C042C133Gini=0.486N1N2C015C142Gini=0.371增益率熵和Gini指标等不纯性度量趋向有利于具有大量不同值得属性。这样，即使在不太极端情形下，也不会希望产生大量输出的测试条件，因为与每个划分相关联的记录太少，以致不能做出可靠的预测。解决该问题的策略有两种。第一种是限制测试条件只能是二元划分（CART），另一种策略是修改评估划分的标准，把属性测试条件产生的输出数也考虑进去。如，C4.5的增益率（gainratio）定义如下：SplitInfoGainRatioinfo其中，划分信息kiiivPvPSplitInfo12)(log)(，而k是划分的总数。决策树归纳算法首先，给出下表算法称作TreeGrowth的决策树归纳算法的框架。该算法的输入是训练记录集E和属性集F。算法递归地选择最优的属性来划分数据（步骤7），并扩充树的叶结点（步骤11和步骤12），知道满足结束条件（步骤1）。算法决策树归纳算法的框架TreeGrowth(E,F)1:ifstopping_cond(E,F)=truethen2:leaf=createNode()3:leaf.label=Classify(E)4:returnleaf5:else6:root=createNode()7:root.test_cond=find_best_split(E,F)8:令V={v|v是root.test_cond的一个可能的输出}以上算法的细节如下：1.函数createNode()为决策树建立新的结点。决策树的结点或一个测试条件，记作node.test_cond，或者是一个类标号，记作node.Label。2.函数find_best_split()确定应当选择哪个属性作为划分训练记录的测试条件。3.函数Classify()为叶结点确定类标号，对于每个叶结点t，令p(i|t)表示该节点上属于类i的训练记录所占的比例，在大多数情况下，都将叶结点指派到具有多数记录的类：)|(argmax.tiplabelleafi其中，操作argmax返回最大化p(i|t)的参数值。P(i|t)还可用来估计分配到叶结点t的记录属于类i的概率。4.函数stopping_cond()通过检查是否所有的记录都属于同一个类，或者都具有相同的属性值，决定是否终止决策树的增长。终止函数的另一种方法是，检查记录数是否小于某个最小阈值。建立决策树后，可以进行树剪枝（tree-pruning），以减小决策树的规模。决策树过大容易造成过分拟合（overfitting）。9:for每个v∈Vdo10:vE={e|root.test_cond(e)=v,并且e∈E}11:child={TreeGrowth(vE,F)}12:将child作为root的派生结点添加到树中，并将边(root-child)标记为v13:endfor14:endif15:returnroot算法特点下面是对决策树归纳算法重要特点的总结。1.决策树归纳是一种构建分类模型的非参数方法。它不需要任何先验假设，不假定类和其他属性服从一定的概率分布。2.找到最佳的决策树是NP完全问题。3.已开发的构建决策树技术不需要昂贵的计算代价。决策树一旦建立，未知样本的分类非常快，最坏情况的时间复杂度O(w)，其中w是数的最大深度。4.决策树相对容易解释。5.决策树是学习离散值函数的典型代表。但是，它不能很好的推广到某些特定的布尔问题。6.决策树算法对于噪声的具有很好的健壮性（鲁棒性），采用避免过分拟合的方法之后尤其如此。7.冗余属性不会对决策树的准确率造成不利影响。然而，数据集中的不相关属性会对其造成影响。8.可能造成数据碎片问题（datafragmentation）。9.子树可能在决策树中重复多次。10.决策边界（decisionboundary，两个不同类的相邻区域之间的边界称作决策边界）可能不平行于x,y轴。此时，就会涉及到斜决策树（obliquedecisiontree）和构造归纳（constructiveinduction，书2.3.5节，会产生冗余属性）的相关问题。11.不纯性度量方法的选择对决策树算法的性能影响很小。模型的过拟合分类模型的误差大致分为两种：训练误差（trainingerror）和泛化误差（generalizationerror）。一般来说，训练误差随模型的复杂度增加而降低，泛化误差与之相反。过拟合现象：模型过于追求对训练记录的拟合程度而失去了对未知数据的预测和泛化能力。反之，如果训练集很小，则可能造成拟合补足的现象。造成过拟合的原因噪声导致的过分拟合：由于某些离群点和特殊的训练记录导致的模型复杂度增加，从而导致模型的泛化能力和预测能力下降。缺乏代表性样本导致的过分拟合：根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会产生这样的模型。多重比较（multiplecomparisonprocedure）过程的学习算法导致的过分拟合：设0T是初始决策树，xT是插入属性x的内部结点后的决策树。原则上，如果观察到的增益Δ(0T，xT)大于某个预先定义的阈值α，就可以将x添加到树中。如果只有一个属性测试条件，则可以通过足够大的阈值α来避免插入错误的结点。然而，在实践中，可用的属性终止测试条件不止一个，并且决策树算法必须从候选集},...,,{21kxxx中选择最佳属性maxx来划分数据。在这种情况下，算法实际上是使用多重比较过程来决定是否需要扩展决策树。更具体地说，这是测试Δ(0T，mzxxT)α，而不是测试Δ(0T，xT)α。随着候选个数k的增加，找到Δ(0T，mzxxT)α的几率也在增加。除非根据k修改增益函数Δ或阈值α，否则算法会不经意间在模型上增加一些欺骗性的结点，导致模型过分拟合。大量的候选属性和少量的训练记录最后可能导致模型的过分拟合。泛化误差估计1.再代入估计再代入估计方法假设训练数据集可以很好地代表整体数据，因而，可以使用训练误差（又称再代入误差）提供对泛化误差的乐观估计。但是，训练误差通常是泛化误差的一种很差的估计。2.结合模型复杂度估计一般来说，模型越是复杂，出现先过拟合的几率就越高。这种策略与应用众所周知的奥卡姆剃刀（Occam’srazor）或节俭原则（principleofparsimony）