A Decision-Based Dynamic Ensemble Selection Method for Concept Drift
Regis Antonio Saraiva Albuquerque Albert Franca Josua Costa Eulanda Miranda dos Santos Robert Sabourin Rafael Giusti






A Decision-Based Dynamic Ensemble Selection Method for Concept Drift

FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas - Edital 009/2017 and Samsung Electronics of Amazonia Ltda, under the terms of Federal Law n^o 8.387/1991, through agreement  n^o  003, signed with  ICOMP/UFAM.

    Régis Antônio Saraiva Albuquerque
Federal University of Amazonas

Manaus, Brazil 

regis.albuquerque1@gmail.com
Albert França Josuá Costa
Federal Institute of Amazonas 

Manaus, Brazil 

albert.costa@ifam.edu.br
Eulanda Miranda dos Santos
Federal University of Amazonas

Manaus, Brazil 

emsantos@icomp.ufam.edu.br
Robert Sabourin
École de Technologie Supérieure 

Montreal, Canada 

Robert.Sabourin@etsmtl.ca
Rafael Giusti
Federal University of Amazonas

Manaus, Brazil 

rgiusti@icomp.ufam.edu.br

    
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





We propose an online method for concept drift detection based on dynamic classifier ensemble selection. The proposed method generates a pool of ensembles by promoting diversity among classifier members and chooses expert ensembles according to global prequential accuracy values. Unlike current dynamic ensemble selection approaches that use only local knowledge to select the most competent ensemble for each instance, our method focuses on selection taking into account the decision space. Consequently, it is well adapted to the context of drift detection in data stream problems. The results of the experiments show that the proposed method attained the highest detection precision and the lowest number of false alarms, besides competitive classification accuracy rates, in artificial datasets representing different types of drifts. Moreover, it outperformed baselines in different real-problem datasets in terms of classification accuracy. 



concept drift, dynamic ensemble selection




§ INTRODUCTION

Practical tasks, such as identification of customer preferences, Internet log analysis, among others, are examples of data stream problems. In this context, the so-called concept drift phenomenon may occur, since when data are continuously generated in streams, data and target concepts may change over time. Algorithms designed to deal with drift may be divided into two main groups: (1) online - when one instance is learned at a time upon arrival; and (2) block-based - when chunks of samples are presented from time to time <cit.>. Online methods are very useful in data stream environments, especially due to three main reasons:  samples arrive sequentially; data usually must be processed in high volumes at fast paces; and each data instance is read only once. 

Different categories of online methods are available in the literature. Drift detectors are common solutions. They focus on monitoring whether the class distribution is stable over time by observing the predictions of a classifier <cit.>. Therefore, it is assumed that one instance is processed and its true label is available right after its classification. This scenario is described as an operational setting whose availability of the ground truth occurs in the next time step, as in food sales prediction <cit.>. 

Online learning ensembles have also been investigated as a strategy to tackle the drift problem. These methods update their knowledge base by adding, removing, or updating classifiers usually in a blind manner, i.e. they do not provide an explicit mechanism to
detect concept drift. However, there are also informed ensemble-based methods. In this case, the explicit drift detection mechanism mainly relies on employing an auxiliary drift detector <cit.>, such as in Leveraging Bagging <cit.>, which generates an ensemble of classifiers using a modified version of Online Bagging <cit.> and employs ADWIN (Adaptive Window algorithm <cit.>) to detect drift. Moreover, some of these ensemble methods allow configurable drift detectors. In this case, most of the drift detectors available in the literature may be used internally <cit.>. For instance, Boosting-like Online Learning Ensemble (BOLE) <cit.>, which is a modified version of Online Boosting <cit.>, uses a configurable drift detector, such as ADWIN or DDM (The Drift Detection Method) <cit.>.

These previous works on informed online learning ensembles have two characteristics in common: 1) they encourage diversity only implicitly - by using algorithms such as the online versions of Bagging and Boosting; and 2) they generate only one ensemble of classifiers. However, by explicitly promoting diversity, one may better cope with drift and be more robust to false alarms, since it has been shown that different levels of ensemble diversity are required before and after a drift <cit.> and that diversity changes over time <cit.>. Besides, it is possible to provide different levels of ensemble diversity over time by using a population of ensemble of classifiers instead of only one ensemble, which may also explicitly encourage diversity among the population members. These hypotheses are investigated in this paper.

