Approximating Optimal Binary Decision Trees
Approximating Optimal Binary Decision Trees
复制标题
近似最优二元决策树
DOI：
10.1007/s00453-011-9510-9
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
Brent Heeringa
中科院分区：
文献类型：
--
作者：
M. Adler;Brent Heeringa
本文给出了决策树（DT）问题的一个（ln n+1）-近似. DT的一个实例是一组m个二元测试T=（T1，.，Tm）和一组n个项目X=（X1，.，Xn）。目标是输出一个二叉树，其中每个内部节点是一个测试，每个叶子是一个项目，并且树的总外部路径长度最小化。总外部路径长度是树中所有叶子的深度之和。DT在计算机科学领域有着悠久的历史，其应用范围从医学诊断到实验设计。它还推广了在偏序集合中寻找最优平均情况搜索策略的问题，其中包括几个字母树问题。我们的工作减少了以前的最佳上限的近似比由一个常数因子。我们提供了一个新的分析贪婪算法，使用一个简单的会计计划，以分散在一个特定的节点上分裂的项目对树的成本。我们的结论表明，我们的上限也持有DT问题的加权测试。
We give a (ln n+1)-approximation for the decision tree (DT) problem. An instance of DT is a set of m binary tests T=(T1,…,Tm) and a set of n items X=(X1,…,Xn). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer science with applications ranging from medical diagnosis to experiment design. It also generalizes the problem of finding optimal average-case search strategies in partially ordered sets which includes several alphabetic tree problems. Our work decreases the previous best upper bound on the approximation ratio by a constant factor. We provide a new analysis of the greedy algorithm that uses a simple accounting scheme to spread the cost of a tree among pairs of items split at a particular node. We conclude by showing that our upper bound also holds for the DT problem with weighted tests.