Average time complexity of decision trees. (Q639456)

The book contains several previously known results on the average time complexity of decision trees for a number of new problems. The author presents bounds on the minimum average time complexity of decision trees. For some classes of information systems he constructs effective algorithms for building such decision trees. The book consists of five chapters. The first chapter discusses the upper and lower bounds on the average weighed depth of decision trees for arbitrary identification problems. In the second chapter, the conditions on the problem structure and the probability distribution for objects that enable problem decomposition are considered. Under these conditions, an optimal decision tree for the initial problem can be synthesized from optimal decision trees for simpler problems. Chapter 4 is devoted to algorithms for decision trees. The author presents an algorithm based on dynamic programming and some greedy algorithms applied to data sets from the UCI machine learning repository are used for fast detection of corner vision. In Chapter 5 it is shown that for restricted information systems there are upper bounds on the average depth of decision trees. This depends purely on the entropy of the object probability distribution. Additionally, this chapter gives necessary and sufficient conditions for limiting the time complexity of a considered algorithm from above using a polynomial for the number of rows in a table. In other words, the results obtained generalize the bounds to an arbitrary restricted information system. In summary, the results presented in the book may be of interest for researchers in test theory, rough set theory, and logical analysis of data and machine learning. The book is suitable for a graduate or PhD course.