Access Restriction

Author Cockett, J. R. B. ♦ Herrera, J. A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1990
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The reduction algorithm is a technique for improving a decision tree in the abseence of aproecise cost criterion. The result of applying the algorithm is an irreducible tree that is no less efficient than the original, and may be more efficient. Irreducible trees arise in discrete decision theory as an algebraic form for decision trees. This form has significant computational properties. In fact, every irreducible is optimal with respect to some expected testing cost criterion and is strictly better than any given distinct tree with respect to some criterion.Many irreducibles are decision equivalent to a given tree; onely some of these are $\textit{reductions}$ of the tree. The reduction algorithm is a particular way of finding one of these. It tends to preserve the overall structure of the tree by reducing the subtrees first.A bound on the complexity of this algorithm with input tree $\textit{t}$ is $\textit{O}(hgt9\textit{t})2).$ $usize(\textit{t})$ is the $\textit{uniform}$ size of the tree (the number of leaves less one) and $hgt(\textit{t})$ is the height of the tree. This means that decision tree reduction has the same worst-case order of complexity as most heuristic methods for building suboptimal trees. While the purpose of using heuristics is often rather different, such comparisons are an indication of the efficiency of the reduction algorithms.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1990-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 37
Issue Number 4
Page Count 28
Starting Page 815
Ending Page 842

Open content in new tab

   Open content in new tab
Source: ACM Digital Library