Algorithms for training decision trees

Now that we have understood how a decision tree works, we'll want to address the issue of how we can train one using some data. There are several algorithms that have been proposed to build decision trees, and in this section we will present a few of the most well-known. One thing we should bear in mind is that whatever tree-building algorithm we choose, we will have to answer four fundamental questions:

• For every node (including the root node), how should we choose the input feature to split on and, given this feature, what is the value of the split point?

• How do we decide whether a node should become a leaf node or if we should make another split point?

• How deep should our tree be allowed to become?

• Once we arrive at a leaf node, what value should we predict?

Note

A great introduction to decision trees is Chapter 3 of Machine Learning, Tom Mitchell. This book was probably the first comprehensive introduction to machine learning and is well worth reading...