An incremental decision tree algorithm is an onlinemachine learning algorithm that outputs a decision tree. Many decision tree methods, such as C4.5, construct a tree using a complete dataset. Incremental decision tree methods allow an existing tree to be updated using only new individual data instances, without having to re-process past instances. This may be useful in situations where the entire dataset is not available when the tree is updated, the original data set is too large to process or the characteristics of the data change over time.
Systems where a user-interpretable output is desired.
Methods
Here is a short list of incremental decision tree methods, organized by their parent algorithms.
CART family
is a nonincremental decision tree inducer for both classification and regression problems. developed in the mathematics and statistics communities. CART traces its roots to AID
incremental CART Crawford modified CART to incorporate data incrementally.
ID3/C4.5 family
and C4.5 were developed by Quinlan and have roots in Hunt's Concept Learning System The ID3 family of tree inducers was developed in the engineering and computer science communities.
ID3' was suggested by Schlimmer and Fisher. It was a brute-force method to make ID3 incremental; after each new data instance is acquired, an entirely new tree is induced using ID3.
ID4 could incorporate data incrementally. However, certain concepts were unlearnable, because ID4 discards subtrees when a new test is chosen for a node.
ID5 didn't discard subtrees, but also did not guarantee that it would produce the same tree as ID3.
ID5R output the same tree as ID3 for a dataset regardless of the incremental training order. This was accomplished by recursively updating the tree's subnodes. It did not handle numeric variables, multiclass classification tasks, or missing values.
ID6MDL an extended version of the ID3 or ID5R algorithms.
ITI is an efficient method for incrementally inducing decision trees. The same tree is produced for a dataset regardless of the data's presentation order, or whether the tree is induced incrementally or non incrementally. It can accommodate numeric variables, multiclass tasks, and missing values. Code is available on the web.
There were several incrementalconcept learning systems that did not build decision trees, but which predated and influenced the development of the earliest incremental decision tree learners, notably ID4. Notable among these was Schlimmer and Granger's STAGGER, which learned disjunctive concepts incrementally. STAGGER was developed to examine concepts that changed over time. Prior to STAGGER, Michalski and Larson investigated an incremental variant of AQ, a supervised system for learning concepts in disjunctive normal form. Experience with these earlier systems and others, to include incremental tree-structured unsupervised learning, contributed to a conceptual framework for evaluating incremental decision tree learners specifically, and incremental concept learning generally, along four dimensions that reflect the inherent tradeoffs between learning cost and quality: cost of knowledge base update, the number of observations that are required to converge on a knowledge base with given characteristics, the total effort that a system exerts, and the quality of the final knowledge base. Some of the historical context in which incremental decision tree learners emerged is given in Fisher and Schlimmer, and which also expands on the four factor framework that was used to evaluate and design incremental learning systems.
VFDT Algorithm
Very Fast Decision Trees learner reduces training time for large incremental data sets by subsampling the incoming data stream.
VFDT
CVFDT can adapt to concept drift, by using a sliding window on incoming data. Old data outside the window is forgotten.
VFDTc extends VFDT for continuous data, concept drift, and application of Naive Bayes classifiers in the leaves.
VFML is a toolkit and available on the web. . It was developed by the creators of VFDT and CVFDT.
EFDT Algorithm
The Extremely Fast Decision Tree learner is statistically more powerful than VFDT, allowing it to learn more detailed trees from less data. It differs from VFDT in the method for deciding when to insert a new branch into the tree. VFDT waits until it is confident that the best available branch is better than any alternative. In contrast, EFDT splits as soon as it is confident that the best available branch is better than the current alternative. Initially, the current alternative is no branch. This allows EFDT to insert branches much more rapidly than VFDT. During incremental learning this means that EFDT can deploy useful trees much sooner than VFDT. However, the new branch selection method greatly increases the likelihood of selecting a suboptimal branch. In consequence, EFDT keeps monitoring the performance of all branches and will replace a branch as soon as it is confident there is a better alternative.
