An Overview on Concept Drift Learning <s> A. TYPES OF ALGORITHMS <s> We present a new approach for dealing with distribution change and concept drift when learning from data sequences that may vary with time. We use sliding windows whose size, instead of being fixed a priori, is recomputed online according to the rate of change observed from the data in the window itself: The window will grow automatically when the data is stationary, for greater accuracy, and will shrink automatically when change is taking place, to discard stale data. This delivers the user or programmer from having to guess a time-scale for change. Contrary to many related works, we provide rigorous guarantees of performance, as bounds on the rates of false positives and false negatives. In fact, for some change structures, we can formally show that the algorithm automatically adjusts the window to a statistically optimal length. Using ideas from data stream algorithmics, we develop a time- and memory-ecient version of this algorithm, called ADWIN2. We show how to incorporate this strategy easily into <s> BIB001 </s> An Overview on Concept Drift Learning <s> A. TYPES OF ALGORITHMS <s> Concept drift constitutes a challenging problem for the machine learning and data mining community that frequently appears in real world stream classification problems. It is usually defined as the unforeseeable concept change of the target variable in a prediction task. In this paper, we focus on the problem of recurring contexts, a special sub-type of concept drift, that has not yet met the proper attention from the research community. In the case of recurring contexts, concepts may re-appear in future and thus older classification models might be beneficial for future classifications. We propose a general framework for classifying data streams by exploiting stream clustering in order to dynamically build and update an ensemble of incremental classifiers. To achieve this, a transformation function that maps batches of examples into a new conceptual representation model is proposed. The clustering algorithm is then applied in order to group batches of examples into concepts and identify recurring contexts. The ensemble is produced by creating and maintaining an incremental classifier for every concept discovered in the data stream. An experimental study is performed using (a) two new real-world concept drifting datasets from the email domain, (b) an instantiation of the proposed framework and (c) five methods for dealing with drifting concepts. Results indicate the effectiveness of the proposed representation and the suitability of the concept-specific classifiers for problems with recurring contexts. <s> BIB002 </s> An Overview on Concept Drift Learning <s> A. TYPES OF ALGORITHMS <s> It is challenging to use traditional data mining techniques to deal with real-time data stream classifications. Existing mining classifiers need to be updated frequently to adapt to the changes in data streams. To address this issue, in this paper we propose an adaptive ensemble approach for classification and novel class detection in concept drifting data streams. The proposed approach uses traditional mining classifiers and updates the ensemble model automatically so that it represents the most recent concepts in data streams. For novel class detection we consider the idea that data points belonging to the same class should be closer to each other and should be far apart from the data points belonging to other classes. If a data point is well separated from the existing data clusters, it is identified as a novel class instance. We tested the performance of this proposed stream classification model against that of existing mining algorithms using real benchmark datasets from UCI (University of California, Irvine) machine learning repository. The experimental results prove that our approach shows great flexibility and robustness in novel class detection in concept drifting and outperforms traditional classification models in challenging real-life data stream applications. <s> BIB003 </s> An Overview on Concept Drift Learning <s> A. TYPES OF ALGORITHMS <s> Learning in nonstationary environments, also known as learning concept drift, is concerned with learning from data whose statistical characteristics change over time. Concept drift is further complicated if the data set is class imbalanced. While these two issues have been independently addressed, their joint treatment has been mostly underexplored. We describe two ensemble-based approaches for learning concept drift from imbalanced data. Our first approach is a logical combination of our previously introduced Learn++.NSE algorithm for concept drift, with the well-established SMOTE for learning from imbalanced data. Our second approach makes two major modifications to Learn++.NSE-SMOTE integration by replacing SMOTE with a subensemble that makes strategic use of minority class data; and replacing Learn++.NSE and its class-independent error weighting mechanism with a penalty constraint that forces the algorithm to balance accuracy on all classes. The primary novelty of this approach is in determining the voting weights for combining ensemble members, based on each classifier's time and imbalance-adjusted accuracy on current and past environments. Favorable results in comparison to other approaches indicate that both approaches are able to address this challenging problem, each with its own specific areas of strength. We also release all experimental data as a resource and benchmark for future research. <s> BIB004
The most usual ways to handle concept drift are the following three BIB003 : (a) instance selection or window-based approach, (b) weight-based approach, and (c) ensemble of classifiers. Instance selection or window-based approaches select an appropriate set of previous data to train a classifier BIB002 . It selects instances inside of a fixed or dynamic sliding window BIB003 . These approaches assume older examples are incompatible with new data classification, so it has to forget old instances which are considered useless to handle concept drift BIB002 . Therefore, the training employs the last batch of information with the last training instances. The window of fixed size approach is the simplest rule and the window size is usually determined by the user. By having information on the time-scale of change, a window of fixed size approach is a good choice. Yet, the user is often caught in a trade-off: choosing a small window size (reflects the current distribution with fast adaptivity) or a large window size (having more instances in periods of stability with no concept drift may increase accuracy and have better generalization) BIB001 . The adaptive window approach adjusts the window size to the length of the drift  . It commonly maintains the examples up until the concept drift: in this case, it is not necessary to choose a priori and unknown parameter BIB001 . Other approaches maintain some of the examples in memory but select a training set of it for classification BIB002 . A weight-based approach weights instances and deletes the outdated training ones based on their weights BIB003 . As time passes, it considers old information increasingly irrelevant. Despite considering all instances of learning, new instances have more relevance. Within this framework, must be chosen an updateable classifier capable of weighted learning BIB002 . The ensemble of classifier combines several outputs from different learners to define a final classification BIB003 . With a dynamic set of classifiers, performance (or another metric) is observed. If performance decreases, new classifiers replace the aged and poor performing classifiers on the ensemble. Outputs from learners are combined to classify instances on classification phase, commonly with a weighted-vote mechanism BIB002 . Benefits of weighted ensembles have been studied empirically and theoretically BIB002 . Data streams can be divided into batches in window-based approaches; thus, it continuously receives batches of data. Some examples are described below  : • Full-memory: the learner employs all instances seen so far (batches), i.e., it can not ''forget'' old data (Fig. 2 ). • No-memory: the learner employs a single batch on training, i.e., the most recent of the stream (Fig. 3) . • Window of fixed size n: the learner employs n batches on training, i.e., a sliding window of size 3 is used with the most recent instances (Fig. 4 ). Ditzler and Polikar BIB004 characterized various forms of concept drift handling algorithms: • Online or Batch approaches: determined by the amount of instances considered at training phase; • Single classifier or Ensemble-based approaches: determined by the number of learners employed to decide a classification; • Incremental or Non-incremental approaches: determined by the reusing a data or not; and • Active or Passive approaches: determined by the use of a drift detection mechanism or not. After receiving an instance, the online approach updates the classifier; whereas the batch approach waits to receive plenty of instances to start learning  . Single classifiers use one learner to decide on classification phase; whereas ensemble learning combines the results of a set of concept learners with a single or weighted vote, or selecting the most significant result  . Incremental learning behaves like online learning with the model update as instances arrive; whereas non-incremental reuses data on learning phase. Active drift detection observes the stream to search for changes and determine whether and when a drift occurs: after a drift, it warns the learner to take the correct action. Passive drift detection considers drift may occur constantly or occasionally, therefore continually updates the learner as data arrive BIB004 .