We propose an ensemble-based method that allows configurable drift detectors. Here, however, a diverse population of ensembles is generated, whose members' diversity may range from low to high values, since the literature shows that diversity plays probably different roles depending on the drift type and frequency. Considering the fact that we propose an online method and that a class must be estimated for each unknown instance, we need to define a strategy to maximize the possibility of making the right decision when assigning a selected class. In our method, instead of pooling the decisions of every ensemble, we perform dynamic ensemble selection (DES) to elect a single ensemble that is probably the best qualified to predict a class to a given instance. The selection is called dynamic because an expert ensemble is defined for each unknown instance as it arrives on the fly. 

In the context of DES, most methods employed in concept drift problems are block-based <cit.> and perform DES by defining local data regions (neighborhood) to estimate ensemble members' competence. However, the strategies used to generate pools of ensembles are mainly global data-oriented. The difference between local and global perspectives may prevent DES based on local competence to be highly effective <cit.>. Unlike these current works, the strategy employed in this paper for dynamic selection is decision-based, focused on selecting experts according to their accuracy calculated on the decision space. 



Experiments were performed using artificial datasets, representing different types of drift, and real datasets. Two configurations of our method, called Dynamic Ensemble Selection for Drift Detection (DESDD), were investigated. Moreover, DESDD was compared to three baselines: DDM - which employs a single classifier; Leveraging Bagging - that works with one ensemble of classifiers; and DDD - which provides a population of ensembles, but performs static selection instead of DES. The results achieved on artificial datasets show that DESDD is more stable and more effective on detecting drifts than all the baselines, since the DESDD detector is triggered more often to indicate correct detections, attaining both lower false detection and miss detection rates as a consequence. The stability and effective capacity of drift detection provided by DESDD is also confirmed with the results obtained using real datasets, since DESDD outperformed all the baselines in terms of classification accuracy in these datasets. 

This paper is organized as follows. Related work is discussed in Section <ref>. Thus, DESDD is detailed in Section <ref>. Experiments and results are summarized in Section <ref>. Finally, conclusion and future work are discussed in Section <ref>.



§ RELATED WORK


Classifier ensembles are considered the most popular technique for handling concept drift both when employing change detection mechanisms and when working in a blind adaptation manner. Several ensemble solutions for online learning rely mainly on methods that implicitly encourage diversity during training, such as the modified versions of Online Bagging and Online Boosting <cit.>. These two algorithms use a Poisson distribution to simulate their offline versions. For instance, Online Bagging updates ensemble components by presenting incrementally each instance to a component k times, where k is defined by the Poisson(1) distribution, and assigns the final prediction by majority voting.






One variant of Online Bagging is proposed in <cit.>, called Leveraging Bagging. It adds more randomization to the original version by increasing resampling and using output detection codes. The first is conducted by including the parameter λ to compute the Poisson(λ) distribution. They set λ=6 to explicitly increase diversity. The second adjustment encourages diversity due to the reduction of experts' predictions correlation. Leveraging Bagging uses ADWIN as change detector, but it can be configured to use other methods <cit.>. Summarizing, Leveraging Bagging generates a diverse ensemble of n classifiers by applying the Poisson(λ) function in a Test-Then-Train approach. In this scenario, the ensemble training is performed using data instances one at a time. When the true class of a test instance is discovered, this instance is subsequently considered as training sample. The hyperparameter λ is fixed for all iterations and majority vote is used to predict classes of unknown examples. When ADWIN indicates a drift, the worst classifier member is removed and a new classifier is added to the ensemble. Since the whole ensemble of classifiers is used for making predictions, DES is not performed in Leveraging Bagging.


