Inductive Learning Algorithm

810:161

Artificial Intelligence

input:

• examples, a training set
• attributes, a set of attributes
• default, the default goal predicate value

output: a decision tree

1. if examples is empty, then return default

2. if all of the remaining examples have the same classification, then return that value

3. if attributes is empty, then return the most common classification of the remaining examples

4. choose the attribute a that best discriminates among the remaining examples

5. create a tree t with a as its root

6. for each possible value v of a
   • select the subset of examples ex having value(a) = v
   • let subtree sub be the result of recursively calling the induction algorithm with ex, (attributes - a), and the most common classification of ex
   • add a branch to t with label v and subtree sub

7. return t