Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950865 | Information Processing Letters | 2017 | 11 Pages |
Abstract
In this paper, we study the problem of constructing an oblivious decision tree that incurs at most k classification errors, where k is a given integer. We present a randomized rounding algorithm that, given a parameter 0<ϵ<1/2, builds an oblivious decision tree with cost at most (3/(1â2ϵ))lnâ¡(n)OPT(I) and produces at most (k/ϵ) errors, where OPT(I) is the optimal cost and n is the number of objects. The probability of failure of this algorithm is at most (nâ1)/2n2. The logarithmic factor in the cost of the tree is the best possible attainable, even for k=0, unless P=NP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Aline Saettler, Eduardo Laber, Felipe de A. Mello Pereira,