题目内容

质检班要把一批已标注样品做成若干个抽检分类器，再给未标注样品投票。标签是非负整数。每个分类器由三步构成：一次有放回抽袋、一次随机特征子集、再在子集上做最近质心分类。实现时只允许使用 $numpy$、$pandas$、$scikit\text{-}learn$。

设训练特征为 $X\in\mathbb{R}^{n\times d}$，标签为 $y$。输入还给出基分类器个数 $T$、每袋特征数 $m$ 和随机种子 $seed$。必须使用 $rg = np.random.RandomState(seed)$，并按下述顺序构造第 $t$ 个分类器。

1. 有放回抽袋：样本数仍为 $n$，下标 $idx = rg.randint(0, n, size=n)$。
2. 无放回抽特征：$feat = rg.choice(d, size=m, replace=False)$，抽出的特征下标再按升序保存。
3. 最近质心：在该袋样本、该特征子集上，对每个类别 $c$ 算质心 $\mu_c=\frac{1}{N_c}\sum_{x_i\in c}x_i$。测试点 $x$ 预测为 $\hat y=\arg\min_c\|x^{(feat)}-\mu_c\|_2^2$（平方欧氏距离）。距离完全相同则取类别编号更小者。

缺失类别：某袋里若类别 $c$ 一次都没抽到，质心不能删，改用完整训练集在同一特征子集上的全局质心。

投票：所有基分类器各投一票，$\hat y=\arg\max_c \mathrm{vote}(c)$；票数并列同样取更小编号。

输入描述

标准输入是一行 $JSON$，字段名必须如下：

{
    "train": [[f11, f12, ..., y1],
              [f21, f22, ..., y2]],
    "test": [[g11, g12, ...],
             [g21, g22, ...]],
    "n_estimators": 5,
    "max_features": 1,
    "seed": 42
}

• $train$：二维列表，形状为训练条数 $\times (d+1)$，每行最后一列是标签
• $test$：二维列表，形状为测试条数 $\times d$，只有特征
• $n\_estimators$：基分类器个数 $T$
• $max\_features$：每袋抽取的特征数 $m$
• $seed$：随机种子
• 标签为非负整数；数据保证合法，$1\le m\le d$，$2\le$ 训练条数、测试条数 $\le 19$，$1\le d\le 9$

输出描述

只输出一个 $JSON$ 对象，字段如下：

{
    "features": [[1], [0], [0]],
    "bootstraps": [[2,3,0,2], [3,0,0,2], [2,2,2,2]],
    "pred": [0,1,0]
}

• $features$：每个基分类器使用的特征下标，子数组升序
• $bootstraps$：每个基分类器的抽袋下标，长度等于训练条数
• $pred$：测试集最终预测，顺序与 $test$ 一致
• 输出的括号、逗号、空格、换行与样例保持同一风格

样例1

输入

{"train":[[1,0,0],[2,0,0],[0,4,1],[0,5,1]],"test":[[1,0],[0,4],[1,2]],"n_estimators":2,"max_features":1,"seed":7}

输出

{"features":[[0],[0]],"bootstraps":[[3,0,1,2],[3,3,3,0]],"pred":[0,1,0]}

说明

两个基分类器都抽到特征 $0$。按多数票，三份测试分别判为 $0$、$1$、$0$。

样例2

输入

{"train":[[0,0,0],[1,0,0],[0,1,1],[8,8,2]],"test":[[0,0],[8,8]],"n_estimators":4,"max_features":2,"seed":1}

输出

{"features":[[0,1],[0,1],[0,1],[0,1]],"bootstraps":[[1,3,0,0],[1,3,1,3],[0,1,0,3],[0,2,1,2]],"pred":[0,2]}

说明

三类标签。抽袋时可能抽不到某一类，此时该类质心改用全训练集在相同特征上的均值。最终两份测试判为 $0$ 与 $2$。

样例3

输入

{"train":[[3,1,0,0],[3,2,0,0],[1,3,1,1],[1,4,1,1],[9,9,9,2]],"test":[[3,1,0],[1,3,1],[9,9,9]],"n_estimators":3,"max_features":2,"seed":13}

输出

{"features":[[1,2],[0,1],[1,2]],"bootstraps":[[2,0,2,0,2],[4,2,3,2,4],[2,1,3,4,2]],"pred":[0,1,2]}

说明

特征下标已按升序写出。三份测试分别落到三个类别。

数据范围

• 训练条数、测试条数均满足 $2\le \cdot \le 19$
• $1\le d\le 9$
• $1\le m\le d$
• 标签为非负整数
• 仅允许 $numpy$ / $pandas$ / $scikit\text{-}learn$
• 输入保证合法