An Algorithm for Constructing Optimal Binary Decision Trees
- 1 September 1977
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-26 (9) , 905-916
- https://doi.org/10.1109/tc.1977.1674938
Abstract
We consider the problem of optimally partitioning an n-dimensional lattice, L = L, X ... X LN, where Lj is a one-dimensional lattice with kj elements, by means of a binary tree into specified (labeled) subsets of L. Such lattices arise from problems in pattern classification, in nonlinear regression, in defining logical equations, and a number of related areas. When viewed as the partitioning of a vector space, each point in the lattice corresponds to a subregion of the space which is relatively homogeneous with respect to classification or range of a dependent variable. Optimality is defined in terms of a general cost function which includes the following: 1) min-max path length (i. e., minimize the maximum number of nodes traversed in making a decision); 2) minimum number of nodes in the tree; and 3) expected path length. It is shown that an optimal tree can be recursively constructed through the application of invariant imbedding (dynamic programming). An algorithm is detailed which embodies this recursive approach. The algorithm allows the assignment of a "don't care" label to elements of L.Keywords
This publication has 2 references indexed in Scilit:
- A Partitioning Algorithm with Application in Pattern Classification and the Optimization of Decision TreesIEEE Transactions on Computers, 1973
- A Nonparametric Partitioning Procedure for Pattern ClassificationIEEE Transactions on Computers, 1969