通过自适应特征与样本缩减扩展最优分类树

# 通过自适应特征与样本缩减扩展最优分类树

来源：https://arxiv.org/html/2609.05826

Jiancheng Tu
机构：香港理工大学计算学系
邮箱：[[email protected]](mailto:)

Wenqi Fan
机构：香港理工大学计算学系
香港理工大学管理与市场学系
邮箱：[[email protected]](mailto:)

###### 摘要

随着特征和训练样本数量的增加，用于最优分类树的动态规划方法在计算上变得非常昂贵。我们基于 **STreeD** 开发了一个联合特征与样本空间缩减框架。
*   **Weighted STreeD** 将投影到固定候选集后创建的重复记录合并为带权重的代表记录。这减少了依赖于样本的计算，同时不改变固定候选集的优化问题。
*   **Adaptive STreeD** 反复优化一个有界候选集，保留当前最优树使用的特征，重建带权重表示，并求解由此产生的缩减问题。每个经认证的 **Weighted STreeD** 解对于其当前候选集是最优的，而外部特征搜索在整个特征空间上仍然是启发式的。
在五个数据集上的实验表明，**Weighted STreeD** 相比标准 **STreeD** 实现了高达 121.41 倍的加速。在深度为 2-4 的匹配比较中，**Adaptive STreeD** 减少了运行时间，并在更深的深度（此时全特征方法受限于时间或内存）持续返回可行树。在相同的计算预算下，其预测性能与所评估的最优分类树基线相当，并在某些比较中更高。这些结果展示了联合特征与样本空间缩减如何将基于动态规划的最优树学习扩展到更具挑战性的实例上。

**关键词：** 可解释机器学习，最优分类树，动态规划

## 1 引言

