ID3 (Inductive Decision tree algorithm 3)
- Well-known Concept - Decision Tree algorithm using a top-down greedy search through the hypothesis space (s.309).
- Designed to handle large training sets with many attributes (s.309).
- Tries to generate fairly simple trees but is not guaranteed to produce the best one (s.309); finding the smallest tree is intractable, ID3 is a simple heuristic for finding small trees (s.308).
- Search heuristic: central choice = which attribute to test at each node, i.e. the one most useful for classifying; measured by Concept - Information Gain (s.310).
Algorithm (s.307)
node = root; main loop:
- Decide the best attribute for the next node;
- For each value of create a new descendant;
- Partition the training examples to the leaf nodes;
- IF training examples are perfectly classified THEN STOP; ELSE iterate over the new leaf nodes.
Related
Concept - Decision Tree | Concept - Entropy | Concept - Gain Ratio | Concept - Gini Impurity