解题思路

本题需要实现一个深度为 $1$ 的决策树，也就是 $Decision\ Stump$。

核心算法是：枚举每个特征的所有候选阈值，计算按照该阈值划分后的加权 $Gini$ 不纯度，选择全局最小的划分。

对每个特征 $j$：

先将训练样本按第 $j$ 个特征稳定排序，然后只在相邻不同值之间产生候选阈值。若相邻值为 $a$ 和 $b$，则候选阈值为：

题目内容

小美正在研究一个分类问题，请你帮助她只用 $numpy、pandas$ 手写实现一个二分类的 $Decision$ $Stump$（深度 $= 1$ 的决策树）。

模型必须遍历每个特征，寻找单一阈值划分，使得加权 $Gini$ 不纯度最小。

训练阶段

1. 数据读取
   • $train$：二维列表，最后一列为标签 $y \in \{0,1\}$；前面为数值型特征
2. 搜索过程（对每个特征独立完成）
   • 将样本按该特征升序；若存在相等值，保持原顺序（即稳定排序）
   • 在所有相邻不同值中点及 最小值 - ε 处设阈值候选
   • 计算候选阈值处的加权Gini$$G = \frac{n_L}{n} g_L + \frac{n_R}{n} g_R,\quad g_s = 1 - \sum_{c \in \{0,1\}} \left( \frac{n_{s,c}}{n_s} \right)^2$$
   • 记录该特征的最优阈值（最低 $G$，若并列取最小阈值）
3. 整棵树最优
   • 在所有特征最优阈值里，再选出全局最小 $G$
   • 若仍并列：先取特征索引最小者，再取阈值最小者
4. 叶子预测值
   • 左子集 $x_j \le \theta$、右子集 $x_j > \theta$ 各取多数类作为预测；若 0/1 数相等则输出 0
   • 若是子集为空，则跳过该阈值

预测阶段

• 对每条测试样本，若 $x_j \le \theta$ 预测左叶类别，否则右叶类别
• 输出与测试样本顺序一致

输入描述

小美提供的数据格式如下，标准输入仅一行 JSON：

{
  "train": [[f11,...,f1m,y1], ..., [fn1,...,fnm,yn]],
  "test": [[t11,...,t1m], ..., [tk1,...,tkm]]
}

• $n \ge 2,\ m \ge 1,\ k \ge 1$
• 所有元素为整数/浮点数，无缺失值

输出描述

单行 $JSON$ 数组 —— 每个测试样本的预测标签 ($0$ 或 $1$)，示例：$[0, 1, 0]$

补充说明

1. $\varepsilon$ 取值: $\varepsilon = 1\mathrm{e}-7$（'最小值 - $ε$' 的候选阈）
2. $Gini$ 计算: 使用公式所示总体频率
3. 为确保通过所有测试用例，建议仅使用 $Numpy$ 库与 $Pandas$ 库

样例1

输入

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

输出

[0, 0, 1]