Decision Trees

Decision Trees (DTs) are a non-parametric supervised learning method used for classification and regression. The goal is to create a model that predicts the value of a target variable by learning simple decision rules inferred from the data features.

Here is a example of decision tree for a person entering in a restaurant will wait for order or not. 0-10,10-30,30-60,>60 minutes are waiting time for order. "T" - Patron will wait for order and "F"- he won't.

Decision tree algorithm first developed in late 1970s and early 1980s known as ID3(Iterative Dechotomiser). This work was expanded on earlier work on Concept learning system, later published as C4.5. In 1984, L.Breiman introduced CART(Classification and regression tree), which described the generation of the binary decision tree. ID3 and CART follow a approach for learning decision tree from training tuples.

All these adopt a greedy(i.e. nonbacktracking) approach in which decision trees are constructed in a top-down recursive divide-and-conquer manner.