ID3算法

小象实战讲义 · 机器学习算法精讲

本节我们将深入探讨决策树学习中的经典算法——ID3。ID3算法以信息增益为准则，通过自顶向下的贪心策略构建决策树，是理解决策树模型运作机制的关键。学完本节，你将能够手动计算信息增益，并理解如何利用它来选择最优特征进行数据划分。

💡 核心导读

• 信息增益的计算：掌握如何基于信息熵计算特征分裂带来的信息增益。
• ID3的贪心构建过程：理解算法如何递归地选择信息增益最大的特征来划分数据，直至满足停止条件。
• 决策树的几何解释：从空间划分的角度理解决策树，它相当于在特征空间中进行一系列垂直切割。
• 过拟合的直观体现：认识决策树生长过深（每个叶子节点只包含一个样本）所导致的过拟合现象。

信息增益与特征选择

决策树构建的核心在于，在每个节点上选择一个特征，使得按照该特征划分后，子节点的“纯度”最高，或者说“不确定性”降低得最多。在ID3算法中，我们使用信息熵（Entropy）来度量不确定性，使用信息增益（Information Gain）来度量不确定性降低的程度。

对于一个包含 $p$ 个正例和 $n$ 个负例的样本集合 $S$，其信息熵定义为： $$\text{Entropy}(S) = -p_{\oplus} \log_2 p_{\oplus} - p_{\ominus} \log_2 p_{\ominus}$$ 其中 $p_{\oplus} = p/(p+n)$, $p_{\ominus} = n/(p+n)$。当所有样本属于同一类时，熵为0；当正负样本各占一半时，熵达到最大值1。

假设我们根据特征 $A$ 将 $S$ 划分为 $v$ 个子集 $\lbrace S_1, S_2, ..., S_v\rbrace$，则划分后的加权平均熵为： $$\text{Entropy}_A(S) = \sum_{i=1}^{v} \frac{|S_i|}{|S|} \text{Entropy}(S_i)$$ 特征 $A$ 带来的信息增益即为原始熵与划分后加权平均熵的差值： $$\text{Gain}(S, A) = \text{Entropy}(S) - \text{Entropy}_A(S)$$ ID3算法在每一步都选择信息增益最大的特征进行分裂。

ID3算法实战：Play-Tennis示例

我们以经典的Play-Tennis数据集为例，手动演示ID3算法的构建过程。数据包含四个特征：Outlook, Temperature, Humidity, Wind，目标是根据天气情况预测是否打网球。

首先，我们计算整个数据集的初始熵。数据共有14条，其中9个正例（Yes），5个负例（No）。

import math

def entropy(probabilities):
    """计算信息熵。probabilities是一个概率列表，例如[0.9, 0.1]"""
    # 对指数输入进行保护（虽然此处log2不涉及exp，但保持函数稳健性）
    total = 0.0
    for p in probabilities:
        if 0 < p < 1:  # 当p为0或1时，p*log2(p)定义为0
            total -= p * math.log2(p)
    return total

# 初始数据集：9正5负
p_pos = 9/14
p_neg = 5/14
initial_entropy = entropy([p_pos, p_neg])
print(f"整个数据集S的初始熵 Entropy(S): {initial_entropy:.3f}")

整个数据集S的初始熵 Entropy(S): 0.940

接下来，我们计算每个特征的信息增益。以特征Wind为例，它有两个取值：Weak和Strong。我们需要计算按Wind划分后的加权平均熵。

import math

def entropy(probabilities):
    """计算信息熵。probabilities是一个概率列表，例如[0.9, 0.1]"""
    total = 0.0
    for p in probabilities:
        if 0 < p < 1:
            total -= p * math.log2(p)
    return total

# 初始数据集：9正5负
p_pos = 9/14
p_neg = 5/14
initial_entropy = entropy([p_pos, p_neg])

# 计算Wind特征的信息增益
# Wind = Weak: 6正2负 (共8条)
# Wind = Strong: 3正3负 (共6条)
total_samples = 14

weight_weak = 8 / total_samples
entropy_weak = entropy([6/8, 2/8])

weight_strong = 6 / total_samples
entropy_strong = entropy([3/6, 3/6])

avg_entropy_wind = weight_weak * entropy_weak + weight_strong * entropy_strong
gain_wind = initial_entropy - avg_entropy_wind

print(f"Wind特征分裂后的加权平均熵: {avg_entropy_wind:.3f}")
print(f"Wind特征的信息增益 Gain(S, Wind): {gain_wind:.3f}")

Wind特征分裂后的加权平均熵: 0.892
Wind特征的信息增益 Gain(S, Wind): 0.048

