Theoretical foundations and algorithms for the generation of optimal decision trees

oretical foundations for the generation of optimal decision trees arc presented. The approach used is based on recent developments in the area of discrete decision theory and on an existing syntactic algorithm for the reduction of decision expressions. An important characteristic of these developments is the treatment of decision trees as (co)algebraic terms. An overview of relevant results from previous investigations as well as a description of the reduction algorithm is included.

A set of algorithms for finding the irreducible forms of a decision tree are developed. The methods presented perform the syntactic optimization of decision expressions by finding minimal terms with respect to a preorder relation. This preorder relation is associated with a class of cost functions called reasonable cost criteria. Any expected testing cost is a member of this class.

The principal technique introduced is a search strategy called separation planning, which, when combined with the reduction method, yields an algorithm for generating all the optimal forms of a decision tree. The manipulations and algorithms are first presented for the simple case involving decision trees in a discrete decision theory without identities. They are then extended to the case when arbitrary identities are present. Several issues regarding the manipulation of terms in decision theories with arbitrary identities are also discussed. An existing implementation of these algorithms is described and several examples are presented.