第3章_分类与决策树bccm.pptx

《第3章_分类与决策树bccm.pptx》由会员分享，可在线阅读，更多相关《第3章_分类与决策树bccm.pptx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章分类与预测分类与预测主要内容v分类与决策树概述分类与决策树概述vID3、C4.5与与C5.0vCART分类 VS.预测v分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来的数据趋势的数据趋势 的模型的模型分类：分类：v预测类对象的分类标号（或离散值）预测类对象的分类标号（或离散值）v根据训练数据集和类标号属性，构建模型来分类现有数据，并用根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据来分类新数据预测：预测：v建立连续函数值模型建立连续函数值模型v比如预测空缺值，或者预测顾客在计算机设备上的

2、花费比如预测空缺值，或者预测顾客在计算机设备上的花费v典型应用典型应用欺诈检测、市场定位、性能预测、医疗诊断欺诈检测、市场定位、性能预测、医疗诊断v分类是一种应用非常广泛的数据挖掘技术分类是一种应用非常广泛的数据挖掘技术 v分类与预测的区别：分类与预测的区别：当估计的属性值是离散值时，这就是当估计的属性值是离散值时，这就是分类分类；当估计的属性值是连续值时，这就是当估计的属性值是连续值时，这就是预测预测。分类和预测分类和预测-示例示例v分类分类银行贷款员需要分析数据，来弄清哪些贷款申请银行贷款员需要分析数据，来弄清哪些贷款申请者是安全的，哪些是有风险的（将贷款申请者分者是安全的，哪些是有风险的

3、（将贷款申请者分为为“安全安全”和和“有风险有风险”两类）两类）v我们需要构造一个分类器来预测类属编号，比如预测我们需要构造一个分类器来预测类属编号，比如预测顾客属类顾客属类v预测预测银行贷款员需要预测贷给某个顾客多少钱是安全银行贷款员需要预测贷给某个顾客多少钱是安全的的v构造一个预测器，预测一个连续值函数或有序值，常构造一个预测器，预测一个连续值函数或有序值，常用方法是回归分析用方法是回归分析数据分类数据分类一个两步过程一个两步过程(1)v第一步，也成为学习步，目标是建立描述预先定义的数第一步，也成为学习步，目标是建立描述预先定义的数据类或概念集的分类器据类或概念集的分类器分类算法通过分析或

4、从训练集分类算法通过分析或从训练集“学习学习”来构造分类器。来构造分类器。训练集由数据库元组（用训练集由数据库元组（用n维属性向量表示）和他们相对维属性向量表示）和他们相对应的类编号组成；假定每个元组属于一个预定义的类应的类编号组成；假定每个元组属于一个预定义的类v训练元组：训练数据集中的单个元组训练元组：训练数据集中的单个元组学习模型可以用分类规则、决策树或数学公式的形式提学习模型可以用分类规则、决策树或数学公式的形式提供供数据分类数据分类一个两步过程一个两步过程(2)v第二步，使用模型，对将来的或未知的对象进行分类第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率首先评

5、估模型的预测准确率v对每个测试样本，将已知的类标号和该样本的学习模型类预测比对每个测试样本，将已知的类标号和该样本的学习模型类预测比较较v模型在给定测试集上的准确率是正确被模型分类的测试样本的百模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比分比v测试集要独立于训练样本集，否则会出现测试集要独立于训练样本集，否则会出现“过分拟合过分拟合”的情况的情况第一步建立模型训练数据集分类算法IF rank=professorOR years 6THEN tenured=yes 分类规则第二步用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?监督学习监督学

6、习 VS.无监督学习无监督学习v监督学习（用于分类）监督学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的模型的学习在被告知每个训练样本属于哪个类的“指导指导”下进行下进行新数据使用训练数据集中得到的规则进行分类新数据使用训练数据集中得到的规则进行分类v无监督学习（用于聚类）无监督学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号通过一系列的度量、观察来建立数据中的类编号或进行聚类或进行聚类数据预测的两步过程数据预测的两步过程v数据预测也是一个

