Optimum decision trees - an optimal variable theorem and its related applications
type: Item
instance of: scholarly article
title: Optimum decision trees - an optimal variable theorem and its related applications
zbMATH Open document ID: 0562.90039
author: Masahiro Miyakawa
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
review text: The problem of translation of a decision table into an optimal sequential testing procedure (STP) under two cost criteria is considered. STP is formulated as a decision tree (herafter simply tree) and its description and execution costs are introduced. Given a decision table, optimum trees are defined as those with a minimal cost. A variable is called optimal when it is placed and hence to be tested at the root of an optimum tree. Quasi-decisive variables are defined as those whose all ''branches'' are constants except a single branch. It is proved that under both costs and under the strong equivalence assumption of quasi-decisive variables (SEA), quasi-decisive variables are optimal and conversely, whenever they exist, only the quasi-decisive variables are optimal (main theorem). SEA holds under the general description cost and under the uniform execution cost. It is shown that SEA cannot be weakened in case of the general execution cost. An algorithm is described which constructs an optimum tree in \(O(N^{\log_ 23}\log_ 2N)\) comparison operations, where N is the size of the input table. Then it is shown that one can speed-up this algorithm by applying the optimal variable theorem in the description cost case though the computational order cannot be lowered below \(O(N^{\log_ 23})\). In fact, the number of executions of the inner- most loop of the algorithm was reduced to 42 \% its value without acceleration in case of the test-data tables. As a related topic, the optimization problem of a quasi-decisive chain under the execution cost is presented. It requires O(N log\({}_ 2N)\) operations. Optimum decision trees have wide applications in various concrete problems, for example, they allow to resolve the optimal ordering of IF statements in programs.
Mathematics Subject Classification ID: 90B50
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3896642
zbMATH Keywords: optimal sequential testing procedure
zbMATH Keywords: decision tree
zbMATH Keywords: optimum tree
zbMATH Keywords: optimal variable theorem
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3896642