类似地，我们可以计算出所有特征的信息增益：

• Gain(S, Outlook) = 0.246
• Gain(S, Humidity) = 0.151
• Gain(S, Wind) = 0.048
• Gain(S, Temperature) = 0.029

Outlook的信息增益最大，因此被选为根节点进行分裂。Outlook有三个取值（Sunny, Overcast, Rain），因此根节点产生三个分支。

递归构建：同一套流程逐层往下

选择 Outlook 为根、分出三个分支之后，算法在每个分支上递归地”重头再来”。讲师逐支检查：

• Overcast 分支（第 3、7、12、13 条）：四条全是正例，熵为 0——立即成为标记 Yes 的叶子，不需要再延伸；
• Sunny 分支：剩 2 正 3 负，还不纯；
• Rain 分支：剩 3 正 2 负，也不纯。

对不纯的分支，把”算各特征信息增益 → 挑最大者分叉”这套流程在子集上完整重做一遍。讲师特别强调两条规则：

• 用过的特征不能再出现在同一路径上：Sunny 分支上不能再用 Outlook——该分支内所有样本的 Outlook 都是 Sunny，再按它分不会产生任何新的划分，候选特征只剩 Temperature、Humidity、Wind 三个。
• 不同分支之间可以各选各的：Sunny 分支和 Rain 分支各自选中的下一个特征可以相同也可以不同，互不影响。

延伸到什么时候停？当某个分支内的样本全部属于同一类（全 Yes 或全 No）时，它就长成叶子。（标准 ID3 的完整停止条件还包括：特征用尽时以多数类作为叶子的标签；实践中还会人为限制树的深度——这些到讲剪枝时再展开。）

这个”每个节点算一遍信息增益、挑最大特征分叉、子集递归”的算法就是 ID3——对离散特征分类非常简单直接的贪心算法。树看起来建得很复杂，其实每一步都在做同一件事：算信息增益。

决策树的本质与过拟合

从几何视角看，决策树是在特征空间中进行一系列轴平行（axis-parallel） 的划分。每个特征测试（例如“Wind = Weak?”）相当于在垂直于该特征轴的超平面上进行切割。对于连续特征，测试如“Temperature < 25”同样产生一个垂直于Temperature轴的切割面。

通过这种垂直切割，决策树将高维特征空间划分成若干个超矩形区域。每个叶子节点对应一个这样的区域，区域内的样本被赋予相同的类别标签。ID3算法的目标就是找到一系列切割，使得最终每个区域内的样本尽可能“纯”。

这种机制也直观地揭示了决策树容易过拟合的原因。如果我们不加限制地让树生长，最终可以使得每个训练样本都落入自己独有的小矩形中（即每个叶子节点只包含一个样本）。这相当于完美地记住了所有训练数据，但对于未见过的数据，由于其特征值组合可能落入未被定义的区域，或者落入只由个别异常样本定义的区域，模型的泛化性能会急剧下降。因此，控制树的复杂度（如剪枝、限制深度）是决策树实践中至关重要的一环。

📝 动手练一练

1. 概念辨析：在ID3算法的递归过程中，为什么在同一个分支路径上不能重复使用已经用过的特征（例如在根节点用了Outlook，在它的子节点就不能再用）？如果允许重复使用，可能会导致什么问题？

2. 动手计算：Outlook 为根之后，Rain 分支有 5 条数据（3 正 2 负）。已知在该分支内，Wind=Weak 的 3 条样本全为正例、Wind=Strong 的 2 条样本全为负例。请计算 Gain(Rain 分支, Wind)。

本章小结

本节我们详细剖析了ID3决策树算法。它以信息增益为特征选择标准，采用自顶向下的贪心策略递归构建树结构。算法的核心在于每一步都选择能最大程度降低数据不确定性的特征进行划分。我们从具体计算示例入手，理解了信息熵和信息增益的运用，并认识到决策树本质上是特征空间的轴平行划分。同时，我们也看到了决策树不加控制时容易导致过拟合的直观原因。

📋 行动清单

• 手动完成Play-Tennis示例中所有特征在根节点的信息增益计算，验证Outlook确实是最优选择。
• 尝试编写一个简化版的ID3算法函数，能够处理小型离散数据集，并输出构建的决策树结构（可以用字典嵌套表示）。
• 思考：如果某个特征有非常多的取值（例如给每条样本编一个”ID”号），按它分裂往往能算出很大的信息增益，但这真是好特征吗？（这是 ID3 偏好多取值特征的已知问题；下一节《决策树节点的划分》会介绍基尼指数等更多样的划分度量。）

—— 小象教研组