技术摘要：具有局部自适应不确定区的三元决策树

问题陈述

标准决策树，特别是基于 CART 算法的决策树，使用硬二元阈值对特征空间进行划分。这种机制无论实例距离决策边界的远近如何，都赋予其相同的置信度。因此，一个远离最优阈值 $\theta$ 的实例与一个直接位于其上的实例被同等地视为确定。这种“硬性承诺”造成了一个已知的弱点：它在最优阈值附近（即学习到的分裂最不可靠的区域）高估了实例的确定性，未能向下游应用发出预测可能存在歧义的信号。

现有的解决不确定性的方法通常依赖外部噪声规范（例如，已知的传感器误差）或源自数据集级别统计的全局阈值。这些方法无法针对每个节点的特定分裂质量或数据分布进行局部自适应。此外，模糊决策树或软决策树等方法往往缺乏基于局部分裂统计的明确、可解释的不确定区。

方法

本文介绍了三元决策树，它在标准二元分裂的基础上，增加了以最优阈值 $\theta^*$ 为中心、半宽为 $\delta$ 的局部自适应不确定区。

三元评估

对于特征 $x_f$ 和阈值 $\theta^*$，决策逻辑定义如下：

• 真（确定性）： $x_f > \theta^* + \delta$
• 假（确定性）： $x_f \leq \theta^* - \delta$
• 未决（边界不确定）： $\theta^* - \delta < x_f \leq \theta^* + \delta$

落入未决区的实例并不会放弃预测。相反，它们会获得一个预测结果，该结果由两个子树的概率输出根据距离加权混合而成。关键在于，这些实例被标记为“边界不确定”，允许下游系统对其采取不同的处理方式（例如，路由至人工审核），而无需 withholding（ withholding 此处指不提供）类别预测。

局部计算 $\delta$

核心的技术贡献是利用标准 CART 分裂查找过程中已计算的统计量，在局部推导每个节点的 $\delta$，无需外部数据或噪声模型。本文提出并评估了五种方法：

1. 质量平台（$\delta_{QP}$）： 测量分裂准则曲线（例如基尼增益）在 $\theta^*$ 周围“平台”的宽度。宽平台表明数据并未精确约束最优分裂位置。
2. 类别重叠（$\delta_{CO}$）： 基于经验百分位数，计算类别条件特征分布重叠区域的宽度。
3. 增益比（$\delta_{GR}$）： 将特征范围与增益比（信息增益相对于分裂熵）成反比缩放。低增益比表明分裂存在歧义，从而导致更大的 $\delta$。
4. 节点自举（$\delta_{NB}$）： 测量节点训练数据的自举重采样中，最优阈值 $\theta^*$ 的标准差。这直接量化了阈值的不稳定性。
5. 间隔（$\delta_{M}$）： 受支持向量机（SVM）启发，将 $\delta$ 定义为从 $\theta^*$ 到最近的跨类别训练样本（即该节点的“支持向量”）的距离。如果分裂完全干净，则使用相邻数据点之间的物理间隙。

路由架构

评估了两种用于传播不确定实例的架构：

• 概率路由： 树结构保持二元。在预测期间，位于不确定区的实例被路由到两个子节点，权重与其距离阈值的距离成反比，输出结果随后被混合。
• 硬中间分支： 在树结构中添加第三个子节点，专门针对不确定区内的实例进行训练。
  实验结果表明，概率路由通常优于硬中间方法，因为后者将不确定样本从左、右分支的训练集中移除，降低了它们的质量。

主要贡献

1. 框架： 引入三元决策树，为每个分裂提供原则性的、局部自适应的不确定区。
2. 五种估计方法： 推导了五种不同的方法来仅使用标准 CART 分裂统计量计算 $\delta$，消除了对外部噪声模型的需求。
3. 路由评估： 对概率路由与硬中间路由进行了比较分析，证明了概率混合在大多数方法中的优越性。
4. 广泛的实证评估： 在 72 个 OpenML-CC18 数据集、三个 Breiman 合成基准（具有已知的贝叶斯误差）以及四个高风险医疗/金融数据集上进行了评估。
5. 诊断框架： 引入未决/贝叶斯（U/B）比率，用于评估方法的标记率与数据集理论不可约误差的对齐程度。

结果

广泛有效性（OpenML-CC18）

在 72 个数据集中，所有使用概率路由的五种方法在确定性准确率（仅限于非不确定实例的准确率）上均显著优于标准 CART 基线，$p \leq 0.001$。

• 间隔方法： 实现了最佳效率（每单位标记率的准确率增益，$\eta = 0.104$）。它在 72 个数据集中赢得了 42 个，仅将 16.7% 的实例标记为不确定，且不需要额外的超参数。
• 类别重叠与增益比： 实现了较高的确定性准确率，但标记了较大比例的实例（分别为 71% 和 58%），导致效率较低。
• 节点自举： 表现良好，但计算成本高昂，因此被排除在 $N > 20,000$ 的数据集之外。

理论分析（Breiman 基准）

在具有已知贝叶斯误差的合成数据集上：

• 间隔： 在几何上干净的数据上表现出自校准行为，标记极少实例为不确定（U/B 比率 < 0.5），当边界清晰时，其行为实际上等同于 CART。
• 节点自举与质量平台： 表现出比例校准，在更困难的数据集（更高的贝叶斯误差）上标记更多实例，尽管所有方法相对于理论贝叶斯误差都存在过度标记（U/B > 1）。
• 校准差距： 没有一种方法达到 1.0 的 U/B 比率，表明局部阈值不确定性并不直接对应于全局贝叶斯误差。

领域应用

• 乳腺 X 光摄影： 节点自举将 10.8% 的病例标记为不确定，同时将确定性准确率提高了 0.71%（优于 CART）。这对于识别需要二次审核的病例非常有价值。
• 糖尿病： 节点自举实现了 +9.8% 的准确率增益，但标记了 63.4% 的患者，表明在准确率和标记率之间存在权衡。间隔方法提供了一个更保守、更实用的工作点（+0.4% 增益，9.5% 标记率）。
• 局限性： 在较小的克利夫兰心脏病数据集（$N=303$）上，由于方差估计不可靠，节点自举表现不佳。在德国信贷数据集上，间隔方法表现不如基线，表明其在复杂经济特征交互方面存在局限性。

意义与主张

本文主张将三元树确立为不确定性感知分类的原则性原语。其意义在于：

• 实用价值： 提供了一种机制，用于标记边界不确定的预测而无需放弃预测，从而使下游系统（例如，医疗筛查、信贷审批）能够应用不同的处理策略。
• 计算可行性： 从现有的分裂统计量中推导不确定区，无需外部数据或复杂的重新训练。
• 理论基础： 提供了一个框架，其中“未决”判决是对预测置信度的限定，而非对预测本身的拒绝。

作者谦逊地指出，虽然这些方法提高了确定性准确率，但尚未将标记率完美校准到理论贝叶斯误差，并将这种校准确定为未来工作的具体开放问题。