DECISION-TREE-LEARNING

AIMA3e

function DECISION-TREE-LEARNING(examples, attributes, parent_examples) returns a tree
 if examples is empty then return PLURALITY-VALUE(parent_examples)
 else if all examples have the same classification then return the classification
 else if attributes is empty then return PLURALITY-VALUE(examples)
 else
   A ← argmax_{a ∈ attributes} IMPORTANCE(a, examples)
   tree ← a new decision tree with root test A
   for each value v_k of A do
     exs ← { e : e ∈ examples and e.A = v_k }
     subtree ← DECISION-TREE-LEARNING(exs, attributes − A, examples)
     add a branch to tree with label (A = v_k) and subtree subtree
   return tree

---

Figure ?? The decision-tree learning algorithm. The function IMPORTANCE is described in Section ??. The function PLURALITY-VALUE selects the most common output value among a set of examples, breaking ties randomly.