Concept Drift in Decision Trees Learning from Data Streams
João Manuel Portela da Gama, Pedro Medas, Pedro Pereira Rodrigues, Rua Campo Alegre · 2004
ABSTRACT: This paper presents the Ultra Fast Forest of Trees (UFFT) system. It is an incremental algorithm that works online, processing each example in constant time, and performing a single scan over the training examples. The system has been designed for numerical data. It uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. For multi-class problems the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees. To detect concept drift, we maintain, at each inner node, a naive-Bayes classifier. Statistical theory states that while the distribution of the examples is stationary, the online error of naive-Bayes will decrease, otherwise, the test installed at this node is not appropriate for the actual distribution of the examples. When this occurs, the entire sub tree rooted at this node is pruned. The use of naive-Bayes classifiers at leaves to classify test examples, and the use of naive-Bayes classifiers at decision nodes to detect changes in the distribution of the examples are directly obtained from the sufficient statistics required to compute the splitting criteria, without any additional computations. This aspect is a main advantage in the context of high-speed data streams. The experimental results show a good performance at the change of concept detection and also with learning the new concept. KEYWORDS: Concept Drift, Forest of Trees, Data Streams.