信息熵：决策树构建的度量基础

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

上一节我们重点介绍了朴素贝叶斯分类器。本节课，我们将开启另一个在机器学习历史上具有里程碑意义的算法——决策树（Decision Tree）的学习。决策树以直观的树状结构和强大的解释性著称。但在深入其构建算法之前，我们必须先掌握一个核心的数学工具：信息熵（Entropy）。信息熵源自信息论，为我们量化数据的”混乱”或”不纯度”提供了精确的标尺，是决策树挑选最优分裂依据的出发点。

💡 核心导读

• 从决策树到信息度量：理解决策树如何像”筛子”一样筛选数据，并引出对节点”纯净度”进行度量的需求。
• 信息论的基石：学习香农（Claude Shannon）如何从直觉出发，定义信息量函数，并推导出信息熵的数学形式。
• 熵的物理与信息学内涵：探讨熵在热力学（系统无序度）与信息论（平均信息量）中的统一思想。
• 熵的计算与性质：掌握离散随机变量信息熵的计算方法，并通过实例理解熵如何衡量数据集的混合程度。
• 熵与分割的关系：看分割数据的目标为什么是”让每一块更纯”，以及为什么需要在类别交界处寻找切分点——正式的评分工具”信息增益”下一节登场。

决策树：直观的分类”筛子”

在汤姆·米切尔（Tom Mitchell）的经典教材《机器学习》中，有一个著名的”是否打网球”例子：一共 14 天的记录，每天有天气（Outlook）、温度、湿度、风力（Wind）四个特征，以及最终是否去打网球（Yes/No）的标签。

决策树的目标，就是根据这些特征构建一个树状模型来做预测。树由节点（node）和分支（branch）构成：

• 根节点（root）：树的起点，对应第一个用于判断的特征（如 Outlook）。Outlook 可取 Sunny、Overcast、Rain 三种值，于是产生三个分支。
• 内部节点：对应后续特征，按取值继续分叉。
• 叶节点（leaf）：不再分叉的终点，给出最终判断（Yes 或 No）。

拿第 10 条数据走一遍这棵树：它的第一个特征 Outlook = Rain，于是沿 Rain 分支下行；遇到下一个节点是关于 Wind 的判断，它的 Wind = Weak，再沿 Weak 分支下行——最终落到标着 Yes 的叶子上，预测”会去打网球”，与真实标签一致。

讲师给了一个形象的比喻：整棵树就像一个大筛子，数据从顶部的”口”扔进去，每经过一个节点就被判断”往左走还是往右走”，像流经一根根管道，最后落进一个个带标签的小篮子（basket）。我们最希望的结果是：每个篮子里的数据都尽量是同一类（homogeneous）——该打网球的都落进 Yes 篮，不该去的都落进 No 篮。换句话说，构建决策树的过程，就是不断降低节点”不纯度”（impurity）、提高”纯净度”的过程。这就引出了一个问题：“不纯”到底怎么量化？ 信息熵，正是这把尺子。

信息论基础：从直觉到数学定义

信息论由克劳德·香农（Claude Shannon）创立。他最初研究的是通信信道：一串符号（比如 0110）作为输入进入信道，输出仍是符号——今天的电话、电视、互联网，都建立在这套理论之上。

香农面对的第一个问题是：如何度量一段信息 $X$ 所包含的”信息量” $h(X)$？ 他的做法很符合我们做数学建模的思路：先把人类的直觉提炼成几条性质，再找出同时满足它们的函数。他给信息量函数设定了三个合理的基本性质：

1. 与概率反向关联：事件发生的概率 $P(X)$ 越大，它发生所带来的信息量应该越小。讲师的例子：你妈打电话提醒”天冷了，穿秋裤”，这是高频事件，信息量很小；老师打电话说你得了一个重要奖学金、要推荐你出国，这是低频事件，信息量大得多。所以 $h(X)$ 应随 $P(X)$ 增大而减小——注意是单调的反向关联，不必是严格成正比于 $1/P(X)$（比如”正比于 $-P(X)$“就不行，后面会看到它违反第三条）。
2. 独立事件可加：两个独立事件 $X_1$、$X_2$ 同时发生带来的总信息量，应等于各自信息量之和：$h(X_1, X_2) = h(X_1) + h(X_2)$。刚才那两个电话就近似如此——知道”穿秋裤”和知道”得奖学金”两件事的信息量，应当相加。
3. 非负性：接到一个电话，你顶多觉得”没什么信息”，绝不会觉得信息倒流回对方那里去，所以 $h(X) \ge 0$。

