游戏皮肤推荐:用决策树判断玩家购买意向
P5939. 游戏皮肤推荐:用决策树判断玩家购买意向
场次:2026年10月21日-AI方向 · 来源:CodeFun2000 P5939
题目描述
一款 5v5 竞技手游每逢版本更新都会上新皮肤。商店推荐位如果不加区分地把所有皮肤推给所有玩家,玩家划得累,购买转化率也上不去。项目组的做法是:先从历史数据里攒一批"看过页面、最终买没买"的记录,用决策树把购买意向学出来,再把新玩家逐条喂进这棵树做预测。
购买意向只用三个布尔特征描述,编号为 0、1、2:
| 特征编号 | 含义 | 取值 |
|---|---|---|
| 0 | 是否 VIP 会员(含月卡) | 0 表示否,1 表示是 |
| 1 | 是否买过该英雄的皮肤 | 0 表示否,1 表示是 |
| 2 | 是否把该英雄打上过最高段位 | 0 表示否,1 表示是 |
训练样本的类别也只有两种:0 表示不购买(不推荐),1 表示购买(推荐)。
决策树的构建规则
熵
对只含两类的样本集 ,记类别 0、1 的样本占比为 、(),熵定义为
其中 的项按 处理。
条件熵与信息增益
用特征 把 分成 (取值为 0 的样本)与 (取值为 1 的样本),分裂后的条件熵是两棵子树熵按样本量加权平均:
特征 的信息增益,是分裂前后不确定性的减少量:
节点分裂
从根节点开始递归建树。在当前节点上,对尚未出现在从根到该节点的路径上的特征逐个计算信息增益,取增益最大的特征作为分裂特征;若几个特征的增益并列最大,取编号最小的那一个。然后按该特征的取值把节点内的样本分成两类:取值为 0 的进左子树,取值为 1 的进右子树。
某个特征一旦在某条路径上用过了,就不能在这条路径的下层节点上再用;但在另一条分支上它仍然可用。
终止条件
满足下列任意一条,当前节点就成为叶节点,不再分裂:
节点内所有样本的类别相同;
三个特征都已经在从根到该节点的路径上出现过;
所有尚未使用的特征,其信息增益都不大于 0。
条件 1 的叶节点,类别就是节点内样本的类别;条件 2、3 的叶节点按多数表决定类:节点内类别 1 的样本多于类别 0 就取 1,少于就取 0,两者数量相等时取 0。
预测
对一条待预测样本,从根节点出发,读出当前节点分裂特征的取值:0 走左子树,1 走右子树,直到落在叶节点,输出该叶节点的类别。
输入格式
第一行:两个整数 与 ,分别表示训练样本数与待预测样本数。
第 2 行到第 行:每行 4 个整数,前三个依次是编号 0、1、2 的特征取值,第四个是该样本的类别(0 或 1)。
第 行到第 行:每行 3 个整数,依次是编号 0、1、2 的特征取值。
例如下面这段输入描述 4 条训练样本与 4 条待预测样本:
4 4
1 1 1 1
1 1 0 0
1 1 1 0
0 0 0 0
1 1 1
1 1 0
1 0 1
0 0 1输出格式
共 行,每行一个整数 0 或 1,按输入顺序给出每条待预测样本的类别。不要输出多余的空格或空行。
数据范围
,
所有特征取值与类别均为 0 或 1
数据保证:在任何需要比较信息增益的节点上,并列最大的几个增益在数学上完全相等;非并列时,最大增益与次大增益之差不少于 。因此用双精度浮点按上述规则实现,不会因舍入误差选错特征。
时间限制:C/C++ ms,其他语言 ms。
内存限制:C/C++ MB,其他语言 MB。
示例
示例 1
输入:
5 5
1 0 1 1
1 1 0 1
0 0 1 0
0 1 1 1
1 0 0 0
1 0 1
1 1 0
0 0 1
0 1 1
1 0 0输出:
1
1
0
1
0说明: 训练集共 5 条,类别 0 有 2 条、类别 1 有 3 条,。三个特征的信息增益分别约为 、、,最大的是特征 1,根节点按特征 1 分裂。特征 1 取 0 的一侧有 3 条样本,类别为 1、0、0,此时特征 0 与特征 2 的增益并列(都约为 ),按规则取编号较小的特征 0;其中特征 0 取 1 的两条样本类别仍不同,再按特征 2 分开。特征 1 取 1 的一侧两条样本类别都是 1,直接成为叶节点。5 条待预测样本依次落到类别 1、1、0、1、0 的叶节点上。
示例 2
输入:
7 5
0 1 0 1
0 0 1 0
0 1 1 1
0 0 0 0
1 0 0 0
1 0 1 1
1 1 0 0
0 0 0
1 1 1
1 0 1
0 1 0
1 1 0输出:
0
0
1
1
0说明: 训练集共 7 条,类别 0 有 4 条、类别 1 有 3 条,。特征 0 的增益约为 ,特征 1 与特征 2 的增益并列最大(都约为 ),按规则取编号较小的特征 1 作为根节点。特征 1 取 1 的一侧有 3 条样本,类别为 1、1、0,特征 0 的增益约为 ,大于特征 2 的 ,按特征 0 分裂后两类完全分开。特征 1 取 0 的一侧有 4 条样本,类别为 0、0、0、1,特征 0 与特征 2 的增益并列(都约为 ),取特征 0;其取值 1 的两条样本再按特征 2 分开。5 条待预测样本依次落到类别 0、0、1、1、0 的叶节点上。
提示
| 要点 | 说明 |
|---|---|
| 并列取小 | 增益并列时一律取编号最小的特征,"并列"指数学上严格相等,不要用过大的容差把不并列的情形判成并列 |
| 特征按路径禁用 | 禁用范围是"从根到当前节点"这一条路径,不是整棵树;另一条分支上同一个特征仍可再分裂 |
| 增益为 0 | 特征在该节点上取值全同、或两侧类别分布相同时,信息增益为 0,不能作为分裂特征 |
| 表决并列 | 多数表决时两类样本数量相等,取类别 0 |
| 样本不会分空 | 只有增益大于 0 的特征才会被选中,选中的特征在节点内两种取值都出现过,因此左右子树都不会为空 |
解题思路
判分对象:"按规则长出来的那棵树"
题面没有给解题者留任何设计空间:选哪个特征、在哪些取值上开子树、什么时候停、叶子输出什么,全部写死。正确性等价于把规则原样复现,而规则里有四处一旦读漏就整棵树走样:
- "尚未使用的特征"是按路径算的。 同一条从根到叶的路上每个特征至多一次,换个分支可以重新用。所以递归得把"本路径已用集合"往下传,不能开一个全局
used一路add。 - 叶节点有两条成因(同类别 / 没有可用特征)再加一条"增益都不大于 0"。三条都要写,缺第三条会在两侧类别分布相同的节点上白分一次。
- 每个节点都得自带一份多数标签,它是条件 2、3 的叶子答案;平票取 0。
- 平局取编号最小,且"并列"必须是数学上的并列。
熵可以只算一遍,增益可以只比"右边那一项"
在同一个节点上, 对所有候选特征是同一个数,所以"增益最大"与"条件熵最小"完全等价。代码里仍然把父集熵只算一次(parent_h),每个候选只累加右边那一项,最后相减——这样写与公式一一对应,读代码时不必在脑子里换式子。
熵本身还能化简。把 代进去:
每个类别只做一次乘法,除法从"每类一次"降到"整体一次"。 时这一步省下的常数是有意义的:整棵树至多 7 次分裂,每次分裂至多 3 个候选特征,每次都要对节点内样本数一遍类别。
def entropy(cnt0, cnt1):
"""两类熵 H = -p0*log2 p0 - p1*log2 p1,p=0 的项按 0 处理。"""
total = cnt0 + cnt1
h = 0.0
if cnt0:
p = cnt0 / total
h -= p * log2(p)
if cnt1:
p = cnt1 / total
h -= p * log2(p)
return hif cnt0: 这两个判断不是防御性编程,而是公式里那句" 的项按 处理"的落地:Python 的 log2(0) 抛 ValueError: math domain error,不跳过就当场崩掉。
选分裂特征:升序遍历 + 严格更大
平局规则不需要单独的比较代码:候选特征按 升序遍历,只在新增益严格大于当前最优时才替换,并列时先到的小编号自然留在 best_gain 上。
每个候选的统计量只有 4 个数(取值 0/1 × 类别 0/1),一遍扫过节点内的样本就能填满:
parent_h = entropy(zeros, ones)
best_gain, best_f = -1.0, -1
for f in unused: # 升序遍历:并列时小编号先占位
counts = [[0, 0], [0, 0]] # counts[取值][类别]
for r in rows:
counts[r[f]][r[3]] += 1
cond = 0.0
for v in (0, 1):
n0, n1 = counts[v]
if n0 + n1: # 该取值没出现过就不参与加权
cond += (n0 + n1) / len(rows) * entropy(n0, n1)
gain = parent_h - cond
if gain > best_gain + EPS: # 只在严格更大时替换
best_gain, best_f = gain, f比较写成 gain > best_gain + EPS,EPS = 1e-9。数学上并列的两个增益由不同的分组权重加起来, 的舍入不保证抵消,裸 > 会把第 位的噪声读成"后者更大",小编号规则当场失效。题面保证非并列时差距 ,所以 这个容差不会把真正更大的增益挡掉。
递归建树:每分裂一次消耗一个特征
节点手里的两样东西是"落在它身上的样本"和"这条路径上还没用过的特征"。分裂时把选中特征从可用集合里剔掉再往下传,于是深度不超过 3——这就是递归一定会停下来的理由,而不是靠增益变小。
def build(rows, unused):
ones = 0
for r in rows:
ones += r[3]
zeros = len(rows) - ones
majority = 1 if ones > zeros else 0 # 平票取 0
if zeros == 0 or ones == 0 or not unused: # 纯节点,或特征已用尽
return (majority,)
# ... 选出 best_f、算出 best_gain ...
if best_gain <= EPS: # 剩余特征的增益都不大于 0
return (majority,)
rest = [f for f in unused if f != best_f]
left = [r for r in rows if r[best_f] == 0]
right = [r for r in rows if r[best_f] == 1]
return (majority, best_f, build(left, rest), build(right, rest))返回值的形状只有两种:(类别) 是叶节点,(多数类别, 分裂特征, 左子树, 右子树) 是内部节点。靠 len(node) 判断是哪一种,预测时可以顺着往下走,不需要额外的类型标记。
left / right 直接按取值过滤,不会出现空表:能走到这一行,说明 best_gain > 0,而增益为正的前提是该特征在节点内两种取值都出现过(只有一种取值时条件熵等于父集熵,增益恰好是 0)。
预测:两条路都是通的
def predict(node, sample):
while len(node) == 4:
_, f, left, right = node
node = left if sample[f] == 0 else right
return node[0]与一般决策树不同,这里不需要"取值没见过就退回本节点多数类"的兜底:特征只有 0/1 两种取值,而每个内部节点在两种取值上都建了子树,待预测样本读出一个 0 或 1 就一定走得下去。兜底是"叶子"自己承担的——三条终止条件保证了任何一条样本都停得下来。
完整代码实现
import sys
from math import log2
EPS = 1e-9 # 增益并列容差(题面保证非并列时最大与次大之差 >= 1e-3)
def entropy(cnt0, cnt1):
"""两类熵 H = -p0*log2 p0 - p1*log2 p1,p=0 的项按 0 处理。"""
total = cnt0 + cnt1
h = 0.0
if cnt0:
p = cnt0 / total
h -= p * log2(p)
if cnt1:
p = cnt1 / total
h -= p * log2(p)
return h
def build(rows, unused):
"""rows 为 [(特征0, 特征1, 特征2, 类别)],unused 为本路径上还没用过的特征(升序)。
节点表示:
(类别) 叶节点
(多数类别, 分裂特征, 左子树, 右子树) 内部节点
"""
ones = 0
for r in rows:
ones += r[3]
zeros = len(rows) - ones
majority = 1 if ones > zeros else 0 # 平票取 0
if zeros == 0 or ones == 0 or not unused: # 纯节点,或特征已用尽
return (majority,)
parent_h = entropy(zeros, ones)
best_gain, best_f = -1.0, -1
for f in unused: # 升序遍历:并列时小编号先占位
counts = [[0, 0], [0, 0]] # counts[取值][类别]
for r in rows:
counts[r[f]][r[3]] += 1
cond = 0.0
for v in (0, 1):
n0, n1 = counts[v]
if n0 + n1: # 该取值没出现过就不参与加权
cond += (n0 + n1) / len(rows) * entropy(n0, n1)
gain = parent_h - cond
if gain > best_gain + EPS: # 只在严格更大时替换
best_gain, best_f = gain, f
if best_gain <= EPS: # 剩余特征的增益都不大于 0
return (majority,)
rest = [f for f in unused if f != best_f]
left = [r for r in rows if r[best_f] == 0]
right = [r for r in rows if r[best_f] == 1]
return (majority, best_f, build(left, rest), build(right, rest))
def predict(node, sample):
"""沿分裂特征下降,落在叶节点就返回该叶的类别。"""
while len(node) == 4:
_, f, left, right = node
node = left if sample[f] == 0 else right
return node[0]
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
pos = 0
n = int(data[pos]); m = int(data[pos + 1]); pos += 2
rows = []
for _ in range(n):
rows.append((int(data[pos]), int(data[pos + 1]), int(data[pos + 2]),
int(data[pos + 3])))
pos += 4
tree = build(rows, [0, 1, 2])
out = []
for _ in range(m):
sample = (int(data[pos]), int(data[pos + 1]), int(data[pos + 2]))
pos += 3
out.append(str(predict(tree, sample)))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1:五条样本怎么长出那棵树
五条训练样本是
| 编号 | 特征 0 | 特征 1 | 特征 2 | 类别 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 | 1 |
| 5 | 1 | 0 | 0 | 0 |
类别计数:0 类 2 条、1 类 3 条,所以
根节点:三个候选特征的条件熵。
特征 0 按取值分组:取值 1 的三条标签是 (熵 ),取值 0 的两条是 (熵 )。条件熵 ,增益 。
特征 1 分组:取值 0 的三条标签是 (熵 ),取值 1 的两条是 (熵 )。条件熵 ,增益 。
特征 2 分组:取值 1 的三条标签是 ,取值 0 的两条是 ,两组的大小与熵都和特征 0 相同,条件熵同样是 ,增益 。
最大,根节点用特征 1。类别不纯、特征没用完、增益为正,三条终止条件都不满足。
第二层:特征 1 取 0 的那一侧。 留下样本 1、3、5,标签 ,。
| 候选特征 | 分组 | 条件熵 | 增益 |
|---|---|---|---|
| 0 | 取值 1:(熵 ,权重 );取值 0:(熵 ) | ||
| 2 | 取值 1:(熵 ,权重 );取值 0:(熵 ) |
两个增益并列,取编号较小的特征 0。
- 取值 0 的分支只剩样本 3,标签 ,成为叶节点
0; - 取值 1 的分支剩样本 1 与 5,标签 ,还有未用特征 2,增益 ,继续分裂:特征 2 取 1 的样本 1 → 叶
1,取 0 的样本 5 → 叶0。
第二层:特征 1 取 1 的那一侧。 只剩样本 2 与 4,标签都是 1,直接成为叶节点 1。
整棵树:
特征 1
├── 0 → 特征 0
│ ├── 0 → 叶:0
│ └── 1 → 特征 2
│ ├── 0 → 叶:0
│ └── 1 → 叶:1
└── 1 → 叶:1预测五条测试样本:
| 测试样本 | 特征 1 → 特征 0 → 特征 2 | 输出 |
|---|---|---|
| → → | 1 | |
| ,直接到叶 | 1 | |
| → ,直接到叶 | 0 | |
| ,直接到叶 | 1 | |
| → → | 0 |
输出 1 1 0 1 0,与题面一致。
示例 2:两次平局都取小编号
七条训练样本的类别分布是 0 类 4 条、1 类 3 条,。三个候选的增益是 、、:后两个并列,取编号较小的特征 1 作根。
两个分支里,一侧靠比较大小选,另一侧遇上一次平局:
- 特征 1 取 1 的一侧三条样本标签 ,特征 0 的增益 (取值 0 的两条全是 1、取值 1 的一条是 0,两侧都纯),特征 2 的增益 ,这里不是平局,选特征 0;
- 特征 1 取 0 的一侧四条样本标签 ,特征 0 与特征 2 的增益都是 ,按规则取特征 0。
预测路径与题面一致,输出 0 0 1 1 0。这两个样例合起来把"平局取小编号"的两个位置(根节点、第二层)都覆盖到了。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个候选特征先把节点样本切成子集列表,再各算一次熵 | 切片复制样本,每层都要重建列表 | ||
| 一次遍历按取值累计 计数(最优) | 只记计数,不复制样本;每层至多扫 遍样本,共 层 |
两行的渐进复杂度相同,因为"试遍所有未用特征"这件事无法回避:每个结点都要对每个候选扫一遍自己手里的样本。省下来的是子集复制与重复计数。
深度上限是 (每层消耗一个特征),所以"每层所有结点扫描量之和不超过 "这一条成立,总代价 。本题 ,结点数不超过 ,实际就是把训练集扫几遍。预测单条 , 条共 。
空间上样本表 是主要开销;递归栈深不超过 ,树本身每个结点只存一个多数标签、一个特征下标和两个孩子指针。
易错点总结
1. 已用特征随着兄弟分支一起被"吃掉"
把"这条路径上可用的特征"当成一个共享的 list、分裂时直接 unused.remove(best_f),父节点手里的 list 会被就地改掉,后建的兄弟分支拿到的是被缩过的版本。示例 2 就会露馅:根节点用特征 1 之后 unused 变成 [0, 2],左分支再 remove(0) 把它改成 [2],等右分支(标签 )建树时只剩特征 2 可用,样本 一路走到标签为 1 的叶子,输出变成 0 1 1 1 1,而正确是 0 0 1 1 0。
安全写法是每层新建一份:rest = [f for f in unused if f != best_f],unused 本身只读不写,兄弟分支各拿一份互不影响的副本。
2. 多数表决写成 1 if ones >= zeros else 0
题面写的是"两者数量相等时取 0",>= 把平票判给了 1。这条错的不是样例里看得见的地方——示例 1、2 的平票节点都还会继续分裂,它们的多数标签只作后备;但一旦某个平票节点因为"特征用尽"或"增益都为 0"成为叶子,答案就翻转。最小复现是
2 1
0 0 0 0
0 0 0 1
0 0 0两条训练样本特征全同、标签一 0 一 1,三个特征的增益都是 0,根节点直接成为叶子,应输出 0;写成 >= 输出 1。
3. 熵里不跳过计数为 0 的类别
把 entropy 写成 p = cnt0/total; h -= p*log2(p) 再接 p = cnt1/total; ...,只要有一个分组里没有样本,就会 total=0 先抛 ZeroDivisionError,或者 log2(0) 抛 ValueError: math domain error——两条路都是程序在 build 里异常退出、标准输出一行都没有。
这种空分组一定会出现:当前节点里只要有一个候选特征"取值全同"(比如上一条那个三条特征全相同的输入,或任何让某特征在子集里退化成常量的数据),它的另一半取值就是空组。所以熵函数里的两个 if cnt0: / if cnt1: 与加权循环里的 if n0 + n1: 都是公式那句" 的项按 处理"的实现,不是多余的判断。