Search

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments. [ABSTRACT FROM AUTHOR]

In this paper, we study decisions trees for decision tables with multiple decisions as a means for knowledge representation. To this end, we consider three methods to design decision trees and evaluate the number of nodes, and local and global misclassification rates of constructed trees. The considered methods are based on a dynamic programming algorithm for bi-objective optimization of decision trees. The goal of this study is to construct trees with reasonable number of nodes and at the same time reasonable accuracy. Previously, it was mentioned that the consideration of only the global misclassification rate of the decision tree is not enough and it is necessary to study also the local misclassification rate. The reason is that even if the global misclassification rate related to the whole tree is enough small, the local misclassification rate related to the terminal nodes of the tree can be too big. One of the considered methods allows us to construct the decision trees with moderate number of nodes as well as moderate global and local misclassification rates. These decision trees can be used for the knowledge representation. [ABSTRACT FROM AUTHOR]

We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth. [ABSTRACT FROM AUTHOR]

We prove that the minimum average depth of a decision tree for sorting 8 pairwise different elements is equal to 620160 / 8 ! . We show also that each decision tree for sorting 8 elements, which has minimum average depth (the number of such trees is approximately equal to 8.548 × 10 326365 ), has also minimum depth. Both problems were considered by Knuth (1998). To obtain these results, we use tools based on extensions of dynamic programming which allow us to make sequential optimization of decision trees relative to depth and average depth, and to count the number of decision trees with minimum average depth. [ABSTRACT FROM AUTHOR]

We study the depth of decision trees for diagnosis of constant 0 and 1 faults in read-once contact networks over finite bases containing only indecomposable networks. For each basis, we obtain a linear upper bound on the minimum depth of decision trees depending on the number of edges in the networks. For bases containing networks with at most 10 edges we find coefficients for linear bounds which are close to sharp. [ABSTRACT FROM AUTHOR]

Abstract: We show that for each iteration-free combinatorial circuit over a basis containing only monotone Boolean functions with at most five variables, there exists a decision tree for diagnosis of constant faults on inputs of gates with depth at most where is the number of gates in . [Copyright &y& Elsevier]

This paper presents a new tool for the study of relationships between the total path length or the average depth and the number of misclassifications for decision trees. In addition to algorithm, the paper also presents the results of experiments with datasets from UCI ML Repository [9] and datasets representing Boolean functions with 10 variables. [ABSTRACT FROM AUTHOR]

This paper is devoted to the consideration of software systemDaggercreated in KAUST. This system is based on extensions of dynamic programming. It allows sequential optimization of decision trees and rules relative to different cost functions, derivation of relationships between two cost functions (in particular, between number of misclassifications and depth of decision trees), and between cost and uncertainty of decision trees. We describe features ofDaggerand consider examples of this system’s work on decision tables from UCI Machine Learning Repository. We also useDaggerto compare 16 different greedy algorithms for decision tree construction. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present the empirical results for relationships between time (depth) and space (number of nodes) complexity of decision trees computing monotone Boolean functions, with at most five variables. We use Dagger (a tool for optimization of decision trees and decision rules) to conduct experiments. We show that, for each monotone Boolean function with at most five variables, there exists a totally optimal decision tree which is optimal with respect to both depth and number of nodes. [Copyright &y& Elsevier]

Abstract: In this paper, we present three approaches for construction of decision rules for decision tables with many-valued decisions. We construct decision rules directly for rows of decision table, based on paths in decision tree, and based on attributes contained in a test (super-reduct). Experimental results for the data sets taken from UCI Machine Learning Repository, contain comparison of the maximum and the average length of rules for the mentioned approaches. [Copyright &y& Elsevier]

Conventional decision trees use queries each of which is based on one attribute. In this study, we also examine decision trees that handle additional queries based on hypotheses. This kind of query is similar to the equivalence queries considered in exact learning. Earlier, we designed dynamic programming algorithms for the computation of the minimum depth and the minimum number of internal nodes in decision trees that have hypotheses. Modification of these algorithms considered in the present paper permits us to build decision trees with hypotheses that are optimal relative to the depth or relative to the number of the internal nodes. We compare the length and coverage of decision rules extracted from optimal decision trees with hypotheses and decision rules extracted from optimal conventional decision trees to choose the ones that are preferable as a tool for the representation of information. To this end, we conduct computer experiments on various decision tables from the UCI Machine Learning Repository. In addition, we also consider decision tables for randomly generated Boolean functions. The collected results show that the decision rules derived from decision trees with hypotheses in many cases are better than the rules extracted from conventional decision trees. [ABSTRACT FROM AUTHOR]

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction. [ABSTRACT FROM AUTHOR]

in the paper algorithms are considered which allow to optimize decision trees consecutively againsts relatively different criterions. For decision tables over an arbitrary infinite restricted information system [4], these algorithms have polynomial time complexity. [ABSTRACT FROM AUTHOR]

Focuses on a study which examined the average time complexity of Boolean functions representation in the form of decision trees. Problem statement, definitions and notions; Results and proofs; Information on a number of auxiliary propositions.

Presents a study on the use of algorithms in constructing a decision tree with minimal depths. Applications of decision trees; Function of a decision table; Procedure for developing an algorithm for optimal decision trees.

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses of values of all attributes. Such decision trees are similar to those studied in exact learning, where membership and equivalence queries are allowed. We present greedy algorithm based on entropy for the construction of the above decision trees and discuss the results of computer experiments on various data sets and randomly generated Boolean functions. [ABSTRACT FROM AUTHOR]

In this paper, we consider decision trees that use two types of queries: queries based on one attribute each and queries based on hypotheses about values of all attributes. Such decision trees are similar to the ones studied in exact learning, where membership and equivalence queries are allowed. We present dynamic programming algorithms for minimization of the depth and number of nodes of above decision trees and discuss results of computer experiments on various data sets and randomly generated Boolean functions. Decision trees with hypotheses generally have less complexity, i.e., they are more understandable and more suitable as a means for knowledge representation. [ABSTRACT FROM AUTHOR]

Presents some results concerning the properties of decision trees with minimal average depth. Conditions which allow for performing a decomposition of problem; Description of the class of all information systems which have linear upper bounds on minimal average weighted depth depending only on entropy; Exponential lower bounds on the number of vertices in branching programs with minimal average weighted depth for some problems.