Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization
Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization
复制标题
使用整数优化学习具有灵活约束和目标的决策树
DOI：
10.1007/978-3-319-59776-8_8
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yingqian Zhang
中科院分区：
文献类型：
--
作者：
S. Verwer;Yingqian Zhang
我们将学习给定深度的最优决策树的问题编码为整数优化问题。我们的实验表明，我们的方法（DTIP）可以用来学习良好的树，深度5从数据集的大小高达1000。除了高效外，我们的新配方还具有很大的灵活性。实验表明，我们可以使用从任何现有的决策树算法学习的树作为初始解，并使用DTIP改进树。此外，所提出的公式使我们能够轻松地创建决策树，不同的优化目标，而不是准确性和错误，和约束可以显式地添加在树的建设阶段。我们展示了如何使用这种灵活性来学习区分感知分类树，改善从不平衡数据中学习，并学习最大限度地减少假阳性/阴性错误的树。
We encode the problem of learning the optimal decision tree of a given depth as an integer optimization problem. We show experimentally that our method (DTIP) can be used to learn good trees up to depth 5 from data sets of size up to 1000. In addition to being efficient, our new formulation allows for a lot of flexibility. Experiments show that we can use the trees learned from any existing decision tree algorithms as starting solutions and improve the trees using DTIP. Moreover, the proposed formulation allows us to easily create decision trees with different optimization objectives instead of accuracy and error, and constraints can be added explicitly during the tree construction phase. We show how this flexibility can be used to learn discrimination-aware classification trees, to improve learning from imbalanced data, and to learn trees that minimise false positive/negative errors.