Decision Trees with Hypotheses

Description

In this book, the concept of a hypothesis about the values of all attributes is added to the standard decision tree model, considered, in particular, in test theory and rough set theory. This extension allows us to use the analog of equivalence queries from exact learning and explore decision trees that are based on various combinations of attributes, hypotheses, and proper hypotheses (analog of proper equivalence queries). The two main goals of this book are (i) to provide tools for the experimental and theoretical study of decision trees with hypotheses and (ii) to compare these decision trees with conventional decision trees that use only queries, each based on a single attribute.  Both experimental and theoretical results show that decision trees with hypotheses can have less complexity than conventional decision trees. These results open up some prospects for using decision trees with hypotheses as a means of knowledge representation and algorithms for computing Boolean functions. The obtained theoretical results and tools for studying decision trees with hypotheses are useful for researchers using decision trees and rules in data analysis. This book can also be used as the basis for graduate courses. Preface Contents 1 Introduction [DELETE] 1.1 Part I. Decision Tables 1.2 Part II. Infinite Binary Information Systems and Infinite Families of Concepts 1.3 Prospects of Using Decision Trees with Hypotheses 1.4 Use of Book Part I Decision Tables 2 Main Notions [DELETE] 2.1 Decision Tables and Uncertainty Measures 2.2 Decision Trees 2.3 Decision Rules Derived from Decision Trees 3 Dynamic Programming Algorithms for Minimization of Decision Tree Complexity [DELETE] 3.1 Construction of Directed Acyclic Graph Δ(T) 3.2 Minimizing the Depth 3.3 Minimizing the Number of Realizable Nodes 3.4 Minimizing the Number of Realizable Terminal Nodes 3.5 Minimizing the Number of Working Nodes 3.6 On Number of Realizable Terminal Nodes 3.7 Results of Experiments 3.7.1 Depth 3.7.2 Number of Realizable Nodes 3.7.3 Number of Realizable Terminal Nodes 3.7.4 Number of Working Nodes 3.8 Conclusions 4 Construction of Optimal Decision Trees and Deriving Decision Rules from Them [DELETE] 4.1 Construction of Decision Trees with Minimum Depth 4.2 Construction of Decision Trees with Minimum Number of Working Nodes 4.3 On Construction of Optimal Decision Trees for L and Lt 4.4 Results of Experiments 4.4.1 Decision Trees with Minimum Depth 4.4.2 Decision Trees with Minimum Number of Working Nodes 4.4.3 Analysis of Experimental Results 4.5 Conclusions 5 Greedy Algorithms for Construction of Decision Trees with Hypotheses [DELETE] 5.1 Greedy Algorithms 5.2 Results of Experiments on Decision Tables from UCI ML Repository 5.2.1 Results for Misclassification Error me 5.2.2 Results for Relative Misclassification Error rme 5.2.3 Results for Entropy ent 5.2.4 Results for Gini Index gini 5.2.5 Results for Uncertainty Measure R 5.3 Results of Experiments on Randomly Generated Boolean Functions 5.4 Analysis of Experimental Results 5.5 Conclusions 6 Decision Trees with Hypotheses for Recognition of Monotone Boolean Functions and for Sorting [DELETE] 6.1 Problem of Recognition of Monotone Boolean Functions 6.1.1 Basic Notions and Notation 6.1.2 Results of Experiments 6.2 Problem of Sorting 6.2.1 Basic Notions and Notation 6.2.2 Results of Experiments 6.3 Conclusions Part II Binary Information Systems and Infinite Families of Concepts 7 Infinite Binary Information Systems. Decision Trees of Types 1, 2, and 3 [DELETE] 7.1 Basic Notions 7.2 Main Results 7.3 Proofs of Theorems 7.1 and 7.2 7.4 Proof of Theorem 7.3 7.5 Conclusions 8 Infinite Binary Information Systems. Decision Trees of Types 4 and 5 [DELETE] 8.1 Five Functions of Shannon Type 8.2 Main Results 8.3 Proof of Theorem 8.1 8.4 Proof of Theorem 8.2 8.5 Conclusions 9 Infinite Families of Concepts [DELETE] 9.1 Basic Notions 9.2 Main Results 9.3 Proofs of Theorems 9.1 and 9.2 9.4 Proof of Theorem 9.3 9.5 Proof of Theorem 9.4 9.6 Conclusions Appendix Computation of Boolean Functions by Decision Trees with Hypotheses Final Remarks Index