In order to analyze how diversity is affected by concept drift, as well as to study the possibility of using diversity as criterion for drift detection, Brzezinski and Stefanowski <cit.> adapted six diversity measures, widely used in static learning, to data streams requirements. They focused on showing visualizations of diversity on streams with various types of drifts and used diversity as criterion on the Page-Hinkley test for drift detection. They conducted experiments using Online Bagging to create several homogeneous ensembles and calculated diversity in three processing scenarios: blocks, incrementally and prequentially. Their results indicated that ensemble diversity visibly changes over time and some diversity measures, especially interrater agreement, are capable of detecting drifts as effectively as accuracy. Again, DES was not conducted. 



A list and description of popular online ensemble methods for concept drift that work with configurable drift detectors is provided in <cit.>. The methods discussed use online versions of either Bagging or Boosting and, except for the Dealing with Drifts (DDD) <cit.>, they all generate only one ensemble of classifiers and do not perform any kind of selection. DDD also employs the variation of Online Bagging used in Leveraging Bagging <cit.>, but it maintains four classifier ensembles with different levels of diversity, which is obtained with different values λ. It is important to mention that the values λ used are fixed parameters. DDD works in two modes: prior to drift and after drift detection. In the first mode, two ensembles are created: one with low diversity and the other with high diversity, but only the low-diversity ensemble is used to assign labels to incoming instances. When the drift detector indicates a drift, DDD goes to the second mode. In this mode, two new ensembles are created, again with low and high diversity. Given that four ensembles are available, only the new high-diversity ensemble is not used to classify incoming instances. Weighted majority vote is employed as fusion function, where weights are defined according to ensembles prequential accuracy. Subsequently, DDD employs a heuristic to lead the system back to the first mode, where only two ensembles are dealt with and the new ensembles may replace the old ones. The authors indicate that DDD is proposed to better exploit the advantages of diversity, since it is able to maintain ensembles with different diversity levels. However, the static selection procedure used may be a limitation to achieve this objective.    

Differently from the works previously discussed, Almeida et al. <cit.> propose a method (Dynamic Selection Based Drift Handler - Dynse) focused on DES designed to detect drift. Dynse works with a stream of batches and creates a classifier for each batch of data. Thus, when an unknown instance arrives, the set of k nearest neighbors from a validation dataset surrounding the instance is defined and the most performing ensemble on this neighborhood is chosen to label it. In order to avoid the pool size to increase indefinitely, Dynse uses a pruning mechanism focused on diversity of region and concepts. Although the authors mention that the framework can be adapted to work as an online learning method, they did not perform the adaptation. Hence, this method may be assumed as a batch-based approach and, due to the neighborhood calculation, it may present the limitation related to local-driven dynamic selection <cit.>.








Our method processes incoming instances online as in <cit.>, <cit.>, and <cit.>. It employs the Online Bagging version used in <cit.> and enforces more diversity by generating a population of diverse ensembles. Also, it performs DES based on prequential accuracy, i.e. it does not need to find the neighborhood of the unknown instances to estimate competence. Finally, DESDD also uses a configurable auxiliary drift detector. 




 
 



 
 






§ PROPOSED METHOD



In order to simplify the description of the proposed method, we use the following notation. Let x_t ∈𝐑^d be a d-dimensional labeled instance observed in time step t whose real class is y_t, from a classification problem with a finite set of class labels. 
Instances are observed one at a time, and the time intervals are not necessarily equally spaced. Given that an unknown instance x_t+1∈𝐑^d arrives at time step t+1, the objective of DESDD is to assign a label y^* to x_t+1. After this decision, the true label y_t+1  becomes available. Then, the pair (x_t+1,y_t+1) is used to update the population of ensembles.

DESDD is divided into four phases: (1) diverse ensembles generation; (2) DES; (3) drift detection; and (4) drift reaction. First, by employing a configurable online ensemble creation algorithm, a population P={ C_1, C_2, ..., C_c } composed of c ensembles, each with n components and different levels of diversity, is generated. Then, for each new instance x_t+1 to be predicted, the ensemble candidate (C_j^*) with the highest current prequential accuracy is selected as an expert to assign a label y^* to x_t+1. As soon as the true class y_t+1 becomes available, DESDD goes into the drift detection phase, where a configurable detector is used. If no drift is detected, the ensembles in P are updated by training with (x_t+1,y_t+1). If a drift is detected, the drift reaction phase is reached. In this case, the entire population is replaced and a new process of diverse ensemble population generation and dynamic ensemble selection begins. We describe the details of DESDD phases in the next subsections. 



 §.§ Diverse Ensembles Population Generation


