数据挖掘导论第四章_924资料.docx

第四章 分类 分类任务的输入数据数记录的集合。每条记录也称实例或者样例，用元祖（x,y）表示，其中x是属性的集合，而y是一个特殊的集合，支出样例的类标号（也称为分类属性或者是目标属性）。属性主要是离散的，但是属性也可以包含连续特征。但是类标号必须是离散属性，这正是区分分类与回归（regression）的关键特征。回归数一种预测建模任务，其中目标属性y是连续的。 分类（calssification）分类的任务就是通过学习得到一个目标函数（target function）f，把每个属性集x映射到一个预先定义的类标号y。 目标函数也称分类模型（classification）。 描述性建模 分类模型可以作为解释性的工具，用于区分不同类中的对象 预测性建模 分类 模型还可以用于未知记录的类标号。 分类技术非常适合预测或者描述二元或标称类型的数据集，对于叙述分类（如把人类分为高收入、中收入低收入组），分类技术不太有效，因为分类技术不考虑隐含在目标类中的序关系。如子类与超类的关系（例如，人类和猿都是灵长类的动物，而灵长类是哺乳类的子类）也被忽略。 决策树归纳 决策树是有一种由节点和有向边组成的层次结构。书中包含三种节点. 根节点(root node)，它没有入边，但有零条或多条出边。 内部节点（internal node），恰有一条入边和两条或多条出边。 叶节点（leaf node）或终结点（reminal node），桥由一条入边和两条或多条出边。 非哺乳类 体温 胎生 哺乳动物 叶节点 内部节点 冷血 恒温 是 否 非哺乳动物 图 4-4 哺乳动物分类问题决策时 如何建立决策树 Hunt算法 在Hunt算法中，通过训练记录相机划分成较纯的子集，以递归方式建立决策树。设Dt是与节点t相关联的训练记录集，而y={y1y2……yc}是类标号，Hunt算法的递归定义如下： 如果Dt中所有的记录都属于同一个类yt，则t是叶节点，则用yt标记。 如果Dt中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将Dt中的记录分布到子女节点中，然后，对于每个子女节点，递归的调用该算法。 如果属性值的每种组合都在训练数据中出现，并且美中组合都有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设都太苛刻了。因此徐福佳的条件来处理一下的情况。 算法的第二步所创建的子女节点可能为空，即不存在与这些相关联的记录。如果没有一个训练记录包含与这样的节点相关联的属性值组合，这种情形就肯能发生，这时该节点成为一个叶节点，类标号为其父节点上训练记录中的多数类。 在第二步，如果与Dt相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该节点为叶节点，其标号与该节点相关联的训练记录中的多数类。 决策树归纳的设计问题，决策树归纳必须解决以下两个问题： （1）如何分裂训练记录？树增长过程中的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。因此算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估美中测试条件的客观度量。 （2）如何停止分裂过程？终止决策树生长的过程的两个策略：①分裂节点，知道所有记录都属于同一个类，或者所有记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但还是可以提前终止生长。 选择最佳划分的度量 选择最佳划分的度量通常是根据划分后子女节点不纯性的程度。不纯的程度越低，类分布就越倾斜。不纯性度量的例子包括： Entropy(t) = -i=0c-1p(i|t)logzp(i|t) Gini(t) = 1-i=0c-1[pit]2 Classfication error(t) = 1-max[pit] 其中c是类的个数，并且在计算熵时，。以上三种方法都是在类均衡时达到最大值，当所有记录都属于同一类时，达到最小值。 为了确定测试条件的效果，我们需要比较父结点（划分前）的不纯程度和子女结点（划分后）的不纯程度。它们的差越大，测试条件的效果就越好，带来的增益定义如下： 其中，I(.)是给定结点的不纯性度量，N是父结点上的记录总数，k是属性值的个数。 是与子女结点相关联的记录的个数。对于所有的测试条件来说，I(parent)是一个不变值，所以最大化增益等价于最小化子女结点的不纯性度量的加权平均。当选择熵作为不纯性度量时，熵的差就是所谓信息增益（information gain）。 二元属性划分：以下表为例计算。 父结点C06C1