ID3信息增益分裂准则

可视化演示

展示信息熵随分布变化、信息增益分裂计算，以及ID3决策树逐步构建过程。

信息熵度量

猜谜游戏刚开始，主持人只透露“是一种水果”，你脑中浮现香蕉、苹果、草莓、榴莲……十几个候选者，每个都差不多可能。这种“完全没头绪”的状态，就是数据科学的“懵”。为了把懵数字化，香农老爷子发明了一个量——信息熵。它回答一个问题：按当前的概率分布，平均还需要几个“是/否”问题才能确定答案。候选越多、分布越均匀，熵越大。

在打球数据集里，“出去打球”这个结果有 9 次 Yes、5 次 No，这就是一个二分类分布。我们把它当水果盘：14 个水果里 9 个写着 “去玩”，5 个写着 “不去”。从这个盘子里随机摸一个水果，想要猜中是哪种，平均需要多少“是/否”问题？答案就是熵。

代入打球数据：H(D) = −(9/14)·log₂(9/14) − (5/14)·log₂(5/14) ≈ 0.940。这意味着平均还要大约一个“是/否”问题才能确定答案。你平时的“懵”有了数字——0.940 bit。接下来所有决策树的分裂，都围绕“如何让这个数字快速归零”展开。

条件熵计算

猜谜当然不能干瞪眼。这时主持人允许你问第一个问题：“是热带水果吗？”你按答案把候选水果分成两堆：是的一堆，不是的一堆。现在“懵”被稀释了：你分别在两小堆里接着猜。这个“问完问题后，按回答分组，各组剩余懵度的加权平均”，就叫条件熵。

技术地说，条件熵 H(D|A) 表示在已知属性 A 的值之后，数据集 D 还剩余多少不确定性。计算分四步：先按 A 的每个取值把数据集切成子集，再算每个子集自己的熵，然后用子集大小占比作为权重，把所有子集熵加权平均。

用 Outlook（天气）举例：Sunny 有 2 玩 3 不去，Overcast 有 4 玩 0 不去，Rain 有 3 玩 2 不去。算下来 H(D|Outlook) ≈ 0.694，比原来的 0.940 少了一大截。问完“今天天气如何”，原本 0.940 bit 的懵度缩水到了 0.694 bit——这个问题确实有用。

信息增益推导

现在把两样东西放在一起：提问前的懵度是 0.940，问完 Outlook 后的剩余懵度是 0.694。那么“问天气”这一个操作，让懵度减少了多少？0.940 − 0.694 = 0.246。这个差值，就是信息增益。你完全可以把它理解为“这个问题的杀伤力”——一个能把可能范围狠狠缩小的好问题，杀伤力自然大。

同样的道理，把 Humidity、Wind、Temperature 也都过一遍，得到四张成绩单：Outlook 增益 0.246，Humidity 增益 0.152，Wind 增益 0.048，Temperature 增益 0.029。其中 Outlook 的杀伤力最大！ID3 的策略就是“谁得分最高选谁”——这就是贪心准则：每一步都在当下找一个收益最大的问题去问，不回头看、不做全局规划。就像猜谜高手总是先问“是不是热带水果”而不是“是不是火龙果”，因为前者能把候选砍掉一半还多。

ID3建树流程

有了选问题的裁判标准，剩下的就是机械地重复：问最狠的问题，把人群按回答分开，再在每一堆里继续问最狠的问题。这个“分而治之”的过程，就是ID3建树。树的根节点先装着全部 14 天数据，第一刀切在 Outlook 上，按 Sunny、Overcast、Rain 分成三个子节点。每个子节点如果还不纯，就再挑当前最狠的问题继续切，直到停下来。

具体流程可以写成伪代码：

这里有几个必须交代的细节。第一，初始化根节点：把整个数据集放在根上，像把所有水果倒进一个大果盘。第二，递归分裂：每次选增益最大的属性，把“果盘”切成几个小盘。第三，停止条件：当某个小盘子里所有样本都是同一类（纯节点），或所有属性都用完了，就不再切了。第四，叶子标记：叶子节点已无法再分，就统计该子集内多数标签作为最终答案。回到打球例子，Overcast 子集 4 条全 Yes，它就成为一片纯绿色叶子；Sunny 和 Rain 子集还是红绿混搭，要继续往深处长。最终生成一棵层层分支的树——树的每一条从根到叶的路径，就是一串“猜水果式”的问题链。

ID3(D, used):  1. 计算 D 的熵 H(D)  2. 对每个未使用属性 A: 计算 g(D,A)  3. 选增益最大的 A* 作为分裂属性  4. 按 A* 的每个取值划分 D 为若干子集  5. 对每个子集: 若纯或属性用完, 标记叶子(多数类)     否则递归调用 ID3

ID3局限剖析

猜谜游戏里最令人不齿的一招，是问“答案是草莓吗？”这问题看似精准，但只对草莓有效。ID3也有同款“作弊技巧”：如果有个属性叫“水果编号”，每个水果值都不一样，那么按它分裂后每个子集只剩一条数据，条件熵直接归零。

这个增益直接顶格达到最大值，ID3会毫不犹豫地选它。可是这样的树毫无预测价值——遇到一个新样本，你对不上任何历史“编号”，只能干瞪眼。这就是著名的多值偏好：ID3 偏爱取值特别多的属性，哪怕它只是在死记硬背。除此以外，ID3 还有三处硬伤。