什么函数能同时满足？对数函数。香农把事件 $X$ 的信息量（自信息）定义为：

$$h(X) = -\log_2 P(X)$$

以 2 为底时，信息量的单位是比特（bit）。逐条验证：$P(X)$ 越大，$\log_2 P(X)$ 越接近 0，$h(X)$ 越小——满足第一条；$\log_2 \frac{1}{P(X_1)P(X_2)} = \log_2 \frac{1}{P(X_1)} + \log_2 \frac{1}{P(X_2)}$（独立事件概率相乘、对数相加）——满足第二条；概率 $P(X)$ 不超过 1 时 $-\log_2 P(X) \ge 0$——满足第三条。而”正比于 $-P(X)$“的构造，会让 $h$ 变成负数，正是被第三条排除的。

从信息量到信息熵

信息量 $h(X)$ 度量的是单个具体事件带来的惊喜程度；机器学习里更关心随机变量 $X$ 整体的平均不确定性。把信息量对分布取数学期望，就得到信息熵（Information Entropy）：

$$H(X) = \mathbb{E}[h(X)] = -\sum_{x} P(x) \log_2 P(x)$$

对离散变量是求和；若是连续变量，则把求和换成积分。

熵的两种视角：

• 物理学视角（热力学熵）：熵度量系统的无序程度。热力学第二定律说，孤立系统的熵总是趋于增大——就像罐子里被挡板隔开的热空气与冷空气，一旦抽掉挡板，快分子与慢分子很快中和成”温吞”的均匀状态，从有序走向无序。薛定谔在《生命是什么》里进一步提出：生命体之所以能维持高度有序，是因为不断摄入”负熵”（minus entropy）——我们吃的食物本身就是高度有序的状态，吸收负熵、排出无序，才对抗了熵增。
• 信息学视角（信息熵）：熵度量随机变量的平均不确定性。分布越”平”，熵越大，每次观测的平均信息量也越大。

信息熵的计算与性质

回到红叉与绿圈两类数据的混合。设红色占 $P(X_1)$、绿色占 $P(X_2)$，直接套公式。动手算几组：

import math

def entropy(probabilities):
    """计算离散概率分布的信息熵（以2为底）"""
    h = 0.0
    for p in probabilities:
        if p > 0:  # 概率为0的项约定为0，因为 lim(p->0) p*log(p) = 0
            h -= p * math.log2(p)
    return h

print("例1 - 完全混合 [0.5, 0.5]:")
h1 = entropy([0.5, 0.5])
print(f"   熵 H = {h1:.4f} bits")
print()
print("例2 - 完全纯净 [1.0, 0.0]:")
h2 = entropy([1.0, 0.0])
print(f"   熵 H = {h2:.4f} bits")
print()
print("例3 - 不均匀混合 [0.4, 0.6]（4 叉 6 圈）:")
h3 = entropy([0.4, 0.6])
print(f"   熵 H = {h3:.4f} bits")
print()
k = 2
print(f"验证熵的范围 (0 <= H <= log2({k}) = {math.log2(k):.4f})")

运行输出：

例1 - 完全混合 [0.5, 0.5]:
   熵 H = 1.0000 bits

例2 - 完全纯净 [1.0, 0.0]:
   熵 H = 0.0000 bits

例3 - 不均匀混合 [0.4, 0.6]（4 叉 6 圈）:
   熵 H = 0.9710 bits

验证熵的范围 (0 <= H <= log2(2) = 1.0000)

手算例 1 也能对上：$H = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{2}\log_2\frac{1}{2} = \frac{1}{2} + \frac{1}{2} = 1$。例 2 里”纯为一种”的情形，靠的是 $p=0$ 时约定 $p\log p$ 一项为 0、$p=1$ 时 $\log 1 = 0$，两部分都消失，熵为 0。由此得到熵的关键性质：

• 最大值：两类各占一半（最混乱）时熵最大，两类情形恰为 1 比特；一般 $k$ 类时最大值为 $\log_2 k$。
• 最小值：数据完全属于一类（最纯净）时熵为 0。
• 越偏越低：分布偏离均匀越远，熵越小。

分割怎么比好坏：用熵给切分点打分

