Decision Tree Construction in Fixed Dimensions: Being Global is Hard but Local Greed is Good
Decision Tree Construction in Fixed Dimensions: Being Global is Hard but Local Greed is Good
复制标题
固定维度的决策树构建：全球化很难，但局部贪婪是好的
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
J. Salowe
中科院分区：
文献类型：
--
作者：
M. Goodrich;V. Mirelli;Mark W. Orletsky;J. Salowe
我们研究的问题nding最佳线性决策树分类的一组点在IR D划分成概念类，其中D是一个固定的，但任意的，常数。我们表明，最佳决策树的建设是NP完全的，即使是3维点集。尽管如此，我们可以证明一些有趣的近似界使用随机抽样nding最佳分裂超平面在贪婪决策树的建设。我们给出的实验证据表明，虽然提供渐近保证分裂质量，这种随机抽样方法的行为在实践中一样好，统一的随机化策略，不提供这样的保证。最后，我们提供了将这种随机抽样策略与局部贪婪爬山方法相结合的实验说明。
We study the problem of nding optimal linear decision trees for classifying a set of points in IR d partitioned into concept classes, where d is a xed, but arbitrary, constant. We show that optimal decision tree construction is NP-complete, even for 3-dimensional point sets. Nevertheless, we can prove a number of interesting approximation bounds on the use of random sampling for nding optimal splitting hyperplanes in greedy decision tree constructions. We give experimental evidence that, while providing asymptotic guarantees on split quality, this random sampling approach behaves as good in practice as uniform randomization strategies that do not provide such guarantees. Finally, we provide experimental justiication for coupling this random sampling strategy with locally-greedy hill climbing" methods.