Advanced Decision Trees - Data Mining with Decision Trees: Theory and Applications - page 169

Fig. 11.2 The LazyDT algorithm.
unnecessarily. Such fragmentation reduces the significance of tests at lower
levels since they are based on fewer instances. Classification paths, built for
a specific instance may be much shorter and hence may provide a better
explanation.
A generic pseudo-code of the LazyDT algorithm is described in
Figure 11.2. The lazy decision tree algorithm, which gets the test instance
as part of the input, follows a separate-and-classify methodology: a test is
selected and the sub-problem containing the instances with the same test
outcome as the given instance is then solved recursively.
11.4 Option Tree
Regular decision trees make a single test at each node and trace a single
path corresponding to test outcomes until a leaf is reached and a prediction
is made. Option decision trees (also known as and-or trees), first introduced
by Buntine (1992), generalize regular decision trees by allowing option
nodes in addition to decision nodes; such nodes make it possible to conduct
several possible tests instead of the commonly used single test. Classification
is similar to regular decision trees, except that a rule is applied to option
nodes to combine the predictions of the children nodes.
There are several reasons for using option trees. Option decision trees
can reduce the error of decision trees in handling real-world problems
by combining multiple options. This is similar to what we find when
implementing ensemble methods that learn multiple models and combine
the predictions. However, unlike ensemble methods, an option decision tree
yields a single tree, which is a compact representation of many possible
trees and which can be easily interpreted by humans. The myopic nature of
top-down classification tree inducers and the stability of the classifiers are
the reasons for the option decision trees improved performance compared
to regular decision trees.