有了熵，就可以回答”怎么分割数据”的问题了。把数据按某一维特征的取值从左到右排开，红绿混杂；我们想画分割线把它们切开，让每一块尽量只含一类。

第一种画法：切一刀后左块全红、右块是 4 个红 1 个绿的混合；第二种画法：左块全绿，右块 6 个红 1 个绿。直觉上第二种更好——右块”更偏”，混得更不均匀。这可以用熵精确地算出来：

import math

def entropy(probs):
    """二类混合的信息熵（比特）"""
    h = 0.0
    for p in probs:
        if p > 0:
            h -= p * math.log2(p)
    return h

# 三种候选分割后"混合块"的熵（讲师课上的划线示例）
print(f"切法一右块 4 叉 1 圈  ->  H(1/5, 4/5) = {entropy([1/5, 4/5]):.4f} bits")
print(f"切法二右块 6 叉 1 圈  ->  H(1/7, 6/7) = {entropy([1/7, 6/7]):.4f} bits")
print(f"切法三右块 5 叉 2 圈  ->  H(2/7, 5/7) = {entropy([2/7, 5/7]):.4f} bits")

运行输出：

切法一右块 4 叉 1 圈  ->  H(1/5, 4/5) = 0.7219 bits
切法二右块 6 叉 1 圈  ->  H(1/7, 6/7) = 0.5917 bits
切法三右块 5 叉 2 圈  ->  H(2/7, 5/7) = 0.8631 bits

三种混合块里，6 叉 1 圈最”偏”，熵最低（0.5917），确实印证了直觉。所以分割的目标很明确：让分出来的每一块整体上熵最小。

还有一个关键观察：候选的分割线不必逐个穷举。把数据排开后，分割线只可能画在不同类别数据的交界处——中间同类数据再多，把线画在它们中间只会让两边都变混，没有任何好处。这正是澳大利亚科学家、ID3 算法的提出者罗斯·昆兰（Ross Quinlan）给出的简化原则：只在类别发生切换的位置考虑切分点。

比如 10 个数据（5 红 5 绿）排成一列，原始终度按例 1 是 1 比特；只在类别交界处有三个候选位置 A、B、C。以切法 A 为例：左块 3 个全红，熵为 0；右块 7 个数据（2 红 5 绿），按上表第三行它的熵约是 0.8631 比特。两块各自的熵都算出来了——但一个分割产生两块，怎么把两块的熵汇总成一个可以横向比较的分数，再在 A、B、C 之间选出最优？这个汇总工具叫信息增益（Information Gain），正是下一节的主角。

📝 动手练一练

练习 1（概念辨析）：三分类数据的分布为 $[0.8, 0.1, 0.1]$，它的信息熵更接近 0，还是更接近最大值 $\log_2 3 \approx 1.585$？这对应数据集的纯净度高还是低？

练习 2（动手改代码）：修改示例一的 entropy 函数调用，分别计算 1 叉 9 圈（$[0.1, 0.9]$）与 4 叉 6 圈（$[0.4, 0.6]$）的熵，比较两者并总结规律。

本章小结

• 决策树像”筛子”：数据经过一个个特征节点流进带标签的”篮子”，目标是让每个篮子里的数据尽量同质（homogeneous）。
• 从三条直觉性质（概率反向关联、独立可加、非负）出发，信息量函数唯一地落到 $h(X) = -\log_2 P(X)$。
• 信息熵是信息量的期望：$H(X) = -\sum P(x)\log_2 P(x)$；两类对半开时最大（1 比特），完全纯净时为 0，分布越偏熵越低。
• 熵同时是物理学的”无序度”（热力学第二定律、薛定谔的”负熵”）与信息论的”平均不确定性”。
• 分割数据时，切分点只需在类别交界处考虑（Quinlan 的简化原则）；分割的目标是让各块整体熵最小——把各块熵汇总成可比分数的”信息增益”，下一节正式登场。

📋 行动清单

• 用示例一的 entropy 函数手算并验证 $H(0.2, 0.8)$ 与 $H(1/3, 2/3)$，体感”分布越偏熵越低”
• 把 10 个红绿数据自排一列，找出所有”类别交界”候选切分点，确认同类内部的切分点都可以直接排除
• 预习思考：一个分割切出两块、熵分别为 0 和 0.8631，两块大小是 3 比 7——你会怎么把它们合成一个”总分”？

—— 小象教研组