第一，过拟合风险。树可以一路长到每个叶子只剩一条样本，训练误差为零，但换一批新数据立刻“见光死”，和背答案的学渣一模一样。第二，连续属性难题。像“气温 26.3℃”这样的连续数值，ID3 无法直接用作分裂条件，只能提前离散化，很麻烦。第三，缺失值处理。数据里某天“湿度未知”，ID3 既不会绕过也不会填补，直接罢工。这些缺点叠加在一起，让 ID3 在真实数据面前显得过于脆弱。

C4.5改进思路

既然“作弊问题”的根源在于取值太多，那就在评分时给题目加一个“难度系数”。C4.5 正是这样做的：它把信息增益除以一个惩罚项——分裂信息量。分裂信息量衡量的是属性取值本身的分布：取值越多、越均匀，这个惩罚就越大。就像老师批改试卷，一道选择题和一道 20 分的综合题要按每分平均的区分度来评价，而不是比总分。

除了增益率，C4.5 还补上了另外两块拼图：对连续属性采用“二分法”，把数据按阈值切成左右两支，比如把气温从“小于等于 26”和“大于 26”分隔开，并尝试多个阈值取增益最大者；对缺失值则引入加权统计，不再直接罢工；同时加入后剪枝，把太深的枝条砍掉，降低过拟合。至此，当年那个只会问“最狠问题”的莽撞少年 ID3，进化成了沉稳老练的 C4.5。而它的登场，也正式拉开了“决策树三兄弟”迭代的序幕——下一站，就是接替它的 CART 树。

AI 应用场景

Python 演示

import mathfrom collections import Counter FEATURES = ["Outlook", "Temperature", "Humidity", "Wind"] DATA = [    ["Sunny", "Hot", "High", "Weak", "No"],    ["Sunny", "Hot", "High", "Strong", "No"],    ["Overcast", "Hot", "High", "Weak", "Yes"],    ["Rain", "Mild", "High", "Weak", "Yes"],    ["Rain", "Cool", "Normal", "Weak", "Yes"],    ["Rain", "Cool", "Normal", "Strong", "No"],    ["Overcast", "Cool", "Normal", "Strong", "Yes"],    ["Sunny", "Mild", "High", "Weak", "No"],    ["Sunny", "Cool", "Normal", "Weak", "Yes"],    ["Rain", "Mild", "Normal", "Weak", "Yes"],    ["Sunny", "Mild", "Normal", "Strong", "Yes"],    ["Overcast", "Mild", "High", "Strong", "Yes"],    ["Overcast", "Hot", "Normal", "Weak", "Yes"],    ["Rain", "Mild", "High", "Strong", "No"],] def entropy(labels):    total = len(labels)    if total == 0:        return 0.0    counts = Counter(labels)    ent = 0.0    for c in counts.values():        p = c / total        ent -= p * math.log2(p)    return ent def conditional_entropy(data, feat_idx):    groups = {}    for row in data:        val = row[feat_idx]        groups.setdefault(val, []).append(row[-1])    total = len(data)    ce = 0.0    for subset in groups.values():        ce += len(subset) / total * entropy(subset)    return ce def info_gain(data, feat_idx):    labels = [row[-1] for row in data]    return entropy(labels) - conditional_entropy(data, feat_idx) def build_tree(data, used):    labels = [row[-1] for row in data]    if len(set(labels)) == 1 or len(used) == len(FEATURES):        return Counter(labels).most_common(1)[0][0]    cur_best, cur_gain = None, -1.0    for i, name in enumerate(FEATURES):        if i in used:            continue        g = info_gain(data, i)        if g > cur_gain:            cur_gain, cur_best = g, i    node = {"attr": FEATURES[cur_best], "children": {}}    for val in set(row[cur_best] for row in data):        subset = [row for row in data if row[cur_best] == val]        node["children"][val] = build_tree(subset, used.union([cur_best]))    return node def predict(tree, row):    while isinstance(tree, dict):        tree = tree["children"][row[FEATURES.index(tree["attr"])]]    return tree def show(node, depth=0):    if not isinstance(node, dict):        print("  " * depth + "-> " + node)        return    print("  " * depth + node["attr"] + "?")    for val, child in node["children"].items():        print("  " * depth + "  [" + val + "]")        show(child, depth + 2) if __name__ == "__main__":    tree = build_tree(DATA, set())    show(tree)    test_row = ["Sunny", "Cool", "High", "Strong"]    print("Predict", test_row, "->", predict(tree, test_row))

1. counts = Counter(labels)统计各类别的样本数量，为算概率做准备。
2. p = c / total把计数转成占比，这是熵公式里的 p_k。
3. ent -= p * math.log2(p)逐类累加「负 p log₂ p」，得到整份数据的熵。
4. ce += len(subset) / total * entropy(subset)按子集大小加权平均各组熵，正是条件熵的核心。
5. return entropy(labels) - conditional_entropy(data, feat_idx)初始熵减条件熵，得到信息增益。
6. if len(set(labels)) == 1 or len(used) == len(FEATURES):节点全纯或属性耗尽，就停止分裂并返回多数类。
7. node = {"attr": FEATURES[cur_best], "children": {}}用字典造树节点，记录本次分裂属性和子节点。
8. for val in set(row[cur_best] for row in data):枚举该属性的每个取值，递归长出分支。

常见误区

面试题