第3章_分类与决策树(1).ppt

1、第三章分类和预测、主要内容、分类和判断树概要ID3，C4.5和C5.0 CART、分类VS .预测、分类和预测以两种数据分析形式描述重要的数据类或提取预测未来数据趋势的模型分类：预测类对象的分类标签条(或离散值) 用于根据训练数据定径套和类标签条属性并分类新的数据预测：建构预测空缺值等连续函数值模型，预测客户在计算机设备上的费用的典型应用欺诈检测、市场定位、性能预测和医疗诊断，分类应用了非常广泛的数据挖掘技术、分类和预测-例如，分类银行贷款员需要分析数据，明确哪些贷款申请方安全，哪些贷款申请方有风险(将贷款申请方分为“安全”和“有风险”两种)。 我们需要建立分类器来预测分类编号的一般方法是回归

2、预测，数据分类是两个阶段的过程(1)，第一步骤也是学习步骤，建立描述预先定义的数据类或概念定径套的分类器分类算法，从分析或训练定径套中“学习”来建构分类器假定每个由数据库元组(由n维属性向量表示)和对应的类编号构成的组属于给定类的训练组，则训练数据定径套中的每个组学习模型以分类规则、判断树或数学式的形式提供数据分类是两个阶段的过程(2)，第二阶段，使用模型来分类未来或未知的对象，首先做评估模型的预报准确率已知的类标签条及其样本的学习模型类预测比较模型的某个测试集的正确率被正确模型分类的测试样本的百分比测试集是训练样本否则会发生“过度适应”。 第一步是模型、训练数据定径套、if等级=profes

3、sororyears6then tenured=是、分类规则、第二步是模型分类、分类规则、测试集、未知数据、(Jeff、ppf、监督学习VS .没有监督学习、) 模型的学习使用在被告知每个训练样本属于哪个类的“指导”下进行新数据的训练数据定径套中得到的规则，不进行分类监督学习(用于聚类)每个训练样本的类编号不明确要学习的类的集合或者数目，可以预先得到一系列未知的元圈套， 由观察者观察的数据中的类编号或聚类、数据预测的两个阶段的过程、数据预测也是两个阶段的过程，与上述数据分类一样，相对于预测，“类标签条属性”不被预测的属性是连续值，可以简单地称为“预测属性”的y是输出连续的或有序的值类似于分类，

4、准确率的预测，是使用单个测试集、3.1判断树摘要和判断树描述概念空间的有效归纳推理方法。 基于判断树的学习方法可以进行无关的多概念学习，具有简单快捷的优点，在各个领域得到广泛的应用。 的双曲馀弦值。 判断树是树型结构，每个内部节点代表属性上的测试，每个分支代表测试输出，每个叶节点代表类别。 判断树学习是一种基于实例的归纳学习。 从无序和不规则(概念)中推论判断树表示的分类规则。 概念分类学习算法：来源于Hunt、Marin和Stone于1966年开发的CLS学习系统，学习单一概念。1979年，J.R. Quinlan提供了ID3算法，1983年和1986年对ID3进行了归纳简化，作为判断树学习

5、算法的典型。 Schlimmer和Fisher在1986年对ID3进行了改造，为每个可能的判断树节点制作了缓冲器，使判断树能够增量生成，得到了ID4算法。 1988年，Utgoff根据ID4化学基提出了ID5学习算法，并进行了一头地，提高了效率。 1993年，Quinlan进一步发展了ID3算法，改进为C4.5算法。 另一个判断树算法是CART，与C4.5不同的是，CART的判断树是根据二元逻辑问题生成的，每个树节点只有两个分支，分别包含学习实例的正例和负例。 其基本思想是以信息熵为尺度建构熵值最低的树，使得到叶结点的熵值为零，此时，各叶结点中的斯坦共和国属于相同类别。 判断树学习采用了自顶向