7、两步的过程，类似于前面描述的数据分类数据预测也是一个两步的过程，类似于前面描述的数据分类对于预测，没有对于预测，没有“类标号属性类标号属性”要预测的属性是连续值，而不是离散值，该属性可简称要预测的属性是连续值，而不是离散值，该属性可简称“预测属性预测属性”vE.g.银行贷款员需要预测贷给某个顾客多少钱是安全银行贷款员需要预测贷给某个顾客多少钱是安全的的v预测器可以看作一个映射或函数预测器可以看作一个映射或函数y=f(X)其中其中X是输入；是输入；y是输出，是一个连续或有序的值是输出，是一个连续或有序的值与分类类似，准确率的预测，也要使用单独的测试集与分类类似，准确率的预测，也要使用单独的测试集

8、3.1 决策树概述决策树概述v决策树决策树(Decision Tree)一种描述概念空间的有效的归纳推理办法。一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。在各个领域取得广泛应用。v决策树是一种树型结构，其中每个内部结决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类表一个测试输出，每个叶结点代表一种类别。别。v决策树学习是以实例为基础的归纳学

9、习。决策树学习是以实例为基础的归纳学习。v从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。v概念分类学习算法：来源于概念分类学习算法：来源于Hunt,Marin和和Stone 于于1966年研制的年研制的CLS学习系统，用于学习学习系统，用于学习单个概念。单个概念。1979年年,J.R.Quinlan 给出给出ID3算法，并在算法，并在1983年和年和1986年对年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。进行了总结和简化，使其成为决策树学习算法的典型。Schlimmer 和和Fisher 于于1986

10、年对年对ID3进行改造，在每个可能的决进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。算法。1988年，年，Utgoff 在在ID4基础上提出了基础上提出了ID5学习算法，进一步提高学习算法，进一步提高了效率。了效率。1993年，年，Quinlan 进一步发展了进一步发展了ID3算法，改进成算法，改进成C4.5算法。算法。另一类决策树算法为另一类决策树算法为CART，与，与C4.5不同的是，不同的是，CART的决策树的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习由二元逻辑问题生成，每个树节点只

11、有两个分枝，分别包括学习实例的正例与反例。实例的正例与反例。v其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。点处的熵值为零，此时每个叶节点中的实例都属于同一类。v决策树学习采用的是自顶向下的递归方法。决策树学习采用的是自顶向下的递归方法。v决策树的每一层节点依照某一属性值向下分为子节点，待分决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子

12、节点扩展，这一过程在到达决据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。策树的叶节点时结束，此时得到结论。v从根节点到叶节点的每一条路经都对应着一条合理的规则，从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。决策树就对应着一组析取的规则。v决策树学习算法的最大优点是，它可以自学习。在学习的过决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子程中，不需要使用者了解过多

13、背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。成新的分枝和叶子，并添加到树中。v树是由节点和分枝组成的层树是由节点和分枝组成的层次数据结构。节点用于存贮次数据结构。节点用于存贮信息或知识，分枝用于连接信息或知识，分枝用于连接各个节点。树是图的一个特各个节点。树是图的一个特例，图是更一般的数学结构，例，图是更一般的数学结构，如贝叶斯网络。如贝叶斯网络。v决策树是描述分类过程的一决

14、策树是描述分类过程的一种数据结构，从上端的根节种数据结构，从上端的根节点开始，各种分类原则被引点开始，各种分类原则被引用进来，并依这些分类原则用进来，并依这些分类原则将根节点的数据集划分为子将根节点的数据集划分为子集，这一划分过程直到某种集，这一划分过程直到某种约束条件满足而结束。约束条件满足而结束。根结点根结点个子大个子大可能是松鼠可能是松鼠可能是老鼠可能是老鼠可能是大象可能是大象在水里在水里会吱吱叫会吱吱叫鼻子长鼻子长脖子长脖子长个子小个子小不会吱吱叫不会吱吱叫鼻子短鼻子短脖子短脖子短可能是长颈鹿可能是长颈鹿在陆地上在陆地上可能是犀牛可能是犀牛可能是河马可能是河马v可可以以看看到到，一一个

15、个决决策策树树的的内内部部结结点点包包含含学学习习的的实实例例，每每层层分分枝枝代代表表了了实实例例的的一一个个属属性性的的可可能能取取值值，叶叶节节点点是是最最终终划划分分成成的的类类。如如果果判判定定是是二二元元的的，那那么么构构造造的的将将是是一一棵棵二二叉叉树树，在在树树中中每每回回答答一一个个 问问 题题 就就 降降 到到 树树 的的 下下 一一 层层，这这 类类 树树 一一 般般 称称 为为CART（Classification And Regression Tree）。）。v判判定定结结构构可可以以机机械械的的转转变变成成产产生生式式规规则则。可可以以通通过过对对结结构构进进行行

