Approximating Decision Trees with Multiway Branches
Approximating Decision Trees with Multiway Branches
复制标题
具有多路分支的近似决策树
DOI：
10.1007/978-3-642-02927-1_19
复制
发表时间：
2009
影响因子：
2.5
通讯作者：
Yogish Sabharwal
中科院分区：
文献类型：
--
作者：
Venkatesan T. Chakaravarthy;Vinayaka Pandit;Sambuddha Roy;Yogish Sabharwal
我们考虑从给定的表中构造实体识别决策树的问题。输入是一个表，其中包含关于一组实体和一组固定属性的信息。我们的目标是构建一个决策树，通过测试属性值来明确识别每个实体，从而使测试的平均数量最小化。这个问题的最佳近似比是O（log2 N）。在本文中，我们提出了一个新的贪婪启发式，产生一个改进的近似比O（logN）。
We consider the problem of constructing decision trees for entity identification from a given table. The input is a table containing information about a set of entities over a fixed set of attributes. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. The previously best known approximation ratio for this problem was O (log2 N ). In this paper, we present a new greedy heuristic that yields an improved approximation ratio of O (logN ).