Construction of Efficient Decision Trees
Masahiro Miyakawa · Institutional Repositories DataBase (IRDB) · 1988
Construction algorithms of optimum and near-optimum decision trees are surveyed under two optimality criteria: d-cost ($e.g $. number of the nodes of a tree) and e-cost (e.g. average time of testing for a decision). Special attentions are paid for: 1) presenting new selection criteria of a variable for constructing near-optimum trees, 2) exploring their properties and 3) the comparison of the performance of the criteria. Experimental results are also mentioned, giving some conclusive remarks about the performance. For converting a decision table by the variable selection method (VSM) to a near-optimal decision tree in the sense of the minimal number of nodes of the tree we present three variable selection criteria from different standpoints: A from combinatorial, $H$ from entropy and $D $ from discriminant analysis. In e-cost case, the combinatorial criterion splits into three criteria loss, $Q $ and O. Thus we have total 5 criteria together with e-cost versions of the criteria $D $ and H. Experimental results indicate that the combinatorial criteria show slightly better performance than others with the expense of auxiliary storage. 1.