16、广广度度优优先先搜搜索索，并并在在每每个个节节点点生生成成“IFTHEN”规规则则来来实实现现。如如图图6-13的决策树可以转换成下规则：的决策树可以转换成下规则：IF“个子大个子大”THEN IF“脖子短脖子短”THEN IF“鼻子长鼻子长”THEN 可能是大象可能是大象形式化表示成形式化表示成 根结点根结点个个 子子大大可可能能是是松松鼠鼠可可能能是是老老鼠鼠可可能能是是大大象象在在 水水里里会会 吱吱 吱吱叫叫鼻鼻 子子长长脖脖 子子长长个子小个子小不不会会吱吱吱吱叫叫鼻鼻 子子短短脖脖 子子短短可可能能是是长长颈颈鹿鹿在在 陆陆 地地上上可可能能是是犀犀牛牛可可能能是是河河马马v构造一

17、棵决策树要解决四个问题：构造一棵决策树要解决四个问题：收集待分类的数据，这些数据的所有属性应该是完全标注的。收集待分类的数据，这些数据的所有属性应该是完全标注的。设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。令人满意。设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此

18、在必要的时候应该停止数据集分裂：往是有限几个，因此在必要的时候应该停止数据集分裂：v该节点包含的数据太少不足以分裂，该节点包含的数据太少不足以分裂，v继续分裂数据集对树生成的目标继续分裂数据集对树生成的目标(例如例如ID3中的熵下降准则中的熵下降准则)没有贡献，没有贡献，v树的深度过大不宜再分。树的深度过大不宜再分。v通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来最大的准则，这种方案使最具有分类潜力的准则最先被提取出来 预测变量目标变量记录样本类标号

19、属性类别集合：类别集合：Class=“优优”，“良良”，“差差”决策树的基本原理 根节点根节点叶子节点叶子节点分裂属性分裂属性分裂谓词分裂谓词 每一个叶子节点都被确定一个类标号每一个叶子节点都被确定一个类标号 v每一个节点都代表了一个数据集。每一个节点都代表了一个数据集。根节点根节点1代表了初始数据集代表了初始数据集D其它节点都是数据集其它节点都是数据集D的子集。的子集。v例如，节点例如，节点2代表数据集代表数据集D中年龄小于中年龄小于40岁的那部分样本组成岁的那部分样本组成的数据集。的数据集。v子节点是父节点的子集。子节点是父节点的子集。vIf(年龄年龄40)and(职业职业=“学生学生”o

20、r职业职业=“教师教师”)Then 信用等级信用等级=“优优”vIf(年龄年龄40)and(职业职业!=“学生学生”and职业职业!=“教师教师”)Then 信用等级信用等级=“良良”vIf(年龄年龄40)and(月薪月薪3000)Then 信用等级信用等级=“优优”v决策树是指具有下列三个性质的树：决策树是指具有下列三个性质的树：每个非叶子节点都被标记一个分裂属性每个非叶子节点都被标记一个分裂属性Ai；每个分支都被标记一个分裂谓词，这个分裂谓每个分支都被标记一个分裂谓词，这个分裂谓词是分裂父节点的具体依据；词是分裂父节点的具体依据；每个叶子节点都被标记一个类标号每个叶子节点都被标记一个类标号

21、CjC。v任何一个决策树算法，其核心步骤都是为任何一个决策树算法，其核心步骤都是为每一次分裂确定一个每一次分裂确定一个分裂属性分裂属性，即究竟按，即究竟按照哪一个属性来把当前数据集划分为若干照哪一个属性来把当前数据集划分为若干个子集，从而形成若干个个子集，从而形成若干个“树枝树枝”。v熵熵，是是数数据据集集中中的的不不确确定定性性、突突发发性性或或随随机机性性的的程度的度量。程度的度量。v当当一一个个数数据据集集中中的的记记录录全全部部都都属属于于同同一一类类的的时时候候，则没有不确定性，这种情况下的熵就为则没有不确定性，这种情况下的熵就为0。v决决策策树树分分裂裂的的基基本本原原则则是是，数

