COMP5318 Week 05 决策树与集成学习讲课总结

Posted on In , Word count in article: 1.6k Reading time ≈ 6 mins.
COMP5318 Week 05 讲课总结，整理决策树的自顶向下分治构建、熵与信息增益的定义和天气数据完整算例、Tutorial 5 形状/颜色手算题、预剪枝与后剪枝（子树替换）、数值属性离散化、高分支属性与增益率；以及集成学习的动机（25 个基分类器的误差计算）、 Bagging 与自助采样、AdaBoost 权重更新、Gradient Boosting 拟合残差、Random Forest 的双重随机性和各方法对比。

COMP5318 W05 考点速成：决策树、规则学习与集成

用时约 15 分钟。必考：熵与信息增益手算（PE1 Q31 大题 10 分）、树路径 = AND、Bagging / Boosting / Random Forest 各自的「定义性操作」。对应 PE1 Q4、Q11–Q13、Q31，PE2 Q4、Q11–Q13。

一、知识点

1. 熵与信息增益

  • 二分类 ：0 = 纯，1 = 一半一半（ 类时最大为 ）；约定 。
  • 选增益最大的属性；父熵固定，加权子熵越小，增益越大。
  • 常用值： ， ， ， ， 。
  • 天气数据：Gain(outlook) = 0.247 最大，作根；sunny 分支再按 humidity 分。

2. 决策树构建

flowchart TD
  O{"outlook？"} -->|"sunny"| H{"humidity？"}
  O -->|"overcast"| Y1["yes"]
  O -->|"rainy"| W{"windy？"}
  H -->|"high"| N1["no"]
  H -->|"normal"| Y2["yes"]
  W -->|"false"| Y3["yes"]
  W -->|"true"| N2["no"]
  • 自顶向下、递归分治：选最佳属性 → 按取值分支 → 对子集递归 → 全同类就建叶。
  • 一条根到叶的路径 = 一条规则，路径上的测试是 AND（合取）。
  • 数值属性：排序 → 在类别变化处取中点作候选切分点 → 逐个算增益取最好。
  • 信息增益偏向取值多的属性（如 ID code，每个子集都纯）→ 用 gain ratio（除以 SplitInfo）惩罚。CART 用 Gini。
  • 过拟合：数据少或有噪声时树会长得过细。预剪枝（提前停，如 max_depth）vs 后剪枝（先长满再剪，更常用）。子树替换：自底向上，把子树换成多数类叶，验证集准确率不降就剪。

3. 规则学习（1R / PRISM，周总结没有单独讲，按标准定义补充）

  • 1R：对每个属性，每个取值预测该取值下的多数类，数总错误；选错误最少的那一个属性的规则集。最终模型只用一个属性，不做多属性合取。
  • PRISM（覆盖算法）：为某一类逐条生成规则；规则覆盖了别的类时再加一个条件，缩小覆盖集、提高该类纯度；规则纯了就移除它覆盖的样本，继续下一条。

4. 集成

flowchart LR
  subgraph Bagging["Bagging / RF：并行"]
    D1["训练集"] --> s1["bootstrap 1 → 树 1"]
    D1 --> s2["bootstrap 2 → 树 2"]
    D1 --> s3["bootstrap M → 树 M"]
    s1 --> v1["等权投票"]
    s2 --> v1
    s3 --> v1
  end
  subgraph Boosting["Boosting：顺序"]
    c1["模型 1"] -->|"错分样本加权 / 拟合残差"| c2["模型 2"]
    c2 -->|"再关注剩下的错误"| c3["模型 3"]
    c3 --> v2["加权投票 / 预测相加"]
  end
  • 集成有效的两个条件：基分类器比随机好（二分类 ）+ 彼此独立 / 多样。25 个独立、 的分类器多数投票，集成错误率约 0.06；完全相同则仍是 0.35； 集成更差。
方法 定义性操作 组合
Bagging 在有放回抽样（bootstrap）的样本上训练各基学习器，并行 等权投票（回归取平均）
AdaBoost 顺序训练；分对样本权重乘 再归一化 → 错分样本相对权重变大 按准确率加权投票
Gradient Boosting 顺序训练；新树拟合残差 （平方损失的负梯度） 各树预测相加
Random Forest Bagging + 每次分裂只在随机的 个特征中挑；树不剪枝 多数投票
  • Bootstrap 样本大小 = ，约 63.2% 的原样本至少出现一次（ ）。
  • Bagging 对不稳定模型（深树、神经网络）最有效；Boosting 可把弱学习器（如 decision stump）提升为强学习器。
  • RF 的 增大，单棵树强度和树间相关性同时增大；代价是失去可解释性、计算量大。

二、考点

  1. ★★★ 信息增益手算：父熵 → 每个子节点熵 → 按样本比例加权 → 相减。
  2. ★★★ 集成的定义：bagging = bootstrap 有放回；AdaBoost = 提高错分样本相对权重；GB = 拟合「观测 − 当前预测」；RF = 每次分裂随机特征子集。
  3. ★★ 树路径是 AND；1R 只选一个属性；PRISM 加条件是为了提高纯度。
  4. ★★ 剪枝用验证集；增益偏向多值属性 → gain ratio。

三、题目

Q1（PE1 Q31，10 分大题） 节点 4 正 4 负；划分后 L = 3 正 1 负，R = 1 正 3 负。(a) 父节点和两个子节点的熵；(b) 加权子熵和信息增益（保留三位小数）。

  1. ； 0.811。
  2. 权重各 0.5，加权子熵 0.811；IG 0.189 bits。

Q2（PE1 Q11） 同一父节点上，划分 X 的加权子熵比划分 Y 低，能推出什么？

X 的信息增益更高（父熵固定，减去的更少）。

Q3（PE2 Q11） 一条树路径只有在 Colour = green 且 Size = small 时到达 Yes 叶，对应的规则？

IF Colour = green AND Size = small THEN Yes。用 OR 会把路径外的样本也包进来。

Q4（PE1 Q12） Bagging 定义性的训练数据操作是什么？

在有放回抽取的 bootstrap 样本上训练各基学习器。「只在上一个学习器错分的样本上训练」是 boosting 的思路。

Q5（PE1 Q13） 平方损失下，后一棵回归树要纠正当前集成没解释的部分，它的训练目标是？

观测值 − 当前集成预测（残差）。符号反过来会放大误差。

Q6（PE2 Q12） 随机森林除了 bootstrap，还常用什么随机化来降低树之间的相似度？

每次分裂只在随机的特征子集里找最佳划分，避免同几个强特征主导所有树。

Q7（PE2 Q13） AdaBoost 训练完一个弱分类器后，下一轮样本权重怎么调？

错分样本的相对权重增大，让下一个学习器关注难样本。

Q8（PE1 Q4） PRISM 为 Yes 类生成规则时，当前规则同时覆盖 Yes 和 No 样本，再加一个条件的目的？

缩小覆盖集，提高对 Yes 类的纯度（把混进来的 No 排除）。

Q9（PE2 Q4） 1R 分类器的最终模型有什么特点？

只选一个属性的规则集（错误最少的那个），不跨多个属性做合取。

Q10（自拟） 8 个样本：shape 划分为 circle 3+/0−、square 2+/2−、triangle 0+/1−；整体 5+/3−（ ）。求 Gain(shape)。

加权子熵 ，Gain 0.45。

Q11（自拟） 为什么 Random Forest 用不剪枝的树也不太过拟合？Bagging 和 Boosting 哪个能并行？

多棵去相关的树投票平均掉了单棵树的方差。Bagging（和 RF）能并行，Boosting 必须顺序训练。