Decision tree classification with bounded number of errors

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.