解题思路

核心思路

本题要建的是一棵按增益率分裂的决策树（C4.5 风格），不是单层划分。

决策树从根结点递归向下：每个结点看当前样本集 $S$，在本条路径上还没用过的指标里选出一个划分，把 $S$ 分到若干子结点，直到触发停止条件，该结点变成叶子。叶子标记取出现次数最多的 $y$，次数相同则标 $0$。待判样本从根走到叶，沿途记下选用的指标编号，就是输出里的路径。

和 ID3 只比较信息增益不同，这里用增益率选指标。信息熵、信息增益、分裂信息分别为

题目内容

某模型平台的样本管理服务归档了一批已标注记录。服务用这批记录做分层划分，再对每条待判记录输出标记和判定路径。

每条记录含 $m$ 项指标以及标记 $y\in\{0,1\}$，指标按输入列顺序编号为 $1\sim m$，类型为连续（$0$）或离散（$1$）。

一、划分起点

划分从根结点开始，根结点深度为 $0$。同一条路径上已经用过的指标不再使用。

二、熵与信息增益

设当前结点样本集为 $S$，$|S|=n_S$，$p_c$ 为标记 $c$ 在 $S$ 中的占比。

• $H(S)=-\sum_c p_c\log_2 p_c$
• $IG(S)=H(S)-\sum_v\frac{|S_v|}{n_S}H(S_v)$
• $IV(S)=-\sum_v\frac{|S_v|}{n_S}\log_2\frac{|S_v|}{n_S}$
• $GR(S)=IG(S)/IV(S)$

$n_S=0$ 时 $H(S)=0$，某类计数为 $0$ 时该项按 $0$ 计、不取对数；$IV(S)$ 与 $0$ 的差的绝对值小于 $10^{-9}$ 时视为 $IV(S)=0$，此时 $GR(S)=0$。

三、可用的划分方式

离散指标按当前结点该指标实际出现的取值分成多支；只有一种取值时该指标不可用。

连续指标把当前结点该指标的取值去重后升序排列为 $u_1<\cdots<u_k$。

• 候选切分点 $t=(u_i+u_{i+1})/2$（$i=1,\ldots,k-1$）
• 取值 $\le t$ 的样本进左侧，$>t$ 的进右侧，某一侧为空则丢弃该 $t$
• 在合法切分点中取 $IG$ 最大的 $t$，$IG$ 相等时取更小的 $t$
• 该指标的 $IG$、$GR$ 按此 $t$ 计算
• $k=1$ 时该指标不可用

四、实数比较

计算得到的两个实数 $a,b$ 满足 $|a-b|<10^{-9}$ 时视为相等，否则按大小比较；该容差也用于 $IG$ 与 $\tau$ 的比较。

五、选择指标

在可用且能合法划分的指标中取 $GR$ 最大者，$GR$ 相等取 $IG$ 最大者，仍相等取编号最小者。

六、停止与叶子

当前结点满足下列任一条时成为叶子：

• 深度已达 $D$
• $n_S<L$
• 标记全部相同
• 没有可用且能合法划分的指标
• 按选择指标规则选出的指标，其 $IG$ 不大于 $\tau$

叶子不再划分。叶子标记取出现次数最多的 $y$，次数相同标 $0$。

七、查询判定

判定从根结点开始，当前结点为叶子时取其标记。

离散指标：待判取值命中对应分支则进入该分支；否则进入该结点下训练样本数最多的分支，样本数相同则进入取值更小的分支。

连续指标：待判取值 $\le t$ 进入左侧分支，否则进入右侧分支。

输入描述

第一行五个数 $n,m,D,L,\tau$，依次为归档记录条数、指标数、深度上限、样本数下限、增益门槛。

第二行 $m$ 个整数 $k_1,\ldots,k_m$，其中 $k_i$ 为第 $i$ 项指标的类型，$0$ 表示连续，$1$ 表示离散。

随后 $n$ 行记录，每行 $m+1$ 个整数 $y,a_1,\ldots,a_m$，其中 $y$ 为标记，$a_i$ 为第 $i$ 项指标取值。

接下来一行整数 $q$。

随后 $q$ 行待判记录，每行 $m+1$ 个整数 $id,a_1,\ldots,a_m$，$id$ 为待判编号，不含 $y$。

约束

$2\le n\le 80$

$1\le m\le 8$

$0\le D\le 6$

$1\le L\le n$

$0\le \tau\le 1$，$\tau$ 至多 $6$ 位小数

$1\le q\le 40$

$k_i\in\{0,1\}$

$y\in\{0,1\}$

指标取值 $a_i$ 为整数，绝对值不超过 $1000$

待判编号 $id$ 为整数，绝对值不超过 $10^6$，且 $q$ 条内互不相同

输出描述

输出 $q$ 行，每行为一条待判记录的结果。每行三个字段，依次为待判编号、标记、路径，以单个空格分隔。路径为判定途中依次选用的指标编号，用 > 连接；未经过任何划分时路径为 -。

样例1

输入

6 3 3 1 0.01
1 1 0
0 1 2 10
0 1 2 12
0 2 2 31
1 1 1 40
0 2 1 50
1 2 1 60
4
1 1 2 10
2 1 1 40
3 2 1 50
4 1 3 45

输出

1 0 2
2 1 2>1
3 0 2>1>3
4 1 2>1

说明

指标 $1$、$2$ 为离散，指标 $3$ 为连续。

根结点有 $6$ 条记录，$4$ 条标记 $0$、$2$ 条标记 $1$，$H=0.918296$。

指标 $2$ 分成两支：取值 $2$ 的 $3$ 条全为标记 $0$；取值 $1$ 的 $3$ 条为两个标记 $1$、一个标记 $0$，$IG=GR=0.459148$。

指标 $3$ 在切分点 $35.5$ 处得到与指标 $2$ 相同的两支，$IG$、$GR$ 也相等；切分点 $11$、$21.5$、$45$、$55$ 的 $IG$ 都更小。

指标 $1$ 两支的标记分布相同，$IG=0$。

按 $GR$、$IG$、编号依次比较，根结点选用指标 $2$。$0.459148>0.01$，继续划分。

取值 $2$ 的一支标记全相同，成为叶子，标记 $0$。

取值 $1$ 的一支有 $3$ 条记录，$H=0.918296$。指标 $1$ 分成一支（$1$ 条，标记 $1$）与另一支（$2$ 条，标记 $0$、$1$），$IG=0.251629$，$GR=0.274018$。指标 $3$ 的切分点 $45$ 与 $55$ 的 $IG$ 相等，取更小的 $45$，分组与指标 $1$ 相同。按编号选用指标 $1$。

路径 $2>1$ 下取值 $1$ 的一支成为叶子，标记 $1$；取值 $2$ 的两条记录再按指标 $3$、切分点 $55$ 分成标记 $0$、标记 $1$ 两片叶子。

待判 $1$ 按指标 $2$ 取值 $2$ 到叶，路径 $2$，输出 1 0 2。待判 $2$ 按指标 $2$ 取值 $1$、指标 $1$ 取值 $1$ 到叶，路径 $2>1$，输出 2 1 2>1。待判 $3$ 按指标 $2$ 取值 $1$、指标 $1$ 取值 $2$、指标 $3$ 左侧到叶，路径 $2>1>3$，输出 3 0 2>1>3。待判 $4$ 的指标 $2$ 取值 $3$ 未出现，取值 $1$ 与取值 $2$ 各有 $3$ 条训练记录，取更小的取值 $1$，再按指标 $1$ 取值 $1$ 到叶，路径 $2>1$，输出 4 1 2>1。