Learning Decision Rules from Sets of Decision Trees

This paper is devoted to the study of the problems of learning inner and general decision rules that are true for the maximum number of decision trees from a given set. Inner rules correspond to paths in decision trees from the root to terminal nodes. General rules are arbitrary rules that use attributes from the considered decision trees. We propose a polynomial time algorithm for the optimization of inner rules, show that the problem of optimization of general rules is NP-hard, and describe a heuristic for this problem. We compare the considered algorithm and heuristic experimentally on artificially generated datasets and induced from them decision trees with Gini index as a splitting criterion.