22、数据据集集被被分分裂裂为为若若干干个个子子集集后后，要要使使每每个个子子集集中中的的数数据据尽尽可可能能的的“纯纯”，也也就就是是说说子子集集中中的的记记录录要要尽尽可可能能属属于于同同一一个个类类别别。如如果果套套用用熵熵的的概概念念，即即要要使使分分裂裂后后各各子子集集的熵尽可能的小。的熵尽可能的小。3.2 ID3、C4.5与与C5.0v数据集数据集D被按照分裂属性被按照分裂属性“年龄年龄”分裂为两分裂为两个子集个子集D1 和和D2 信息增益信息增益:Gain(D,年龄年龄)=H(D)P(D1)H(D1)+P(D2)H(D2)v显显然然，如如果果D1和和D2中中的的数数据据越越“纯纯”，H

23、(D1)和和H(D2)就就越越小小，信信息息增益就越大，或者说熵下降得越多。增益就越大，或者说熵下降得越多。v按按照照这这个个方方法法，测测试试每每一一个个属属性性的的信信息息增增益益，选选择择增增益益值值最最大大的的属属性性作作为为分裂属性。分裂属性。信息熵计算举例信息熵计算举例v令令C1对应对应“是是”，C2对应对应“否否”。那么。那么C1有有9个样个样本，本，C2有有5个样本，所以数据集个样本，所以数据集D的熵为：的熵为：决策树归纳策略(1)v输入输入数据划分数据划分D是训练元组和对应类标号的集合是训练元组和对应类标号的集合attribute_list,候选属性的集合候选属性的集合Att

24、ribute_selection_method，指定选择属性的启发性过程，指定选择属性的启发性过程算法步骤算法步骤1.树以代表训练样本的单个节点（树以代表训练样本的单个节点（N）开始）开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法调用否则，算法调用Attribute_selection_method，选择能够最，选择能够最好的将样本分类的属性；确定好的将样本分类的属性；确定“分裂准则分裂准则”，指出，指出“分裂点分裂点”或或“分裂子集分裂子集”。决策树归纳策略(2)4.对测试属性每个已知的值，创建一个分支，对测试属

25、性每个已知的值，创建一个分支，并以此划分元组并以此划分元组5.算法使用同样的过程，递归的形成每个划分算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件递归划分步骤停止的条件划分划分D（在（在N节点提供）的所有元组属于同一类节点提供）的所有元组属于同一类没有剩余属性可以用来进一步划分元组没有剩余属性可以用来进一步划分元组使用多数表决使用多数表决没有剩余的样本没有剩余的样本给定分支没有元组，则以给定分支没有元组，则以D中多数类创建一个

26、树叶中多数类创建一个树叶属性选择度量v属属性性选选择择度度量量是是一一种种选选择择分分裂裂准准则则，将将给给定定类标号的训练元组最好的进行划分的方法类标号的训练元组最好的进行划分的方法理理想想情情况况，每每个个划划分分都都是是“纯纯”的的，即即落落在在给给定定划分内的元组都属于相同的类划分内的元组都属于相同的类属性选择度量又称为分裂准则属性选择度量又称为分裂准则v常用的属性选择度量常用的属性选择度量信息增益信息增益增益率增益率Gini指标指标信息增益信息增益(1)vS是一个是一个训练样本训练样本的集合，该样本中每个集的集合，该样本中每个集合的合的类编号类编号已知。每个样本为一个已知。每个样本为

27、一个元组元组。有个属性用来判定某个训练样本的类编号有个属性用来判定某个训练样本的类编号v假设假设S中有中有m个类，总共个类，总共s个训练样本，每个训练样本，每个类个类Ci有有si个样本个样本(i1,2,3.m)，那么任意，那么任意一个样本属于类一个样本属于类Ci的概率是的概率是si/s，那么用来，那么用来分类一个给定样本的分类一个给定样本的期望信息期望信息是：是：信息增益信息增益(2)v一个有一个有v个值的属性个值的属性Aa1,a2,.,av可以将可以将S分成分成v个子集个子集S1,S2,.,Sv，其中，其中Sj包含包含S中属性中属性A上的值为上的值为aj的样本。的样本。假设假设Sj包含类包含