The first phase involves the online generation of a population of diverse ensembles to allow decision-based dynamic selection. The strategy used to explicitly enforce diversity when creating ensembles depends on the online ensemble creation algorithm employed. It is possible to observe that this phase of DESDD may be undertaken using any online ensemble generation method that explicitly enforces diversity, such as the modified versions of Online Bagging used in <cit.> and Online Boosting used in <cit.>. As previously mentioned, both algorithms have the same parameter λ that determines the level of explicit diversity inserted when creating an ensemble. In this work, we employ Online Bagging. Taking into account that a diverse classifier ensemble is created by varying the values λ, we define the range for the values λ  (minimum and maximum values λ) as a parameter. Thus, each DESDD iteration involves assigning a numeric value in the range [λ_min, λ_max] for each ensemble member of P randomly. 













































































Besides the online learning algorithm and the minimum and maximum values of λ, the following parameters must be set at the first phase of DESDD: 1) size of the population P; 2) number n of components of each ensemble; and 3) types of components – the ensembles may be either homogeneous or heterogeneous. After creating the population P, when x_t+1 arrives, DESDD reaches the dynamic selection phase. It is important to point out that this process follows the Test-Then-Train technique. However, without loss of generality, it is also possible to perform initial training with a batch of labeled instances and then follow the Test-Then-Train learning process.





 §.§ Dynamic Ensemble Selection


The goal of the selection phase of DESDD is choosing an expert ensemble C_j^* to assign a label for each unknown instance x_t+1. The expert is chosen as the ensemble with highest prequential accuracy up to instance x_t, that is, its prequential accuracy is not a local measure. Such ensemble is expected to be the most likely to assign a correct label to x_t+1. The prequencial accuracy (fusion of predictive and sequential), also called Interleaved Test-Then-Train, is the evaluation metric more often used in data stream mining. It is the average accuracy of predicted examples prior to the example being learned, and it is computed at time step t by:


    Acc = 
    	  
      	  acc_ex(t),    if t=f 
    
          acc(t-1) + acc_ex(t) - acc(t-1)/t-f+1,    otherwise


In this equation, acc_ex is 0 when the prediction of the current training example  is incorrect and 1 otherwise. The term f indicates the first time step.





 
 
 
  
   
    
     
     
     
      
   




 §.§ Drift Detection


In this third phase, a drift detector based on error monitoring is employed. Here, the prediction y^*, provided by the C_j^* chosen in the previous phase, is compared to the true label y_t+1 of x_t+1 in order to indicate whether or not the prediction was correct. Then, this information is used in an error monitoring process to indicate the occurrence of a drift. Since our method is configurable with a drift detector, several strategies, ranging from traditional to newer detectors can used. In <cit.>, a large-scale comparison of ten drift detectors is performed in the context of ensemble algorithms configurable with detectors. The authors indicate that no single drift detector may be deemed to be the best strategy in all situations. Based on this observation, although DESDD can be configured to use any detector investigated in <cit.>, in this work we employ the following two drift detectors: DDM and ADWIN. The former, is a traditional drift detector based on error monitoring. The latter, is employed in conjunction with Leveraging Bagging, which is a baseline used in our experiments. 








 §.§ Drift Reaction


For the last phase of DESDD, there are also different possible scenarios. In this work, the drift detector monitors each ensemble in P. When a drift is indicated, a new population of ensembles is created, i.e. the whole current population is discarded. The strategy used to generate the new population of ensembles after a drift detection depends on the drift detector employed. Considering the two detectors investigated in this work, two different training processes are conducted. When DDM is the drift detector, ensembles training is performed using instances stored by DDM during its warning level and drift level interval. In terms of ADWIN, training follows the traditional Test-Then-Train strategy. 
























§ EXPERIMENTS AND RESULTS


