课件第6章 决策树

1、数据挖掘方法与应用数据挖掘方法与应用浙江工商大学统计与数学学院浙江工商大学统计与数学学院徐雪琪第6章 决策树6.1 决策树概述6.2 ID3算法6.3 C5.0算法6.4 基于IBM SPSS Modeler的应用6.5 基于R语言的应用6.1 决策树概述决策树的建模思路是尽量模拟人做决策的过程，如图6.1 中A 同学周六的计划安排。图图6.1 A 同学的决策过程同学的决策过程6.1.1 决策树分析相关概念1. 树结构相关概念如图6.1 所示，决策树包含根节点根节点、叶节点叶节点和中间节点。中间节点。中间节点，也称内部节点。同层节点称为兄弟节点，上层节点是下层节点的父节点，下层节点是上层节点的

2、子节点。根节点没有父节点，叶节点没有子节点。如果树中每个节点最多只能生长出两个分枝，这样的决策树称为二叉树。如果父节点能够生长出两个以上的子节点，这样的决策树称为多叉树。2. 分类树和回归树如果用于预测的输出变量是类别型变量，则称该决策树为分类树。如果用于预测的输出变量是数值型变量，则称该决策树为回归树。3. 训练集、测试集和验证集训练集是用于训练模型的数据集。测试集用于测试模型对新样本的预测性能，从而评估模型的性能。验证集用于选择模型的超参数超参数。所以，在有监督的学习中，我们通常至少把数据集划分为训练集和测试集两部分。当模型有超参数存在时，我们需要把数据集划分为训练集、测试集和验证集三部分

3、。6.1.2 决策树分析核心问题1. 决策树的生长问题决策树生长过程中，需要解决的主要问题是：第一，如何如何从众多的输入变量中选择一个当前最佳的分组变量选择一个当前最佳的分组变量；第二，如何如何从选定的分组变量中找到最佳的分割点找到最佳的分割点用于分枝。2. 决策树的剪枝问题为了避免过拟合现象，我们需要对树进行修剪。修剪技术主要分为预修剪预修剪和后修剪后修剪两种。6.2 ID3 算法6.2.1 信息论的基本概念1. 自信息量信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。自信息量表示事件发生后，事件给予观察者的信息量，是事件发生概率的函数，事件X 的自信量计算公式

4、为式(6-1)。(6-1)式中，I (X )实质上是无量纲的，为研究问题方便，I (X )的量纲根据对数的底来定义。一般情况下，我们使用以2 为底的对数，单位为比特。【例6.1】假设英文字母“c”出现的概率为0.105，“f ”出现的概率为0.035，“h”出现的概率为0.012。请分别计算它们的自信息量。2. 信息熵自信息量度量的是一个具体事件发生了所带来的信息，而信息熵则是考虑一个随机变量所有可能发生的事件带来的信息量的期望，是随机变量平均不确定性的度量。其计算公式为式(6-2)。(6-2)6.2.2 ID3 算法基本原理ID3 算法最早由Quinlan 提出，是一种典型的决策树学习算法，

5、主要通过信息增益信息增益的方式来选择最优划分属性。1. 信息增益(6-3)(6-4)(6-5)2. ID3 算法描述ID3 算法以信息增益为度量标准，用于决策树节点的属性选择，即每次优先选取信息增益最大的属性作为最佳的分组变量。6.2.3 使用ID3 算法建立决策树【例6.2】表6.1 给出了一个关于2019 年学生是否参加暑期支教活动的训练数据集，包含14 名学生，描述属性分别为：在读阶段、已参加公益活动次数、是否党员和性别，类别属性为是否参加。要求使用ID3 算法生成决策树。1. 创建根节点创建根节点31545(|)= ()=0.97100.9710.694141414jjsEE jn是否

6、参加 在读阶段是否参加2. 创建分枝创建分枝所以，对于分枝在读阶段=“本科”，属性“是否党员”信息增益最高，选取该描述属性继续划分样本数据集。分枝是否党员=“否”，由于所有记录属于同一类别“否”，所以分枝是否党员=“否”的节点为叶节点。分枝是否党员=“是”，由于所有记录属于同一类别“是”，所以分枝是否党员=“是”的节点为叶节点。(2) 分枝在读阶段=“博士”。由于所有记录属于同一类别“是”，所以分枝在读阶段=“博士”的节点为叶节点。(3) 分枝在读阶段=“硕士”。所以，对于分枝在读阶段=“硕士”，属性“性别”信息增益最高，选取该描述属性继续划分样本数据集。分枝性别=“男”，由于所有记录属于同一

