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
- ID3 uses an iterative method.
- Simple trees preferred as more accurate classification is afforded.
- A random choice of samples from training set chosen for initial assembly of tree -- the window subset.
- Other training examples used to test tree.
- If all examples classified correctly stop.
- Otherwise add a number of training examples to window and start again.
