Relations between Decision Trees and Decision Rule Systems

Overview

The study of relationships between systems of decision rules and deterministic decision trees is an important task of computer science. It is easy to transform a decision tree into a decision rule system. The inverse transformation is a more difficult task.

In this work, we study unimprovable upper and lower bounds on the minimum depth of decision trees derived from decision rule systems depending on the various parameters of these systems. To illustrate the process of transformation of decision rule systems into decision trees, we generalize a well-known result for Boolean functions to the case of functions of k-valued logic.

We address six problems related to the inverse transformation. We demonstrate the complexity of constructing complete decision trees can be superpolynomial in many instances. We proposed three polynomial-time algorithms for each of the six problems, which focus on outlining the computation path within the decision tree for a specified input rather than constructing the entire tree. Additionally, we introduced a dynamic programming algorithm that calculates the minimum depth of a decision tree corresponding to a given decision rule system. We describe these algorithms and related to them theoretical results for each of the six problems and experimentally compare the performance of the three algorithms and evaluate their outcomes against the optimal results generated by the dynamic programming algorithm.

Finally, for conventional problems over an arbitrary infinite binary information system, we study relations between time and space complexity of deterministic and nondeterministic decision trees solving these problems and using only attributes from the problem descriptions. As time and space complexity, we consider the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either as a logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into three complexity classes and study for each class issues related to time-space trade-off for decision trees.