Our experiments were broken down into three main series. In the first, we investigate the behavior of the decision-based dynamic selection strategy employed by DESDD related to diversity variation in the presence of different types of drift. After that, the two versions of DESDD obtained by using DDM and ADWIN as drift detectors are compared. Then, in the third series, DESDD is compared to three baselines: (1) DDD; (2) DDM; and (3) Leveraging Bagging. These baselines were chosen mainly because DDD is a method that works with a population of ensembles (4 ensembles) and a configurable drift detector; DDM is a component of DESDD; and Leveraging Bagging was shown in <cit.> to be competitive with the best ensemble algorithms for drift detection, especially when using Hoeffding Tree as classifier component, which is the base classifier used in our experiments. First, however, the datasets investigated are detailed.



 §.§ Datasets

The experiments are conducted using ten artificial datasets (representing gradual and abrupt drifts with and without noise) and four real datasets. All artificial datasets are balanced, publicly available in the MOA framework, contain 10,000 instances, and were generated to present a drift at each block of 1,000 instances, i.e. they present nine concept drifts. For datasets with noise, they contain 10% examples with class noise. The artificial datasets allow us to evaluate the methods in terms of detection rate, detection delay and miss detection, besides prequential accuracy. The datasets are: 




  * Agrawal: Four datasets were created with Agrawal generator based on all 10 functions available, two presenting gradual drift and two presenting abrupt drift - Agrawal Gradual; Agrawal Gradual with Noise; Agrawal Abrupt; and Agrawal Abrupt with Noise. The datasets are represented by nine features and divided into two classes. 

  * Gauss: Its instances are represented by two features and divided according to two Gaussian distributions, i.e. two classes. This dataset presents abrupt concept drifts, noise, and reversal of the classes after every drift. 

  * SEA: SEA generator based on all functions available was used
to create four datasets - SEA Gradual; SEA Gradual with Noise; SEA Abrupt; and SEA Abrupt with Noise. They contain 3 attributes and 3 classes.

  * Sine1: It is a dataset composed of instances generated according to a sine equation. This dataset presents gradual concept drifts, is noise-free and, after every drift, classes are reversed.


The real datasets only allow the analysis of the investigated methods regarding accuracy, since it is not possible to know when a drift starts to occur, which type of drift is present or even if there is drift in the data. This is a common characteristic in real applications. The following real datasets are investigated. All of them have been previously used in works dealing with concept drift detection.


  * Forest Covertype: This dataset contains 581,012 instances divided into 7 classes representing forest cover types. A set of 54 features describes each instance.

  * KDD Cup 1999: It is composed of 489,844 instances divided into two classes, which represent several network intrusion problems simulated in a military network. Each instance is described by 41 features.

  * Poker-Hand: It contains 829,201 instances, 10 classes and its feature vector is composed of 11 attributes.

  * SPAM: It contains 9,324 instances divided into spam and ham classes and is represented by 499 binary features. 




 §.§ Base Classifiers

Ensembles may be composed of identical or nonidentical base classifiers. Since the three baselines investigated in this work use Hoeffding Tree as base learning algorithm, in this work we generate homogeneous classifier ensembles composed of Hoeffding Tree, which is an online learning algorithm for large volumes of data generated in stream.



We have conducted experiments for evaluating the impact of the number of ensemble members of the population by varying the amount of members. Our results indicated a population size of 11 ensembles as ideal size. In addition, we have compared different ensemble sizes, between 10 and 25 components. The results showed no significant differences in terms of prequential accuracy by varying ensembles sizes. Thus,  the number of components of each ensemble was defined as 10, i.e. the smallest tested size. 

Besides population and ensembles sizes, the range for the values λ used to generate the population of ensembles was also defined. The values used were: λ_min=0.001 and λ_max=100. This range has been expanded from the study presented in <cit.>. The same range was used for all datasets. It is important to mention that, in all series of experiments, simple majority voting was employed as fusion function. 















































 §.§ Analyzing Dynamic Selection vs. Diversity Variation


This section presents an analysis of the dynamic selection process conducted in the second phase of DESDD. We aim at answering the following question: how would the selection process behave considering a diverse population of ensembles in the presence of different types of drift? In order to understand such a behavior, this analysis is conducted using the population of ensembles that is generated at the first phase of DESDD. However, rather than randomly assign a numeric value in the range [λ_min, λ_max] to each ensemble member of the population P, we have fixed the values λ for the population of 11 ensembles to better monitor each one. Therefore, the same values were employed at each iteration: 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1, 5, 10, 50, 100. In this first series of experiments, DDM is used as configurable drift detector. Moreover, only artificial datasets are investigated.

