Learning optimal decision trees using constraint programming
Learning optimal decision trees using constraint programming
复制标题
使用约束规划学习最优决策树
作者：
Hélène Verhaeghe;Siegfried Nijssen;Gilles Pesant;Claude;P. Schaus
决策树是机器学习中最流行的分类模型之一。传统上，它们是使用贪婪算法学习的。然而，这样的算法有几个缺点：很难限制决策树的大小，同时保持良好的分类精度，并且很难对学习的模型施加额外的约束。由于这些原因，最近人们对用于学习决策树的精确和灵活的算法感兴趣。在本文中，我们介绍了一种新的方法来学习决策树使用约束规划。与早期的方法相比，我们表明，我们的方法获得了更好的性能，同时仍然足够灵活，允许包含的约束。我们的方法建立在三个关键的构建块：（1）使用AND/OR搜索，（2）使用缓存，（3）使用最近提出的CoverSize全局约束项集挖掘的问题。这使得我们的约束编程方法能够以更有效的方式处理学习问题中的分解。
Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms pose several disadvantages: it is difficult to limit the size of the decision trees while maintaining a good classification accuracy, and it is hard to impose additional constraints on the models that are learned. For these reasons, there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees using constraint programming. Compared to earlier approaches, we show that our approach obtains better performance, while still being sufficiently flexible to allow for the inclusion of constraints. Our approach builds on three key building blocks: (1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize global constraint proposed recently for the problem of itemset mining. This allows our constraint programming approach to deal in a much more efficient way with the decompositions in the learning problem.