Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents an hybrid adaptive system for induction of forest of trees from data streams. The Ultra Fast Forest Tree system (UFFT) is an incremental algorithm, with constant time for processing each example, works online, and uses the Hoeffding bound to decide when to install a splitting test in a leaf leading to a decision node. Our system has been designed for continuous data. It uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. The number of examples required to evaluate the splitting criteria is sound, based on the Hoeffding bound. For multiclass problems, the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees. During the training phase the algorithm maintains a short term memory. Given a data stream, a fixed number of the most recent examples are maintained in a data-structure that supports constant time insertion and deletion. When a test is installed, a leaf is transformed into a decision node with two descendant leaves. The sufficient statistics of these leaves are initialized with the examples in the short term memory that will fall at these leaves. We study the behavior of UFFT in different problems. The experimental results shows that UFFT is competitive against a batch decision tree learner in large and medium datasets.

REFERENCES

• 1: C. Blake, E. Keogh, and C. J. Merz. UCI repository of Machine Learning databases, 1999.
• 2: Leo Breiman. Random forests. Technical report, University of Berkeley, 2002.
• 3: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 4: Johannes Fürnkranz, Round robin classification, The Journal of Machine Learning Research, 2, p.721-747, 3/1/2002 [doi>10.1162/153244302320884605]
• 5: Joao Gama, An Analysis of Functional Trees, Proceedings of the Nineteenth International Conference on Machine Learning, p.155-162, July 08-12, 2002
• 6: Jonathan Gratch. Sequential inductive learning. In Proc. Thirteenth National Conference on Artificial Intelligence, volume 1, pages 779--786, 1996.
• 7: João Gama , Ricardo Rocha , Pedro Medas, Accurate decision trees for mining high-speed data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956813]
• 8: Dimitrios Kalles , Tim Morris, Efficient incremental induction of decision trees, Machine Learning, v.24 n.3, p.231-242, Sept. 1996 [doi>10.1023/A:1018295910873]
• 9: J. Kittler. Combining classifiers: A theoretical framework. Pattern analysis and Applications, Vol. 1, No. 1, 1998.
• 10: R. Kohavi. Scaling up the accuracy of naive Bayes classifiers: a decision tree hybrid. In Proc. 2nd International Conference on Knowledge Discovery and Data Mining. AAAI Press, 1996.
• 11: W.-Y. Loh and Y.-S. Shih. Split selection methods for classification trees. Statistica Sinica, 1997.
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 14: P. Utgoff. Perceptron trees - a case study in hybrid concept representation. In Proc. Seventh National Conference on Artificial Intelligence. Morgan Kaufmann, 1988.
• 15: Paul E. Utgoff , Neil C. Berkman , Jeffery A. Clouse, Decision Tree Induction Based on Efficient Tree Restructuring, Machine Learning, v.29 n.1, p.5-44, Oct. 1997 [doi>10.1023/A:1007413323501]

INDEX TERMS

Keywords:
Hybrid Forest of Trees, data streams