I am reading Pattern Matching and Machine Learning by Bishop at the moment. The chapter about decision trees states that to train a decision tree, one can use a greedy algorithm. The book describes the algorithm as follows:

  1. We start at a root node, growing the tree by adding nodes one at a time.
  2. For every region that can be split we decide how to split the region like so:

there is a choice of the $D$ input variables to split, as well as the value of the threshold. The joint optimization of the choice of region to split, and the choice of input variable and threshold, can be done efficiently by exhaustive search, noting that, for a given choice of split variable and threshold, the optimal choice of predictive variable is given by the local average of the data

Two things are unclear to me:

  1. How exactly does the exhaustive search work? In particular, if one of the features, i.e. input variables, is continuous, then how does a exhaustive search over a continuous search space work? Moreover, what is the fitness function for the exhaustive search. That is, how does the algorithm decide which feature/threshold combination is best to split?
  2. If there are multiple regions that can be split, how does the algorithm decide which node (=region) to split into two daughter nodes?

1 Answer 1

  1. Your data can be discrete or continuous, but it is finite (say $N$ points). First, you sort the values (for that feature) and decide which one of the $N-1$ split points is the best one. For each feature/threshold, depending on the decision tree algorithm (e.g. C4.5) metrics like Information Gain, Gini Index are used and the feature whose gain is the largest is chosen for split for a specific node.

  2. This is similar to (1), the nodes with largest gains acquired via splitting are in general splitted first. This is exhaustive since you need to analyze the aftermath of each node being split.

This is a greedy approach since we always bet on quick and large gains.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.