数据挖掘导论第四章_924

1、第四章 分类分类任务的输入数据数记录的集合。每条记录也称实例或者样例，用元祖（x,y）表示，其中x是属性的集合，而y是一个特殊的集合，支出样例的类标号（也称为分类属性或者是目标属性）。属性主要是离散的，但是属性也可以包含连续特征。但是类标号必须是离散属性，这正是区分分类与回归（regression）的关键特征。回归数一种预测建模任务，其中目标属性y是连续的。分类（calssification）分类的任务就是通过学习得到一个目标函数（target function）f，把每个属性集x映射到一个预先定义的类标号y。目标函数也称分类模型（classification）。描述性建模 分类模型可以作为解

2、释性的工具，用于区分不同类中的对象预测性建模 分类 模型还可以用于未知记录的类标号。分类技术非常适合预测或者描述二元或标称类型的数据集，对于叙述分类（如把人类分为高收入、中收入低收入组），分类技术不太有效，因为分类技术不考虑隐含在目标类中的序关系。如子类与超类的关系（例如，人类和猿都是灵长类的动物，而灵长类是哺乳类的子类）也被忽略。决策树归纳决策树是有一种由节点和有向边组成的层次结构。书中包含三种节点.根节点(root node)，它没有入边，但有零条或多条出边。内部节点（internal node），恰有一条入边和两条或多条出边。叶节点（leaf node）或终结点（reminal node

3、），桥由一条入边和两条或多条出边。非哺乳类体温胎生哺乳动物叶节点 内部节点冷血恒温是否非哺乳动物图 4-4 哺乳动物分类问题决策时 如何建立决策树Hunt算法在Hunt算法中，通过训练记录相机划分成较纯的子集，以递归方式建立决策树。设Dt是与节点t相关联的训练记录集，而y=y1y2yc是类标号，Hunt算法的递归定义如下：（1） 如果Dt中所有的记录都属于同一个类yt，则t是叶节点，则用yt标记。（2） 如果Dt中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将D

4、t中的记录分布到子女节点中，然后，对于每个子女节点，递归的调用该算法。如果属性值的每种组合都在训练数据中出现，并且美中组合都有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设都太苛刻了。因此徐福佳的条件来处理一下的情况。（1） 算法的第二步所创建的子女节点可能为空，即不存在与这些相关联的记录。如果没有一个训练记录包含与这样的节点相关联的属性值组合，这种情形就肯能发生，这时该节点成为一个叶节点，类标号为其父节点上训练记录中的多数类。（2） 在第二步，如果与Dt相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该节点为叶节点，其标号

5、与该节点相关联的训练记录中的多数类。决策树归纳的设计问题，决策树归纳必须解决以下两个问题：（1）如何分裂训练记录？树增长过程中的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。因此算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估美中测试条件的客观度量。（2）如何停止分裂过程？终止决策树生长的过程的两个策略：分裂节点，知道所有记录都属于同一个类，或者所有记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但还是可以提前终止生长。选择最佳划分的度量选择最佳划分的度量通常是根据划分后子女节点不纯性的程度。不纯的程度越低，类分布就越倾斜。不纯性度量的例子

