Comparison of Complexity of Regular and Oblivious Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes

In this paper, classes of decision tables with many-valued decisions (also known as multi-labeled decision tables) closed with respect to deletion of attributes (columns) and change of decisions are considered. For tables from these classes, the dependence of the minimum complexity of regular decision trees on the minimum complexity of oblivious decision trees, in which the order of queries on attribute values is predetermined, is studied. It is proved that the function describing this dependence is either bounded from above by a constant or grows as a logarithm, or grows almost linearly. This result is valid for the so-called bounded complexity measures, including the depth and weighted depth of decision trees. Motivation of this work constitutes in analyzing growth in the worst-case of the minimum complexity of a regular decision tree for a decision table from a closed class with the growth of the minimum complexity of an oblivious decision tree for this decision table. It is also shown that the minimum complexity of an oblivious tree for a decision table is equal to the minimum complexity of a reduct for this table. This finding can be useful for applications related to oblivious decision trees.