An incremental decision tree algorithm is an online machine 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 (i.e. the data was not stored), the original data set is too large to process or the characteristics of the data change over time.
Contents
Applications
Methods
Here is a short list of incremental decision tree methods, organized by their (usually non-incremental) parent algorithms.
CART family
CART (1984) 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 (1963)
ID3/C4.5 family
ID3 (1986) and C4.5 (1993) were developed by Quinlan and have roots in Hunt's Concept Learning System (CLS, 1966) The ID3 family of tree inducers was developed in the engineering and computer science communities.
note: ID6NB (2009) is not incremental.
Other Incremental Learning Systems
There were several incremental concept 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 (1986), which learned disjunctive concepts incrementally. STAGGER was developed to examine concepts that changed over time (concept drift). Prior to STAGGER, Michalski and Larson (1978) investigated an incremental variant of AQ (Michalski, 1973), a supervised system for learning concepts in disjunctive normal form (DNF). 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: (1) cost of knowledge base update, (2) the number of observations that are required to converge on a knowledge base with given characteristics, (3) the total effort (as a function of the first two dimensions) that a system exerts, and the (4) quality (often consistency) of the final knowledge base. Some of the historical context in which incremental decision tree learners emerged is given in Fisher and Schlimmer (1988), and which also expands on the four factor framework that was used to evaluate and design incremental learning systems.
VFDT
Very Fast Decision Trees learner reduces training time for large incremental data sets by subsampling the incoming data stream.