Tree induction algorithm
tree induction algorithm
This article describes the basic tree induction algorithm used by ID3 and successors. The basic idea is to pick an attribute A with values a1, a2, ..., ar, split the training instances into subsets Sa1, Sa2, ..., Sar consisting of those instances that have the corresponding attribute value. Then if a subset has only instances in a single class, that part of the tree stops with a leaf node labelled with the single class. If not, then the subset is split again, recursively, using a different attribute.
This leaves the question of how to choose the best attribute to split on at any branch node. This issue is handled in the article on splitting criterion in ID3.