思路

• 关键：因为特征是一维且阈值只按大小划分，所以只需在相邻不同特征值之间、以及两端考虑切分点。重复特征值的样本不可被阈值拆分，需整组一起在同侧。

• 做法：

  • 将样本按特征 $x$ 升序排序。
  • 预处理前缀计数 $\text{prefL}(i)$：排序后前 $i$ 个（含 $i$）中标签等于 $L$ 的数量。
  • 预处理后缀计数 $\text{sufR}(i)$：排序后从 $i$ 到末尾中标签等于 $R$ 的数量。
  • 只在每个“特征值分组的末尾”作为切分（记该位置为 $i$）计算

题目内容

决策树生成算法递归地产生决策树，直到不能继续下去为止，在这个过程中，最关键的是确定每个节点的阈值。一种传统方法是划分之后，需要使得数据集的熵减最大化。

而小明同学面对的问题是一个基座问题：只有一个特征的数据集的二分类问题。如果构建出二叉树，那么将形如：”一个根节点配两个儿子节点“的结构。

在这种问题下，小明希望通过一个更加简洁的策略来获得结果：枚举阈值，得到验证集上的最优的准确率。请问给定验证集，需要设定怎样的阈值使得准确率最大化。