Machine learning basics (part 13): Decision or classification trees

Next we are going to consider a rather different approach from those presented so far to machine learning that use one of the most common and important data structures, the binary tree. Generally, the computational cost of making the tree is fairly low, but the cost of using it is even lower, O(log m), where m is the number of nodes. This is important for machine learning, since querying the trained model should be as fast as possible since it happens more often and the result is often wanted immediately. Trees also have other benefits, such as the fact they are easy to understand.

In terms of optimisation and search, decision trees use a greedy heuristic to make search, evaluating the possible options at the current stage of learning and making the one that seems optimal at the point. This works well a large amount of the time. Let us look at the example of student life in Fig. 7.1. First, one checks whether there is party and decides accordingly. Second, in the case of no party, it is good to check whether some deadline is close. If this is urgent, it is good to study, but otherwise selections are to be lazy or not, i.e. to study, or go to pub.

Decision trees can be turned into a set of logical conjunctions, if-then rules, that then go into program code simply: