基于信息增益的决策树
P5946. 基于信息增益的决策树
场次:2026年10月28日-AI方向 · 来源:CodeFun2000 P5946
题目描述
信息熵表示数据集的不确定性:
数据集 中有 个类别, 为第 类的出现频率。
按特征 划分后,不确定性减少的量是信息增益:
其中 是 取值为 的样本子集。信息增益越大,越适合用该特征分裂。
请实现按信息增益建树的决策树分类器。每条训练样本形如
[feature_1, feature_2, ..., feature_m, label]特征与类别标签都用整数表示。特征从左到右的下标为 。
建树从根结点开始,规则如下:
- 若当前子集的标签全部相同,或没有尚未使用的特征,则该结点为叶子。叶子类别是子集中出现次数最多的标签;次数相同取较小的标签。
- 否则只在尚未使用的特征中选择信息增益最大的特征进行划分。信息增益相同则选择下标较小的特征。同一条从根到叶的路径上,每个特征至多使用一次。
- 只对当前子集里实际出现过的取值建立子结点,并在对应子集上递归。
预测时从根结点向下。若测试样本在当前特征上的取值没有出现在该结点的训练子集中,则输出该结点的多数标签(次数相同取较小标签)。
下列表格只帮助理解划分过程。真正的输入全部是整数,不需要把单词换成数字。
| Outlook | Wind | Play |
|---|---|---|
| Sunny | Weak | No |
| Sunny | Strong | No |
| Overcast | Weak | Yes |
| Rain | Weak | Yes |
| Rain | Strong | No |
得到的决策树为:
Outlook
├── Sunny → No
├── Overcast → Yes
└── Rain
├── Weak → Yes
└── Strong → NoOutlook 划分后的信息增益最大,所以放在根结点。
输入格式
第一行一个整数 ,表示特征数。
第二行一个整数 ,表示训练样本数。
接下来 行,每行 个整数,以空格分隔,依次是 个特征值和 个类别标签。
接下来一行一个整数 ,表示测试样本数。
接下来 行,每行 个整数,以空格分隔,表示一条测试样本的特征值。
输出格式
输出 行,每行一个整数,为对应测试样本的预测类别。
数据范围
- 特征值和类别标签均为整数
示例
示例 1
输入:
2
5
0 0 0
0 1 0
1 0 1
1 1 0
2 0 1
4
0 1
1 0
1 1
2 0输出:
0
1
0
1说明:
五条训练样本的标签为 。
按特征 划分:取值 的标签是 ,取值 的标签是 ,取值 的标签是 。加权熵为 。
按特征 划分:取值 的标签是 ,取值 的标签是 。前者熵约为 ,加权熵约为 。
父集熵相同,特征 的信息增益更大,根结点选用特征 。
- 特征 为 时标签全是 ,叶子预测 。样本 因此输出 。
- 特征 为 时标签是 ,叶子预测 。样本 输出 。
- 特征 为 时还剩样本 与 ,再用特征 :取值 预测 ,取值 预测 。样本 输出 ,样本 输出 。
示例 2
输入:
2
5
0 0 1
1 1 0
1 1 0
1 2 0
1 2 0
2
0 9
1 1输出:
1
0说明:
特征 与特征 都能把样本划成纯子集,条件熵都是 ,信息增益相同。应选择下标较小的特征 。
特征 为 的子集标签是 ,为 的子集标签全是 。样本 预测 ,样本 预测 。
若改选特征 ,样本 的取值 在训练集中没有出现,只能输出根结点的多数类 ,与正确类别 不同。
解题思路
判分对象是"按规则长出来的那棵树"
题面没有给解题者留设计空间:选哪个特征(未使用、增益最大、平局取小下标)、在哪些取值上开子结点、什么时候停、叶子输出什么,全部写死。正确性等价于把规则原样复现,而规则里有三处容易读漏:
- "尚未使用的特征"是按路径算的,不是全局的。同一条从根到叶的路上每个特征至多一次,换个分支可以重新用。这一点决定了递归得把"本路径已用集合"往下传,而不能开一个全局
used一路add。 - 叶子的两条终止条件是"标签全同"或"没有可用特征",没有第三条。题面没有"增益为 0 就不分裂"这种话——增益为 0 时照样按下标最小的可用特征分裂,靠"每分裂一次消耗一个特征"收敛。自己加上这条,特征全是常量而标签混杂的数据上,根结点会直接变成叶子,而题面要求它长成一条 层深的链。
- 结点得自带一份多数标签。它同时是叶子答案与预测时"取值没见过"的兜底,所以它必须随结点一起存下来(代码里
("split", 特征, 多数标签, 子结点表)的第三项)。
信息增益的比较只需算条件熵
在同一个结点上, 对所有候选特征是同一个数。于是"增益最大"与"条件熵最小"是同一件事,代码可以把父集熵只算一次(parent_h),每个候选只算右边那一项;比较时仍然相减,读起来和公式一致。
熵本身还有一处可以化简。把 代进去:
这样每个类别只做一次乘法,除法也从"每类一次"降到"整体一次"。样例 1 的父集 、计数 与 :,与 一致。
def entropy_of(counts, total):
"""H = log2(total) - (1/total) * Σ c*log2(c)。"""
mixed = 0.0
for c in counts.values():
mixed += c * log2(c)
return log2(total) - mixed / total
def majority(counts):
"""次数最多;并列取较小标签。"""
return min(counts, key=lambda label: (-counts[label], label))majority 用 (-次数, 标签) 当键交给 min,一次比较同时表达"人数多者胜"和"平票取小编号",等价于手写 if c > best_count or (c == best_count and label < best_label)。
选特征:升序遍历 + 严格更大
平局规则不需要单独的比较代码。候选特征按 升序遍历,只在新增益严格大于当前最优时才替换,并列时先到者(下标更小者)自然留在 best_feature 上。
parent_h = entropy_of(label_counts, total)
best_gain, best_feature = -1.0, -1
for f in unused: # 升序遍历
groups = {}
for r in rows:
groups.setdefault(r[f], []).append(r[m])
cond = 0.0
for labels in groups.values():
cond += len(labels) / total * entropy_of(Counter(labels), len(labels))
gain = parent_h - cond
if gain > best_gain + EPS: # 并列不替换 → 留下更小的下标
best_gain, best_feature = gain, f比较带了一个 EPS = 1e-12 的容差,原因在熵是 的和:数学上并列的两个候选会算成相差 量级,裸 > 会把"并列"读成"后者更大",小编号规则当场失效。
递归:每分裂一次就消耗一个特征
结点手里的两样东西是"落在它身上的样本"和"这条路径上还没用过的特征"。分裂时把选中特征从可用集合里剔掉再往下传,于是深度不超过 ——这就是递归一定会停下来的理由,而不是靠增益变小。
def build(rows, m, unused):
label_counts = Counter(r[m] for r in rows)
total = len(rows)
maj = majority(label_counts)
if len(label_counts) == 1 or not unused: # 两条终止条件
return ("leaf", maj)
# ... 选出 best_feature ...
rest = [f for f in unused if f != best_feature]
buckets = {}
for r in rows:
buckets.setdefault(r[best_feature], []).append(r)
children = {}
for value, sub in buckets.items(): # 只为出现过的取值建子结点
children[value] = build(sub, m, rest)
return ("split", best_feature, maj, children)buckets 的键只来自 rows 本身,所以"没出现过的取值不建子结点"是构造方式带来的,不需要额外判断。反过来,预测时一定会遇到训练子集里没有的取值,children 里查不到——这就是要兜底的地方。
预测:三种落点
def predict(node, sample):
while node[0] == "split":
_, feature, maj, children = node
nxt = children.get(sample[feature])
if nxt is None: # 该取值没在这个结点的训练子集里出现过
return maj # 退到"本结点的多数标签"
node = nxt
return node[1] # 走到叶子,输出叶子类别兜底用的是当前结点的多数标签,不是根结点的、也不是全局的。样例 2 的说明把这条讲得很清楚:若根结点错选特征 ,测试样本 的取值 从没出现过,只能退到根结点的多数类 ,与正确类别 相反。
完整代码实现
import sys
from collections import Counter
from math import log2
EPS = 1e-12 # 信息增益的并列容差:浮点差在 1e-16 级的候选视作并列
def entropy_of(counts, total):
"""H = log2(total) - (1/total) * Σ c*log2(c),每个类别只做一次乘法。"""
mixed = 0.0
for c in counts.values():
mixed += c * log2(c)
return log2(total) - mixed / total
def majority(counts):
"""出现次数最多的标签;次数相同取较小的标签。"""
best_label, best_count = None, -1
for label, c in counts.items():
if c > best_count or (c == best_count and label < best_label):
best_label, best_count = label, c
return best_label
def build(rows, m, unused):
"""在 rows 上建子树,unused 是这条路径上还没用过的特征(升序)。
结点表示:
("leaf", 标签)
("split", 特征下标, 本结点多数标签, {取值: 子树})
"""
label_counts = Counter(r[m] for r in rows)
total = len(rows)
maj = majority(label_counts)
# 叶子:标签已经全同,或这条路径上不再有可用特征
if len(label_counts) == 1 or not unused:
return ("leaf", maj)
parent_h = entropy_of(label_counts, total)
best_gain, best_feature = -1.0, -1
for f in unused: # 升序遍历,并列时先到者留下
groups = {}
for r in rows:
groups.setdefault(r[f], []).append(r[m])
cond = 0.0
for labels in groups.values():
cond += len(labels) / total * entropy_of(Counter(labels), len(labels))
gain = parent_h - cond
if gain > best_gain + EPS: # 只在严格更大时替换 → 平局取小下标
best_gain, best_feature = gain, f
rest = [f for f in unused if f != best_feature]
buckets = {}
for r in rows:
buckets.setdefault(r[best_feature], []).append(r)
children = {}
for value, sub in buckets.items(): # 只对出现过的取值建子结点
children[value] = build(sub, m, rest)
return ("split", best_feature, maj, children)
def predict(node, sample):
"""沿树下降;取值没在训练子集里出现过时返回本结点的多数标签。"""
while node[0] == "split":
_, feature, maj, children = node
nxt = children.get(sample[feature])
if nxt is None:
return maj
node = nxt
return node[1]
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
pos = 0
m = int(data[pos])
pos += 1
n = int(data[pos])
pos += 1
# 每条样本 m 个特征 + 1 个标签
rows = []
for _ in range(n):
rows.append(tuple(int(x) for x in data[pos:pos + m + 1]))
pos += m + 1
k = int(data[pos])
pos += 1
tree = build(rows, m, list(range(m)))
out = []
for _ in range(k):
sample = tuple(int(x) for x in data[pos:pos + m])
pos += m
out.append(str(predict(tree, sample)))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
样例 1:两个候选的增益分别是多少
五条样本是 、、、、,标签计数 类 条、 类 条:
特征 0 的取值分组与条件熵:
| 取值 | 成员标签 | 子集熵 | 权重 |
|---|---|---|---|
| 0 | 0 | ||
| 1 | 1 | ||
| 2 | 0 |
条件熵 ,增益 。
特征 1 的取值分组:
| 取值 | 成员标签 | 子集熵 | 权重 |
|---|---|---|---|
| 0 | |||
| 1 | 0 |
条件熵 ,增益 。
,根结点用特征 ,与题面说明一致。
第二层。取值 的分支只含标签 ,成叶子 ;取值 的分支只含 ,成叶子 ;取值 的分支还剩两条样本 与 ,标签不纯,可用特征只剩 ,条件熵 ,增益 ,于是用特征 再分一次,两个取值各得一个纯叶子。
特征 0
├── 0 → 叶:0
├── 1 → 特征 1
│ ├── 0 → 叶:1
│ └── 1 → 叶:0
└── 2 → 叶:1预测四条测试样本:
| 测试样本 | 根(特征 0) | 第二层(特征 1) | 输出 |
|---|---|---|---|
| 取值 0,走左 | — | 0 | |
| 取值 1 | 取值 0 | 1 | |
| 取值 1 | 取值 1 | 0 | |
| 取值 2,走右 | — | 1 |
输出 0 1 0 1。顺带看一条题面里没有的样本 :它走到第二层时取值 不在 里,按规则退到该结点的多数标签——两条训练样本一票对一票,取较小的 。
样例 2 说明的是平局:两个特征都把五条样本切成纯子集,条件熵同为精确的 ,增益相同,unused 的升序遍历让下标 的候选先坐上 best_gain,后面的候选不严格更大,于是根结点用特征 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个候选特征先切出子集列表、再逐块数类别 | 每层所有结点的样本总数是 ,每个结点最多试 个特征;切片复制带来额外常数 | ||
| 一次遍历按取值分组、直接累计标签计数(最优) | 不复制样本,只记计数;、 时约 次基本操作 |
两行的渐进复杂度相同,因为每个特征都得扫一遍自己结点的全部样本,"试遍所有候选"这件事无法回避;省下的是子集复制与重复计数。深度上限为 (每层消耗一个特征),所以"每层 、共 层"这一乘是对的。预测是 ,与建树相比可以忽略。空间上样本表 是主要开销,递归栈深 ,树本身每个结点只存一个字典。
易错点总结
1. "已用特征"写成了全局集合
used.add(best_feature) 之后不按路径回滚,兄弟分支就用不了已经被别的分支用掉的特征。样例 1 的两个分支各用一个特征,恰好测不出来;换成需要同一特征在两个分支复用的数据(例如四条的异或型样本),一侧分支会因为"无可用特征"提前变成叶子,该侧所有测试样本退回多数类,四条预测里两条翻转。
2. 结点没留多数标签,兜底无处可退
兜底要两样东西一起到位:建树时把每个结点的多数标签算好存进结点,预测时用 children.get(sample[feature]) 显式判断"这个取值没出现过"。只做后一半,get 拿到 None 却没有任何标签可返回;只做前一半、索引仍写成 children[sample[feature]],一旦落空就 KeyError,程序异常退出、整个文件一行输出都没有。样例里的测试样本恰好都走在见过的取值上(示例 2 的 只有在根结点错选特征 时才会落空),所以这条防线很容易被漏掉却测不出来。
3. 增益用裸浮点比较
if gain > best_gain: 在数学上并列的两个候选之间会看到 级的差(两侧条件熵由不同的分组权重加权得到, 的舍入不抵消),于是"并列取小下标"失效、树形随浮点误差漂移,部分测试样本的预测跟着翻转。样例 2 的两个候选条件熵都是精确的 ,测不出这个问题;gain > best_gain + EPS 才是稳的写法。