28、类Ci的的sij个样本。根据个样本。根据A的这种划分的期望的这种划分的期望信息称为信息称为A的的熵熵vA上该划分的获得的信息增益定义为：上该划分的获得的信息增益定义为：v具有高信息增益的属性，是给定集合中具有高区分度的具有高信息增益的属性，是给定集合中具有高区分度的属性。所以可以通过计算属性。所以可以通过计算S中样本的每个属性的信息增中样本的每个属性的信息增益，来得到一个属性的相关性的排序。益，来得到一个属性的相关性的排序。v若若以以“年年龄龄”作作为为分分裂裂属属性性，则则产产生生三三个个子子集集（因因为为该该属属性性有有三三个个不不同同的的取取值值），所所以以D按按照照属属性性“年年龄龄”

29、划划分分出出的的三三个个子子集集的的熵熵的的加加权权和和为：为：其中有一个子集的熵为其中有一个子集的熵为0v同理，若以“收入水平”为分裂属性：v若以“有固定收入”为分裂属性：v若以“VIP”为分裂属性：以以“年龄年龄”作为分裂属性，所得信息增益最大。作为分裂属性，所得信息增益最大。叶子节点叶子节点ID3的主要缺点的主要缺点vID3算算法法只只能能处处理理分分类类属属性性（离离散散属属性性），而而不不能能处处理理连连续续属属性性（数数值值属属性性）。在在处处理理连连续续属属性性时时，一一般般要要先先将将连连续续属属性性划划分分为为多多个个区区间间，转转化化为为分分类类属属性性。例例如如“年年龄龄

30、”，要要把把数数值值事事先先转转换换为为诸诸如如“小小于于30岁岁”、“30至至50岁岁”、“大大于于50岁岁”这这样样的的区区间间，再再根根据据年年龄龄值值落落入入了了某某一一个个区区间间取取相相应应的的类类别别值值。通通常常，区区间间端端点点的的选选取取包包含含着着一一定的主观因素。定的主观因素。vID3生生成成的的决决策策树树是是一一棵棵多多叉叉树树，分分支支的的数数量量取取决决于于分分裂裂属属性性有有多多少少个个不不同同的的取取值值。这这不不利利于于处处理理分分裂裂属属性性取取值值数数目目较较多多的的情情况况。因因此此目目前前流流行行的的决策树算法大多采用二叉树模型。决策树算法大多采用

31、二叉树模型。vID3是是采采用用“信信息息增增益益”来来选选择择分分裂裂属属性性的的。虽虽然然这这是是一一种种有有效效的的方方法法，但但其其具具有有明明显显的的倾倾向向性性，即即它它倾倾向向于于选选择择具具有有大大量量不不同同取取值值的的属属性性，从从而而产生许多小而纯的子集。产生许多小而纯的子集。v尤尤其其是是关关系系数数据据库库中中作作为为主主键键的的属属性性，每每一一个个样样本本都都有有一一个个不不同同的的取取值值。如如果果以以这这样样的的属属性性作作为为分分裂裂属属性性，那那么么将将产产生生非非常常多多的的分分支支，而而且且每每一一个个分分支支产产生生的的子子集集的的熵熵均均为为0（因

32、因为为子子集集中中只只有有一一个个样样本本！）。显显然然，这这样样的的决决策策树树是是没没有有实实际际意意义义的的。因因此此，Quinlan提提出出使使用用增增益益比比例例来来代代替替信息增益。信息增益。3.2.2 C4.5v设设S代表训练数据集，由代表训练数据集，由s个样本组成。个样本组成。A是是S的某个属性，有的某个属性，有m个不同的取值，根据这个不同的取值，根据这些取值可以把些取值可以把S划分为划分为m个子集，个子集，Si表示第表示第i个子集（个子集（i=1,2,m），），|Si|表示子集表示子集Si中的中的样本数量。那么：样本数量。那么：称为“数据集数据集S关于属性关于属性A的熵的熵”

