信息增益与决策树的构建

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

在上一节我们学习了信息熵的概念，它衡量了一个系统的不确定性。本节我们将利用信息熵，构建一个核心指标——信息增益，并以此为基础，阐述决策树模型如何通过一系列“提问”来对数据进行分类。学完本节，你将能够理解并手动计算信息增益，并掌握决策树选择最佳分割属性的核心思想。

💡 核心导读

• 信息增益的定义：理解信息增益是原始数据熵与分割后各子集加权熵的差值，它量化了通过一次分割所获得的“信息纯度”提升。
• 信息增益的计算：掌握如何具体计算一个属性分割前后的信息增益，包括计算原始熵、子集熵以及加权和。
• 决策树的分割准则：学习决策树在构建时，如何通过比较不同属性分割带来的信息增益大小，来选择当前最佳的“提问”。
• 从一维到多维：理解决策树的思想可以自然地扩展到多维特征空间，通过在不同维度上依次进行分割，构建出复杂的分类边界。
• 信息增益的直观理解：明确信息增益越大越好，因为它意味着分割后的子集更“纯净”，分类更明确。

信息增益：从熵的减少到信息的获得

在决策树学习中，我们的目标是将一个混合的数据集，通过一系列基于属性的判断，分割成尽可能“纯净”的子集。如何衡量一次分割的好坏呢？这就需要引入信息增益的概念。

信息增益衡量的是：当我们根据某个属性（例如“天气”）对数据集进行分割后，整个系统的不确定性（熵）减少了多少。这个减少的量，就是我们通过这次分割所获得的“信息”。

其计算公式如下：

对于一个属性 $A$，它将原始数据集 $S$ 分割成了 $v$ 个子集 $\lbrace S_1, S_2, ..., S_v\rbrace$，则属性 $A$ 的信息增益 $Gain(S, A)$ 为：

$$Gain(S, A) = Entropy(S) - \sum_{i=1}^{v} \frac{|S_i|}{|S|} Entropy(S_i)$$

其中：

• $Entropy(S)$ 是分割前原始数据集 $S$ 的熵。
• $|S_i|$ 是第 $i$ 个子集中样本的数量，$|S|$ 是总样本数。因此 $\frac{|S_i|}{|S|}$ 就是该子集的权重 $w_i$。
• $Entropy(S_i)$ 是第 $i$ 个子集的熵。
• $\sum_{i=1}^{v} w_i Entropy(S_i)$ 是分割后所有子集的加权平均熵。

直观理解：原始熵 $Entropy(S)$ 代表了分割前的不确定性。加权平均熵代表了分割后，各个子集内部不确定性的平均水平。信息增益就是不确定性减少的部分。增益越大，说明这次分割让数据变得越有序、越纯净。

信息增益计算示例

让我们通过一个具体的例子来巩固这个概念。假设我们有一个一维数据集，包含10个点，用颜色（红/绿）标记类别。我们考虑三种不同的分割线（A, B, C）将其分成左右两部分。

为了简化，我们直接使用上一节计算过的结果：

• 原始数据集 $S$ 的熵 $Entropy(S) = 1$（因为红绿各5个，完全不确定）。
• 对于分割线A：左边（A1）有3个点，全是红色，$Entropy(A1) = 0$；右边（A2）有7个点（2红5绿），其熵需要计算。

首先计算 $Entropy(A2)$。A2中有2个红色，5个绿色，共7个点。

• $P(红) = 2/7$
• $P(绿) = 5/7$
• $Entropy(A2) = -[\frac{2}{7} \log_2(\frac{2}{7}) + \frac{5}{7} \log_2(\frac{5}{7})]$

我们可以用一小段代码来精确计算这个值，并最终得到信息增益 $Gain(S, A)$。

import math

def entropy(probabilities):
    """计算熵，输入为概率列表"""
    return -sum(p * math.log2(p) for p in probabilities if p > 0)

# 计算原始熵 (5红5绿)
entropy_S = entropy([0.5, 0.5])
print(f"原始数据集熵 Entropy(S): {entropy_S:.4f}")

# 计算子集A2的熵 (2红5绿)
p_red_A2 = 2/7
p_green_A2 = 5/7
entropy_A2 = entropy([p_red_A2, p_green_A2])
print(f"子集A2的熵 Entropy(A2): {entropy_A2:.4f}")

# 计算信息增益 Gain(S, A)
# A1权重 w1 = 3/10, A2权重 w2 = 7/10
w1 = 3/10
w2 = 7/10
# 注意：Entropy(A1) = 0
gain_A = entropy_S - (w1 * 0 + w2 * entropy_A2)
print(f"基于分割线A的信息增益 Gain(S, A): {gain_A:.4f}")

原始数据集熵 Entropy(S): 1.0000
子集A2的熵 Entropy(A2): 0.8631
基于分割线A的信息增益 Gain(S, A): 0.3958

