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

Fig. 11.5 Algorithm for calculating lookahead splitting criterion.

11.5 Lookahead

The splitting criteria in regular top-down decision tree inducers is usually
greedy and local. Fixed-depth lookahead search is a standard technique
for improving greedy algorithms. More extensive search quickly leads to
intolerable time consumption. Moreover, limited lookahead search does not
produce significantly better decision trees [ Murthy and Salzberg (1995) ] .
On average, it produces trees with approximately the same generalization
error and size as greedy induction. In fact, pruning methods are usually at
least as beneficial as limited lookahead.
Figure 11.5 specifies an algorithm of lookahead splitting criterion by
wrapping a regular splitting criterion (denoted as SimpleSplitCriterion).
Note that the proposed algorithm performs a lookahead of levels.

LSID3 [ Esmeir and Markovitch (2004) ] , a variation of the well-known
ID3 algorithm, invests more resources for making better split decisions. For
every possible candidate split, LSID3 estimates the size of the resulting
subtree, and prefers the one with the smallest expected size. For this
purpose, it uses a sample of the space of trees rooted at the evaluated
attribute. The sample is obtained by selecting attributes with a probability
proportional to its information gain.

Depth

11.6 Oblique Decision Trees

Regular top-down decision trees inducers, such as C4.5, use only a single
attribute in each node. Consequently these algorithms are partitioning