SAT-based Decision Tree Learning for Large Data Sets
SAT-based Decision Tree Learning for Large Data Sets
复制标题
基于 SAT 的大数据集决策树学习
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Stefan Szeider
中科院分区：
文献类型：
--
作者：
André Schidler;Stefan Szeider
低深度的决策树有利于理解和解释它们所代表的数据。
Decision trees of low depth are beneficial for understanding and interpreting the data they represent.
Unfortunately, finding a decision tree of lowest depth that correctly represents given data is NP-hard.
Hence known algorithms either (i) utilize heuristics that do not optimize the depth or (ii) are exact but scale only to small or medium-sized instances.
We propose a new hybrid approach to decision tree learning, combining heuristic and exact methods in a novel way.
More specifically, we employ SAT encodings repeatedly to local parts of a decision tree provided by a standard heuristic, leading to a global depth improvement.
This allows us to scale the power of exact SAT-based methods to almost arbitrarily large data sets.
We evaluate our new approach experimentally on a range of real-world instances that contain up to several thousand samples.
In almost all cases, our method successfully decreases the depth of the initial decision tree; often, the decrease is significant.