33、。v用来衡量属性A分裂数据集的广度和均匀性。样本在属性A上的取值分布越均匀，Split_Info(S,A)的值就越大。v增益比例的定义为：v增益比例消除了选择那些值较多且均匀分布的属性作为分裂属性的倾向性。连续属性的处理连续属性的处理 v设属性设属性Y有有m个不同的取值，按大小顺序升序排列个不同的取值，按大小顺序升序排列为为v1v2,vi”将数据集划分为两个部分，将数据集划分为两个部分，形成两个分支。显然，形成两个分支。显然，v1,v2,vm-1就是可能的就是可能的阈值的集合，共阈值的集合，共(m-1)个元素。个元素。v把这些阈值一一取出来，并根据把这些阈值一一取出来，并根据“Yvi”和和“Y

34、 vi”把训练数据集划分为两个子集，并计算每一种把训练数据集划分为两个子集，并计算每一种划分方案下的信息增益或增益比例，选择最大增划分方案下的信息增益或增益比例，选择最大增益或增益比例所对应的那个阈值，作为最优的阈益或增益比例所对应的那个阈值，作为最优的阈值。值。v可以看出，如果选择连续属性作为分裂属性，则可以看出，如果选择连续属性作为分裂属性，则分裂后只有两个分支，而不象离散属性那样可能分裂后只有两个分支，而不象离散属性那样可能会有多个分支（由离散属性的取值个数决定）。会有多个分支（由离散属性的取值个数决定）。v如果要计算如果要计算“年龄年龄”属性的信息增益，属性的信息增益，则首先将不同的属

35、性值排序则首先将不同的属性值排序20,25,28,40,46,55,56,58,60,65,70v那么可能的阈值集合为那么可能的阈值集合为20,25,28,40,46,55,56,58,60,65,70，从中一一取出，并形成分裂谓词，例从中一一取出，并形成分裂谓词，例如取出如取出“20”，形成谓词，形成谓词“20”和和“20”，用它们划分训练数据集，然，用它们划分训练数据集，然后计算信息增益或增益比例。后计算信息增益或增益比例。处理有缺失值的样本处理有缺失值的样本 vC4.5并不会武断地将一个有缺失值的样本并不会武断地将一个有缺失值的样本抛弃抛弃,也不会随意地将它分配到某个类别中也不会随意地将

36、它分配到某个类别中去。去。v“收入水平收入水平”的值，取为的值，取为“高高”的概率为的概率为3/12，取为，取为“中中”的概率为的概率为5/12，取为，取为“低低”的概率为的概率为4/12。vS1（收入水平（收入水平=“高高”）的样本数量为：）的样本数量为：3+2(3/12)；3.2.4 C5.0算法算法vC5.0C5.0是经典的决策树模型的算法之一，可生成多分支的决是经典的决策树模型的算法之一，可生成多分支的决策树，目标变量为分类变量策树，目标变量为分类变量v使用使用c5.0c5.0算法算法可以可以生成决策树（生成决策树（decision treedecision tree）或者规则）或者规

37、则集（集（rulerule setssets）。）。C5.0C5.0模型根据能够带来最大信息增益模型根据能够带来最大信息增益（information gaininformation gain）的字段拆分样本。）的字段拆分样本。第一次拆分确定第一次拆分确定的样本子集随后再次拆分，通常是根据另一个字段进行拆的样本子集随后再次拆分，通常是根据另一个字段进行拆分，这一过程重复进行直到样本子集不能再被拆分为止。分，这一过程重复进行直到样本子集不能再被拆分为止。最后，重新检验最低层次的拆分，那些对模型值没有显著最后，重新检验最低层次的拆分，那些对模型值没有显著贡献的样本子集被剔除或者修剪。贡献的样本子集被

38、剔除或者修剪。C5.0的优点的优点v优点：优点：C5.0C5.0模型在面对数据遗漏和输入字段很多的问题时非常模型在面对数据遗漏和输入字段很多的问题时非常稳健。稳健。C5.0C5.0模型通常不需要很长的训练次数进行估计。模型通常不需要很长的训练次数进行估计。C5.0C5.0模型比一些其他类型的模型易于理解，模型推出的模型比一些其他类型的模型易于理解，模型推出的规则有非常直观的解释。规则有非常直观的解释。C5.0C5.0也提供强大的增强技术以提高分类的精度。也提供强大的增强技术以提高分类的精度。vC5.0C5.0算法选择分支变量的依据算法选择分支变量的依据以信息熵的下降速度作为确定最佳分支变量和分

