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. 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. This means that decision tree reduction has the same worst-case order of complexity as most heuristic methods for building suboptimal trees.