7、类别“否”，所以分枝性别=“男”的节点为叶节点。分枝性别=“女”的节点，由于所有记录属于同一类别“是”，所以分枝性别=“女”的节点为叶节点。生成的决策树如图6.2 所示。6.3 C5.0 算法结合以上ID3算法的理论与实例，思考ID3算法有什么局限性？选用最大信息增益的属性作为决策树分裂属性，会偏向于取值多的属性不能处理带有缺失值的数据集只能处理离散属性没有考虑剪枝，会导致过拟合6.3.1 C5.0 算法的决策树生长1. 最佳分裂属性选择标准假设年龄段中把中青年拆成两个取值：中年和青年，客户ID 号为2、10 和12 的客户为青年，客户ID 号为3 和13 的为中年，如表6.3 所示。则重新计

8、算变量年龄段的后验熵：可见，调整后的后验熵比调整前增大了。为了解决这个问题，C5.0 使用信息增益率作为选择标准，计算公式为(6-6)调整前年龄段的信息增益率调整后年龄段的信息增益率2. 对连续型属性的处理C5.0 算法集成了对连续型属性的离散化。IBM SPSS Modeler C5.0 节点基于最短描述长度原则，即MDLP(minimum description length principle)的熵分组方法自动完成对连续型属性的离散化。按照上述方法，可计算出取所有可能组限值分组后的信息增益，然后选择信息增益最大的且有意义的组限值进行分组。这个过程可在各个分组中不断重复。基于MDLP 的停

9、止标准是，分组带来的收益不大于分组代价时，分组就不应该继续下去了。从信息传输角度看，分组的代价在于分组需要一定长度的编码来描述分组方案。编码长度计算公式为式(6-7)。(6-7)可见，以30 分组得到的信息增益0.151 6 小于分组代价0.555 7，因此不能依此分组，需要继续寻找。3. 对具有缺失值属性的处理C5.0 算法选择最佳分裂属性时，如果遇到属性值有缺失，会将带有缺失值的样本临时剔除，并进行权重调整处理。假设表6.2 中，ID 号为1 的客户年龄段属性取值缺失，如表6.4 所示。C5.0 算法计算年龄段属性的信息增益率过程如下。4. 分裂属性最佳分割点的处理IBM SPSS Mod

10、eler C5.0 节点最佳分割点默认采用方法：（1）如果最佳分裂属性为具有k 个类别的分类型变量，则根据k 个取值将样本分为k 组，形成树的k 个分枝。（2）如果最佳分裂属性为连续型属性，则按以上基于MDLP 的二分法产生两个分枝。除了以上默认的方法，IBM SPSS Modeler C5.0 节点还允许通过选择“组符号(groupsymbolics)”将分裂属性的相似类别进行合并，然后再基于合并的结果分枝。6.3.2 C5.0 算法的决策树修剪C5.0 采用后剪枝方法后剪枝方法从叶节点向上逐层修剪1. 悲观估计法(6-8)(6-9)(6-10)2. 修剪标准在悲观估计法的基础上，C5.0

11、算法将根据“是否减少误差”判断是否修剪。(6-11)以上的修剪标准，只考虑了误差的大小，而没有区分不同的错误对预测带来的损失大小。IBM SPSS Modeler C5.0 节点允许选择使用损失矩阵，将“是否减少误差”调整为“是否减少损失”进行剪枝。通过判断待剪子树中叶节点的加权损失是否大于父节点的损失来修剪，如果大于就剪掉，如式(6-12)。(6-12)6.4 基于IBM SPSS Modeler 的应用示例数据集为“药物数据集.xlsx”，包含999 位患者的基本信息、临床检验数据和服用的药物，这些患者患有同种疾病，服用不同药物后都取得了同样的治疗效果。患者基本信息为年龄和性别，临床检验数

12、据包括血压、胆固醇、唾液中的钠含量和钾含量。从数据读入、数据检查、探索性分析到决策树模型构建及预测，建立的数据流如图6.5所示。图图6.5 药物数据药物数据C5.0 决策树分析数据流决策树分析数据流6.4.1 数据读取与审核1. 数据读取图图6.6 药物数据集药物数据集结果如图6.6 所示，包括999 条记录，7 个字段。2. 数据审核连接“输出”选项卡下的“数据审核”节点查看数据基本特征及质量，结果如图6.7和6.8 所示。图图6.7 “数据审核数据审核”节点节点“审核审核”选项卡结果选项卡结果图图6.8 “数据审核数据审核”节点节点“质量质量”选项卡结果选项卡结果6.4.2 探索性分析1.