39、割阀值以信息熵的下降速度作为确定最佳分支变量和分割阀值的依据。信息熵的下降意味着信息的不确定性下降的依据。信息熵的下降意味着信息的不确定性下降举例：在举例：在Clementine中应用中应用C5.0v这里，以学生参加某次社会公益活动的数据（文这里，以学生参加某次社会公益活动的数据（文件名为件名为Students.xls）为例，讲解）为例，讲解C5.0算法的具算法的具体实现操作。体实现操作。v分析目标是，研究那些因素将显著影响到学生参分析目标是，研究那些因素将显著影响到学生参与社会公益活动。与社会公益活动。其中，是否参加为输出变量，除编号以外的其中，是否参加为输出变量，除编号以外的变量均为输入变

40、量。变量均为输入变量。数据流如下：数据流如下：一、建立模型 第一步建立数据源，第二步选择第一步建立数据源，第二步选择Modeling卡中的卡中的C5.0节点节点并将其连接到恰当位置，鼠标右击该节点，弹出下面窗口。并将其连接到恰当位置，鼠标右击该节点，弹出下面窗口。模型名称（模型名称（Model nameModel name）输出类型（输出类型（Output typeOutput type）：此处）：此处指定希望最终生成的模型是决策树指定希望最终生成的模型是决策树还是规则集。还是规则集。群体字符（群体字符（Group symbolicsGroup symbolics）。）。如果选择该选项，如果选

41、择该选项，C5.0C5.0会尝试将所会尝试将所有与输出字段格式相似的字符值合有与输出字段格式相似的字符值合并。如果没有选择该选项，并。如果没有选择该选项，C5.0C5.0会会为用于拆分母节点的字符字段的每为用于拆分母节点的字符字段的每个值创建一个子节点。个值创建一个子节点。使用自举法（使用自举法（Use boostingUse boosting）：提）：提高其精确率。这种方法按序列建立高其精确率。这种方法按序列建立多重模型。第一个模型以通常的方多重模型。第一个模型以通常的方式建立。随后，建立第二个模型，式建立。随后，建立第二个模型，聚焦于被第一个模型错误分类的记聚焦于被第一个模型错误分类的记录

42、。以此类推，最后应用整个模型录。以此类推，最后应用整个模型集对样本进行分类，使用加权投票集对样本进行分类，使用加权投票过程把分散的预测合并成综合预测。过程把分散的预测合并成综合预测。The Number of trialsThe Number of trials选项允许控选项允许控制用于助推的模型数量。制用于助推的模型数量。v交叉验证（交叉验证（Crossvalidate）：如果选择了该）：如果选择了该选项，选项，C5.0将使用一组基于将使用一组基于训练数据子集建立的模型，训练数据子集建立的模型，来估计基于全部数据建立的来估计基于全部数据建立的模型的精确度。如果数据集模型的精确度。如果数据集过

43、小，不能拆分成传统意义过小，不能拆分成传统意义上的训练集和测试集，这将上的训练集和测试集，这将非常有用。或用于交叉验证非常有用。或用于交叉验证的模型数目。的模型数目。v模式（模式（Mode）：对于简单的）：对于简单的训练，绝大多数训练，绝大多数C5.0参数是参数是自动设置。高级训练模式选自动设置。高级训练模式选项允许对训练参数更多的直项允许对训练参数更多的直接控制。接控制。v简单模式选项（简单模式选项（simplesimple）v偏好（偏好（FavorFavor）：）：在在accuracyaccuracy下，下，C5.0C5.0会生会生成尽可能精确的决策树。成尽可能精确的决策树。在某些情况下，

44、这会导致在某些情况下，这会导致过度拟和。选择过度拟和。选择GeneralityGenerality（一般化）项（一般化）项以使用不易受该问题影响以使用不易受该问题影响的算法设置。的算法设置。v期望噪声百分数期望噪声百分数（Expected noise Expected noise （%）：）：指定训练集中的噪声或错指定训练集中的噪声或错误数据期望比率。误数据期望比率。v高级模式选项高级模式选项v修剪纯度（修剪纯度（pruning severity）：决定生）：决定生成决策树或规则集被修剪的程度。提高纯成决策树或规则集被修剪的程度。提高纯度值将获得更小，更简洁的决策树。降低度值将获得更小，更简洁

