Decision tree classification with bounded number of errors

Oblivious decision trees are decision trees where every node in the same level is associated with the same attribute. These trees have been studied in the context of feature selection. 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 < is an element of < 1/2, builds an oblivious decision tree with cost at most (3/(1 - 2 is an element of)) In (n)O PT (I) and produces at most (k/is an element of) errors, where O PT (I) is the optimal cost and n is the number of objects. The probability of failure of this algorithm is at most (n - 1)/2n(2). The logarithmic factor in the cost of the tree is the best possible attainable, even for k = 0, unless P = NP. (C) 2017 Elsevier B.V. All rights reserved.