6、下的递归方法。 判断树的每个层级节点根据其属性值来到达子节点，将分类索引斯坦共和国与每个节点处的与该节点相关联的属性值进行比较，根据不同的比较结果扩展到相应的子节点，并且在该过程到达判断树的叶结点时终止，这时得到结论。 从根结点到叶节点的各路径对应于合理的规则，规则间的各部分(各层的条件)的关系是综合关系。 整个判断树对应于提取的规则的定径套。 判断树学习算法的最大优点是可以进行自我学习。 在学习过程中，使用者不必太了解背景知识，只需仔细标记训练例子即可学习。 如果在应用程序中发现不符合规则的实例，则plump会询问用户该斯坦共和国的正确分类，生成新的分支和叶，并将其添加到树中。 树是由节点和

7、分枝构成的阶层数据构造。 节点用于存储信息和知识，分支用于连接各节点。 树是图的特例，图是贝叶斯网络等更一般的数学构造。 判断树是描述分类过程的数据结构，从上端的根结点引用各种分类原则，按照这些个的分类原则将根结点的数据定径套划分为子定径套，该划分过程直到满足某一制约为止结束。 当喀呖声时，可以看出，一个判断树的内部节点包括学习斯坦共和国，其中每个层的分支表示实例斯坦共和国的一个属性的可能值，叶结点是最终分类的类。 判定为二叉树的话，构造就会变成二叉树，树中每回答一个问题就会掉到树的下层。 这样的树一般被称为cart (classificationandregressiontree )。 判定

8、结构可以机械地变换成生成式规则。 可以通过对结构进行宽度优先搜索，为每个节点生成“IFTHEN”规则来实现。 图6-13的判断树建构了用于解决四个问题的判断树，即IF“高”THEN IF“短脖子”THEN IF“长鼻子”THEN可能以目标形式表达，并且收集分类数据。 这些个数据的所有属性都应当完全标签条。 修订分类策略，即数据的哪些属性可用于分类，以及如何量化属性。 分类原则的选择，即在许多分类标准中，各步骤选择哪个标准使最终的树更满脚丫子。 设定分类停止条件，实际应用中的数据属性多，真正有分类意义的属性有几个，所以必要时应该停止数据定径套的分裂：该节点包含的数据太少，继续分裂数据定径套是树生

9、成的目标(例如ID3的熵下降基准)共同的判断树分裂目标是通过选择整个树的熵总量最小，并按每个一头地减少熵的最大标准，最先提取具有分类潜力的标准，预测变量、目标变量、记录样本、类标签条属性、类集合： 根结点1中表示原始数据定径套d的其它节点是数据定径套d的子定径套。 例如，节点2表示由数据定径套d内年龄未满40岁的样本的一部分组成的数据定径套。 子节点是父节点的子定径套。 If (年龄3000) Then信用等级=“优”，判断树是具有以下三个性质的树：在每个非叶节点上标记了分裂属性Ai的各分支上，标记了分裂谓词，这是分裂父节点的具体根据。每个叶节点都带有类标签条CjC 在任何一个判断树算法中，其

10、核心步骤都是决定每个分裂的分裂属性，即，根据当前数据定径套被哪个属性分割成几个子定径套，形成几个“分支”。 熵是数据定径套内的不真实自我、突发性或随机化的程度的度量。 如果一个数据定径套中的所有报告查询密码属于相同类，则没有不真实自我，此时熵为0。 判断树分裂的基本原则是在数据定径套分裂成几个子定径套之后，尽可能使各子定径套的数据属于“纯粹”，即子定径套的记录查询密码属于同一类别。 应用熵的概念，应尽量缩小分裂后各子定径套的熵。 3.2 ID3、C4.5和C5.0，数据定径套d根据分裂属性“年龄”分裂为两个子定径套D1和D2，信息男同志： Gain(D，年龄)=H(D)P(D1)H(D1) P

11、(D2)H(D2 )，其中D1和D2的数据是“纯粹的” 在该方法中，测试各属性的信息增益，选择增益值最大的属性作为分裂属性。 信息熵算例使C1对应于“是”，使C2对应于“否”。 由于c-1有9个样本，c-2有5个样本，数据定径套d具有熵：判断树归纳策略(1)、输入数据分割d具有与训练组对应的类标签条的集合attribute_list， 指定选择候选属性的集合Attribute_selection_method属性的启发性过程算法步骤树，其中，从表示训练样本的单个节点(n )开始，如果样本全部在同一类别中，则该节点成为叶并在该类别中被标记算法调用Attribute_selection_metho

