Decision trees for entity identification: approximation algorithms and hardness results
Decision trees for entity identification: approximation algorithms and hardness results
复制标题
用于实体识别的决策树：近似算法和硬度结果
DOI：
10.1145/1265530.1265538
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Mohania
中科院分区：
文献类型：
--
作者：
Venkatesan T. Chakaravarthy;Vinayaka Pandit;Sambuddha Roy;Pranjal Awasthi;M. Mohania
我们考虑从给定的关系表构建用于实体识别的决策树的问题。输入是一个表，其中包含有关一组固定属性上的实体集的信息以及该实体集上指定每个实体出现的可能性的概率分布。目标是构建一个决策树，通过测试属性值来明确标识每个实体，从而最小化平均测试次数。这个经典问题具有多种应用，例如有效的故障检测、生物学中的物种识别以及医学领域的有效诊断。先前的工作主要处理输入表是二进制的并且实体集上的概率分布是均匀的特殊情况。我们研究涉及任意输入表和实体集上的任意概率分布的一般问题。我们考虑自然贪婪算法并证明 O(rK • log N) 的近似保证，其中 N 是实体的数量，K 是属性的不同值的最大数量。 rK 值是一个适当定义的 Ramsey 数，最多为 log K。我们表明，即使对于二进制表（即 K=2），在 Ω(log N) 因子内近似该问题也是 NP 困难的。因此，对于二进制表的情况，我们的近似算法在常数因子范围内是最优的（因为 r2=2）。此外，我们的分析表明了解决埃尔多斯拉姆齐理论猜想的一种可能方法。
We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. 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. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O(rK • log N), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value rK is a suitably defined Ramsey number, which is at most log K. We show that it is NP-hard to approximate the problem within a factor of Ω(log N), even for binary tables (i.e. K=2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r2=2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdos.