Decision tree classifier and Hunt's algorithm

A decision tree classifier builds a tree-structured model: internal nodes test an attribute, branches are test outcomes, leaves give the class. To classify a record, the path from the root is followed according to its attribute values. It is built by recursive partitioning and can be turned into IF-THEN rules.

Example

Buys-computer data (14 tuples: 9 yes, 5 no) gives:

            age?
       /     |       \
    young  middle   senior
      |      |         |
  student?  YES    credit_rating?
   /   \             /       \
  no   yes        fair    excellent
  NO   YES        YES        NO

A record (young, student = yes) reaches the leaf YES.

Hunt's algorithm

Hunt's algorithm is the basis of ID3, C4.5 and CART. It grows the tree recursively. Let Dₜ be the set of training records at node t and y = {y₁, y₂, …, y_c} the class labels.

1. If all records in Dₜ belong to the same class yₜ, then t is a leaf labelled yₜ.
2. If Dₜ is empty, t is a leaf labelled with the majority (default) class of its parent.
3. If Dₜ contains records of more than one class, select an attribute test condition to split Dₜ into smaller subsets, create a child node for each outcome, distribute the records, and apply the algorithm recursively to each child.

Additional rules are needed: if all records have identical attribute values but different classes (no split is possible), make a leaf with the majority class; and a best-split criterion (information gain, gain ratio or Gini index) is used to choose the test in step 3. The tree is grown in a greedy way, and pruning is done afterwards to avoid overfitting.