模式识别与智能计算-MATLAB技术实现（第5版）-课件 第七章+决策树

模式识别与智能计算第七章

决策树分类器设计

杨淑莹第七章决策树分类器设计7.1

决策树的基本概念1.决策树的基本原理2.决策树分类3.决策树方法的特点

7.2决策树理论的分类方法1.理论基础3.编程代码

2.实现步骤4.效果图

7.3总结

7.1决策树的基本概念1.决策树的基本原理决策树（DecisionTree)：又称为判定树，是用于分类和预测的一种树结构。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。例1

图1所示为买车问题的决策树，从中可以看出一位客户是否会买汽车，用它可以预测某个人的购买意向。决策树的基本概念年龄月薪买健康状况不买买不买买<3030~60>60<3000≥3000不好好图1

买车问题的决策树决策树的基本概念自然树对应决策树中的意义分类问题中的表示意义树根根节点训练实例整个数据集空间杈内部节点、决策节点待分类对象的属性树枝分支属性的一个可能取值叶子叶子结点、状态节点数据分割（分类结果）表1决策树与自然树的对应关系及代表含义

构造决策树通常采用自上而下的递归构造方法。如果训练集中所有数据都是同类的，则将之作为叶节点，节点内容即该类标记，否则根据某种策略选择一个属性，按照属性的各个取值，把数据集合划分若干个子集，使得每个子集上的所有数据在该属性上具有同样的属性值。2.决策树分类

决策树分类算法起源于概念学习系统，然后发展到ID3方法，最后又演化为能处理连续属性的C4.5。此外，还有CART、SLIQ、SPRINT等方法。使用决策树进行分类可分为两步：步骤1：建立决策树模型：利用训练集建立并精化一棵决策树。（建树、剪枝）步骤2：利用生成的决策树对数据进行分类。决策树的基本概念3.决策树方法的特点与其他分类方法相比，决策树分类有如下优点：分类速度快，计算量相对较小，容易转化成分类规则。分类准确性高，从决策树中挖掘出的规则准确性高且便于理解。决策树的基本概念7.2决策树理论的分类方法1.理论基础Quinlan提出的ID3算法是决策树算法的代表，具有描述简单、分类速度快的优点，大多数决策树算法都是在它的基础上加以改进而实现的。（1）ID3算法基本思想决策树理论的分类方法年龄月薪买健康状况不买买不买买<3030~60>60<3000≥3000不好好图1

买车问题的决策树（2）属性选择度量期望信息量：设训练集为

，样品总数为N，其中包含M个不同的类ωi(i=1,2，…，M)的样品的个数。设Ni是

中属于类ωi的样品个数。对一个给定样品分类所需的期望信息为

其中，pi是样品属于ωi的概率。决策树理论的分类方法熵：熵是一个衡量系统混乱程度的统计量，熵越大，表示系统越混乱。对于给定子集Sj，有决策树理论的分类方法决策树理论的分类方法信息增益：Gain（A）是指由于知道属性A的值而导致的熵的期望压缩。在属性A上分支获得的信息增益表示为例2

表2所示的是一个顾客买车意向的训练集，通过此例来说明属性选择方法。决策树理论的分类方法样品编号年龄月薪健康状况买车意向1<30<3000好不买2<30<3000不好不买3<30≥3000不好买4<30≥3000好买530~60<3000好买630~60≥3000好买730~60≥3000不好买8>60<3000好买9>60<3000不好不买10>60≥3000不好不买表2决策树理论的分类方法从表2中可以看出，类属性“买车意向”有两个不同的值｛买，不买｝，因此一共有两个类M＝2。设ω1对应于“买”，ω2对应于“不买”，则ω1有6个样本，N1＝6，ω2有4个样本，N2＝4。首先计算期望信息I（N1，N2）。然后计算每个属性的熵。对于属性“年龄”，有三种取值，即三个子集，分别计算三个子集的期望信息。决策树理论的分类方法计算样本按“年龄”划分成子集的熵为信息增益为同理，我们可以得到其余两个属性的信息增益：决策树理论的分类方法图2对属性“年龄”进行划分对属性“年龄”划分后得到图2所示树，年龄30~60的样本都是同一类，故可作为叶子结点，因此对年龄<30以及>60的需要继续操作.决策树理论的分类方法(3)决策树剪枝剪枝

就是指将决策树的某些内部节点下面的节点都删掉，留下来的内部决策节点作为叶子节点。为什么需要剪枝？决策树是充分考虑了所有的数据点而生成的复杂树，它在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，造成决策树很庞大。决策树过于庞大，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高。所以，为了避免过拟合，咱们需要对决策树进行剪枝。决策树理论的分类方法(3)决策树剪枝先剪枝：建树过程中进行判断，若满足一定条件节点不再分裂。后剪枝：建树完成，从叶子到根的方向修剪，若某个叶子剪去后测试集的准确率不降低，则剪去该叶子。决策树理论的分类方法(4)从决策树提取分类规则从根结点到叶结点的每一条路径创建一条分类规则，路径上的每一对“属性-值”对应规则的前件的一个合取项，叶结点为规则的后件。表三所示为例2构造决策树后的分类规则。年龄月薪健康状况买车意向<30<3000不买<30≥3000买30~60买>60不好不买>60好买表3决策树理论的分类方法(5)ID3算法的改进ID3算法的缺点：最优属性选取不准确，信息增益的计算依赖于属性取值数目较多的特征，而取值较多的属性不一定是最优属性；抗噪性差，训练集中正例和反例较难控制。因此，众多学者针对ID3算法的不足，提出了许多改进策略。离散化空缺值处理属性选择度量可伸缩性碎片、重复和复制处理7.2决策树理论的分类方法2.实现步骤构建训练样本集构建分类决策树利用决策树分类显示决策树决策树理论的分类方法习题73.对于一个训练集，如表4所示，利用ID3算法构造一棵决策树。表4决策树理论的分类方法构建训练样本集图3通过创建CSV文件构建样本集决策树理论的分类方法构建分类决策树图4导入要使用的库并读取数据集决策树理论的分类方法构建分类决策树图5创建决策树对数据集进行训练决策树理论的分类方法显示决策树图6显示决策树决策树理论的分类方法显示决策树运行以上代码将在左侧项目区下生成pdf文件。如图7为文件内显示的决策树。0：否

1：是2：体温正常

3：体温高4：体温非常高图7显示决策树决策树理论的分类方法利用决策树分类图8验证决策树构造的正确性，并预测一组数据进行分类决策树理论的分类方法利用决策树分类图9验证结果与预测结果7.3总结