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:
- We start at a root node, growing the tree by adding nodes one at a time.
- 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:
- 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?
- If there are multiple regions that can be split, how does the algorithm decide which node (=region) to split into two daughter nodes?