当预测需要通过明确的决策规则进行解释时，分类树被广泛使用。这在信用评分、医疗预测和刑事司法等高风险应用中尤为重要，因为决策者可能需要检查和证明单个预测的合理性（Rudin 2019 (https://arxiv.org/html/2609.05826#bib.bib4)）。浅层树通过从根节点到叶子的短规则序列提供这种透明度。经典的树学习方法如 CART、ID3 和 C4.5 是贪婪地构建树的（Breiman 等 1984 (https://arxiv.org/html/2609.05826#bib.bib1)，Quinlan 1986 (https://arxiv.org/html/2609.05826#bib.bib2)，Quinlan 1993 (https://arxiv.org/html/2609.05826#bib.bib3)）。它们计算效率高，但局部的分裂决策可能不会导致最终的最优树。

最优分类树方法则对整个树进行优化。现有方法包括混合整数优化（Bertsimas 和 Dunn 2017 (https://arxiv.org/html/2609.05826#bib.bib5)，Verwer 和 Zhang 2019 (https://arxiv.org/html/2609.05826#bib.bib6)，Alston 等 2026 (https://arxiv.org/html/2609.05826#bib.bib50)，Liu 等 2024 (https://arxiv.org/html/2609.05826#bib.bib51)，Blanquero 等 2021 (https://arxiv.org/html/2609.05826#bib.bib52)，Blanquero 等 2020 (https://arxiv.org/html/2609.05826#bib.bib53)）、动态规划（Aglin 等 2020 (https://arxiv.org/html/2609.05826#bib.bib19)，Demirović 等 2022 (https://arxiv.org/html/2609.05826#bib.bib20)，Lin 等 2020 (https://arxiv.org/html/2609.05826#bib.bib21)，van der Linden 等 2023 (https://arxiv.org/html/2609.05826#bib.bib22)）以及 SAT 和约束规划（Verhaeghe 等 2020 (https://arxiv.org/html/2609.05826#bib.bib30)，Shati 等 2021 (https://arxiv.org/html/2609.05826#bib.bib31)）。在这些方法中，动态规划利用了决策树的递归结构，并在浅层最优树学习中表现出色。

我们基于 **STreeD** 进行研究，这是一个通用的用于最优决策树的动态规划框架（van der Linden 等 2023 (https://arxiv.org/html/2609.05826#bib.bib22)）。其计算成本在很大程度上取决于候选特征和训练样本的数量。大的特征空间增加了状态数和分裂评估次数，而许多状态会重复处理训练记录。当预处理创建出高维二进制特征空间后，这些成本变得更加严重。

我们利用了特征缩减和样本缩减之间的相互作用。限制候选集可以减少分裂枚举，并可能产生额外的重复投影记录，这些记录可以合并为带权重的代表记录。基于这一想法，**Weighted STreeD** 提供了一种针对固定候选集的无损重构，而 **Adaptive STreeD** 则在重建带权重表示的同时迭代优化有界候选集。这两种方法的保证范围不同。经认证的 **Weighted STreeD** 解对于其固定的候选集是最优的。然而，**Adaptive STreeD** 在整个特征空间上仍然是启发式的。当访问的候选集包含这样一个最优树的分裂特征并且相应的缩减问题被最优求解时，它才能恢复全特征最优解。我们还推导了复杂度和有条件的解质量结果，以阐明这些保证。

在五个二值化数据集上的实验表明，**Weighted STreeD** 相比标准 **STreeD** 实现了高达 121.41 倍的加速。**Adaptive STreeD** 在深度 2-4 的匹配比较中减少了运行时间，并在更深的深度（此时全特征方法受限于时间或内存）持续返回可行树。在相同的计算预算下，其预测性能与所评估的最优树基线相当。

本文做出了两项方法论贡献。首先，我们开发了一种联合特征与样本空间缩减方案，其中候选集限制可以增加无损加权聚合的数量。其次，我们开发了一种自适应候选集优化方法，该方法在更新缩减特征空间的同时保留当前最优树使用的特征。理论分析描述了计算缩减和保证范围，计算实验分别和联合评估了这两种机制。

## 2 相关工作

我们按优化、数据与特征缩减以及近似最优搜索来组织最相关的工作，重点强调每种方法缩减了什么以及其保证的范围。

### 2.1 最优分类树

最优分类树方法优化整个树，而不是贪婪地选择分裂。主要精确方法包括混合整数优化、动态规划、SAT/MaxSAT、约束规划和分支定界。
混合整数优化模型联合确定树结构、分裂规则和叶子预测。OCT 公式为有界深度树确立了这种方法（Bertsimas 和 Dunn 2017 (https://arxiv.org/html/2609.05826#bib.bib5)），随后出现了更强的公式以及向更丰富的分裂规则、目标和约束的扩展（Verwer 和 Zhang 2019 (https://arxiv.org/html/2609.05826#bib.bib6)，Aghaei 等 2025 (https://arxiv.org/html/2609.05826#bib.bib7)，Günlük 等 2021 (https://arxiv.org/html/2609.05826#bib.bib8)，Subramanian 和 Sun 2023 (https://arxiv.org/html/2609.05826#bib.bib16)，Ales 等 2024 (https://arxiv.org/html/2609.05826#bib.bib17)，D'Onofrio 等 2024 (https://arxiv.org/html/2609.05826#bib.bib18)）。这些模型灵活，但依赖于样本索引的路由变量和大规模的分裂空间可能限制其可扩展性。SAT、MaxSAT 和约束规划方法提供了基于逻辑约束和结构化搜索的替代精确公式（Shati 等 2021 (https://arxiv.org/html/2609.05826#bib.bib31)，Hu 等 2020 (https://arxiv.org/html/2609.05826#bib.bib32)，Verhaeghe 等 2020 (https://arxiv.org/html/2609.05826#bib.bib30)）。列生成和基于路径的方法通过按需生成规则或路径进一步缩减了初始模型（Firat 等 2020 (https://arxiv.org/html/2609.05826#bib.bib14)，Patel 等 2024 (https://arxiv.org/html/2609.05826#bib.bib15)，Subramanian 和 Sun 2023 (https://arxiv.org/html/2609.05826#bib.bib16)）。

动态规划方法利用决策树的递归结构，并通过缓存和界来重用重复的子问题。DL8.5 结合了缓存与分支定界搜索（Aglin 等 2020 (https://arxiv.org/html/2609.05826#bib.bib19)），而 MurTree 引入了专门的界、基于相似性的剪枝和高效的浅层树例程（Demirović 等 2022 (https://arxiv.org/html/2609.05826#bib.bib20)）。OSDT 和 GOSDT 使用正则化和强剪枝规则来学习稀疏最优树（Hu 等 2019 (https://arxiv.org/html/2609.05826#bib.bib23)，Lin 等 2020 (https://arxiv.org/html/2609.05826#bib.bib21)）。**STreeD** 通过识别目标和约束可以分解为独立子树问题的条件，概括了这一工作方向（van der Linden 等 2023 (https://arxiv.org/html/2609.05826#bib.bib22)）。近期的替代方案包括 MAPTree 中的 AND/OR 搜索和 Branches 中的 AO* 搜索（Sullivan 等 2024 (https://arxiv.org/html/2609.05826#bib.bib47)，Chaouki 等 2025 (https://arxiv.org/html/2609.05826#bib.bib48)）。Quant-BnB 和 ConTree 则专门针对连续特征优化了搜索（Mazumder 等 2022 (https://arxiv.org/html/2609.05826#bib.bib11)，Briţa 等 2025 (https://arxiv.org/html/2609.05826#bib.bib28)）。

### 2.2 数据与特征缩减

数据缩减方法利用重复或不可区分的记录来减少计算。CORELS 和 OSDT 使用等价点参数来推导不可避免的预测误差（Angelino 等 2018 (https://arxiv.org/html/2609.05826#bib.bib43)，Hu 等 2019 (https://arxiv.org/html/2609.05826#bib.bib23)）。类似的想法已被用于加强下界或减少最优树搜索中的冗余观测（Zhang 等 2023 (https://arxiv.org/html/2609.05826#bib.bib44)，Keegan 等 2025 (https://arxiv.org/html/2609.05826#bib.bib10)，Hua 等 2022 (https://arxiv.org/html/2609.05826#bib.bib33)）。GOSDT 提供了一个相关的动态规划先例。它在固定的二进制特征矩阵中存储每一不同行的正负经验质量（Lin 等 2020 (https://arxiv.org/html/2609.05826#bib.bib21)）。WFlowOCT 在基于流的混合整数模型中将重复的特征-标签记录聚合为带权重的实例（Tu 等 2026 (https://arxiv.org/html/2609.05826#bib.bib9)）。**Weighted STreeD** 的不同之处在于，重复记录是在投影到当前候选集后定义的。因此，限制候选集可以产生额外的重复记录，这些记录被合并为带权重的代表记录。每当候选集发生变化时，带权重的表示就会被重建，从而将特征空间缩减与样本空间缩减耦合起来。在所述的可分性和信息保留条件下，该变换保持固定候选集优化问题不变。

特征缩减可以在优化前或求解过程中应用。BinOCT 减少了与不同特征值相关的二进制变量（Verwer 和 Zhang 2019 (https://arxiv.org/html/2609.05826#bib.bib6)），而参考引导方法使用黑盒模型来选择阈值、估计树大小或引导下界（McTavish 等 2022 (https://arxiv.org/html/2609.05826#bib.bib24)）。其他研究更直接地缩减特征空间。Ruggieri (2019) (https://arxiv.org/html/2609.05826#bib.bib45) 为固定的贪婪学习器枚举特征子集，而 Ing 等 (2024) (https://arxiv.org/html/2609.05826#bib.bib46) 和 Eiben 等 (2023) (https://arxiv.org/html/2609.05826#bib.bib12) 研究了在不同结构假设下的紧凑特征支持集。这些方法缩减了搜索空间，但它们通常不保证所选特征包含全特征最优树所使用的特征。**Adaptive STreeD** 遵循不同的策略：它求解一系列有界候选集问题，并在每次候选集更新后重建带权重的数据表示。

### 2.3 近似最优分类树

当证明全最优性代价过高时，几种方法在固定的计算预算内寻找高质量的树。有限差异搜索、Blossom 和随时波束搜索保留完整的搜索空间，但在完成最优性证明之前优先考虑强有力的当前最优解（Demirović 等 2023 (https://arxiv.org/html/2609.05826#bib.bib25)，Kiossou 和 Schaus 2026 (https://arxiv.org/html/2609.05826#bib.bib27)）。内存受限方法则限制缓存使用或修改状态处理（Aglin 等 2022 (https://arxiv.org/html/2609.05826#bib.bib26)）。其他方法通过只优化树的一部分来缩减精确搜索：SPLIT 精确求解上子问题，并贪婪地构建下层（Babbar 等 2025 (https://arxiv.org/html/2609.05826#bib.bib29)），而基于 SAT 的局部改进重新优化启发式解的选定子树（Schidler 和 Szeider 2021 (https://arxiv.org/html/2609.05826#bib.bib13)）。**Adaptive STreeD** 的不同之处在于限制候选特征空间，而不是限制树结构或搜索顺序。每个经认证的内部求解对于其当前候选集是最优的，而外部特征优化在整个特征空间上仍然是启发式的。只有当访问的候选集包含这样一个最优树的分裂特征并且相应的缩减问题被最优求解时，才能恢复全特征最优解。

## 3 加权唯一数据动态规划

本节开发 **STreeD** 的固定候选集加权重构。我们首先为满足信息保留条件的可分离任务建立原始表示与加权表示之间的固定候选集等价性。然后，我们专门针对训练准确度目标来呈现明确的递归式并分析其时间和空间复杂度。这种专门化反映了本文对可扩展性的关注，而非对加权重构的限制。证明见附录 D (https://arxiv.org/html/2609.05826#A4)。

### 3.1 问题设定

设 \( \mathcal{I} = \{(\mathbf{x}_i, y_i, \eta_i)\}_{i=1}^n \) 是一个训练集，其中 \( \mathbf{x}_i \in \{0,1\}^p \) 是二值化后的特征向量，\( y_i \in \mathcal{K} \) 是从有限类集 \( \mathcal{K} \) 中抽取的类标签，\( \eta_i \) 收集了任务所需的任何其他记录级信息，例如特定类别的成本、治疗和结果信息，或群体成员资格。令 \( \mathcal{F} = \{1, \ldots, p\} \) 为完整的二值化后特征集。固定一个候选集 \( S \subseteq \mathcal{F} \)，并令 \( q = |S| \)。限制在 \( S \) 上的树只能使用 \( S \) 中的特征作为分裂特征；\( h_T(\mathbf{x}_{iS}) \) 表示观测 \( i \) 投影到 \( S \) 后树 \( T \) 的预测值。对于一棵树 \( T \)，令 \( L_{\mathrm{mis}}(T) = \sum_{i=1}^n \mathbf{1}\{y_i \neq h_T(\mathbf{x}_{iS})\} \) 表示其训练误分类计数。经验误分类误差为 \( L_{\mathrm{mis}}(T)/n \)，训练准确度为 \( 1 - L_{\mathrm{mis}}(T)/n \)。因此，最大化训练准确度等价于最小化 \( L_{\mathrm{mis}}(T) \)。下面的递归式使用了这个可加的计数。

###### 定义 1。遵循 van der Linden 定义 4.2。