基于轻量级节点级神经网络的精确决策树动态规划求解特征排序方法及其可靠性边界分析

《Scientific Reports》：Learned feature ordering for exact optimal decision tree search: a lightweight neural scoring approach

　　

摘要

精确最优决策树求解器提供了透明的模型，但面临组合搜索规模增长的问题，这意味着每当达到可靠的早停边界时，候选特征的探索顺序就变得至关重要。现有的求解器主要依赖手工设计的排序方式，而学习得到的排序方式在精确决策树归纳中的可靠性仍未得到充分刻画。我们研究了一种轻量级的仅节点级神经网络评分器，该评分器预测数据集特定的特征顺序，并将其插入动态规划（DP）求解器中，而不改变返回的最优解。在八个有规模上限的数据集和10个配对随机种子上，每数据集的聚合状态减少量平均为8.3%（中位数3.6%），但在种子级别的结果为60次胜出、9次持平和11次失利，中位数减少量为2.1%；信息增益和mRMR方法仍然具有竞争力，而在60个特征的压力测试中，学习得到的策略出现退化，这界定了当前方法的可靠性范围。