ID5R Algorithm

An ID5R Algorithm is a Decision Tree Algorithm that is an based on an incremental variant of the ID3.

• Context:
  • It was first developed by Utgoff (1989).
• Example(s):
  • …
• Counter-Example(s):
  • ID6MDL,
  • ID3,
  • ID4.
• See: Online Learning System, Machine Learning System, Classification System, Cumulative Learning System, Inductive Learning System.

---

---

References

2022a

• (Wikipedia, 2022) ⇒ https://en.wikipedia.org/wiki/Incremental_decision_tree Retrieved:2022-4-2.
  • 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.

2022b

• (Wikipedia, 2022) ⇒ https://en.wikipedia.org/wiki/Incremental_decision_tree#ID3 Retrieved:2022-4-2.
  • ID3 (1986) Quinlan, J. R. (1986) Induction of Decision Trees. Machine Learning 1(1), 81-106. and C4.5 (1993) Quinlan, J. R. (1993) C4.5: Programs for machine learning. San Mateo, CA: Morgan Kaufmann. were developed by Quinlan and have roots in Hunt's Concept Learning System (CLS, 1966) Hunt, E. B., Marin, J., & Stone, P. J. (1966) Experiments in induction. New York: Academic Press. The ID3 family of tree inducers was developed in the engineering and computer science communities.
    • ID3' (1986)Schlimmer, J. C., & Fisher, D. (1986) A case study of incremental concept induction. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 496-501). Philadelphia, PA: Morgan Kaufmann. 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) Utgoff, P. (1988) ID5: An incremental ID3. Fifth International Conference on Machine Learning, pp. 107-120. Morgan Kaufmann Publishers. didn't discard subtrees, but also did not guarantee that it would produce the same tree as ID3.
    • ID5R (1989) Utgoff, P. E. (1989) Incremental induction of decision trees. Machine Learning 4, 161-186. 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 (2007) Kroon, M., Korzec, S., Adriani, P. (2007) ID6MDL: Post-Pruning Incremental Decision Trees. an extended version of the ID3 or ID5R algorithms.
    • ITI (1997) Utgoff, P. E., Berkman, N. C., & Clouse, J. A. (1997) Decision tree induction based on efficient tree restructuring. Machine Learning 29, 5-44. 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. [1] note: ID6NB (2009) Appavu, S., & Rajaram, R. (2009) Knowledge-based system for text classification using ID6NB algorithm. Knowledge-based systems 22 1-7. is not incremental.

1989

• (Utgoff, 1989) ⇒ Utgoff, P. E. (1989). "Incremental induction of decision trees". Machine learning, 4(2), 161-186. doi: 10.1023/A:1022699900025
  • ABSTRACT: This article presents an incremental algorithm for inducing decision trees equivalent to those formed by Quinlan's nonincremental ID3 algorithm, given the same training instances. The new algorithm, named ID5R, lets one apply the ID3 induction process to learning tasks in which training instances are presented serially. Although the basic tree-building algorithms differ only in how the decision trees are constructed, experiments show that incremental training makes it possible to select training instances more carefully, which can result in smaller decision trees. The ID3 algorithm and its variants are compared in terms of theoretical complexity and empirical behavior.

---