Figure <ref> shows two types of information related to each candidate ensemble: 1) histograms of the frequency of selection and 2) the distribution of diversity. Here, diversity is measured as ambiguity. The classification ambiguity is an unsupervised dissimilarity measure defined for each candidate ensemble C_j in terms of its component c_i as:


    a_i(x_t+1) = 
    	  
      	  0,    if y_i=y_j 
    
          1,    otherwise


where a_i is the ambiguity, y_i is the class assigned by component c_i to instance x_t+1, and y_j is C_j's output. The final ambiguity for ensemble C_j is:


    div =  1 /n∑_i ∈ C_j a_i(x_t+1)


Due to lack of space, it is not possible to present histograms and distribution of diversity for all artificial datasets investigated in this paper. Hence, we show in Figure <ref> three datasets only: SEA Gradual, Agrawal Abrupt and Gauss (abrupt drift with noise). Even so, some observations can be made considering all datasets investigated. First, although it can be clearly observed in our experiments that the ensemble with λ=1.0 is most often selected as expert (8 datasets out of a total of 10 datasets), the selection process presents higher variation for abrupt drift problems (figures <ref> and <ref>) than for gradual drift problems (<ref>). For gradual drift problems, the selection is more concentrated on ensembles whose values λ are higher than 0.1. Although in abrupt drift datasets the selection frequency is also higher for λ > 0.1,  almost all candidate ensembles are selected through the iterations. We may, therefore, indicate that a larger range for values λ is more useful in problems with abrupt changes. It is important to observe that DES assures a high variance of expert selection. Second, noise does not play a key role on changing this behavior (Figure <ref>, which shows the results in a dataset with abrupt drifts and noise). Finally, the relation between λ and diversity cannot be clearly observed. However, diversity is higher when λ < 0.1. In general, the highest diversity rate was attained by the ensemble with λ=0.01 (7 datasets out of the 10 datasets). The diversity behavior appears to be problem-dependent.





 §.§ Comparison of Different DESDD Versions


In this second series of experiments, two DESDD versions are investigated by varying the drift detector: DDM and ADWIN. Again, only the artificial datasets were used in these experiments. It is important to mention that DESDD is employed as described in Section <ref>, i.e. each iteration involves randomly assigning a numeric value in the range [λ_min, λ_max] to each ensemble member of the population P. Mean and standard deviation values of 30 replications obtained by each version of DESDD are shown in Table <ref> for all 10 datasets. The best result for each dataset is in bold. 







The results shown in Table <ref> allow us to observe that the two versions of DESDD attained very different accuracy rates. DESDD-DDM was significantly better than DESDD-ADWIN. It is important to note in this table that DESDD operating with ADWIN is more affected by noise than its version with DDM. For instance, the reduction of DESDD-ADWIN accuracy in the SEA Abrupt dataset was 17% when noise was added - if we compare accuracy rates achieved in SEA Abrupt and SEA Abrupt with Noise datasets, while this difference is only 10% for DESDD-DDM. This behavior is observed in all datasets with noise. Moreover, since the whole population of ensembles is replaced after a drift detection, DDM may present faster recovery from drifts due to its buffer of instances stored during the warning level of DDM, which is used for training the new population in the first iteration after a drift detection. Therefore, based on these results, the DESDD-DDM version is used for comparison with baselines in the next section.




 §.§ Comparison between DESDD and Baselines


In this last series of experiments, our objective is to verify the impact of using diverse populations of ensembles and DES to detect concept drift. DESDD is compared to DDD, DDM and Leveraging Bagging (LB). All methods were configured with Hoeffding Tree as base learning algorithm. For DESDD, 11 homogeneous ensembles were used, all with 10 Hoeffding Trees. The range for the values λ was the same used in the previous experiment. For the baselines, they were employed using their standard versions, i.e., LB: 10 Hoeffding Trees, λ=6 and ADWIN as drift detector; DDM: 1 Hoeffding Tree; DDD: EDDM (Early Drift Detection Method) <cit.> as drift detector and a population limited to 4 ensembles, all with 25 components. However, DDD was employed using ensembles with Hoeffding Trees, instead of the standard Naive Bayes, to a fair comparison. Since only one replication of the baselines was performed due to the fact that these methods have no random component, the results of only one replication of DESDD are compared in this section.

