|
Incremental induction of decision trees is a method for the task of concept learning (supervised learning). When a new training example is entered it is classified by the decision tree. If it is incorrectly classified then the tree is revised. Restructuring the tree can be done by storing all training examples or by maintaining statistics associated with nodes in the tree.
Given:
A sequence of classified examples in attribute-value representation, where the set of classes is finite.
The ID4 algorithm
The ID4 algorithm builds decision trees incrementally. A decision tree is updated when new instances become available. A non-incremental algorithm could also be used, simply by storing all examples and running the method again on all data. This requires storing all data.
ID5R and IDL maintain statistics on the distributions of instances over attributes at each node in the tree. When a new example is entered then the effect of the training example on this distribution is computed and the method checks if the tree must be revised by replacing the current node by a different attribute. This can be done top-down, recursively for each subtree, or bottom-up.
|
