On Complexity of Decision Trees for Decision Tables from Closed Classes

Overview

In this thesis, we consider classes of decision tables closed under operations of removal of attributes (columns) and changing of decisions and sometimes some other operations and study for the tables from these classes relationships among the minimum complexity of deterministic and nondeterministic decision trees and the complexity of the set of attributes attached to columns of the table. Nondeterministic decision trees can be considered as a way to represent an arbitrary system of decision rules that are true for the table and cover all its rows.

Decision tables are a well-known way of presenting the information needed to make decisions. These tables are used, in particular, in data analysis, including classification problems, in modeling and studying combinatorial optimization problems, fault diagnosis, computational geometry, etc. Decision trees and decision rule systems are widely used as a means for knowledge representation, as classifiers that predict decisions for new objects, and as algorithms for solving various problems. Decision trees and decision rules systems (representing in our case by nondeterministic decision trees) are among the most interpretable models for classifying and representing knowledge. The study of relationships between these two models is an important task of computer science.

We study three types of decision tables: conventional tables, tables with 0-1-decisions and tables with many-valued decisions. We now describe a part of results obtained for each of these types of decision tables.

For tables from an arbitrary closed class of decision tables with many-valued decisions, we study three functions that characterize (i) the growth in the worst case of the minimum complexity of deterministic decision trees with the growth of the complexity of the set of attributes attached to columns, (ii) the growth in the worst case of the minimum complexity of nondeterministic decision trees with the growth of the complexity of the set of attributes attached to columns, and (iii) the growth in the worst case of the minimum complexity of deterministic decision trees with the growth of the minimum complexity of nondeterministic decision trees.

We proved that the first function is either bounded from above by a constant, or grows as a logarithm, or grows almost linearly (as a function depending on $n$, it is bounded from above by $n$ and is equal to $n$ for infinitely many $n$). The second function is either bounded from above by a constant or grows almost linearly. We indicated a criterion for the third function to be defined everywhere and described a wide range of behavior of this function when it is defined everywhere. This function (as a function depending on $n$) is either bounded from above by a constant or is greater than or equal to $n$ for infinitely many $n$. In particular, for any nondecreasing function $\varphi$ such that $\varphi (n)\geq n$ and $\varphi (0)=0$, the third function can grow between $\varphi (n)$ and $\varphi (n)+n$. We also indicated the conditions under which the third function is bounded from above by a polynomial. We obtained a bit weaker results for conventional decision tables describing the behavior of the above functions. Additionally, we provided a detailed analysis of algorithms for constructing deterministic and nondeterministic decision trees in this context.

We also obtained similar results for 0-1-decision tables (but, instead of nondeterministic decision trees, we consider here strongly nondeterministic decision trees that represent systems of true rules covered all rows with the decision 1). Furthermore, for this case, we explored the behavior of a function that characterizes the worst-case growth of the minimum complexity of a deterministic decision tree for a decision table from a closed class with the growth of the minimum complexity of a test of the decision table.

For closed classes of decision tables with many-valued decisions, we also obtained a rough classification of the relationships between each ordered pair of the considered three parameters and described all seven types of these relationships.