The Wilcoxon statistical test was applied by testing the equality between pairs of methods. The confidence level was 95% (p-value of 0.05). Each dataset investigated was divided into batches of 30 iterations and prequential accuracies of each batch were used to provide different values for the Wilcoxon statistical test. Table <ref> reports classification accuracy achieved by all four methods and their execution times in seconds. 

This table shows that, except for the Agrawal Abrupt and the SEA Gradual Noise datasets, where DDM outperformed DESDD, DDD and LB in terms of classification accuracy, according to the Wilcoxon statistical test, DESDD outperformed the baselines or achieved accuracy very similar to the best rate for the remaining artificial datasets. Therefore, these results indicate that DESDD is effective for dealing with both abrupt and gradual changes, even when noise is added to the data. In terms of real datasets, the differences between accuracy rates obtained were much more significant. DESDD outperformed all the baselines in three of the four real datasets tested, and was tied at the best rate for the remaining KDDCup. These results are especially important because they indicate that DESDD can be very effective when used in real-world problems. If we compare the baselines, our results confirm the literature that DDM is better in artificial datasets, while LB achieves higher accuracy in real datasets <cit.>.




Moreover, the investigated methods can be ordered with respect to computational complexity: DDM, LB, DDD and DESDD. This result was expected, since DDM employs only one classifier, LB uses an ensemble of 10 classifiers, and DDD works with a population limited to 4 ensembles (with 25 components each), while DESDD generates a population with 11 ensembles, each composed of 10 members. On the other hand, we believe that DESDD establishes a good trade-off between accuracy and complexity, since designing classifiers with a high level of generalization performance is the main objective in learning problems, especially in real-world applications. In addition, as discussed in the next paragraphs, DESDD may reduce the computational complexity involved when updating the system after a drift detection due to its higher robustness to false alarms and its precision at signaling correct drift detections.   

Besides the competitive classification accuracy rates achieved by DESDD, our method outperformed the baselines taking into account important aspects in practical tasks involving concept drift, such as: miss detection and false detection rates. In order to identify and analyze in details these aspects, Table <ref> shows values of four metrics: detected drifts; false detection; miss detection; and late detection. The last row refers to total counts of each measure. It is possible to observe in this table that DESDD significantly outperformed its competitors in terms of precisely detecting concept drifts with fewer missed or false detections, regardless of drift types. DESDD achieved the lowest false detection rate, i.e. it was the most robust method to false alarms and the most precise on signaling changes. This is an important measure in the context of practical problems involving concept drift, since false detection may lead to unnecessary system updates and higher computational cost. 

In terms of miss detection, DDD reached the lowest rate, while DESDD and LB were tied at the second best rate. However, it is very probably that the low detection rates achieved by DDD and LB are due to the fact that these two methods trigger significantly much more false alarms than DESDD (as seen in the FD columns). For instance, LB was the only method that missed all drifts in the SEA Gradual Noise dataset. This can also be the reason for the lower detection delays (ADR) attained by these two methods. These results show that DESDD can accurately detect almost all drifts, leading to faster recovery. Taking into account that DESDD is able to precisely detect drifts the earliest possible and it is robust to false alarms, it is expected to adapt faster to new concepts and provide higher accuracy. The results attained in the real datasets corroborate these observations, since DESDD, except for the KDDCup dataset, triggers significantly much less drift detection in real datasets than the other methods. As a result, DESDD achieved classification accuracy significantly superior when compared to baselines in these datasets, as seen in Table <ref>.



