logo资料库

数据挖掘十大算法之决策树详解.docx

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：1.58M 资料格式：docx 举报 版权申诉
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页，剩余部分请下载后查看
    数据挖掘十大算法之决策树详解
    分类误差
    数据挖掘十大算法之决策树详解 在 2006 年 12 月召开的 IEEE 数据挖掘国际会议上（ICDM， International Conference on Data Mining），与会的各位专家选出了当时的十大数据挖掘算法（ top 10 data mining algorithms ）， 可以参见文献【1】。本博客已经介绍过的位列十大算法之中的算法包括： [1] kk-means 算法（http://blog.csdn.net/baimafujinji/article/details/50570824） [2] 支持向量机 SVM（http://blog.csdn.net/baimafujinji/article/details/49885481） [3] EM 算法（http://blog.csdn.net/baimafujinji/article/details/50626088） [4] 朴素贝叶斯算法（http://blog.csdn.net/baimafujinji/article/details/50441927） [5] kkNN 算法（http://blog.csdn.net/baimafujinji/article/details/6496222） 本文主要介绍机器学习中的决策树模型。决策树模型是一类算法的集合，在数据挖掘十大算 法中，具体的决策树算法占有两席位置，即 C4.5 和 CART 算法，本文都会介绍到它们。 欢迎关注白马负金羁的博客 http://blog.csdn.net/baimafujinji，为保证公式、图表得以正确显 示，强烈建议你从该地址上查看原版博文。本博客主要关注方向包括：数字图像处理、算法 设计与分析、数据结构、机器学习、数据挖掘、统计分析方法、自然语言处理。 从分类问题开始 分类（Classification）任务就是确定对象属于哪个预定义的目标类。分类问题不仅是一个普 遍存在的问题，而且是其他更加复杂的决策问题的基础，更是机器学习和数据挖掘技术中最 庞大的一类算法家族。我们前面介绍过的很多算法（例如 SVM，朴素贝叶斯等）都可以用 来解决分类问题。作为本文的开始，我们首先来简单回顾一下什么是分类。 假设我们现在有如下表所示的一个属性集（feature set），它收集了几个病患的症状和对应的 病症。症状包括头疼的程度、咳嗽的程度、体温以及咽喉是否肿痛，这些症状（feature）的 组合就对应一个病症的分类（Cold 还是 Flu）。 分类问题的本质就是当给定这样一个数据集后，要求我们训练出（或建立）一个模型 ff。当 出现一组新的特征向量时，要求我们预测（或判断）拥有这样一组特征向量的对象应当属于 哪个类别。就我们现在给出的例子而言，假设你是一名医生，现在收治了一位新的病患，然 后你通过问诊得知他的一些症状（包括头疼的程度、咳嗽的程度、体温以及咽喉是否肿痛）， 然后你就要根据你已经建立好的模型来判断该病人得的到底是 Cold（普通感冒）还是 Flu（流
    行性感冒）。 分类问题的类别数目可以是两类也可以是多类。二分类问题是最简单的分类问题，而多分类 问题模型可以在二分类模型的基础上进行构建。我们在前面文章中一直使用的鸢尾花数据集 就是一个典型的多分类问题，问题的最终目标是判断给定一朵花，它应该属于 setosa、 versicolor 和 virginica 中的哪一类。 决策树基础 决策树是一种用于对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点的类型有两种：内部节点和叶子节点。其中，内部节点表示一个特征或属 性的测试条件（用于分开具有不同特性的记录），叶子节点表示一个分类。 一旦我们构造了一个决策树模型，以它为基础来进行分类将是非常容易的。具体做法是，从 根节点开始，地实例的某一特征进行测试，根据测试结构将实例分配到其子节点（也就是选 择适当的分支）；沿着该分支可能达到叶子节点或者到达另一个内部节点时，那么就使用新 的测试条件递归执行下去，直到抵达一个叶子节点。当到达叶子节点时，我们便得到了最终 的分类结果。 下图是一个决策树的示例（注意我们仅用了两个 feature 就对数据集中的 5 个记录实现了准 确的分类）： 构建决策树——Hunt 算法 Hunt 算法是一种采用局部最优策略的决策树构建算法，它同时也是许多决策树算法的基础， 包括 ID3、C4.5 和 CART 等。该算法的具体执行步骤如下： 在 Hunt 算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。设 DtDt 是与结点 tt 相关联的训练记录集，而 y={y1,y2,⋯,yc}y={y1,y2,⋯,yc}是类标号，Hunt 算法的 递归定义如下： (1) 如果 DtDt 中所有记录都属于同一个类，则 tt 是叶结点，用 ytyt 标记。 (2) 如果 DtDt 中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition）， 将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果 将 DtDt 中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。
    为了演示这方法，我们选用文献【2】中的一个例子来加以说明：预测贷款申请者是会按时 归还贷款，还是会拖欠贷款。对于这个问题，训练数据集可以通过考察以前贷款者的贷款记 录来构造。在下图所示的例子中，每条记录都包含贷款者的个人信息，以及贷款者是否拖欠 贷款的类标号。 该分类问题的初始决策树只有一个结点，类标号为“拖欠货款者＝否”（见图 a），意味大多 数贷款者都按时归还贷款。然而，该树需要进一步的细化，因为根结点包含两个类的记录。 根据“有房者”测试条件，这些记录被划分为较小的子集，如图 b 所示。接下来，对根结点 的每个子女递归地调用 Hunt 算法。从下图给出的训练数据集可以看出，有房的贷款者都按 时偿还了贷款，因此，根结点的左子女为叶结点，标记为“拖欠货款者二否”（见图 b)。对 于右子女，我们需要继续递归调用 Hunt 算法，直到所有的记录都属于同一个类为止。每次 递归调用所形成的决策树显示在图 c 和图 d 中。
    如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类标号，则 Hunt 算法是有效的。但是对于大多数实际情况，这些假设太苛刻了，因此，需要附加的条件来处 理以下的情况： 算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关联的记录。如果没有一 个训练记录包含与这样的结点相关联的属性值组合，这种情形就可能发生。这时，该结点成 为叶结点，类标号为其父结点上训练记录中的多数类。 在第二步，如果与 DtDt 相关联的所有记录都具有相同的属性值（目标属性除外），则不可 能进一步划分这些记录。在这种情况下，该结点为叶结点，其标号为与该结点相关联的训练 记录中的多数类。 此外，在上面这个算法过程中，你可能会疑惑：我们是依据什么原则来选取属性测试条件的， 例如为什第一次选择“有房者”来作为测试条件。事实上，如果我们选择的属性测试条件不 同，那么对于同一数据集来说所建立的决策树可能相差很大。如下图所示为基于前面预测病 人是患了 Cold 还是 Flu 的数据集所构建出来的另外两种情况的决策树：
    事实上，在构建决策树时我们需要关心的问题包括： How to build optimal Decision Tree? How to choose attribute values at each decision point (node)? How to choose number of branches at each node and attribute values for partitioning the data? When to stop the growth of the tree? 我会在接下来的部分回答上述这些问题。 构建决策树进阶：GiniGini 测度与划分 构建一棵最优的决策树是一个 NP 难问题！所以我们只能采用一些启发式策略来解决： Choose an attribute to partition the data at the node such that each partition is as homogeneous (least impure) as possible. This means we would like to see most of the instances in each partition belonging to as few classes as possible and each partition should be as large as possible. We can stop the growth of the tree if all the leaf nodes are largely dominated by a single class (that is the leaf nodes are nearly pure). 现在新的问题来了：如何评估节点的 Impurity？通常可以使用的指标有如下三个（实际应用 时，只要选其中一个即可）： Gini Index Entropy Misclassification error 第一个可以用来评估节点 Impurity 的指标是 Gini 系数。对于一个给定的节点 tt，它的 Gini 系数计算公式如下： 其中，p(j | t)p(j | t) is the relative frequency of class jj at node tt（即表示给定节点 tt 中属于 类 jj 的记录所占的比例）。通过这个计算公式你可以看出： Maximum value of Gini index = (1 - 1/ncnc) when records are equally distributed among all classes, implying least interesting information or most impure. Minimum is (0.0) when all records belong to one class, implying most interesting information or most pure or most homogeneous.
    说到这里，我们插一句题外话（如果你对这部分 Background 无感可以跳过）。你在生活中有 没有听过基尼系数这个名词？是的，基尼系数本来是经济学里的一个概念。基尼系数是 1943 年美国经济学家阿尔伯特·赫希曼根据劳伦茨曲线所定义的判断收入分配公平程度的指标。 基尼系数是比例数值，在 0 和 1 之间，是国际上用来综合考察居民内部收入分配差异状况的 一个重要分析指标。其具体含义是指，在全部居民收入中，用于进行不平均分配的那部分收 入所占的比例。基尼系数最大为“1”，最小等于“0”。前者表示居民之间的收入分配绝对不 平均，即 100%的收入被一个单位的人全部占有了；而后者则表示居民之间的收入分配绝对 平均，即人与人之间收入完全平等，没有任何差异。但这两种情况只是在理论上的绝对化形 式，在实际生活中一般不会出现。因此，基尼系数的实际数值只能介于 0～1 之间，基尼系 数越小收入分配越平均，基尼系数越大收入分配越不平均。国际上通常把 0.4 作为贫富差距 的警戒线，大于这一数值容易出现社会动荡。 选择最佳划分的度量通常是根据划分后子女结点不纯性的程度。不纯的程度越低，类分布就 越倾斜。例如，类分布为 (0, 1)的结点具有零不纯性，而均衡分布(0.5, 0.5)的结点具有最高 的不纯性。现在我们回过头来看一个具体的计算例子。现在我们一共有 6 个 records，以二 元分类问题不纯性度量值的比较为例，下图的意思表示有四个节点，然后分别计算了每一个 节点的 GINI 系数值（注意决策树中每一个内节点都表示一种分支判断，也就可以将 6 个 records 分成几类，我们这里讨论的是二元分类所以是分成两个子类）： 从上面的例子可以看出，第一个结点，具有最低的不纯性度量值，接下来节点的不纯度度量 值依次递增。为了确定测试条件的效果，我们需要比较父结点（划分前）的不纯程度和子女 结点（划分后） 的不纯程度，它们的差越大，测试条件的效果就越好。增益ΔΔ是一种可 以用来确定划分效果的标准： 其中，I(.)I(.) 是给定结点的不纯性度量，NN 是父结点上的记录总数，kk 是属性值的个数， N(vj)N(vj)是与子女结点 vjvj 相关联的记录个数。决策树构建算法通常选择最大化增益ΔΔ 的测试条件，因为对所有的测试条件来说，I(parent)I(parent)是一个不变的值，所以最大化 增益等价于最小化子女结点的不纯性度量的加权平均值。 考虑下面这个划分的例子。假设有两种方法将数据划分成较小的子集。划分前，Gini 系数等 于 0.5，因为属于两个类（C0 和 C1）的记录个数相等。如果选择属性 A 来划分数据，节点 N1N1 的 Gini 系数为 1−(4/7)2−(3/7)2=0.48981−(4/7)2−(3/7)2=0.4898，而 N2N2 的 Gini 系数为 1−(2/5)2−(3/5)2=0.481−(2/5)2−(3/5)2=0.48 ， 派 生 节 点 的 Gini 系 数 的 加 权 平 均 为 (7/12)×0.4898+(5/12)×0.48=0.486(7/12)×0.4898+(5/12)×0.48=0.486。同理，我们还可以计算 属性 B 的 Gini 系数的加权平均为(7/12)×0.408+(5/12)×0.32=0.371(7/12)×0.408+(5/12)× 0.32=0.371。因为属性 B 具有更小的 Gini 系数，所以它比属性 A 更可取。
    考虑多分类的情况 标称属性可以产生二元划分也可以产生多路划分，如下图所示。二元划分的 Gini 系数的计 算与二元属性类似。对于车型属性第一种二元分类，{运动，豪华}的 Gini 系数是 0.4922，而 {家用}的 Gini 系数是 0.375。这个划分的 Gini 系数加权平均是： (16/20)×0.4922+(4/20)×0.375=0.468 类似地，对第二种二元划分{运动}和{家用，豪华}，Gini 系数加权平均是 0.167。第二种划分 的 Gini 系数相对更低，因为其对应的子集的纯度更高。对于多路划分，需要计算每个属性 值的 Gini 系数。Gini({家用})=0.375，Gini({运动})=0，Gini({豪华})=0.219，所以多路划分的 Gini 系数加权平均值为： (4/20)×0.375+(8/20)×0+(8/20)×0.219=0.163 多路划分的 Gini 系数比两个二元划分都小。这是因为二元划分实际上合并了多路划分的某 些输出，自然降低了子集的纯度。
    考虑特征值连续的情况 考虑下图所示的例子，其中测试条件“年收入≤v≤v”用来划分拖欠贷款分类问题的训练记 录。用穷举方法确定 vv 的值，将 NN 个记录中所有的属性值都作为候选划分点。对每个候 选 vv，都要扫描一次数据集，统计年收入大于和小于 vv 的记录数，然后计算每个候迭的 Gini 系数，并从中选择具有最小值的候选划分点。这种方法的计算代价显然是高昂的，因为对每 个候选划分点计算 Gini 系数需要 O(N)O(N)次操作，由于有 NN 个候选，总的计算复杂度为 O(N2)O(N2)。 为 了 降 低 计 算 复 杂 度 ， 按 照 年 收 入 将 训 练 记 录 排 序 ， 所 需 要 的 时 间 为 O(NlogN)O(Nlog⁡N)，从两个相邻的排过序的属性值中选择中间值作为候选划分点，得到候 选划分点 55, 65, 72 等。无论如何，与穷举方法不同，在计算候选划分点的 Gini 指标时，不 需考察所有 NN 个记录。 对第一个候选 v=55v=55，没有年收入小于$55K 的记录，所以年收入＜$55K 的派生结点的 Gini 系数是 0；另一方面，年收入≥≥$55K 的样本记录数目分别为 3（类 Yes）和 7（类 No)。 如此一来，该结点的 Gini 系数是 0.420。该候选划分的 Gini 系数的加权平均就等于 0×0+1 ×0.42=0.420×0+1×0.42=0.42。 对第二个候选 v=65v=65，通过更新上一个候选的类分布，就可以得到该候选的类分布。更 具体地说，新的分布通过考察具有最低年收入（即$60K）的记录的类标号得到。因为该记录 的类标号是 No 所以类 No 的计数从 0 增加到 1（对于年收入≤≤$65K），和从 7 降到 6（对 于年收入>> $65K），类 Yes 的分布保持不变。新的候选划分点的加权平均 Gini 系数为 0.4。 重复这样的计算，直到算出所有候选的 Gini 系数值。最佳的划分点对应于产生最小 Gini 系
    分享到：
    赞 收藏

    相关推荐

    资料库

    大数据

    共收录841份资料，累计11个分类，关注成员有19位，主要包括：Matlab,统计分析,数据挖掘,Hbase,Hive,flink,kafka,spark,Storm,算法与数据结构,Hadoop

    热门标签

    Matlab 统计分析 数据挖掘 Hbase Hive flink kafka spark Storm 算法与数据结构 Hadoop

    最新资料