Classification trees are a powerful tool for mining non-stationary data streams. In these situations, mas sive data are constantly generated at high speed and the underlying target function can change over time. The iadem family of algorithms is based on Hoeffding’s and Chernoff’s bounds and induces online deci sion trees from data streams, but is not able to handle concept drift. This study extends this family to deal with time-changing data streams. The new online algorithm, named iadem-3, performs two main actions in response to a concept drift. Firstly, it resets the variables affected by the change and main tains unbroken the structure of the tree, which allows for changes in which consecutive target functions are very similar. Secondly, it creates alternative models that replace parts of the main tree when they significantly improve the accuracy of the model, thereby rebuilding the main tree if needed. An online change detector and a non-parametric statistical test based on Hoeffding’s bounds are used to guaran tee this significance. A new pruning method is also incorporated in iadem-3, making sure that all split tests previously installed in decision nodes are useful. The learning model is also viewed as an ensem ble of classifiers, and predictions of the main and alternative models are combined to classify unlabeled examples. iadem-3 is empirically compared with various well-known decision tree induction algorithms for concept drift detection. We empirically show that our new algorithm often reaches higher levels of accuracy with smaller decision tree models, maintaining the processing time bounded, irrespective of the number of instances processed.

Incremental and online learning algorithms are more relevant in the data mining context because of the increasing necessity to process data streams. In this context, the target function may change overtime, an inherent problem of online learning (known as concept drift). In order to handle concept drift regardless of the learning model, we propose new methods to monitor the performance metrics measured during the learning process, to trigger drift signals when a significant variation has been detected. To monitor this performance, we apply some probability inequalities that assume only independent, univariate and bounded random variables to obtain theoretical guarantees for the detection of such distributional changes. Some common restrictions for the online change detection as well as relevant types of change (abrupt and gradual) are considered. Two main approaches are proposed, the first one involves moving averages and is more suitable to detect abrupt changes. The second one follows a widespread intuitive idea to deal with gradual changes using weighted moving averages. The simplicity of the proposed methods, together with the computational efficiency make them very advantageous. We use a Naive Bayes classifier and a Perceptron to evaluate the performance of the methods over synthetic and real data.