计算表明，使用分割线A，我们获得了约0.396的信息增益。按照同样的方法，我们可以计算分割线B和C的信息增益 $Gain(S, B)$ 和 $Gain(S, C)$。

决策树的选择策略：在构建决策树时，我们会在当前节点所有可用的属性（或分割点）中，选择那个能带来最大信息增益的属性进行分割。因为这意味着这次分割能最有效地降低系统的不确定性，让数据朝着更纯净的方向发展。

按同样的方法可以计算分割线 B（左 6 右 4）和 C 的信息增益。讲师凭直觉给出了他的预判：$IG_A > IG_C > IG_B$，但特别声明”这个我具体没算过，只是凭对这些数的直觉，有可能写错——大家可以去验证一下”。这是个现成的练习：把 A、B、C 三条线的信息增益都算出来，看看排序是否如他所料。

从一维分割到多维决策树

上面的例子是在一维空间（一条线上）找分割点。现实中的数据往往是多维的。决策树的强大之处在于它能自然地处理多维特征。

考虑一个二维分类问题，数据点散落在平面上，有红色和绿色两类。我们无法用一条平行于x轴或y轴的直线完美分开它们。

决策树的思路是进行序列的、轴平行的分割：

1. 首先，我们可能在x轴上找到一个最佳分割点 $x_0$，将平面分成左右两部分。
2. 然后，在左边的区域，我们可能发现数据仍然混合，于是再在y轴上找一个分割点 $y_0$，将该区域进一步细分。
3. 在右边的区域，可能也需要在y轴上找另一个分割点 $y_1$ 进行分割。

通过这样一系列“如果 $x < x_0$ 且 $y < y_0$，则为红类”的规则，我们最终将二维平面划分成了多个矩形区域（在更高维是超矩形）。每个矩形区域对应决策树的一个叶节点，并赋予一个类别标签。

扩展到高维：对于三维或更高维的数据，决策树构建的“盒子”就是高维超立方体。决策树的学习过程，就是自动地、贪婪地（每一步选择当前最优）寻找一系列这样的分割超平面（总是平行于坐标轴），将特征空间划分为不同的区域，使得每个区域内的样本尽可能属于同一类别。

熵函数的形状回顾

在结束本节前，我们回顾一下熵函数的典型形状，这有助于理解信息增益的动机。对于最简单的二分类问题（类别为1和2），熵 $H(p) = -p \log_2(p) - (1-p) \log_2(1-p)$，其中 $p$ 是类别1的概率。

• 当 $p = 0.5$ 时（两类样本数量相等），不确定性最大，熵 $H = 1$。
• 当 $p = 0$ 或 $p = 1$ 时（所有样本属于同一类），不确定性最小，熵 $H = 0$。 熵函数是一个在 $p=0.5$ 处取得最大值的凹函数（concave，开口向下）。

决策树的目标，正是通过不断分割，使得每个子节点中样本的类别分布尽可能偏向 $p=0$ 或 $p=1$，即让每个子节点的熵尽可能小。信息增益直接衡量了我们向这个目标前进的“步长”有多大。

📝 动手练一练

1. 概念辨析：假设我们有一个数据集，根据属性“温度”分割成“高”、“中”、“低”三个子集后，计算得到信息增益为0.2。根据属性“湿度”分割成“高”、“低”两个子集后，信息增益为0.15。如果只能根据一个属性来构建决策树的根节点，应该选择哪个属性？为什么？

2. 动手计算：假设一个二分类数据集S有8个样本，其中5个正例，3个反例。现有一个属性A，它将S分割为两个子集S1（4个样本，全为正例）和S2（4个样本，1个正例，3个反例）。请手动计算属性A的信息增益 $Gain(S, A)$。（可使用计算器，$\log_2(3) \approx 1.585, \log_2(0.75) \approx -0.415$）

本章小结

本节我们深入探讨了决策树构建的核心机制——信息增益。信息增益将信息熵从一个静态的“不确定性”度量，转变为一个动态的“分割效果”评估工具。通过计算和比较不同属性分割带来的信息增益，决策树算法能够以贪婪、递归的方式，构建出一个层次化的“提问-回答”模型，从而解决复杂的分类问题。

📋 行动清单

• 理解公式：确保能独立写出信息增益 $Gain(S, A) = Entropy(S) - \sum w_i Entropy(S_i)$ 并说明每一项的含义。
• 手动计算：针对一个简单的3-5个样本的二分类例子，自己设计一个属性分割，并完整计算其信息增益。
• 思考延伸：信息增益总是越大越好吗？是否存在某种情况下，单纯追求最大信息增益会带来问题？（这将引出了我们后续要讨论的“过拟合”和“剪枝”概念）。

—— 小象教研组