next up previous
Next: Explanation Based Learning (EBL) Up: Inductive Learning Previous: Version Spaces

Decision Trees

Quinlan in his ID3 system (986) introduced the idea of decision trees.

ID3 is a program that can build trees automatically from given positive and negative instances.

Basically each leaf of a decision tree asserts a positive or negative concept. To classify a particular input we start at the top and follow assertions down until we reach an answer (Fig 28)


Fig. 28 Edible Mushroom decision tree

Building decision trees

Adding new nodes

When assembling the tree we need to choose when to add a new node:

Decision tree advantages: