Chikalov I. Average Time Complexity of Decision Trees

Springer, 2011, -114 p.The monograph is devoted to theoretical and experimental study of decision trees with a focus on minimizing the average time complexity. The study resulted in upper and lower bounds on the minimum average time complexity of decision trees for identification problems. Previously known bounds from information theory are extended to the case of identification problem with an arbitrary set of attributes. Some examples of identification problems are presented giving an evidence that the obtained bounds are close to unimprovable. In addition to universal bounds, we study effectiveness of representing several types of discrete functions in a form of decision trees. In particular, for each closed class of Boolean functions we obtained upper bounds on the average depth of decision trees implementing functions from this class.
The monograph also studies the problem of algorithm design for optimal decision tree construction. An algorithm based on dynamic programming is proposed that describes a set of optimal trees and allows for subsequent optimization on other criteria. Experimental results show applicability of the algorithm to real-life applications that are represented by decision tables containing dozens of attributes and several thousands of objects.
Beside individual identification problems, infinite classes of problems are considered. It describes necessary conditions on such classes in order to have polynomial complexity algorithms for optimal decision tree construction.
The presented results can be of interest for researchers in test theory, rough set theory and machine learning. Some results may be considered for including in graduate courses on discrete mathematics and computer science.Bounds on Average Time Complexity of Decision Trees
Representing Boolean Functions by Decision Trees
Algorithms for Decision Tree Construction
Problems over Information Systems
Closed Classes of Boolean Functions