通过参数化局部搜索优化决策树分类错误，揭示了可解性的关键条件。
Improving Decision Trees through the Lens of Parameterized Local Search
- 限定操作次数的局部搜索优化决策树分割
- 小特征数与小取值域组合时可在多项式时间内求解
- 适合研究算法复杂性或需要精确优化的场景
学习决策树的算法常包含启发式局部搜索操作，如调整分割阈值或交换分割特征。本文研究在固定次数的单一类型操作下最小化分类错误的问题。尽管发现此类问题一般为NP完全，但通过全面的参数化复杂性分析，揭示了问题难解与易解的关键因素。例如，当特征数 $d$ 和取值域大小 $D$ 均较小时，问题仍困难；但两者结合时可实现固定参数可解，时间复杂度为 $(D + 1)^{2d} ullet |I|^{O(1)}$，其中 $|I|$ 为输入规模。文中还提供了算法原型实现并报告了实验结果。
原文摘要 · Abstract (English)
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。