《数据把掘概念与技术》第七章 决策树和决策规则

第七章决策树和决策规则 本章目标 分析解决分类问题的基于逻辑的方法的特 性 描述决策树和决策规则在最终分类模型中 的表述之间的区别 介绍C4.5算法 了解采用修剪方法降低决策树和决策规则 的复杂度

第七章 决策树和决策规则 本章目标 ◼ 分析解决分类问题的基于逻辑的方法的特 性. ◼ 描述决策树和决策规则在最终分类模型中 的表述之间的区别. ◼ 介绍C4.5算法. ◼ 了解采用修剪方法降低决策树和决策规则 的复杂度

决策树和决策规则是解决实际应用中分类 问题的数据挖掘方法。 个堆来分迷是故精项吹到博 过程。由一组输入的属性值向量(也叫属性 向量)和相应的类,用基于归纳学习算法得 出分类 学习的目标是构建—个分类模型,通常也 叫分类器。它可以根据有效的属性输入值 预测一些实体(所给样本)的类。是一个在样 本其他属性已知的情况下预测另外一个属 性(样本的类)舶模型(分类的结果)

◼ 决策树和决策规则是解决实际应用中分类 问题的数据挖掘方法。 ◼ 一般来说，分类是把数据项映射到其中一 个事先定义的类中的这样一个学习函数的 过程。由一组输入的属性值向量(也叫属性 向量)和相应的类，用基于归纳学习算法得 出分类。 ◼ 学习的目标是构建一个分类模型，通常也 叫分类器。它可以根据有效的属性输入值 预测一些实体(所给样本)的类。是一个在样 本其他属性已知的情况下预测另外一个属 性(样本的类)的模型(分类的结果)

7.1决策树 」从数据中生成分类器的一个特别有效的方 法是生成一个决策树。它是种基于逻辑 的方法,通过组输入-输出样本构建决策 树的有指导学习方法。 决策树包含属性已被检验的节点,个节 点的输出分枝和该节点的所有可能的检验 结果相对应

7.1 决策树 ◼ 从数据中生成分类器的一个特别有效的方 法是生成一个决策树。它是一种基于逻辑 的方法，通过一组输入-输出样本构建决策 树的有指导学习方法。 ◼ 决策树包含属性已被检验的节点，一个节 点的输出分枝和该节点的所有可能的检验 结果相对应

图72是一个简单的决策树。该问题有两个 属性XY。所有属性值X>1和Y>B的样本属 于类2。不论属性Y的值是多少,值×1 是 Y>? YA Y>B Y>C 类1 类2 类2 类1 图7-2关于属性X和Y的检验的一个简单的决策树

◼ 图7-2是一个简单的决策树。该问题有两个 属性X,Y。所有属性值X>1和Y>B的样本属 于类2。不论属性Y的值是多少，值X <1的 样本都属于类1

对于树中的非叶节点,可以沿着分枝 继续分区样本,每—个节点得到它相 应的样本子集。 生成决策树的一个著名的算法是 Quinlan的ID3算法,C4.5是它改进版

◼ 对于树中的非叶节点，可以沿着分枝 继续分区样本，每一个节点得到它相 应的样本子集。 ◼ 生成决策树的一个著名的算法是 Quinlan的ID3算法，C4.5是它改进版

ID3算法的基本思路 从树的根节点处的所有训练样本开始,选 取一个属性来划分这些样本。对属性的每 值产生一分枝。分枝属性值的相应样 本子集被移到新生成的子节点上。 2.这个算法递归地应用于每个子节点,直到 个节点上的所有样本都分区到某个类中。 3.到达决策树的叶节点的每条路径表示 分类规则

◼ ID3算法的基本思路： 1. 从树的根节点处的所有训练样本开始，选 取一个属性来划分这些样本。对属性的每 一个值产生一分枝。分枝属性值的相应样 本子集被移到新生成的子节点上。 2. 这个算法递归地应用于每个子节点，直到 一个节点上的所有样本都分区到某个类中。 3. 到达决策树的叶节点的每条路径表示一个 分类规则

该算法的关键性决策是对节点属性值的选 择。ID3和C4.5算法的属性选择的基础是基 于使节点所含的信息熵最小化。 基于信息论的方法坚持对数据库中一个样 本进行分类时所做检验的数量最小。ID3的 属性选择是根据个假设,即:决策树的 复杂度和所给属性值表达的信息量是密切 相关的。基于信息的试探法选择的是可以 给出最高信息的属性,即这个属性是使样 本分类的结果子树所需的信息最小

◼ 该算法的关键性决策是对节点属性值的选 择。ID3和C4.5算法的属性选择的基础是基 于使节点所含的信息熵最小化。 ◼ 基于信息论的方法坚持对数据库中一个样 本进行分类时所做检验的数量最小。ID3的 属性选择是根据一个假设，即：决策树的 复杂度和所给属性值表达的信息量是密切 相关的。基于信息的试探法选择的是可以 给出最高信息的属性，即这个属性是使样 本分类的结果子树所需的信息最小

7,24.5算法:生成一个决策树 C4.5算法最重要的部分是由一组训练样本 生成一个初始决策树的过程。决策树可以 用来对一个新样本进行分类,这种分类从 该树的根节点开始,然后移动样本直至达 叶节点。在每个非叶决策点处,确定该节 点的属性检验结果,把注意力转移到所选 择子树的根节点上

7.2 C4.5算法：生成一个决策树 ◼ C4.5算法最重要的部分是由一组训练样本 生成一个初始决策树的过程。决策树可以 用来对一个新样本进行分类，这种分类从 该树的根节点开始，然后移动样本直至达 叶节点。在每个非叶决策点处，确定该节 点的属性检验结果，把注意力转移到所选 择子树的根节点上

例如,如图73a为决策树分类模型,待分 类有样本如图73b所示,由决策树分类模 型可得出待分类样本为类2。(节点ACF(叶 节点) (属性1>5) A 假 属性 值 B)(属性2=“黑”)(C)(属性3=“否”) 属性 5 假 真 假 属性2 黑 属性3 否 E F G 类 类2 类2 类 a)决策树 b)分类的例子 图7-3基于决策树模型的一个新样本的分类

◼ 例如，如图7-3a为决策树分类模型，待分 类有样本如图7-3b所示，由决策树分类模 型可得出待分类样本为类2。(节点A,C,F(叶 节点))

C45算法的构架是基于亨特的CLS方法 其通过一组训练样本「构造一个决策树 用{C1CCk来表示这些类,集合T所含 的内容信息有3种可能性 丁包含一个或更多的样本,全部属于单个 的类C那么的决策树是曲类C标识的 个叶节点 2.T不包含样本。决策树也是一个叶,但和 该叶关联的类由不同于T的信息决定,如「 中的绝大多数类

◼ C4.5算法的构架是基于亨特的CLS方法， 其通过一组训练样本T构造一个决策树。 用{C1 ,C2 ,…,CK}来表示这些类，集合T所含 的内容信息有3种可能性： 1. T包含一个或更多的样本，全部属于单个 的类Cj。那么T的决策树是由类Cj标识的一 个叶节点。 2. T不包含样本。决策树也是一个叶，但和 该叶关联的类由不同于T的信息决定，如T 中的绝大多数类