6、包括： Entropy(t) = -i=0c-1p(i|t)logzp(i|t) Gini(t) = 1-i=0c-1pit2 Classfication error(t) = 1-maxpit其中c是类的个数，并且在计算熵时，。以上三种方法都是在类均衡时达到最大值，当所有记录都属于同一类时，达到最小值。为了确定测试条件的效果，我们需要比较父结点（划分前）的不纯程度和子女结点（划分后）的不纯程度。它们的差越大，测试条件的效果就越好，带来的增益定义如下：其中，I(.)是给定结点的不纯性度量，N是父结点上的记录总数，k是属性值的个数。是与子女结点相关联的记录的个数。对于所有的测试条件来说，I(pa

7、rent)是一个不变值，所以最大化增益等价于最小化子女结点的不纯性度量的加权平均。当选择熵作为不纯性度量时，熵的差就是所谓信息增益（information gain）。二元属性划分：以下表为例计算。父结点C06C16Gini=0.5分类AN1N2C042C133Gini=0.486分类BN1N2C015C142Gini=0.371Gini(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中的第二个公式计算标称属性的划分：与二元划分类似，只不过多计算一些结点

8、而已。一般来说，多路划分的Gini指标比二元划分都小，因为二元划分实际上合并了多路划分的某些输出，自然降低了自己的纯度。连续属性的划分：总体思路是把连续属性划分为若干个区间，在套用1、2中的思路。但在这之前，如果先对训练记录按照分类属性进行排序，能够把时间复杂度从降低至。其他还有一些可以考虑的优化方案：如仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点。增益率熵和Gini指标等不纯性度量趋向有利于具有大量不同值得属性。这样，即使在不太极端情形下，也不会希望产生大量输出的测试条件，因为与每个划分相关联的记录太少，以致不能做出可靠的预测。解决该问题的策略有两种。第一种是限制测试条件只能是二元

9、划分（CART），另一种策略是修改评估划分的标准，把属性测试条件产生的输出数也考虑进去。如，C4.5的增益率（gain ratio）定义如下：其中，划分信息，而k是划分的总数。决策树归纳算法首先，给出下表算法称作TreeGrowth的决策树归纳算法的框架。该算法的输入是训练记录集E和属性集F。算法递归地选择最优的属性来划分数据（步骤7），并扩充树的叶结点（步骤11和步骤12），知道满足结束条件（步骤1）。算法 决策树归纳算法的框架TreeGrowth(E,F)1: if stopping_cond(E,F)=true then2: leaf=createNode()3: leaf. label

10、=Classify(E)4: return leaf5: else6: root=createNode()7: root. test_cond=find_best_split(E,F)8: 令V=v | v是root. test_cond的一个可能的输出9: for 每个vV do10: = e| root. test_cond(e)=v, 并且eE11: child=TreeGrowth(,F)12: 将child作为root的派生结点添加到树中，并将边(root->child)标记为v13: end for14: end if15: return root以上算法的细节如下：1. 函

11、数createNode()为决策树建立新的结点。决策树的结点或一个测试条件，记作node. test_cond，或者是一个类标号，记作node. Label。2. 函数find_best_split()确定应当选择哪个属性作为划分训练记录的测试条件。3. 函数Classify()为叶结点确定类标号，对于每个叶结点t，令p( i | t)表示该节点上属于类i的训练记录所占的比例，在大多数情况下，都将叶结点指派到具有多数记录的类：其中，操作argmax返回最大化p(i|t)的参数值。P(i|t)还可用来估计分配到叶结点t的记录属于类i的概率。4. 函数stopping_cond()通过检查是否所有

12、的记录都属于同一个类，或者都具有相同的属性值，决定是否终止决策树的增长。终止函数的另一种方法是，检查记录数是否小于某个最小阈值。建立决策树后，可以进行树剪枝（tree-pruning），以减小决策树的规模。决策树过大容易造成过分拟合（overfitting）。算法特点下面是对决策树归纳算法重要特点的总结。1. 决策树归纳是一种构建分类模型的非参数方法。它不需要任何先验假设，不假定类和其他属性服从一定的概率分布。2. 找到最佳的决策树是NP完全问题。3. 已开发的构建决策树技术不需要昂贵的计算代价。决策树一旦建立，未知样本的分类非常快，最坏情况的时间复杂度O(w)，其中w是数的最大深度。4. 决

13、策树相对容易解释。5. 决策树是学习离散值函数的典型代表。但是，它不能很好的推广到某些特定的布尔问题。6. 决策树算法对于噪声的具有很好的健壮性（鲁棒性），采用避免过分拟合的方法之后尤其如此。7. 冗余属性不会对决策树的准确率造成不利影响。然而，数据集中的不相关属性会对其造成影响。8. 可能造成数据碎片问题（data fragmentation）。9. 子树可能在决策树中重复多次。10. 决策边界（decision boundary，两个不同类的相邻区域之间的边界称作决策边界）可能不平行于x, y轴。此时，就会涉及到斜决策树（oblique decision tree）和构造归纳（constr

14、uctive induction，书2.3.5节，会产生冗余属性）的相关问题。11. 不纯性度量方法的选择对决策树算法的性能影响很小。模型的过拟合分类模型的误差大致分为两种：训练误差（training error）和泛化误差（generalization error）。一般来说，训练误差随模型的复杂度增加而降低，泛化误差与之相反。过拟合现象：模型过于追求对训练记录的拟合程度而失去了对未知数据的预测和泛化能力。反之，如果训练集很小，则可能造成拟合补足的现象。造成过拟合的原因噪声导致的过分拟合：由于某些离群点和特殊的训练记录导致的模型复杂度增加，从而导致模型的泛化能力和预测能力下降。缺乏代表性样本

15、导致的过分拟合：根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会产生这样的模型。多重比较（multiple comparison procedure）过程的学习算法导致的过分拟合：设是初始决策树，是插入属性x的内部结点后的决策树。原则上，如果观察到的增益(，)大于某个预先定义的阈值，就可以将x添加到树中。如果只有一个属性测试条件，则可以通过足够大的阈值来避免插入错误的结点。然而，在实践中，可用的属性终止测试条件不止一个，并且决策树算法必须从候选集中选择最佳属性来划分数据。在这种情况下，算法实际上

16、是使用多重比较过程来决定是否需要扩展决策树。更具体地说，这是测试(，)>，而不是测试(，)>。随着候选个数k的增加，找到(，)>的几率也在增加。除非根据k修改增益函数或阈值，否则算法会不经意间在模型上增加一些欺骗性的结点，导致模型过分拟合。大量的候选属性和少量的训练记录最后可能导致模型的过分拟合。泛化误差估计1. 再代入估计再代入估计方法假设训练数据集可以很好地代表整体数据，因而，可以使用训练误差（又称再代入误差）提供对泛化误差的乐观估计。但是，训练误差通常是泛化误差的一种很差的估计。2. 结合模型复杂度估计一般来说，模型越是复杂，出现先过拟合的几率就越高。这种策略与应用众所

17、周知的奥卡姆剃刀（Occams razor）或节俭原则（principle of parsimony）一致。奥卡姆剃刀：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。悲观误差评估：第一种方法明确使用训练误差与模型复杂度罚项（penalty term）的和计算泛化误差。结果泛化误差可以看作模型的悲观误差估计（pessimistic error estimate）。例如，设n(t)是结点t分类的训练记录数，e(t)是被误分类的记录数。决策树T的悲观误差估计可以用下式计算：其中，k是决策树的结点数，e(T)是决策树的总训练误差，是训练记录数，是每个结点对应的罚项。最小描述长度原则

18、：另一种结合模型复杂度的方法是基于称作最小描述长度（minimum description length, MDL）原则的信息论方法。为了解释说明该原则，考虑下图中的例子。在该例中，A和B都是已知属性x值得给定记录集。另外，A知道每个记录的确切类标号，而B却不知道这些信息。B可以通过要求A顺序传送类标号而获得每个记录的分类。一条消息需要(n)比特的信息，其中n是记录总数。另一种可能，A决定建立一个分类模型，概括x和y之间的关系。在传递给B前，模型用压缩形式编码。如果模型的准确率是100%，那么传输的代价就等于模型编码的代价。否则，A还必须传输哪些数据被模型错误分类信息。传输的总代价是：其中，等

19、式右边的第一项是模型编码的开销，而第二项是误分类记录编码的开销。根据MDL原则，我们寻找最小化开销函数的模型。3. 估计统计上界泛化误差也可以用训练误差的统计修正来估计。因为泛化误差倾向于比训练误差大，所以统计修正通常是计算训练误差的上界。具体计算和证明会涉及到概率论和数理统计的知识。4. 使用确认集在该方法中，我们把原始的训练数据集分为两个较小的子集，一个自己用于训练，而另一个称作确认集，用于估计泛化误差。该方法通常用于参数控制获得具有不同复杂度模型的分类技术。通过调整学习算法中的参数（如决策树剪枝的程度），直到学习算法产生的模型在确认集上达到最低的错误率，可以估计最佳模型的复杂度。虽然该方

20、法为评估模型在未知样本上的性能提供了较好的办法，但用于训练的记录减少了。处理决策树中的过拟合先剪枝（提前终止规则）：树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树，然而，很难为提前终止选取正确的阈值。阈值太高将导致拟合不足的模型，而阈值太低就不能充分地解决过分拟合的问题。此外，即便使用已有的属性测试条件得不到显著的增益，接下来的划分也可能产生较好的子树。后剪枝：在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。修剪的方法有两种：1. 用新的叶结点替换子树

21、，该叶结点的类标号有子树下记录中的多数类决定。2. 用子树中最常使用的分支代替子树（常见的有子树提升（subtree raising）和子树替换（subtree replacement）。当模型不能改进时，终止剪枝步骤。分类器性能评估和比较分类器性能评估保持方法（holdout）：将被标记的原始数据分成两个不相交的集合，分别称为训练集和检验集。在训练数据集上归纳分类模型，在检验集上评估模型的性能。两者的比例通常是1:1或1:2。保持方法的局限性：第一，用于训练的被标记样本较少；第二，模型可能高度依赖于训练集和检验集的组成；最后，训练集和检验集不再是互相独立的。因为训练集和检验集源于同一个数据集

22、，在一个子集中超出比例的类在另一个子集就低于比例，反之亦然。随机二次抽样（random subsampling）：多次重复保持方法来改进对分类器性能的估计，这种方法称作随机二次抽样。设是第i次迭代的模型准确率，总准确率是随机二次抽样也会遇到一些与保持方法同样的问题。交叉验证（cross-validation）：在方法中，每个记录用于训练的次数相同，并且恰好检验一次。K折交叉检验定义如下：把数据分为大小相同的k份，在每次运行，选择其中一份作为检验集，而其余的作为训练集，该过程重复k次，使得每份数据都用于检验恰好一次。总误差是所有k次运行的误差之和。留一（leave-one-out）方法是k折交叉

23、检验的特殊情况，即每个检验集只有一个记录。注意：以上三种方法中，训练记录采取的都是不放回抽样。自助法（bootstrap）：自助方法中，训练记录采用有放回抽样。如果原始数据有N个记录，可以证明，平均来说，大小为N的自助样本大约包含原始数据中63.2%的记录。没有抽中的记录成为检验集的一部分，将训练集建立的模型应用到检验集上，得到资助样本准确率的一个估计。抽样过程重复b次，产生b个自助样本。按照如何计算分类器的总准确率，有几种不同的自助抽样方法。常用的方法之一是.632自助（.632 bootstrap），它通过组合每个自助样本的准确率（）和由包含所有标记样本的训练集计算的准确率（）计算总准确率