Most decision tree

Decision tree learning

Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model which maps observations about an item to conclusions about the item's target value. More descriptive names for such tree models are classification trees or regression trees...

 methods take a complete data set and build a tree using that data. This tree cannot be changed if new data is acquired later.

Incremental decision trees are built using methods that allow an existing tree to be updated or revised using new, individual data instances. This is useful in several situations: a) the entire dataset is not available at the time the original tree is built, b) the original data set is too large to process, or c) the characteristics of the data change over time.

Applications

• On-line learning
• Data streams
• Concept drift
  Concept drift
  In predictive analytics and machine learning, the concept drift means that the statistical properties of the target variable, which the model is trying to predict, change over time in unforeseen ways. This causes problems because the predictions become less accurate as time passes.The term concept...
  
  
• Data which can be modeled well using a hierarchical model.
• Systems where a user-interpretable output is desired.

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)

• incremental CART (1989) Crawford modified CART to incorporate data incrementally.

ID3/C4.5 family

ID3

ID3 algorithm

In decision tree learning, ID3 is an algorithm used to generate a decision tree invented by Ross Quinlan. ID3 is the precursor to the C4.5 algorithm.-Algorithm:The ID3 algorithm can be summarized as follows:...

 (1986) and C4.5 (1993) were developed by Quinlan

Ross Quinlan

John Ross Quinlan is a computer science researcher in data mining and decision theory. He has contributed extensively to the development of decision tree algorithms, including inventing the canonical C4.5 and ID3 algorithms...

 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.

• ID3' (1986) 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 (1986) could incorporate data incrementally. However, certain concepts were unlearnable, because ID4 discards subtrees when a new test is chosen for a node.
• ID5 (1988) didn't discard subtrees, but also did not guarantee that it would produce the same tree as ID3.
• ID5R (1989) 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
  Multiclass classification
  In machine learning, multiclass or multinomial classification is the problem of classifying instances into more than two classes.While some classification algorithms naturally permit the use of more than two classes, others are by nature binary algorithms; these can, however, be turned into...
  
   tasks, or missing values.
• ID6MDL (2007) an extended version of the ID3 or ID5R algorithms.
• ITI (1997) 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 (batch mode). It can accommodate numeric variables, multiclass tasks, and missing values. Code is available on the web. http://www-lrn.cs.umass.edu/iti/index.html

note: ID6NB (2009) is not incremental.

STAGGER

Schlimmer and Granger's STAGGER (1986) was an early incremental learning system. It was developed to examine concepts that changed over time (concept drift

Concept drift

In predictive analytics and machine learning, the concept drift means that the statistical properties of the target variable, which the model is trying to predict, change over time in unforeseen ways. This causes problems because the predictions become less accurate as time passes.The term concept...

).

VFDT

Very Fast Decision Trees learner reduces training time for large incremental data sets by subsampling the incoming data stream.

• VFDT (2000)
• CVFDT (2001) can adapt to concept drift
  Concept drift
  In predictive analytics and machine learning, the concept drift means that the statistical properties of the target variable, which the model is trying to predict, change over time in unforeseen ways. This causes problems because the predictions become less accurate as time passes.The term concept...
  
  , by using a sliding window on incoming data. Old data outside the window is forgotten.
• VFDTc (2006) extends VFDT for continuous data, concept drift, and application of Naive Bayes classifiers in the leaves.
• VFML (2003) is a toolkit and available on the web. http://www.cs.washington.edu/dm/vfml/. It was developed by the creators of VFDT and CVFDT.

See also

• Decision tree
  Decision tree learning
  Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model which maps observations about an item to conclusions about the item's target value. More descriptive names for such tree models are classification trees or regression trees...
  
  
• Online learning
• Concept drift
  Concept drift
  In predictive analytics and machine learning, the concept drift means that the statistical properties of the target variable, which the model is trying to predict, change over time in unforeseen ways. This causes problems because the predictions become less accurate as time passes.The term concept...
  
  
• Machine Learning
  Machine learning
  Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
  
  

External links

• ITI code. http://www-lrn.cs.umass.edu/iti/index.html
• VFML code. http://www.cs.washington.edu/dm/vfml/