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

注脚

展开查看详情

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 好瓜

30.剪枝处理 - 后剪枝 然后考虑结点 , 若将其替换为叶结点,根据落在其上的 训练样本 将 其标记为“好瓜”,得到验证集 精度仍为 ,可以不进行剪枝 好瓜 好瓜 乌黑 浅白 青绿 色泽 ? 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 脐部 平坦 稍凹 凹陷 1 2 3 4 5 验证集精度 剪枝前 : 57.1 % 剪枝后 : 57.1% 后 剪枝决策 : 不剪枝 好瓜

31.剪枝处理 - 后剪枝 然后考虑结点 , 若将其替换为叶结点,根据落在其上的 训练样本 将 其标记为“好瓜”,得到验证集 精度仍为 ,可以不进行剪枝 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 好瓜 坏瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 脐部 平坦 稍凹 凹陷 1 2 3 4 5 好瓜

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

33.剪枝处理 - 后剪枝 对 结点 和 ,先后替换为叶结点,验证集精度均未提升,则分支得到保留 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 ? 坏 瓜 脐部 ? 平坦 稍凹 凹陷 1 3 4 5 好瓜 好瓜 2

34.剪枝处理 - 后剪枝 最终基于后剪枝策略得到的决策树如图所示 好瓜 好瓜 乌黑 浅白 青绿 色泽 坏 瓜 好瓜 蜷缩 硬挺 稍蜷 根蒂 坏 瓜 脐部 平坦 稍凹 凹陷 1 3 4 5 好瓜 好瓜 2

35.剪枝处理 - 后剪枝 后 剪枝的优缺点 优点 后剪枝比预剪枝保留了更多的分支, 欠拟合风险小 , 泛化性能往往优于预剪枝决策树 缺点 训练时间开销大 :后剪枝过程是在 生成 完全决策树之后进行的,需要自底向上对所有非叶结点逐一考察

36.剪枝处理 - 后剪枝 后 剪枝的优缺点 优点 后剪枝比预剪枝保留了更多的分支, 欠拟合风险小 , 泛化性能往往优于预剪枝决策树 缺点 训练时间开销大 :后剪枝过程是在 生成 完全决策树之后进行的,需要自底向上对所有非叶结点逐一考察

37.连续与缺失 值 – 连续 值处理 连续属性离散化 ( 二分法 ) 第一步:假定连续属性 在样本集 上出现 个不同的取值,从小到大 排列,记为 ,基于划分点 ,可将 分为子集 和 , 其中 包含那些在属性 上取值不大于 的样本, 包含那些在属性 上取值大于 的样本。考虑包含 个元素的候选划分点集合 即把区间 的中位点 作为候选划分点

38.连续与缺失值 – 连续值处理 连续属性离散化 ( 二分法 ) 第二步:采用离散属性值方法,考察这些划分点,选取最优的划分点进行样本集合的划分 其中 是样本集 基于划分点 二分后的信息增益,于是, 就可选择使 最大化的划分点

39.连续与缺失值 – 连续值处理 对属性“密度”,其候选划分点集合包含 个候选值: 可计算其信息增益为 ,对应划分点为 对属性“含糖量”进行 同样 处理 与离散属性不同,若当前结点划分属性为连续属性, 该 属性 还可作为其后代结点的划分属性 连续值处理实例

40.连续与缺失 值 – 缺失值 处理 不 完整样本,即样本的属性值缺失 仅使用无缺失的样本进行学习 ? 使用有缺失值的样本,需要解决哪些问题? 对数据信息极大的浪费 Q1 :如何在属性缺失的情况下进行划分属性选择? Q2 :给定划分属性 , 若样本在该属性上的值缺失,如何对样本进行划分?

41.连续与缺失 值 – 缺失值 处理 表示 中在属性 上没有缺失值的样本子集 , 表示 中在属性 上取值为 的样本子集, 表示 中属于第 类的样本子集 为 每个 样本 赋予 一个权重 ,并 定义 : 无 缺失值样本 所占的比例 无 缺失值样本 中 第 类 所占 比例 无 缺失值样本中在属性 上取值 的样本所 占比例 Q1 :如何 在属性缺失的情况下进行划分属性 选择?

42.连续与缺失值 – 缺失值处理 基于上述定义,可得 其中 对于 Q2 若样本 在划分属性 上的取值已知,则将 划入与其取值对应的子结点,且样本权值在子结点中保持为 若样本 在 划分 属性 上 的 取值未知,则将 同时划入所有子结点,且样本权值在与属性值 对应的子结点中调整为 ( 直观来看,相当于让同一个样本以不同概率划入不同的子结点中去 )

43.连续与缺失值 – 缺失值处理 学习 开始时,根结点包含样本集 中 全部 个 样例,各样例的权值均 为 以属性“色泽”为例 , 该属性上无缺失值的样例子集 包含 个样例, 的信息熵为 缺失值 处理实例

44.连续与缺失值 – 缺失值处理 令 , , 分别表示在属性“色泽”上取值为“青绿”“乌黑”以及“浅白”的样本子集,有 因此,样本子集 上属性“色泽”的信息增益为 于是,样本集 上属性“色泽”的信息增益为

45.连续与缺失值 – 缺失值处理 类似地可计算出所有属性在 数据集 上的信息增益 进入“纹理 = 清晰”分支 进入“纹理 = 稍糊”分支 进入“纹理 = 模糊 ”分支 在属性“纹理”上出现缺失值,样本 8 和 10 同时进入 3 个分支,调整 8 和 10 在 3 分分支权值分别为 7/15 , 5/15 , 3/15 样本权重在各子结点仍为 1

46.连续与缺失值 – 缺失值处理 类似地可计算出所有属性在 数据集 上的信息增益 进入“纹理 = 清晰”分支 进入“纹理 = 稍糊”分支 进入“纹理 = 模糊 ”分支 在属性“纹理”上出现缺失值,样本 8 和 10 同时进入 3 个分支,调整 8 和 10 在 3 分分支权值分别为 7/15 , 5/15 , 3/15 样本权重在各子结点仍为 1

47.多变量 决策树 单变量决策树分类边界 : 轴平行 多变量决策树 0 非叶节点不再是仅对某个属性 , 而是对属性的线性组合 每个非叶结点是一个形如 的线性分类器,其中 是属性 的权值, 和 可在该结点所含的样本集和属性集上 学得

48.多变量 决策树 单变量 决策树 含糖率 ≤ 0.126? 密度 ≤ 0.381? 坏 瓜 密度 ≤ 0.560? 坏 瓜 好 瓜 是 否 好 瓜 是 含糖率 ≤ 0.205? 是 否 坏 瓜 是 否 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 否

49.多变量 决策树 多变量决策树 坏 瓜 是 否 坏 瓜 好 瓜 是 否 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率

50.Take Home Message 属性划分选择 剪枝处理 ( 预剪枝 , 后剪枝 ) 属性连续值和缺失值的处理 单 变量决策树到多变量决策树

51.成熟的 决策树 软件包 ID3,C4.5,C5.0 http://www.rulequest.com/Personal/ J48 http://www.cs.waikato.ac.nz/ml/weka /