决策树

1 .杨杨 范颖

2 .第 四 章 ： 决策树

3 .大纲 基本流程 划分选择 剪枝处理 连续与缺失值 多变量决策树

4 .基本流程 决策树基于树结构来进行预测 色泽 =? 根蒂 =? 敲声 =? 好瓜 青绿 蜷缩 浊响 …... … …... … …... …

5 .基本流程 决策过程中提出的每个判定问题都是对某个属性的“测试” 决策过程的最终结论对应了我们所希望的判定结果 每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑 范围 是在上次决策结果的限定范围之内 从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵 泛化能力强 ，即 处理未见示例能力强的决策树

6 .基本流程 （ 1 ） 当前结点 包含 的样本全部属于同一类别 （ 2 ）当前属性集为空，或所有样本在所有属性上取值相同 （ 3 ）当前结点包含的样本集合为空

7 .基本流程 （ 1 ） 当前结点 包含 的样本全部属于同一类别 （ 2 ）当前属性集为空，或所有样本在所有属性上取值相同 （ 3 ）当前结点包含的样本集合为空

8 .划分选择 决策树学习的关键在于 如何选择最优划分属性 。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本 尽可能属于同一类别，即结点的“纯度” (purity) 越来越高 经典的属性划分方法： 信息增益 增益率 基 尼指数

9 .划分选择 - 信息增益 “ 信息熵 ”是 度量样本集合纯度最常用的一种指标 ，假定当前样本集合 中第 类样本所占的比例为 ， 则 的信息熵定义为 的 值越小， 则 的 纯度越 高 计算信息熵时约定 ： 若 ，则 的最小值为 ，最大值为

10 .划分选择 - 信息增益 离散属性 有 个 可能的 取值 ，用 来 进行划分 ，则会产生 个 分支 结点 ，其中 第 个 分支 结点包含了 中 所有在 属性 上 取值为 用属性 对样本集 进行 划分所获得的 “信息增益”： 一般而言 ， 信息增益越大 ，则意味着使用 属性 来进行划分所获得的“ 纯度提升 ”越大 ID3 决策树学习算法 [Quinlan, 1986] 以信息增益为准则来选择划分属性   为 分支结点权重，样本数越多的分支结点的影响越大

11 .划分选择 - 信息增益 信息增益实例 …... … …... … 该数据集 包含 个训练样本 ， ， 其中正例 占 ， 反例占 ，计算得到根结点的信息熵为

12 .划分选择 - 信息增益 以属性“色泽”为例，其对应的 个数据子集分别为 ( 色泽 = 青绿 ) ， ( 色泽 = 乌黑 ) ， ( 色泽 = 浅白 ) 子集 包含编号为 的 个样例，其中正例占 ，反例占 ， 、 同理， 个结点的信息熵为： 属性 “色泽”的 信息增益为

13 .划分选择 - 信息增益 类似的，其他属性的信息增益为 显然，属性“纹理”的信息增益最大，其被选为划分属性 清晰 稍糊 模糊 {1,2,3,4,5,6,8,10,15} 纹理 =? {7,9,13,14,17} {11,12,16}

14 .划分选择 - 信息增益 决策树学习算法将对每个分支结点做进一步划分，最终得到的决策树如图： 清晰 稍糊 模糊 根蒂 =? 坏瓜 纹理 =? 坏瓜 好瓜 蜷缩 稍 蜷 硬挺 好瓜 坏 瓜 好瓜 好瓜 色泽 =? 青绿 乌黑 浅白 好瓜 坏瓜 触感 =? 硬滑 软粘 触感 =? 硬滑 软粘

15 .划分选择 - 信息增益 存在的问题 若把“编号”也作为一个候选划分属性，则其信息增益一般远大于其他属性。显然，这样的决策树不具有泛化能力，无法对新样本进行有效预测 信息增益对 可取值数目较多的属性有所 偏好

16 .划分选择 - 增益率 增益率定义： 其中 称为 属性 的“固有值” [Quinlan , 1993] ，属性 的可能取值 数目 越多（即 越大），则 的值通常就越大 存在的问题 C4.5 [Quinlan, 1993] 使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选取增益率最高的 增益率准则对可取值数目较少的属性有所偏好

17 .划分选择 - 基尼指数 数据集 的纯度可用“基尼值”来度量 越小，数据集 的纯度越高 属性 的基尼指数定义为： 应选择那个使划分后基尼指数最小的属性作为最优划分属性， 即 CART [ Breiman et al., 1984] 采用“基尼指数”来选择划分属性 反映了从 中随机抽取两个样本，其类别标记不一致的概率