12、d来确定“分裂标准”以选择可以对样本进行最佳分类的属性，并指定“分裂点”或“分裂子定径套”。判断树归纳策略(2)、测试属性的每个已知值创建一个分支，并在此划分元组算法使用相同的过程递归地形成每个划分上的元组判断树。 如果在一个节点中出现属性，则该节点的任何子节点中都没有出现递归分割步骤停止的条件分割d (由n个节点提供)的所有元组利用没有多数表决的样本在指定分支中没有元组，以进一步分割属于相同类的没有剩馀属性在d的许多类中创建叶，并且属性选择圈套、属性选择元圈套最好地划分作为选择分裂标准的给定类标签条的训练集的方法是理想的，并且每个划分是“纯”，即，属于给定划分的组属于同一类属性选择元圈套，

13、信息增益(1)、s是训练样本的集合，其中信息增益(1)、s是该样本中的每个集合的类编号，也称为分裂标准中常用的属性选择元圈套信息增益率Gini指标。 各样品为元组。假设s中有m个类以确定某一训练样本的类编号、具有校正数目s个训练样本且在每一类Ci中有si个样本(I1、2、3.m )，则任一样本属于类Ci的概率以si/s计将基于这样的区分而得到的期望信息定义为a在熵a上的该区分中得到的信息增益具有高信息增益的属性，在一个集合中具有高区分度的属性。 相应地，可以通过校正s个样本中每个属性的信息增益获得一个属性的相关性的排序。 对于年龄，由于产生了3个子定径套(由于该属性具有3个不同的可能值)，因此

14、按d属性的年龄分类的3个子定径套的熵的加权和为： )，其中子定径套的熵为0，以及类似地，叶结点，id-3的主要缺点，id-3算法分类在处理连续属性的情况下，一般将连续属性分割成多个区间，并转换为分类属性。 例如，“年龄”预先将数值变换为“不满30岁”、“30岁到50岁以上”、“50岁以上”等区间，根据年龄值取与某区间相当的类别值。 通常，区间端点的选择包含一定的主观因素。 由ID3生成的判断树是多叉树，分支的数量取决于分裂属性有多少不同。 这对于应对分裂属性取值数多的情况是不利的。 因此，现在流行的判断树算法大多采用二叉树模式。 ID3使用信息男同志选择分割属性。 这是一个有效的方法，但有明显

15、的趋势。 也就是说，它倾向于选择具有许多不同值的属性，从而生成许多小的纯子定径套。 特别是关系数据库中的主关牛鼻子字属性，每个样本都有不同的可能值。 将此类属性作为分裂属性将生成非常多的分支，并且每个分支生成的子定径套的熵为零(因为子定径套只有一个样本)。 的双曲馀弦值。 很明显，这样的判断树实际上是没有意义的。 因此，Quinlan提议使用增益比率来代替信息增益。 作为3.2.2 C4.5、s代表训练数据定径套，由s个样本构成。 a是s的属性，有m个不同的可能值，并且根据这些个的可能值可以将s划分为m个子定径套，其中Si表示第I个子定径套(I=1，2，m )，|Si|表示子定径套Si中的样本

16、数。 中，称为“与数据定径套s属性a相关的熵”。 用于测量属性a的分割数据定径套的广度和均匀性。 如果样本属性a中的可能值的分布变得均匀，则原来如此和Split_Info(S，a )的值变大。 男同志比例的定义是消除男同志比例选择其值多且均匀分布的属性作为分裂属性的倾向。连续属性的处理中，属性y具有m个不同的可能值，将数据定径套分割为2个部分，形成2个分支。 显然，v1、v2、和vm-1是可能的阈值集合，其是合并(m-1 )个元素。 逐个提取这些个的阈值，基于“Yvi”和“Yvi”将训练数据定径套分割为两个子定径套，校正各个分割后的垃圾牛鼻子中的信息男同志或男同志尺度，选择与最大男同志或增益尺度对应的阈值作为最佳阈值。 已知当选择连续属性作为划分属性时，划分之后仅有两个分支，并且如离散属性一样可能存在多个分支(取决于