第六讲 · 决策树

Views: --
#机器学习 #AI

如果分类过程可以写成一串问题——“天气如何？”“湿度高不高？”“风强不强？”——那么它天然就能画成一棵树。决策树学习的任务不是人工写这些问题，而是从带标签的样本中自动选择提问顺序，逐步把混在一起的类别分开。

课件以睡眠脑电分析为引子，并介绍了一个包含 53 名患者、用决策树识别快速眼动阶段的案例；课件给出的识别准确率为 96%。这个数字属于课件案例，真正评价一个新模型时仍要核对数据划分、类别比例和指标定义。无论数据来自脑电、设备传感器还是日常记录，树模型做的事情都一样：把数表转换成可执行的 IF ... THEN ... 规则。

一、树、分类规则与递归划分

一棵分类决策树包含三类元素：

  • 内部节点：检查某个属性，例如“天气”；
  • 分支：属性的某个取值，例如 Sunny；
  • 叶节点：最终类别，例如“打网球”或“不打网球”。

从根到叶的一条路径就是一条合取规则。例如

个子大∧脖子短∧鼻子长⇒可能是大象.\text{个子大}\land\text{脖子短}\land\text{鼻子长} \Rightarrow\text{可能是大象}.

学习一棵树可以看成不断重复同一个动作：在当前样本集合上选一个属性，按属性取值切成子集，再对子集递归建树。真正困难的问题是：这一步应该先问哪个属性？

决策树的发展脉络也围绕这个问题展开：早期概念学习之后，Quinlan 提出 ID3；ID4、ID5 进一步考虑增量式生成；C4.5 则在 ID3 的基础上处理属性选择与过拟合等问题。

二、信息量与信息熵

一个几乎必然发生的事件不会带来多少新信息；一个小概率事件一旦发生，信息量更大。事件 xx 的自信息量定义为

I(x)=−log⁡2P(x).I(x)=-\log_2P(x).

若分类集合 DD 中第 kk 类的比例为 pkp_k，信息熵是自信息量的期望：

H(D)=−∑k=1Kpklog⁡2pk.H(D)=-\sum_{k=1}^{K}p_k\log_2p_k.

约定 0log⁡0=00\log 0=0。采用以 2 为底的对数时，单位是 bit；换用其他底数只会整体缩放，不改变属性优劣的排序。

熵可以理解为“只知道类别比例时，标签还剩多少不确定性”：

  • 全部样本同类时，H(D)=0H(D)=0；
  • 二分类各占一半时，H(D)=1H(D)=1，不确定性最大；
  • 类别越混杂，熵越大；越纯，熵越小。

因此，决策树希望每次划分后，子节点的加权平均熵尽量小。

三、信息增益：一次提问消除了多少不确定性

属性 AA 有若干取值 vv，记取值为 vv 的样本子集为 DvD_v。划分后的条件熵为

H(D∣A)=∑v∈Values⁡(A)∣Dv∣∣D∣H(Dv).H(D\mid A)=\sum_{v\in\operatorname{Values}(A)} \frac{|D_v|}{|D|}H(D_v).

信息增益定义为

Gain⁡(D,A)=H(D)−H(D∣A).\operatorname{Gain}(D,A)=H(D)-H(D\mid A).

它回答：“知道属性 AA 后，标签的不确定性平均减少了多少？”增益越大，说明这次提问把类别分得越纯。

注意，ID3 每一步只选择当前信息增益最大的属性，这是贪心选择；它不保证得到全局节点数最少的树。奥卡姆剃刀提供的是“偏好简单规则”的动机，不是这一步贪心算法的全局最优证明。

四、完整算例：到底要不要打网球

课件使用经典的 14 条记录：

编号天气温度湿度风力打网球
1SunnyHotHighWeakNo
2SunnyHotHighStrongNo
3OvercastHotHighWeakYes
4RainMildHighWeakYes
5RainCoolNormalWeakYes
6RainCoolNormalStrongNo
7OvercastCoolNormalStrongYes
8SunnyMildHighWeakNo
9SunnyCoolNormalWeakYes
10RainMildNormalWeakYes
11SunnyMildNormalStrongYes
12OvercastMildHighStrongYes
13OvercastHotNormalWeakYes
14RainMildHighStrongNo

其中 Yes 有 9 条，No 有 5 条，所以根节点的熵为

H(D)=−914log⁡2914−514log⁡2514≈0.940.H(D) =-\frac{9}{14}\log_2\frac{9}{14} -\frac{5}{14}\log_2\frac{5}{14} \approx0.940.

计算“天气”的信息增益

  • Sunny：5 条，其中 2 Yes、3 No，熵约为 0.9710.971；
  • Overcast：4 条，全是 Yes，熵为 00；
  • Rain：5 条，其中 3 Yes、2 No，熵约为 0.9710.971。

因此

H(D∣天气)=514×0.971+414×0+514×0.971≈0.694,H(D\mid\text{天气}) =\frac{5}{14}\times0.971 +\frac{4}{14}\times0 +\frac{5}{14}\times0.971 \approx0.694, Gain⁡(D,天气)=0.940−0.694≈0.247.\operatorname{Gain}(D,\text{天气}) =0.940-0.694 \approx0.247.

其余属性用同样方法计算：

属性信息增益（约）
天气0.247
湿度0.152
风力0.048
温度0.029

天气的信息增益最大，所以它成为根节点。

