分类:基本概念、决策树与模型评估

分类 （classification）分类任务就是通过学习得到一个目标函数（targetfunction）f，把每个属性集x映射到一个预先定义的类别号y。目标函数也称分类模型（classification model）。分类模型可用于以下目的：描述性建模、预测性建模

分类技术(或分类法)是一种根据输入数据集建立分类模型的系统方法。分类法的例子包括决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法。

首先，需要一个训练集（training set),它又类标号一致的记录组成。使用训练集建立分类模型，该模型随后运用于检验集（test set )，检验集由类标号未知的记录组成。

分类模型的性能根据模型正确和错误预的检验记录计数进行评估,这些计数存放在称作混淆矩阵( confusion matrix)的表格中。表4-2描述二元分类问题的混滑矩阵。表中每个表项 fij 表示实际类标号为i但被预测为类j的记录数,例如, f01 代表原本属于类0但被误分为类1的记录数。按照混淆矩阵中的表项,被分类模型正确预测的样本总数是( f11+f00 ),而被错误预测的样本总数是( f10+f01 )。

同样，分类模型的性能可以用错误率（error rate）来表示，其定义如下：

为了解释决策树分类的工作原理,考虑上一节中介绍的脊椎动物分类问题的简化版本。这里我们不把脊椎动物分为五个不同的物种,而只考虑两个类别:哺乳类动物和非哺乳类动物。假设科学家发现了一个新的物种,怎么判断它是哺乳动物还是非哺乳动物呢?一种方法是针对物种的特征提出一系列问题。第一个问题可能是,该物种是冷血动物还是恒温动物。如果它是冷血的,则该物种肯定不是哺乳动物;否则它或者是某种鸟,或者是某种哺乳动物。如果它是恒温的,需要接着问:该物种是由雌性产越进行繁殖的吗?如果是,则它肯定为哺乳动物,否则它有可能是非哺乳动物(鸭嘴兽和针鼹这些产蛋的哺乳动物除外)。

上面的例子表明,通过提出一系列精心构思的关于检验记录属性的问题,可以解决分类问题。每当一个问题得到答案,后续的问题将随之而来,直到我们得到记录的类标号。这一系列的问题和这些问题的可能回答可以组织成决策树的形式,决策树是一种由结点和有向边组成的层次结图4-4显示哺乳类动物分类问题的决策树,树中包含三种结点。

根节点 （root node),它没有入边，但有零条或多条出边。

内部节点 （internal node)，恰有一条入边和两条或多条出边。

叶节点 （leaf node)或 终结点 （terminal node）。恰有一条入边，但没有出边。

在决策树中,毎个叶结点都赋予一个类标号。非终结点(non- terminal node)(包括根结点和内部结点)包含属性测试条件,用以分开具有不同特性的记录。例如,在图44中,在根结点处,使用体温这个属性把冷血脊権动物和恒温脊椎动物区别开来。因为所有的冷血脊椎动物都是非乳动物,所以用一个类称号为非嘴乳动物的叶结点作为根结点的右子女。如果脊椎动物的体温是恒温的,则接下来用胎生这个属性来区分乳动物与其他恒温动物(主要是鸟类)。

一旦构造了决策树,对检验记录进行分类就相当容易了。从树的根结点开始,将测试条件用于检验记录,根据测试结果选择适当的分支,沿着该分支或者到达另一个内部结点,使用新的测试条件,或者到达一个叶结点。到达叶结点之后,叶结点的类称号就被赋值给该检验记录。例如图45显示应用决策树预测火烈鸟的类标号所经过的路径,路径终止于类称号为非哺乳动物的叶结点。

在 Hunt算法中,通过将训练记录相继划分成较纯的子集,以递归方式建立决策树。设 是与结点t相关联的训练记录集,而y={y1,y2…,yc}是类标号,Humt算法的递归定义如下:

(1)如果 中所有记录都属于同一个类 ,则t是叶结点,用 标记。