18 .划分选择 - 基尼指数 数据集 的纯度可用“基尼值”来度量 越小，数据集 的纯度越高 属性 的基尼指数定义为： 应选择那个使划分后基尼指数最小的属性作为最优划分属性， 即 CART [ Breiman et al., 1984] 采用“基尼指数”来选择划分属性 反映了从 中随机抽取两个样本，其类别标记不一致的概率

19 .剪枝处理 为什么剪枝 “剪枝”是 决策树学习算法 对付“过拟合” 的 主要 手段 可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过 拟合 剪枝的基本策略 预剪枝 后 剪枝 判断决策树泛化性能是否提升的方法 留 出法 ：预留一部分数据用作“验证集”以进行性能评估

20 .剪枝处理 数据集 训练集 验证集

21 .剪枝处理 未剪枝决策树 好瓜 坏瓜 好瓜 清晰 纹理 =? 模糊 稍糊 好瓜 好瓜 乌黑 浅白 青绿 色泽 =? 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 =? 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 =? 坏 瓜 脐部 =? 平坦 稍凹 凹陷 1 2 3 4 5 6

22 .剪枝处理 - 预剪枝 决策树生成过程 中 ， 对 每个结点在 划分前先进行估计 ， 若 当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为 叶结点，其类别标记为训练样例数最多的类别 针对上述数据集，基于 信息增益准则，选取属性“脐部”划分训练集。分别计算划分 前（即 直接将该结点作为叶 结点）及划分 后的验证集精度，判断是否需要划分。若划分 后能 提高验证集精度，则划分，对划分后的属性，执行同样 判断；否则，不划分

23 .剪枝处理 - 预剪枝 脐部 =? 1 “脐部 =? ” 验证集精度 划分前 : 42.9% 结点 1 ：若不划分，则将其标记为叶结点，类别标记为训练样例中最多的类别，即好瓜。验证集中， 被分类正确，得到验证集精度为 验证集

24 .剪枝处理 - 预剪枝 好瓜 坏瓜 好瓜 稍凹 平坦 凹陷 脐部 =? 1 2 3 4 “脐部 =? ” 验证集精度 划分前 : 42.9% 划分后 : 71.4% 预剪枝决策 : 划分 结点 1 ：若划分，根据结点 ， ， 的训练样例，将这 个结点分别标记为“好瓜”、“好瓜”、“坏瓜”。此时，验证集中编号为 的样例被划分正确，验证集精度为 验证集

25 .剪枝处理 - 预剪枝 好瓜 坏瓜 好瓜 稍凹 平坦 凹陷 脐部 =? 1 2 3 4 “脐部 =? ” 验证集精度 划分前 : 42.9% 划分后 : 71.4% 预剪枝决策 : 划分 “色泽 =? ” 验证集精度 划分前 : 71.4% 划分后 : 57.1% 预剪枝决策 : 禁止划分 “根蒂 =? ” 验证集精度 划分前 : 71.4% 划分后 : 71.4% 预剪枝决策 : 禁止划分 对结点 ， ， 分别进行剪枝判断，结点 ， 都禁止划分，结点 本身为叶子结点。最终得到仅有一层划分的决策树，称为“ 决策树桩 ” 验证集

26 .剪枝处理 - 预剪枝 预剪枝的优缺点 优点 降低过拟合风险 显著减少训练时间和测试时间开销 缺点 欠拟合风险 ：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险

27 .剪枝处理 - 后剪枝 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶 结点 能带来决策树泛化性能提升，则将该子树替换为叶结点 好瓜 坏瓜 好瓜 清晰 纹理 模糊 稍糊 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 脐部 平坦 稍凹 凹陷 1 2 3 4 5 6 首先生成一棵完整的决策树，该决策树的验证集精度为

28 .剪枝处理 - 后剪枝 首先考虑结点 ，若将其替换为叶结点，根据落在其上的训练样本 将其标记为“好瓜”，得到验证集精度提高至 ，则决定剪枝 好瓜 坏瓜 好瓜 清晰 纹理 ? 模糊 稍糊 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 脐部 平坦 稍凹 凹陷 1 2 3 4 5 6 验证集精度 剪枝前 : 42.9% 剪枝后 : 57.1% 后 剪枝决策 : 剪枝

29 .剪枝处理 - 后剪枝 首先考虑结点 ，若将其替换为叶结点，根据落在其上的训练样本 将其标记为“好瓜”，得到验证集精度提高至 ，则决定剪枝 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 脐部 平坦 稍凹 凹陷 1 2 3 4 5 好瓜