题目内容

某自动化分拣系统需要对流水线上的物品进行快速分类，每个物品通过多个检测模块获得一组特征值，并被人工标记为“保留”（标签 1）或“淘汰”（标签 0）。由于硬件限制，实际分类时只能选用某一个特征，将特征值不超过某个阈值的物品分到一侧，超过阈值的分到另一侧，并依据这一侧的训练标签决定对该物品的最终判定。

现给定一组训练数据，请你找出一个最优的特征编号和阈值，使得按照该划分得到的混乱程度最低，并利用该规则对一批新物品进行预测。

对于特征 $j$ 和阈值 $\theta$，将训练样本中满足 $x_j \le \theta$ 的样本归入左集合，$x_j > \theta$ 的归入右集合。定义集合的混乱度 $h$ 为基尼不纯度：

其中 $p_0$ 和 $p_1$ 分别是该集合中标签为 0 和 1 的样本所占比例。整个划分的加权混乱度定义为：

其中 $n$ 为训练样本总数，$n_L, n_R$ 分别为左、右集合的样本数，$h_L, h_R$ 为对应集合的混乱度。

训练时，对每个特征独立寻找最优阈值：

• 将该特征对应的所有样本值按升序进行稳定排序（相等值保持原相对顺序）；
• 构造候选阈值集合，包括：任意两个相邻且不等的特征值的中点，以及“最小特征值减去一个极小常数 $\varepsilon = 10^{-7}$”；
• 对每个候选阈值计算加权混乱度 $H$；若该阈值导致左集合或右集合为空，则直接跳过该阈值；
• 记录该特征下使 $H$ 最小的阈值；若存在多个使 $H$ 相等的最小值，取阈值最小的那个。

比较所有特征的最优划分，选出全局 $H$ 最小的特征及阈值。如果多个组合的 $H$ 并列最小，则优先选择特征编号较小的；若特征编号也相同，则选择阈值较小的。

对最终选定的划分，左集合的预测标签取集合内出现次数更多的标签（若 0 和 1 出现次数相等，则取 0），右集合同理。如果没有任何有效划分可保留（即所有候选阈值都会导致某一侧为空），则直接以训练集全部样本的多数标签作为全局预测标签（相等时取 0），此时不再依赖任何特征与阈值。

预测时，对每个新物品，检查其在选定特征上的值：若值 $\le \theta$，则赋予左集合的预测标签；否则赋予右集合的预测标签。

数据范围与约束

• 训练样本总数 $n \ge 2$，特征个数 $m \ge 1$，待预测的样本数 $k \ge 1$。
• 所有特征值及标签均为整数或浮点数，数据中不存在缺失值。
• 极小常数 $\varepsilon = 10^{-7}$，仅用于生成最小特征值左侧的候选阈值。

输入描述

输入为一行 JSON 字符串，包含两个键："train" 和 "test"。

• "train" 是一个二维数组，每个元素为一个一维数组，其前 $m$ 个数为该样本的 $m$ 个特征值（数值类型），最后一个元素为标签（整数 0 或 1）。
• "test" 是一个二维数组，每个元素为一个长度为 $m$ 的数值数组，表示一个待测样本的 $m$ 个特征值。

输出描述

输出一行 JSON 数组，依次包含每个测试样本的预测标签（整数 0 或 1）。

样例1

输入

{"train":[[1,2,0],[2,3,0],[3,5,1],[4,6,1]],"test":[[2.5,4],[3.5,5.5]]}

输出

[0,1]

说明

训练集有 4 个样本，特征数 $m=2$。

对于特征 $1$（第一列），排序后值为 [1,2,3,4] 对应标签 [0,0,1,1]。候选阈值包括 1.5、2.5、3.5。计算加权混乱度：

• $\theta=1.5$：左集合 $\{1\}$（标签 0），右集合 $\{2,3,4\}$（标签 0,1,1），$H = 0.25\times0 + 0.75\times(1-(\frac{2}{3})^2-(\frac{1}{3})^2) = \frac{1}{3}$；
• $\theta=2.5$：左集合 $\{1,2\}$（标签 0,0），右集合 $\{3,4\}$（标签 1,1），$H=0$；
• $\theta=3.5$：左集合 $\{1,2,3\}$（标签 0,0,1），右集合 $\{4\}$（标签 1），$H=\frac{1}{3}$。 最优阈值为 2.5，加权混乱度 $0$。

对于特征 $2$（第二列），排序后值为 [2,3,5,6]，同样在阈值 4 处得到 $H=0$。

两个特征均能完美划分，优先选择特征编号较小的特征 $1$（编号 0），阈值 2.5。左集合预测标签 0，右集合预测标签 1。

测试样本 [2.5,4] 在特征 $1$ 上的值为 2.5，满足 $\le 2.5$，预测为 0；[3.5,5.5] 的特征 $1$ 值为 3.5，$>2.5$，预测为 1。

样例2

输入

{"train":[[0,0,0],[0,0,1]],"test":[[1,1]]}

输出

[0]

说明

训练集仅有 2 个样本，特征数 $m=2$。所有样本的两个特征值均为 0。

对任一特征，排序后所有值相等，不存在相邻不等的值，因此无法生成有效候选阈值（最小值减 $\varepsilon$ 的阈值会导致左集合为空而被跳过）。此时无法选出有效划分，直接以训练集全体样本的多数标签作为全局预测。

训练标签为 [0,1]，0 和 1 出现次数相等，取标签 0。测试样本无论特征值如何，均预测为 0。

样例3

输入

{"train":[[1,0,0],[3,2,1],[5,4,0],[7,6,1]],"test":[[2.0,3],[4.0,1]]}

输出

[0,1]

说明

训练集包含 4 个样本，特征数 $m=2$，标签依次为 0,1,0,1。

特征 $1$ 的值排序后为 [1,3,5,7]。候选阈值 2.0、4.0、6.0。

• $\theta=2.0$：左 $\{1\}$（0），右 $\{3,5,7\}$（1,0,1），$H=\frac{1}{3}$；
• $\theta=4.0$：左 $\{1,3\}$（0,1），右 $\{5,7\}$（0,1），$H=0.5$；
• $\theta=6.0$：左 $\{1,3,5\}$（0,1,0），右 $\{7\}$（1），$H=\frac{1}{3}$。 最小 $H$ 为 $\frac{1}{3}$，对应阈值 2.0 和 6.0，按规则选择更小的阈值 2.0。此时左集合标签为 0，右集合多数标签为 1。

特征 $2$ 的值排序为 [0,2,4,6]，同样存在两个阈值（1.0 和 5.0）使 $H=\frac{1}{3}$，特征内选 1.0。

全局比较，两个特征最小 $H$ 相同，优先选特征编号较小的特征 $1$（编号 0），阈值 2.0。

测试样本 [2.0,3] 特征 $1$ 值为 2.0，满足 $\le 2.0$，预测为 0；[4.0,1] 特征 $1$ 值为 4.0，$>2.0$，预测为 1。