a7模式识别与智能计算第七章+决策树.pptxVIP

模式识别与智能计算第七章决策树分类器设计杨淑莹

第七章决策树分类器设计7.1决策树的基本概念1.决策树的基本原理2.决策树分类3.决策树方法的特点7.2决策树理论的分类方法1.理论基础3.编程代码2.实现步骤4.效果图7.3总结

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

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

决策树的基本概念自然树对应决策树中的意义分类问题中的表示意义树根根节点训练实例整个数据集空间杈内部节点、决策节点待分类对象的属性树枝分支属性的一个可能取值叶子叶子结点、状态节点数据分割（分类结果）表1决策树与自然树的对应关系及代表含义构造决策树通常采用自上而下的递归构造方法。如果训练集中所有数据都是同类的，则将之作为叶节点，节点内容即该类标记，否则根据某种策略选择一个属性，按照属性的各个取值，把数据集合划分若干个子集，使得每个子集上的所有数据在该属性上具有同样的属性值。

2.决策树分类决策树分类算法起源于概念学习系统，然后发展到ID3方法，最后又演化为能处理连续属性的C4.5。此外，还有CART、SLIQ、SPRINT等方法。使用决策树进行分类可分为两步：步骤1：建立决策树模型：利用训练集建立并精化一棵决策树。（建树、剪枝）步骤2：利用生成的决策树对数据进行分类。决策树的基本概念

3.决策树方法的特点与其他分类方法相比，决策树分类有如下优点：分类速度快，计算量相对较小，容易转化成分类规则。分类准确性高，从决策树中挖掘出的规则准确性高且便于理解。决策树的基本概念

7.2决策树理论的分类方法1.理论基础Quinlan提出的ID3算法是决策树算法的代表，具有描述简单、分类速度快的优点，大多数决策树算法都是在它的基础上加以改进而实现的。

（1）ID3算法基本思想决策树理论的分类方法年龄月薪买健康状况不买买不买买30303000不好好图1买车问题的决策树

（2）属性选择度量期望信息量：设训练集为，样品总数为N，其中包含M个不同的类ωi(i=1,2，…，M)的样品的个数。设Ni是中属于类ωi的样品个数。对一个给定样品分类所需的期望信息为其中，pi是样品属于ωi的概率。决策树理论的分类方法

熵：熵是一个衡量系统混乱程度的统计量，熵越大，表示系统越混乱。对于给定子集Sj，有决策树理论的分类方法

决策树理论的分类方法信息增益：Gain（A）是指由于知道属性A的值而导致的熵的期望压缩。在属性A上分支获得的信息增益表示为

例2表2所示的是一个顾客买车意向的训练集，通过此例来说明属性选择方法。决策树理论的分类方法样品编号年龄月薪健康状况买车意向1303000好不买2303000不好不买330≥3000不好买430≥3000好买530~603000好买630~60≥3000好买730~60≥3000不好买8603000好买9603000不好不买1060≥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)决策树剪枝剪枝就是指将决策树的某些内部节点下面的节点都删掉，留下来的内部决策节点作为叶子节点。为什么需要剪枝？决策树是充分考虑了所有的数据点而生成的复杂树，它在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，造成决策树很庞大。决策树过于庞大，有可能出现过拟合的情况，决策