13、 血压与药物关系探索通过网络图来观察不同血压特征患者的药物选择。图图6.9 “网络网络”节点参数设置节点参数设置图图6.10 血压与药物网络图血压与药物网络图2. 唾液中钠含量和钾含量关系探索通过散点图来观察服用不同药物的患者唾液中的钠含量和钾含量。图图6.11 “散点图散点图”选项卡选项卡图图6.12 “选项选项”选项卡选项卡“点点”样式参数样式参数图图6.13 “选项选项”选项卡选项卡“线线”样式参数样式参数图图6.14 “外观外观”选项卡参数选项卡参数本示例中，“散点图”选项卡参数按图6.11 设置，“选项”选项卡选择“点”样式，“外观”选项卡参数按图6.14 设置，则运行结果如图6.1

14、5 所示。图图6.15 “散点图散点图”节点运行结果节点运行结果6.4.3 数据预处理1. 使用“导出”节点衍生新的变量使用“导出”节点衍生新的变量：钠含量/钾含量，并观察其分布特征。图图6.16 “导出导出”节点节点“设置设置”选项卡参数设置选项卡参数设置图图6.17 “导出导出”字段表达式构建器字段表达式构建器设定参数后，连接“表格”节点，运行结果如图6.18所示。图图6.18 导出结果导出结果选择“图形”选项卡下的“直方图”节点，添加到数据流，设置节点参数如图6.19 所示，运行结果如图6.20 所示。图图6.19 直方图参数设置直方图参数设置图图6.20 钠含量钠含量/钾含量直方图钾含

15、量直方图2. 使用“过滤器”节点过滤变量图图6.21 “过滤器过滤器”节点节点3. 使用“分区”节点划分训练集与测试集图图6.22 “分区分区”节点参数设置节点参数设置图图6.23 分区结果分区结果4. 使用“类型”节点重新实例化数据并设置字段角色图图6.24 实例化并设置字段角色后的结果实例化并设置字段角色后的结果6.4.4 决策树模型构建与评估：基于C5.0 算法1. 决策树模型构建选择“建模”选项卡下的C5.0 节点，添加到数据流。图图6.25 C5.0 节点节点“字段字段”选项卡选项卡“模型”选项卡用于设置C5.0 算法的主要参数，如图6.26、6.27 所示。图图6.26 C5.0

16、算法算法“模型模型”选项卡简单模式选项卡简单模式图图6.27 C5.0 算法算法“模型模型”选项卡专家模式选项卡专家模式“成本”选项卡用于设置误差成本代价，如图6.28 所示。“分析”选项卡用于设置计算输入变量重要性的指标，如图6.29 所示。图图6.28 C5.0 算法算法“成本成本”选项卡选项卡图图6.29 C5.0 算法算法“分析分析”选项卡选项卡图图6.30 C5.0 算法结果的算法结果的“模型模型”选项卡选项卡图图6.31 C5.0 算法结果的算法结果的“查看器查看器”选项卡选项卡2. 决策树模型评估为了进一步评估模型，在“药物模型”节点添加“输出”选项卡下的“分析”节点，进行参数设

17、置，如图6.32 所示。图图6.32 “分析分析”选项卡参数设置选项卡参数设置按图6.32设定参数，运行“分析”节点，结果如图6.33 所示图图6.33 模型评估结果模型评估结果6.4.5 预测结果为观察预测结果，将“表格”节点添加到数据流，运行“表格”节点，结果如图6.34。图图6.34 预测结果预测结果6.5 基于R 语言的应用本节示例数据集来自于UCI 机器学习数据仓库(machine learning data repository)，由汉堡大学的Hans Hofmann 捐赠，是德国一个信贷机构的贷款数据。6.5.1 数据探索1. 数据集初探2. 类别型变量探索使用table( )函

18、数分别对default、credit_history、purpose 和job 四个类别型变量进行分析使用table( )函数探索default 变量与credit_history 、checking_balance 和savings_balance 变量的交叉分布关系。3. 数值型变量探索对于数值型变量，我们可以使用summary( )函数得到常用的6 个汇总统计量。除了使用常用的汇总统计量反映数值型变量特征，我们还可以使用统计图来进一步观察数值型变量。使用hist( )函数分别为变量age、months_loan_duration 和amount 绘制直方图，结果如图6.35、6.36、6.37 所示。使用p