对每个子集继续递归

Overcast 的 4 条记录已经全是 Yes，直接成为叶节点。

Sunny 子集中，湿度恰好能完全分开标签：

  • High：编号 1、2、8，全是 No；
  • Normal：编号 9、11，全是 Yes。

Rain 子集中，风力恰好能完全分开标签：

  • Strong：编号 6、14，全是 No；
  • Weak：编号 4、5、10，全是 Yes。

最终规则可以写成：

  1. 天气为 Overcast，打球；
  2. 天气为 Sunny 且湿度为 Normal，打球；
  3. 天气为 Sunny 且湿度为 High，不打；
  4. 天气为 Rain 且风力为 Weak，打球；
  5. 天气为 Rain 且风力为 Strong，不打。

树不只是给出预测，还把预测依据显式暴露出来，这是它容易解释的原因。

五、ID3 算法走一遍

输入当前样本集 DD 与可用属性集合 A\mathcal A，ID3 的递归过程是：

  1. 若 DD 中样本全属同一类，创建该类叶节点；

  2. 若 A\mathcal A 为空，创建叶节点，类别取 DD 中的多数类；

  3. 计算每个属性的信息增益，选择

    A∗=arg⁡max⁡A∈AGain⁡(D,A);A^*=\arg\max_{A\in\mathcal A}\operatorname{Gain}(D,A);

  4. 以 A∗A^* 创建内部节点，按它的每个取值 vv 生成分支；

  5. 对每个非空子集 DvD_v，递归调用

    ID3⁡(Dv,A∖{A∗});\operatorname{ID3}(D_v,\mathcal A\setminus\{A^*\});

  6. 若某个取值没有训练样本，就用当前节点的多数类作为该分支预测。

“属性用过后从集合里删除”适合离散属性的原始 ID3。连续属性通常通过候选阈值转成“x≤tx\le t / x>tx>t”的二分；后续子树仍可能再次使用同一连续属性。

六、为什么训练树会过拟合

如果一直分到每个叶子只剩一个样本，训练误差很容易降到 0，但树可能记住噪声。例如新增一个“样本编号”属性，每条记录的取值都不同，它能一步把所有样本切成纯叶子，信息增益看起来很大，却对新样本毫无帮助。

过拟合常见信号是：

  • 树很深、叶子样本很少；
  • 训练误差继续下降，验证误差却开始上升；
  • 小幅改动训练数据，树结构就剧烈变化。

有两类控制方法：

预剪枝

建树过程中提前停止，例如限制最大深度、叶节点最少样本数、最小信息增益，或要求一次划分必须改善验证集表现。优点是训练快，风险是过早停止，错过后续组合才能显现的有效结构。

后剪枝

先生成较完整的树，再自底向上尝试把一棵子树替换成叶节点。若替换后验证误差没有明显变差，或“误差增加”小于“模型复杂度降低”带来的收益，就剪掉该子树。后剪枝通常判断更充分，但先要长出整棵树。

七、C4.5 对 ID3 的关键改进

ID3 的信息增益偏爱取值很多的属性。C4.5 使用增益率抑制这种偏好。先定义属性本身把样本切得多碎：

SplitInfo⁡(D,A)=−∑v∣Dv∣∣D∣log⁡2∣Dv∣∣D∣,\operatorname{SplitInfo}(D,A) =-\sum_v\frac{|D_v|}{|D|}\log_2\frac{|D_v|}{|D|},

再定义

GainRatio⁡(D,A)=Gain⁡(D,A)SplitInfo⁡(D,A).\operatorname{GainRatio}(D,A) =\frac{\operatorname{Gain}(D,A)} {\operatorname{SplitInfo}(D,A)}.

一个属性若只是制造大量小分支，分裂信息也会很大，增益率便受到惩罚。实际选择时还要避免偏向“几乎不分裂”的极端属性，通常先筛掉信息增益过低的候选，再比较增益率。

C4.5 还扩展了原始 ID3：

  • 通过寻找阈值处理连续属性；
  • 允许样本存在缺失属性，并按可用信息或分支权重处理；
  • 采用剪枝降低训练噪声造成的过拟合；
  • 可把树转换成更紧凑的规则集合。

因此，“C4.5 = ID3 再换一个公式”并不完整；属性度量、数据类型和复杂度控制都发生了变化。

八、容易混淆的四件事

  1. 自信息量与熵：前者对应一个事件，后者是整个分布上自信息量的期望。
  2. 熵与信息增益：熵衡量当前有多混；信息增益衡量一次划分让它少混了多少。
  3. 局部贪心与全局最优：ID3 每个节点选当前最优属性，不等于找到了全局最小的树。
  4. 训练纯净与泛化良好：叶子越纯，训练误差通常越低；但树过深时，新数据表现可能更差，所以还需要验证与剪枝。

本讲速记

  • 一条根到叶路径就是一条 IF ... THEN ... 分类规则。
  • 熵衡量类别不确定性；信息增益是划分前熵减去划分后的加权熵。
  • ID3 自顶向下、递归地选择当前信息增益最大的属性。
  • “打网球”例中先选天气，再在 Sunny 分支选湿度、在 Rain 分支选风力。
  • C4.5 用增益率缓解多取值偏好，并加入连续值、缺失值和剪枝等处理。
  • 决策树一定要同时看训练效果与验证效果；生长负责拟合，剪枝负责控制复杂度。

评论