These observations are reinforced in Figure <ref>, which shows the learning curves of the investigated methods on six artificial datasets: two datasets with abrupt drifts (figures <ref> and <ref>); one with abrupt drifts and noise (<ref>); two with gradual drifts (<ref> and <ref>); and one with gradual drifts and noise (<ref>). As changes are known on these problems, each figure also shows the moment when a change occurs (vertical line) and the moment each method detects a change. It can be seen that DESDD achieves better detection performance, since it detects almost all known changes with lower delay rate and generates very few false detections on datasets presenting different types of concept drifts. It is worth noting that DDM may be deemed to be the second best strategy for detecting drift in artificial datasets. Taking into account that DDM is the drift detector employed by DESDD, we may conclude that DESDD inherits the advantage of DDM. However, the population of diverse ensembles and the dynamic selection process provided by DESDD add more stability and robustness to false alarms and allow classification accuracy improvement, especially in real datasets, where DESDD outperformed DDM in terms of classification accuracy, while generating much fewer drift detections.  



§ CONCLUSION


A novel method for drift detection is proposed in this paper. DESDD is focused on generating a diverse population of ensembles and on dynamic ensemble selection. Our experiments show that DESDD was superior to baselines in most of the tests conducted. Based on these results, it is possible to highlight that by using a population of classifier ensembles generated with different levels of diversity and by selecting classifier ensembles dynamically using a global-oriented criterion, we may improve the effectiveness of drift detectors by reducing their detection delay, false detection and miss detection rates, besides increasing their accuracy, especially in real-world application problems. Future work includes using diversity as drift detection criterion. 


00
Brzezinski2016 Dariusz Brzezinski and Jerzy Stefanowski, “Ensemble Diversity in Evolving Data Streams,” pp. 229–244, 2016, Discovery Science. DS 2016. Lecture Notes in Computer Science, vol 9956.
BARROS2019213 Roberto S. M. de Barros and Silas G. T. C. Santos, “An overview and comprehensive comparison of ensembles for concept drift,” Information Fusion, vol. 52, pp. 213 - 244, 2019.
Zliobaite2016 I. Zliobaite, M. Pechenizkiy and J. Gama, “An Overview of Concept Drift Applications,” in N. Japkowicz, and J. Stefanowski (Eds.), Big Data Analysis: New Algorithms for a New Society (pp. 91-114), (Studies in Big Data; Vol. 16) Cham: CSpringer International Publishing.
Bifet2010a Albert Bifet, Geoff Holmes, and Bernhard Pfahringer, “Leveraging bagging for evolving data streams,” Lecture Notes in Computer Science, vol. 6321 LNAI, pp. 135–150, 2010.
Oza2001 N.C. Oza and S. Russell, “Experimental Comparisons of Online
and Batch Versions of Bagging and Boosting,” pp. 359-364, 2001, ACM SIGKDD
Int. Conf. Knowledge Discovery and Data Mining.
Bifet2007 Albert Bifet and Ricard Gavaldà, “Learning from Time-Changing Data with Adaptive Windowing,” pp. 443–448, 2007, 2007 SIAM International Conference on Data Mining.
Gama2004 J. Gama and G. Castillo, “Learning with local drift detection,” pp. 286–295, 2004, Advances in Artificial Intelligence. Lecture Notes in
Computer Science, vol. 3171.
Minku2012 L. L. Minku and X. Yao, “DDD: A New Ensemble Approach for Dealing with Concept Drift,” IEEE Transactions on Knowledge and Data Engineering, vol. 24, pp. 619-633, 2012.
ALMEIDA201867 Paulo R.L. Almeida, Luiz S. Oliveira, Alceu S. Britto and Robert Sabourin, “Adapting dynamic classifier selection for concept drift,” Expert Systems with Applications, vol. 104, pp. 67 - 85, 2018.
CRUZ2018195 Rafael M.O. Cruz, Robert Sabourin and George D.C. Cavalcanti, “Dynamic classifier selection: Recent advances and perspectives,” Information Fusion, vol. 41, pp. 195 - 216, 2018.
BaenaGarc2005EarlyDD Manuel Baena-Garc and José del Campo Ávila and Albert Bifet and Ricard Gavald and Rafael Morales-Bueno, “Early Drift Detection Method,” pp. 77-86, 2006, Fourth ECML PKDD Int’l Workshop Knowledge Discovery from Data Streams (IWKDDS ’06).