(2)如果 中包含属于多个类的记录,则选择一个 属性测试条件 ( attribute test condition),将记录划分成较小的子集。对于测试条件的每个输出,创建一个子女结点,并根据测试结果将 中的记录分布到子女结点中。然后,对于每个子女结点,递归地调用该算法。为了解释该算法如何执行,考虑如下问题:预测贷款申请者是会按时归还贷款,还是会拖欠贷款。对于这个问题,训练数据集可以通过考察以前货款者的贷放记录来构造。在图4-6所示的例子中,每条记录都包含贷款者的个人信息,以及货款者是否拖欠货款的类标号。

该分类问题的初始决策树只有一个结点,类标号为“拖欠款者=否”(见图4-7a),意味大多数贷款者都按时归还贷款。然而,该树需要进一步的细化,因为根结点包含两个类的记录。根据“有房者”测试条件,这些记录被划分为较小的子集,如图4-7b所示。选取属性测试条件的理由稍后讨论,目前,我们假定此处这样选是划分数据的最优标准。接下来,对根结点的每个子女递归地调用Hunt算法。从图4-6给出的训练数据集可以看出,有房的货款者都按时偿还了贷款,因此,根结点的左子女为叶结点,标记为“抱欠款者=否”(见图4-7b)。对于右子女,我们需要继续递归调用Hunt算法,直到所有的记录都属于同一个类为止。每次递归调用所形成的决策树显示在图4-7c和图4-7d中。

如果属性值的每种组合都在训练数据中出现,并且每种组合都具有算法是有效的。但是对于大多数实际情况,这些假设太苛刻了,因此,需要附加的条件来处理以下的情况。

(1)算法的第二步所创建的子女结点可能为空,即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合,这种情形就可能发生。这时,该结点成为叶结点,类标号为其父结点上训练记录中的多数类。

(2)在第二步,如果与D相关联的所有记录都具有相同的属性值(目标属性除外),则不可能进一步划分这些记录。在这种情况下,该结点为叶结点,其标号为与该结点相关联的训练记录中的多数类。

决策树归纳的学习算法必须解决下面两个问题。

(1) 如何分裂训练记最? 树增长过程的每个递归步都必须选择一个属性测试条件,将记录划分成较小的子集。为了实现这个步骤,算法必须提供为不同类型的属性指定测试条件的方法,并且提供评估每种测试条件的客观度量。

(2) 如何停止分裂过程? 需要有结束条件,以终止决策树的生长过程。一个可能的策略是分裂结点,直到所有的记录都属于同一个类,或者所有的记录都具有相同的属性值。尽管两个结东条件对于结束决策树归纳算法都是充分的,但是还可以使用其他的标准提前终止树的生长过程。提前终止的优点将在4.4.5节讨论。

决策树归纳算法必须为不同类型的属性提供表示属性测试条件和其对应输出的方法。

二元属性 二元属性的测试条件产生两个可能的输出,如图4-8所示。

标称属性 由于标称属性有多个属性值,它的测试条件可以用两种方法表示,如图4-9所示对于多路划分(图4-9a),其输出数取决于该属性不同属性值的个数。例如,如果属性婚姻状况有三个不同的属性值一单身、已婚、离异,则它的测试条件就会产生一个三路划分。另一方面,某些决策树算法(如CART)只产生二元划分,它们考虑创建k个属性值的二元划分的所有 +1种方法。图4-9b显示了把婚姻状况的属性值划分为两个子集的三种不同的分组方法。

序数属性 序数属性也可以产生二元或多路划分,只要不违背序数属性值的有序性,就可以对属性值进行分组。图410显示了技照属性村衣尺吗划分训练记录的不同的方法。图4-10a和图4-10b中的分组保持了属性值间的序关系,而图4-10c所示的分组则违反了这一性质,因为它把小号和大号分为一组,把中号和加大号放在另一组。

连续属性对于连续属性来说,测试条件可以是具有二元输出的比较测试(A

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com