45、的决策树。降低纯度值将获得更加精确的决策树。纯度值将获得更加精确的决策树。v子分支最少记录数（子分支最少记录数（Minimum records per child branch）：子群大小可以用于）：子群大小可以用于限制决策树任一分支的拆分数。只有当两限制决策树任一分支的拆分数。只有当两个或以上的后序子分支包括来自训练集的个或以上的后序子分支包括来自训练集的记录不少于最小记录数，决策树才会继续记录不少于最小记录数，决策树才会继续拆分。默认值为拆分。默认值为2，提高该值将有助于避，提高该值将有助于避免噪声数据的过度训练。免噪声数据的过度训练。v全局修剪（全局修剪（Use global pruni

46、ng）：）：第一阶段：局部修建第一阶段：局部修建 第二阶段：全局修剪第二阶段：全局修剪v排除属性（排除属性（Winnow attributes）：如果）：如果选择了该选项，选择了该选项，C5.0会在建立模型前检验会在建立模型前检验预测字段的有用性。被发现与分析无关的预测字段的有用性。被发现与分析无关的预测字段将不参与建模过程。这一选项对预测字段将不参与建模过程。这一选项对有许多预测字段元的模型非常有用，并且有许多预测字段元的模型非常有用，并且有助于避免过度拟和。有助于避免过度拟和。图图1 指定错误归类损失指定错误归类损失错错误误归归类类损损失失允允许许指指定定不不同同类类型预测错误之间的相对重

47、要性。型预测错误之间的相对重要性。错错误误归归类类损损失失矩矩阵阵显显示示预预测测类类和和实实际际类类每每一一可可能能组组合合的的损损失失。所所有有的的错错误误归归类类损损失失都都预预设设设设置置为为1.01.0。要要输输入入自自定定义义损损失失值值，选选 择择 Use Use misclassification misclassification costscosts，然然后后把把自自定定义义值值输输入入到到损失矩阵中。损失矩阵中。具体设置具体设置执行结果执行结果二、预测结果二、预测结果 为为观观测测C5.0对对每每个个样样本本的的预预测测结结果果，可可在在流流管管理理器器的的Models卡

48、卡中中，鼠鼠标标右右击击C5.0模模型型结结果果，选选择择弹弹出出菜菜单单中中的的Add To Stream，并并将将模模型型结结果果连连接接到到数数据据流流中中，然然后后连连接接Table节点查看预测结果，如下图所示：节点查看预测结果，如下图所示：三、三、C5.0模型评价模型评价3.3 CARTv分类和回归树（分类和回归树（Classification and Regression Trees，CART,在在Clementine中中简写为简写为C&RT）vCART算法中的每一次分裂把数据分为算法中的每一次分裂把数据分为两个两个子集，每个子集中的样本比被划分之前具有子集，每个子集中的样本比被划

49、分之前具有更好的一致性。它是一个递归的过程，也就更好的一致性。它是一个递归的过程，也就是说，这些子集还会被继续划分，这个过程是说，这些子集还会被继续划分，这个过程不断重复，直到满足终止准则，然后通过修不断重复，直到满足终止准则，然后通过修剪和评估，得到一棵最优的决策树。剪和评估，得到一棵最优的决策树。三个步骤三个步骤v生成最大树生成最大树生成一棵充分生长的最大树生成一棵充分生长的最大树v树的修剪树的修剪根据修剪算法对最大树进行修剪，生成由许多子根据修剪算法对最大树进行修剪，生成由许多子树组成的子树序列树组成的子树序列v子树评估子树评估从子树序列中选择一棵最优的子树作为最后的结从子树序列中选择一

50、棵最优的子树作为最后的结果。果。3.3.1 生成最大树生成最大树v标准问题集标准问题集 就某个给定的属性来说，由于属性的取值可能有很多个，所以按照这个属性来分裂数据集的方式也有很多种，属性的标准问题集标准问题集就是所有候选分支方案的集合。连续属性的标准问题集离散属性的标准问题集杂度杂度 v在ID3算法中，用“熵”来度量数据集随机性的程度。v在CART中我们把这种随机性的程度称为“杂杂度度”（impurity，也称为“不纯度”），并且用“吉尼”(gini)指标来衡量它。吉尼指标 v设t是决策树上的某个节点，该节点的数据集为S，由s个样本组成，其类标号属性具有m个不同的取值，即定义了m个不同的类C