ADAW: Age decay accuracy weighted ensemble method for drifting data stream mining

Abstract

Dynamic environment data generators are very often in real-world that produce data streams. A data source of a dynamic environment generates data streams in which the underlying data distribution changes very frequently with respect to time and hence results in concept drifts. As compared to the stationary environment, learning in the dynamic environment is very difficult due to the presence of concept drifts. Learning in dynamic environment requires evolutionary and adaptive approaches to be accommodated with the learning algorithms. Ensemble methods are commonly used to build classifiers for learning in a dynamic environment. The ensemble methods of learning are generally described at three very crucial aspects, namely, the learning and testing method employed, result integration method and forgetting mechanism for old concepts. In this paper, we propose a novel approach called Age Decay Accuracy Weighted (ADAW) ensemble architecture for learning in concept drifting data streams. The ADAW method assigned weights to the component classifiers based on its accuracy and its remaining life-time in the ensemble is such a way that ensures maximum accuracy. We empirically evaluated ADAW on benchmark artificial drifting data stream generators and real datasets and compared its performance with ten well-known state-of-the-art existing methods. The experimental results show that ADAW outperforms over the existing methods.

Keywords

Data stream mining concept drifts ensemble methods classification machine learning

1. Introduction

In real-world applications, many data sources generate data streams, which changes continuously with time due to the change in their underlying data distribution [1, 2, 3, 4, 5, 6]. The dynamicity in the real-world data sources is very common due to the impact of seasonality or periodicity on the sensors responsible for generating data streams [1, 2, 3, 4, 5, 7, 8, 9]. The data streams generated in the dynamics environment are generally characterized by the properties of 3Vs in big data, i.e. volume, velocity, and variety [10]. The high-speed data generation and the requirement of quick real-time response to the data streams classification make the classical single classifier approaches very inappropriate in this situation [11]. In contrast to the classical classification approaches used so far for classification in a static environment, where the classification algorithms are rarely restricted on time of learning and testing instead of accuracy, the data streams mining imposes many new necessities on algorithms such as high-speed learning and limited memory usage [12]. Furthermore, in data streams, the non-stationary underlying data distribution often causes the evolution of new concepts from time to time. Such evolution of new concept in the data stream is also called concept drift [7, 13, 14]. The use of a classical single classifier approach for the classification of data streams with drifting concepts may lead to poor classification accuracy with time [15, 16].

Based on, how the feature values demonstrating the occurrence of concept drift changes in the data streams, one can categorize the concept drifts in various types, for example sudden, gradual, recurring and incremental [17, 18]. Figure 1 depicts some common kind of concept drifts occur in data streams.

Figure 1.

Types of concept drifts.

A good data stream classification algorithm is supposed to perform equally well in the presence of any type of drifts. In recent years, many approaches have been proposed that are exclusively designed to deal with the classification of concept drifting data streams [9, 19, 20, 21, 22, 23, 24]. Some recently proposed methods for dealing with the mining of concept drifting data streams have utilized some common approaches such as windowing (both sliding and adaptive), ensemble methods [25] and drift detection strategies [9, 26].

Figure 2.

Possible points of modifications in concept drifting data stream mining algorithms.

The desired properties of a good classification system for mining high-speed, voluminous and time-varying, open-ended data streams have been discussed in [12], which includes the properties such as constant time constraints, limited primary memory requirement, one scan learning, and adaptive towards the changes in the underlying data distribution.

In general, the ensemble-based approaches designed for mining data streams with concept drift mainly targets the following five possible points of modifications: ensemble architecture, learning, and testing strategy, drift detection methods, forgetting mechanism and result integration rules as shown in Fig. 2. In this paper, we propose an ensemble-based architecture and algorithm to organize the components of the ensemble at all five levels. We empirically evaluated our designed model on some benchmark datasets and compared its performance with some well-known existing ensemble methods. The results of our ensemble model outperform the existing methods.

The rest of the paper is organized as follows. Section 2 describes the concepts related to data streams mining and concept drifts. Section 3 presents the literature survey of some pioneering work done so far for mining of concept drifting data streams. In Section 4, we present our proposed novel approach for handling concept drifting data streams. Section 5 provide a description of data collection and experiment evaluation of our model with some existing algorithms over some synthetic and real datasets. Finally, Section 6 and 7 present the conclusion and future scope of the work.

2. Data stream mining and concept drifts

The problem of a standard non-streaming dataset classification task can be explained as follows: let $\chi$ denotes a training sample, where $\chi$ contains several (i.e. $N$ ) ordered pairs of instances $({x^{i},r_{j}^{i}})_{i=1}^{N}$ indexed with $N$ . Where $x$ vector of attributes values and $r$ is its corresponding class label such that $r\epsilon({R_{1},R_{2}\ldots\ldots R_{l}})$ for $l$ classes. The task of any classifier learned on $\chi$ is to predict the class of a given unseen instance. In a non-streaming dataset classification problem, it is assumed that the $\chi$ follows a uniform static distribution throughout the training dataset.

In contrast to the non-streaming dataset, a data stream ${\cal S}$ can be considered as a sequence of instances, which arrived sequentially with respect to time but not necessarily with equally spaced time. Therefore, a data stream ${\cal S}$ can be defined as a time-ordered sequence of instances $({x^{t},r^{t}})_{t=1}^{T}$ generated by the data stream source in $T$ time.

Generally, an incremental learning strategy is recommended for data stream mining [27, 28]. In incremental learning approach an incremental learner ${\cal L}_{t}$ is built on $t$ historical instances target to predict the label of $x^{t+1}$ . If the predicted $\hat{r}^{t+1}\neq r^{t+1}$ , then ${\cal L}_{t}$ updates itself to ${\cal L}_{t+1}$ for incorporating the $x^{t+1}$ feature’s values in new updated classifier. Furthermore, the incremental learning may proceed either by taking single instance at a time or by taking some equal-sized blocks instances at a time. In the later case, the updating of the classifier is performed by computing the average accuracy attained in each block. If the average accuracy in predicting the classes of instances of the targeted block drops significantly (i.e. above some threshold value) then the classifier updates itself with features values of the targeted block. Both the instance wise and the batch-wise incremental learning have their advantages and disadvantages, for instance, the instance-based incremental learning offers time-consuming learning but adapts to the changes very quickly. On the other hand, the batch increment learning offers quick learning but has a high change adaptation time that is dependent on the block size. The occurrences of concept drifts are among the most prominent reasons for the accuracy drop of a classifier while it classifies the data streams [27]. The next section presents a formal description of concept drifts.

2.1 Concept drifts

The occurrence of concept drifts in a data stream can be better understand by using Bayesian interpretation or Bayesian decision theory as presented by Kelly et al. [15] and explained using Eq. (1). Kelly et al. explained that the change in population distribution could occur in three ways, which may result to concept drift.

$\displaystyle P({\raise 3.01pt\hbox{${r_{i}}$}\!\mathord{/{\vphantom{{r_{i}}x}% }.\kern-1.2pt}\!\lower 3.01pt\hbox{$x$}})=\frac{P({r_{i}})P({\raise 3.01pt% \hbox{$x$}\!\mathord{/{\vphantom{x{r_{i}}}}.\kern-1.2pt}\!\lower 3.01pt\hbox{$% {r_{i}}$}})}{P(x)}$ (1)

(i) The class priors $P({r_{i}})$ may change over time.

(ii) The distributions of one or several classes $P({\raise 3.01pt\hbox{$x$}\!\mathord{/{\vphantom{x{r_{i}}}}.\kern-1.2pt}\!% \lower 3.01pt\hbox{${r_{i}}$}})$ may change.

(iii) The posterior distributions of the class memberships $P({\raise 3.01pt\hbox{${r_{i}}$}\!\mathord{/{\vphantom{{r_{i}}x}}.\kern-1.2pt}% \!\lower 3.01pt\hbox{$x$}})$ may change.

3. Related work

Abstractly, the mining process of concept drifting data streams can be considered as a two-step process: (i) drift detection method and (ii) taking corrective actions to neutralize the adverse effects on the classification accuracy due to the drifts. Mandatorily, both these steps should qualify the time and space constraints generally required for data stream mining. Some commonly utilized approach for drift detection in data streams includes the monitoring of change in the underlying change in the data distribution, monitoring the change in the class conditional probabilities or monitoring the average accuracy drop with time. After drift has been detected, certain corrective actions are required to cope up with the increased misclassification errors. These corrective actions include updating, rebuilding or dropping of the classifiers depending on the used strategy.

Based on the various approaches proposed in some recent pioneer work done [12, 25, 26, 29, 30], we can abstractly categorized the methods for handling concept drifting data streams into three major categories as (i) windowing-based methods [12, 30] (ii) methods based on separate drift detection strategy [26, 29] and (iii) ensemble-based methods [25, 31, 32]. While focusing on these major identified categorizations, in this section, we present discussions on some related work under these categories.

3.1 Windowbased strategies

Window-based strategies are very common in incremental learning of data streams [27]. Mainly sliding window-based approaches are very popular because of their inherited tendency of always keeping recent training instances limited to the window size [33]. However, the deciding of window size is a kind of trade-off. Small window sizes are fast in the change detection but they may suffer from false change detection. Similarly, large window sizes are slow in the change detection but are more accurate to change detection. To overcome the slow response of a large window approach toward the change in data distribution, various adaptive windowing strategies are proposed [30, 34]. Depending on the size selection strategies, the window-based strategies can be further categorized into fixed-sized and adaptive window-based strategies. In an adaptive windowing strategy, the size of the window is adjusted automatically depending upon certain measures like rate of change or any other statistical measures. Kifer et al. [35] proposed a fixed-sized window-based approach for the detection and estimation of changes in data streams. In this work, a novel distance measures between distributions has been introduced to compute the change in distribution between reference and current window. Klinkenberg et al. [36] proposed the Support Vector Machine (SVM) based concept drifts detection method for the data stream. This approach uses adaptive windowing to reduce the estimated generalization error. The estimated error is computed using $\xi\alpha$ -estimators.

The window-based learning strategy can be used in either of two ways for data stream mining: As an external mechanism in a learning model for detecting the change or as an integral part of the learning algorithm. The Very Fast Decision Tree (VFDT) of Hoeffding Tree (HT) [12] an incremental learning anytime decision tree induction algorithm. VFDT is a decision tree based on Hoeffding bounds. The VFDT can learn from a large data stream. It does not store any example in the main memory and the memory requirement of VFDT is proportional to the size of the decision tree. It performs one pass learning that’s why it does not requires to storing the example ever. To achieve one-pass learning and low memory utilization, the VFDT utilizes the Hoeffding bound. The Hoeffding bound is stated as follows. Let $r$ be a real-valued random number having range $R$ . Suppose $\bar{r}$ is the mean of $r$ for $n$ independent observations, then according to Hoeffding bound, the true mean value of $r$ will be at least $\bar{r}-\epsilon$ with the probability $1-\delta$ . Where $\epsilon$ is computed using Eq. (2).

$\displaystyle\epsilon=\sqrt{\frac{R^{2}m({\raise 3.01pt\hbox{$1$}\!\mathord{/{% \vphantom{1\delta}}.\kern-1.2pt}\!\lower 3.01pt\hbox{$\delta$}})}{2n}}$ (2)

The Hoeffding bound is independent of the probability distribution, which is generating the observation. The major shortfall of VFDT is that it is designed for stationary massive data streams. Later, to cope up with the concept drifting data streams, the VFDT was modified to CVFDT (Concept-adapting Very Fast Decision Tree learner) algorithm [37]. The CVFDT is a window-based algorithm that is capable of mining time-changing data streams. To handle drifting data streams, CVFDT grows alternate subtree with the recent best attribute and replaces the old subtree when the alternate subtree one becomes more accurate. Based on the accuracy of the alternate subtrees computed on some examples, the low accuracy subtrees are pruned to maintain the low requirement of memory. The CVFDT dynamically shrinks the window size when many nodes get questionable or data rate changes rapidly and increase the window size when only few nodes are questionable. Both, the VFDT and the CVFDT attain the same accuracy.

Adaptive Windowing (ADWIN) [30] provides an approach that deals with drifting data streams. The ADWIN is also a sliding window-based algorithm that dynamically changes the window size depending on the online computation of the rate of change observed from instance within the window itself. The algorithm automatically increases the window size when no change in data is observed and shrinks window when data changes. By adapting the window size, the ADWIN manages an optimal trade-off between small and large window size dynamically.

Hoeffding Adaptive Tree (HAT) [38], is a variation of HWT (Hoeffding Window Tree) that adaptively learn from time-changing data streams with having constraints of the fixed sized sliding window concepts. The solution of the optimal window size is not an easy deal in streaming data due to the varying rate of change of frequency distribution in data stream. Instead of depending on a size parameter, the HAT manages certain statistics at the nodes of Hoeffding Tree (HT) to estimate the frequency statistics at every node. Three variations of HAT have been proposed in [38], which include HAT-INC, HAT-EWMA and HAT-ADWIN. The HAT-INC is based on based linear, HAT-EWMA is based on exponential weight moving average and HAT-ADWIN is based on ADWIN estimator. The HAT has two main advantages over HWT, first, in HAT, there is no need to calculate optimal window size and second HAT keeps all data in main memory instead of keeping it in secondary memory as HWT does. The Hoeffding Option Trees (HOT) [39] provides additional optional nodes on HT, which allows several tests on HT. This leads to many HTs as a separate path. HOT is consisting of single tree structure that can efficiently represents many trees.

3.2 Drift detection based methods

There are two very fundamental approaches in mining time of varying data streams: (i) practicing regular periodic updates in the learning model without considering about the changes and (ii) first detect the change and then adapt the learning model accordingly. In the former approach, weighted examples and time windows of fixed size are utilized. For instance, the higher weights can be given to recent examples [36, 40]. In a time window-based approach only those instances are included for training which are included in the window. The later approach is based on certain measures like monitoring the change in accuracy or change in the underlying distribution, etc. Such concept changes are monitored regularly and if a concept drift is detected the learning model is adapted accordingly to cope up with the adverse effects of concept drifts. This approach is also called drift detection-based methods. The performance measures of drift detection methods include the following measures [32]:

(i)
Drift detection delay: The time delay between actual drift detection time and drift detection time by the detector.
(ii)
Number of true positive drift detection: Total number of detected drifts, which are actual drifts.
(iii)
Number of false positive drift detection: Total number of detected drifts, which are not actual drifts.
(iv)
Drift detection accuracy: Ratio of actual drifts with a total number of drifts detected.

For good drift detectors, drift detection delay should be low and accuracy should be high. In the group of drift detectors, the Drift Detection Method (DDM) [29] and Early Drift Detection Method (EDDM) [26] are very popular. The DDM is based on the fact that the prediction error can be approximated through a binomial distribution. To track the error rate in DDM, certain alarm values are decided for detecting the changes. Once the alarm is reached, the older classifier is dropped and a new classifier is learned. The DDM is good in detecting sudden drifts but not well for gradual drifts. Furthermore, DDM is not so quick in drift detection. The EDDM is a kind of variant of DDM, in which the frequency of misclassified instance is considered for quick detection of drifts. The EDDM is comparatively well for gradual drifts as compared to DDM.
3.3 Ensemble based methods

A variety of machine learning tasks like classification [41], clustering [42, 43] and reinforcement learning [44] have been approached by ensemble methods. A large group of researchers has shown their affinity in the ensemble-based methods for data stream mining with concept drifts [9, 19, 25, 31]. Test-then-train incremental methods and bagging [45] are commonly used for learning in data streams. Online bagging is an online version of incremental learning in which the member classifiers are learned incrementally and the decision are integrated using majority weighting. Leveraging Bagging (Lev) [46] is a variant of bagging that adds randomization to the input and output of the classifiers with a simple bagging strategy. An online version of bagging and boosting is presented by Oza (OzaBag and OzaBoost) [47] that is based on one pass learning. The Weighted Majority Algorithm (WMA) [48] method is based on the pool of classifiers, where each classifier are called an expert. Initially, each classifier is assigned a weight of one and whenever any expert makes the wrong prediction, its weight is multiplied by fixed $\beta$ , where $({0\leqslant\beta<1})$ in order to decrease its weight. During prediction, the most weighted class is assigned to the instance. The Dynamic Weighted Majority (DWM) [49] is an incremental ensemble in which a set of incremental learners are weighted accordingly on the basis of their classification accuracy for each coming instances. The Streaming Ensemble Algorithms (SEA) [50] maintains a fixed sized pool of learners by training all learners on the batch of training examples. SEA uses C4.5 to build decision tree for each newly arrived batch. If there is free space in the pool, then this new classifier is added to the ensemble. If there is no free space, then the performance of the new classifier is compared with the existing members of the ensemble for the newly arrived batch and the least accurate classifier is then drooped to make space for the new one. In SEA, the weighted majority is utilized for combining the decision of the pool. Similar to SEA, the Accuracy-weighted Ensemble (AWE) [51] also utilized a fixed size ensemble pool by training each members on the batch of training example. However, unlike to SEA each classifier is assigned weights according to their accuracy on the recent batch. If there is free space in the ensemble then the new classifier is added to the pool, otherwise only $k$ top ranked classifiers are accommodated in the ensemble. The authors of AWE formally shown that if the member classifiers of ensemble are assigned weight according to their expected accuracy, then the ensemble outperforms over single classifiers. However, since the actual weighting function is unavailable, therefore, in AWE it is proposed to derive the weights by estimating the rate of error for the latest data block $x_{i}$ as given by Eqs (3)–(5).

$\displaystyle\textit{MSE}_{i}=\frac{1}{|{x_{i}}|}\sum_{({x,c})\in x_{i}}({1-f_% {c}^{i}(x)})^{2}$ (3) $\displaystyle\textit{MSE}_{r}=\sum_{c}p(c)({1-p(c)})^{2}$ (4) $\displaystyle w_{i}=\textit{MSE}_{r}-\textit{MSE}_{i}$ (5)

Where, the probability of classifier $C_{i}$ to classify $x$ as $c$ is denoted by $f_{c}^{i}(x)$ and $\textit{MSE}_{r}$ is the mean square error of the randomly predicting classifier. The Accuracy Updated Ensemble (AUE) [19] extends the concept of AWE by utilizing online learning and by updating the member classifiers with respect to the current distribution. Furthermore, for dropping the undesired classifier from the ensemble, it uses a modified weighting function as given in Eq. (6).

$\displaystyle w_{i}=\frac{1}{\textit{MSE}_{i}+\epsilon}$ (6)

Where $\epsilon$ is a very small value to avoid infinity weight when $\textit{MSE}_{i}$ is zero, the $\textit{MSE}_{i}$ is calculated using Eq. (3). The Accuracy Updated Ensemble (AUE2) [11] is built on the concepts of AUE. The aims of AUE2 is to achieve accurate predictions in the presence of all kinds of drifts. To achieve this aim, AUE2 combines an accuracy-based weighting strategy and utilized VFDT to incorporate incremental learning.

Figure 3.

ADAW architecture.

4. Architecture and organization of ADAW

The architecture of an ensemble method of classification explains the interaction among the component classifiers within the ensemble. Various ensemble architectures can be categorized based on their topologies. Heitor et al. [52] attempt to classify the various ensemble architecture under the following major categories: (i) Flat (ii) meta-learner (iii) hierarchical and (iv) network. The architecture of the proposed ADAW method is given in Fig. 3. Our proposed ensemble architecture and its organization is based on the certain modifications of the three very important aspects of the commonly used strategy of ensemble building [9, 13, 22, 53, 54, 55], that is, how component classifiers are virtually arranged, how the component classifiers are participating in decision making, and how the learning is performed. These modification phases are depicted in Fig. 2. Based on the standard practices involved in the designing of an ensemble of classifiers for online learning in drifting data stream, we illustrate our approach under the following categories: (i) The structure of ensemble ADAW (ii) learning and testing strategy used in ADAW (iii) method of weight assignment to the component classifiers and decision integration rule and (iv) forgetting mechanism. The complete ADAW algorithm is also illustrated in Algorithm A.

Figure 4.

Array-based structure and decision integration rule of ADAW.

4.1 Ensemble structure of ADAW

Let ${\cal E}$ denotes the ensemble structure of ADAW. Initially, ${\cal E}$ is set to null ( ${\cal E}=\emptyset$ ) and the component classifiers are added to the ${\cal E}$ sequentially with one at a time. The maximum number of classifiers in the ensemble is simply limited by a fixed value $L$ . The maximum number of classifiers in an ensemble at a given time specifies its cardinality $|{\cal E}|$ . Whenever, the ensemble achieved its maximum number of component classifiers, one least weighted classifier gets dropped out from the ensemble to prevent overflow conditions in the ensemble. The ensemble structure of ADAW follows an array-based structure, where the highest index value is assigned to the most recent component classifier and the least index is assigned to the oldest member as depicted in Fig. 4.

4.2 Learning and testing strategy of ADAW

Batch setting approaches such as holdout and K-fold-cross-validation are commonly used for the supervised learning and testing of classifiers using static datasets [56]. In batch learning, the training dataset is divided into two sets, one part is used for training the model and the other is used for testing the model. The K-fold cross-validation offers certain modifications to the holdout method. In K-fold cross-validation the labelled dataset is divided into $k$ equal parts. From all samples, only one sample is used for testing and the rest $k-1$ samples are utilized for training. Both, the holdout and the K-fold cross-validation methods have their advantages and disadvantages while learning and testing the classifiers using static datasets.

The one-pass learning requirements of data streams limit the scope of these approaches in learning and testing of classifiers used for data stream classification. Instead of using holdout or k-folds, in ADAW, we followed two separate procedures, one for the training and testing of every newly inserted component classifier and one for only testing of the already existing component classifiers in the ensemble ${\cal E}$ for the same data chunk on which the most recent classifiers has been trained as shown in Fig. 3. In ADAW, we used a fixed-sized data chunk $(\delta)$ of a fixed number of instances $k$ for performing these two procedures. In ADAW, we selected Hoeffding Tree (HT) as the base classifier. The strategy utilized in ADAW for training and testing are explained below:

(i)
Test-then-train: All newly introduced component classifiers are trained in test-then-train fashion. In this approach of learning each coming instance is first tested on the newly inserted component classifier and if the classifier made the wrong prediction for the instance then only learning is performed [57].
(ii)
Test-only: Instead of performing training, this procedure merely evaluates the accuracy of the existing component classifiers on the recent data chunk. Therefore, instead of learning, all existing component classifiers in the ensemble only perform prediction for the coming new instances and their accuracies are updated accordingly for every data chunk.

The learning and testing strategy of ADAW makes it different from AUE, in AUE the test-then-train has been applied to all existing component classifiers for all recent data chunks. The intention of having two different procedures of learning and testing strategy for newly created component classifier and the existing old component classifiers in ADAW is to preserve some outdated concepts with the ensemble. By doing this, the ADAW maintains a kind of inherited diversity within the ensemble due to which it performs well in the presence of recurring drifts.
4.3 Weight assignment to component classifiers and decision integration rule

The weight assignment to the component classifiers in an ensemble of classifiers is a very crucial step because weights of the component classifiers play a very important role in the decision integration rule of the ensemble. The weight assignment function of ADAW is based on the two very simple concepts. The first concept is based on the consideration of the temporal and spatial locality of reference and the second is based on the observation of the Wang et al. [51]. According to Wang et al., if an ensemble of classifiers ${\cal E}_{n}$ is trained by $n$ most recent examples of a data stream and similarly a single classifier system $G_{n}$ has also trained on the similar $n$ recent examples, then the Theorem 1 holds.

Theorem 1: The ensemble system ${\cal E}_{n}$ generates less misclassification as compared to a single classifier system $G_{n}$ it the component classifiers of ${\cal E}_{n}$ are assigned weights according to their accuracy of classification [51].

The temporal and spatial locality of reference consideration is one of the most commonly used strategies for estimating the distribution of newly arriving instances. To ensure this consideration in ADAW, the newly introduced classifiers always assigned the highest index value $(j)$ in the array structured architecture of ADAW at any given time. Based on the index value of the component classifiers in the ADAW ensemble and current cardinality $|{\cal E}|$ of the ADAW an experimentally derived equation Eq. (7) is used to compute the remaining age $(\tau)$ of the component classifiers in ADAW. The remaining age of a component classifier defines that how much older or younger the component classifiers are for a given time in ADAW, the high $\tau$ valued component classifiers will remain in the ensemble for a long time as compared to a low $\tau$ valued component classifier.

$\displaystyle\tau_{j}=\frac{({j+1})}{|{\cal E}|}$ (7)

The weight $(w_{j})$ of $j^{\text{th}}$ component classifier in the ensemble for a given data chunk $\delta$ is computed using Eq. (8), where $\alpha_{j}$ and $\tau_{j}$ are the accuracy and the remaining age of the $j^{\text{th}}$ component classifiers evaluate on the data chunk $\delta$ respectively.

$\displaystyle w_{j}=(\alpha_{j}\times\tau_{j})$ (8)

Where the accuracy $\alpha_{j}$ of the component classifiers $j$ for a data chunk $\delta_{i}$ can be computed using Eq. (9).

$\displaystyle\alpha_{j}=\frac{\textit{No. of correct prediction by }j^{\text{% th}}\textit{ member over }\delta_{i}}{|{\delta_{i}}|}$ (9)

The ADAW simply utilizes the weighted sum as given in Eq. (10) for the decision integration of all the component classifiers in the ensemble for predicting the class of an instance. The weighted sum approach used in ADAW is depicted in Fig. 4, where $C_{i}$ for $i=({1,2,\ldots})$ are the possible classes, $w_{j}$ is the weight of the $j^{\text{th}}$ component classifier and $C\_C_{j,i}$ is the vote of the $j^{\text{th}}$ component classifier for class $C_{i}$ in the ensemble ${\cal E}$ .

$\displaystyle y_{i}=\sum_{j=0}^{|\varepsilon|}(w_{j}\times C\_C_{j,i})$ (10)

4.4 Forgetting mechanism of ADAW

The forgetting of outdated concepts is a very common practice in online data stream classification for limiting the memory requirements. Generally, in the single classifier approach, the forgetting of the old concepts is achieved by simply dropping the old classifier and rebuilding a new classifier trained on the recent data chunk. However, the ensemble methods deal with forgetting by dropping of the least accurate classifier component from the ensemble [19, 51]. Based on the same principle, the ADAW also drops the one component classifier from the ensemble to maintain low memory requirements whenever the ensemble attain its maximum size (i.e. $L$ ), however, instead of dropping the least accurate component classifier, the ADAW drops the least weighted classifier from the ensemble. To facilitate the dropping of the least weighted component classifier from the full ensemble, the ADAW keeps repositioning of the component classifiers within the array-structured ensemble of ADAW by sorting the array with respect to the weights of the component classifiers. After the repositioning of the component classifiers, based on their new index in the sorted array, the new remaining age and the new weights of existing component classifiers are again re-computed for predicting the instances of the new data chunk using decision integration rule given in Eq. (10). This process is followed until the streaming as illustrated in pseudo-code of ADAW Algorithm A.

Algorithm 1: ADAW
Input: ${\cal S}$ : Data stream of instances divided into equal-sized data chunks $\delta_{i}$ .
$L$ : maximum number of component classifiers allowed in ${\cal E}$ .
Output: ${\cal E}$ : Ensemble of $L$ weighted component classifiers trained incrementally on data chunks $\delta_{i}$ .
1: ${\cal E}\leftarrow\emptyset$ ; j $=$ 0
2: while ( $\delta_{i})$
3: if ( $\|{\cal E}\|<L)$
4: $j\leftarrow j\%L$ ;
5: $C_{j}\leftarrow$ New component classifier (apply Test-then-train on $\delta_{i})$ ;
6: $w_{ij}\leftarrow\tau_{j}\times\alpha_{ij}$ ; //Using Eqs (7)–(9)//
7: ${\cal E}\leftarrow{\cal E}\cup\{C_{j}\}$ ;
8: for all $((C_{k}\in{\cal E})\&\&(k\neq j))$
9: Apply Test_only on $C_{k}$ over $\delta_{i}$ ;
10: $w_{ik}\leftarrow\tau_{k}\times\alpha_{ik}$ ;
11: $j++$ ;
12: else
13: Rearrange $C_{k}$ in ${\cal E}$ in non-increasing order of $w_{ik}$ ;
14: ${\cal E}\leftarrow{\cal E}-\{C_{0}\};$ // $C_{0}$ is the least weighted classifier//
15: for all $(C_{k}\in{\cal E})?$
16: $C_{k\leftarrow{k}-1}$ ;
17: $j--$ ;
18: $i++$ ;

5. Data collection and experimental setup

The proposed algorithm ADAW is evaluated for many experiments comprised of different types of drifting data streams. Furthermore, the performance of ADAW is also compared with ten well-known state-of-the-art existing methods. In the following sections, first, we present a discussion on datasets and then we present the experimental setup.

Table 1
Dataset characteristics

Datasets	Types of drifts	No. of instances in millions	No. of attributes	No. of drifts	No. of classes	Noise
Hyp	Incremental	1M	10	1	2	5%
SEA	Sudden	1M	3	4	4	10%
RBF	Gradual	1M	10	4	4	0%
RTG	Recurring	1M	10	15	6	0%
LED	None	1M	24	0	10	20%
LED-Drift	Mixed	1M	24	3	10	10%
Cov	Unknown	$\approx 581$ K	54	–	7	–
Poker	Unknown	$\approx 1$ M	11	–	10	–

5.1 Data collection

The performance of the proposed algorithm is empirically evaluated on a few artificial and real datasets for accuracy and CPU time elapsed. For the analysis of the proposed algorithm on various types of concept drifts, we prepared a group of artificial datasets, which includes sudden drift, recurring drift, incremental drift and gradual drift as shown in Table 1. We used Massive Online Analysis (MOA) [58] framework for generating synthetic real-time data streams. A brief description of the theses generated data stream is given below.

Rotating Hyperplane (Hyp): Hyperplane 3̧7 is the data stream generator that generates data streams with incremental drifts by simply rotating the decision boundary with every successive instance. The hyperplane generator is one of the most popular generators used for the analysis of data stream mining algorithms. There are 10 attributes in this dataset. We have utilized the hyperplane generator to generate 1,000,000 instances with 5% noise and contains incremental drifts with magnitude changing by weight of 0.001 for each instance.

Streaming Ensemble Algorithm (SEA) Concepts Generator: The SEA [50] Concept Generator generates points between 0 and 10. In this generator, three attributes are utilized for generating points, however, out of the three attributes, only the first two attributes are relevant. The SEA concept generator generates sudden drifts. The generated points are grouped into four different blocks, where each block represents a different concept upon a threshold value. The threshold value is the upper bound of the sum of the first two attributes. For performing the experiments, a total of 1,000,000 instances are generated with three introduced drifts at instances 250K, 500K, and 750K and with 10% noise.

Random Radial Basis Function (RBF): The Radial Basis Function generates a numerical dataset in which classes are represented by the drifting centroids of the hypersphere. Each center is designated by a random position, weight, class and a single standard deviation that generates gradual drifts. By using this generator, we generated a dataset with 1,000,000 instances having 10 attributes. This dataset contains two gradual concept drifts at instance position 400K and 800K, where each concept holding four decision classes.

Random Tree Generator (RTG): The Random Tree Generator generates a data stream with recurring drifts. For experiment purposes, we have generated RTG data stream of 1,000,000 instances that contains 5 numerical and 5 nominal features. Three drifts are introduced at instance positions 300K, 600K, and 900K.

Light Emitting Diode (LED) dataset: The LED generator [59] used for generating the LED dataset. The LED dataset is an artificial data stream that contains 24 binary attributes which are used to denote the digits in seven segment display constituting 10 classes. The LED data stream generator is used to generate two variants of LED type datasets, the LED dataset, and LED-Drift dataset. The LED dataset contains 1,000,000 instances with no drifts and with relatively high noise of 20%. The LED-Drift dataset also has 1,000,000 instances but with three introduced drifts at 300K, 600K, and 900K that constitute a mixed kind of drifts with 10% noise. A mixed kind of drifting data stream is challenging to learn.

Forest Cover Types (Cov): The Forest Cover Types (Cov) [60] dataset contains information on wilderness areas of the US obtained by US forest service. It is widely used for classification purposes. The Forest Cover Type dataset contains 7 classes of forest cover types and having 54 attributes constituting 12 measures that include 4 binary wilderness areas, 40 binary variables for soil type and 10 quantitative. The dataset is having 581,012 instances.

Poker Hand (Poker): The Poker Hand (Poker) [61] dataset is consisting of a hand containing five playing cards. Each card is described by two attributes rank and suit for 10 predictive attributes. The class attribute is described by “Poker Hand”. This dataset is consisting of 1,025,010 instances. It is widely associated with classification tasks.

5.2 Experimental setup

This section presents the comparative study of ADAW with ten well-known state-of-the-art existing methods of data stream mining. We utilized prequential accuracy and learning time for comparing the performance of all other methods with ADAW. We utilized MOA framework for comparing ADAW with the existing algorithms. All these algorithms are implemented in java and are part of MOA framework. We implemented our approach using JAVA.

The experiments were carried out on an octa-core i7 processor of frequency 1.8 GHz and 16 GB RAM. To make the comparative analysis, we utilized the same parameter values for all algorithms. For instance, we used training chunk size $\delta=$ 500 instances. We used Hoeffding Tree enhanced with adaptive naïve Bayes leaf with a grace period of $\eta$ m $=$ 100, splitting confidence $=$ 0.01 and tie threshold $=$ 0.05. For ensemble-based methods, namely AUE, AWE, DWM, Oza and Lev, the maximum numbers of component classifiers is set to 10 as we have not observed any significant increase in accuracy while increasing the number of members in the ensemble.

Based on the crucial characteristics of streaming data, we evaluated the performance of the algorithms on their accuracy and the CPU time elapsed. We used a test-then-train strategy to train the newly inserted component classifiers by using a fixed-sized data chunk of size $\delta=$ 500 instances. To limit the memory usage of the ensemble, we utilized a forgetting procedure, in which we drop least weighted component classifier from the ensemble whenever the number of the component classifiers reaches to its maximum value (i.e. $L=$ 10), and insert a new classifier test-then-train on the recent data chunk. In that way, we limit our maximum memory usage window of $L\times\delta$ without using any extra buffer memory.

The selection of the maximum number of component classifiers in an ensemble is a very crucial decision [62]. However, both the large and small number of component classifiers in an ensemble is having their own advantages and disadvantages. The ensembles that are having a large number of component classifiers are beneficial in the presence of recurring drifts in data streams; however, having the large number of component classifiers has high memory requirements and often contains outdated concepts. Similarly, for those data streams, which contain frequent sudden drifts with evolving new concepts, the large size ensemble is worthless. Although, the small size ensemble is good in terms of memory requirements, however, in this case, the data streams with recurring drifts the ensemble can produce low accuracy. The optimal situation must be like that a small number of component classifiers in an ensemble might be able to produce maximum accuracy for all concepts present in the data stream [62].

6. Comparative study and result analysis

We have conducted a set of experiments to compare the performance of ADAW against AUE, AWE, DDM, DWM, HOT, Leveraging Bagging (Lev), Naïve Bayesian (NB), Oza, VFDT and WMA. In order to have the representation of all major categories of approaches that we have discussed in related work section, we have intentionally selected such set of data stream classification methods, we selected AWE and AUE as we have considered them as a base for our proposed method, which is also based on ensemble approach and follows the accuracy-based weighting of the component classifiers. We have selected NB as it is a popular single classifier method, which does not exclusively employ any drift detection method. The HOT is selected as a prominent representative of the hybrid approach, which utilized both; the incremental learning and ensemble approach. The VFDT is selected as a potential representation of very fast incremental online learner. The WMA covers one of the best-known decision integration rules. Lev covers a variant of bagging strategy, whereas the Oza is a variant of online bagging strategy. Both Lev and Oza also follows the ensemble strategy. The proposed and the selected algorithms are evaluated on the two performance parameters: the average accuracies of the algorithms and the CPU time elapsed in performing the experiments.

Table 2
Average classification accuracies in percentage [%]

Datasets	AUE	AWE	DDM	DWM	HOT	Lev	NB	Oza	VFDT	WMA	ADAW
HYP	90.67	93.25	88.99	93.78	87.28	90.52	84.17	90.59	87.28	94.07	94.86
SEA	88.26	86.81	86.89	87.99	86.52	88.31	86.05	86.48	86.49	86.98	89.32
RBF	98.03	64.09	69.17	69.66	83.68	98.72	65.84	97.22	82.89	82.93	98.82
RTG	92.12	67.71	63.29	66.11	69.74	93.37	58.37	71.50	69.23	69.35	93.49
LED	73.94	73.81	74.13	73.95	73.95	73.99	74.13	73.87	73.94	74.09	74.15
LED-Drift	73.64	73.66	73.70	73.71	68.15	73.71	62.45	67.59	67.43	67.57	73.84
Poker	49.93	47.61	50.11	47.69	50.12	49.77	50.11	50.10	50.12	50.14	51.39
Cov	87.00	80.82	88.57	83.59	85.86	92.06	61.07	84.48	80.85	81.17	91.83

Table 3

CPU time elapsed [seconds]

Datasets	AUE	AWE	DDM	DWM	HOT	Lev	NB	Oza	VFDT	WMA	ADAW
HYP	502.09	56.37	1.65	62.02	22.16	1548.03	0.92	172.15	10.34	49.47	403.03
SEA	48.03	21.46	0.71	22.95	4.76	197.74	0.46	60.86	3.14	15.60	45.21
RBF	542.55	97.41	6.84	162.76	10.87	1037.25	4.07	350.55	6.77	28.40	443.36
RTG	414.70	37.87	1.22	20.06	43.53	1222.36	0.81	722.27	31.84	193.11	307.43
LED	62.12	117.24	3.33	139.68	21.66	84.46	2.07	90.55	6.10	31.43	60.23
LED-Drift	64.7	122.06	3.34	132.46	14.82	90.19	2.07	97.45	6.07	28.47	61.17
Poker	22.53	26.07	2.77	13.30	20.31	35.17	1.90	54.94	4.30	20.02	19.37
Cov	78.10	114.99	3.95	36.93	38.42	103.17	4.37	159.07	10.62	50.39	63.17

Figure 5.

Runtime accuracies of various classification methods on various datasets.

6.1 Comparative study of classifiers

The average classifier accuracies and the CPU time elapsed in performing the experiments for all algorithms are shown in Tables 2 and 3 respectively. In addition to the average accuracy and the CPU time in tabular format, the run time prequential accuracies per chunk of the algorithms with processed instances is also depicted with help of graph plots as shown in Fig. 5a–h, for all utilized data stream generators. In the graphical representation, the X-axis represents the processed instances and the Y-axis represents the prequential accuracy achieved by the classifiers per data chunk.

The graphs in Fig. 5a depicts the prequential accuracies of all algorithms on hyperplane (HYP) data stream generator. The hyperplane data stream generator generates data streams with incremental drifts. From Table 2, it can be observed that the ADAW is leading over the rest of the classifiers with an average accuracy of 94.86 %. The ADAW is very closely followed by WMA, which has shown an average accuracy of 94.07%. The minimum average accuracy of 84.17% is shown by NB. As given in Table 3, the CPU time consumed by Lev is 1548.03 seconds which highest among all other evaluated methods. The ADAW consumed CPU time of 403.03 seconds, which is very large as compared to NB that has taken CPU time of 0.92 seconds only. In the presence of incremental concept drifts, the concepts keep changing very slowly within the data stream; therefore, each consecutive data chunk has high possibility of having a very low deviation in the feature values. Generally, such consideration of consecutiveness among the component classifiers can be inherently achieved by maintaining the order of insertion of new component classifiers in the ensemble. The ADAW maintains this generalization by utilizing the array-based ensemble structure. The array-based ensemble structure also maintains the temporal and spatial locality of reference for the underlying data distribution of the data stream. The obvious reason for the over the performance of ADAW on other methods is that the ADAW has utilized the remaining age factor $\tau$ while calculating the weights of the component classifiers. From the graphs in Fig. 5a it can be observed that at many points of time, the ADAW outperforms its nearest competitor WMA.

The graphs in Fig. 5b show the average accuracy of evaluated methods on the SEA data stream. The sea data stream contains sudden drifts. The ADAW performs well with an average accuracy of 89.32% as compared to other methods on the SEA data stream. For this dataset, the ADWA is followed by AUE and Lev, which gave an average accuracy of 88.26% and 88.31% respectively. The very often property of any classifier used for the classification of the data stream containing sudden drifts is that the accuracy of the classifier drops suddenly. This property can be easily verified by the graphs in Fig. 5b. An intuitive solution for caring for the presence of sudden drifts in the data stream can be obtained by always updating the classifiers with the recent data distribution of the data stream. In an ensemble approach, this requirement of routine updating can be satisfied by simply having the newly inserted component classifier trained over the recent data chunk. The ADAW fulfills this requirement by always adding the new component classier trained on the recent data chunk. In ADAW, the remaining age value $(\tau)$ of the newly inserted classifier is always highest among the rest of the component classifiers present in the ensemble, hence the newly inserted classifiers assigned with the highest weight in the ensemble. Due to the highest weight of the newly inserted classifiers, it attains the highest value in the decision integration rule. As given in Table 3 the ADAW takes CPU time of 45.21 seconds, which is very less than the CPU time consumed by Lev that holds 2nd position in terms of average accuracy but utilized the CPU time of 197.74 seconds. The NB has shown the worst performance with an average accuracy of 86.05% but consumed the least CPU time of only 0.46 seconds.

The graphs in Fig. 5c shows the runtime accuracies of all evaluated methods on the RBF data stream. The RBF dataset contains gradual drifts. For this dataset, two drifts are introduced at instance 400K and 800k. From the graph, it can observe that the accuracies of the evaluated classifiers can be partitioned in three fluctuating range of accuracies 50% to 75%, 80% to 90% and more than 90%. The AUE, Lev, and ADAW belong to the range having accuracies more than 90% with a highest average accuracy of 98.82% is given by ADAW that is sharply followed by AUE and Lev showing average accuracy of 98.03% and 98.72% respectively. A drop in average runtime accuracy can be observed at 300K for DWM, NB, AWE, DDM and at 800K for HOT and WMA. Similarly, a slight drop in prequential accuracies is also observed between 300K and 400K for AUE and Oza. However, the ADAW has shown quite a consistent accuracy throughout the stream. From Table 3, it can be observed that a very high CPU time of 1037.25 seconds is consumed by Lev as compared to NB which has only consumed the CPU time of 4.07 seconds. For the RBF dataset, the ADAW consumes a reasonable CPU time of 443.36 seconds and tries to maintain a kind of trade-off between accuracy and CPU time.

The graphs in Fig. 5d depicts the accuracy of all algorithms including ADAW on the data stream generated by the Random Tree Generator (RTG). The RTG contains recurring drifts. From Table 2 it can be observed that ADAW attained average accuracy of 93.49%, which is maximum for the given set of algorithms and slightly better than the average accuracy of Lev, which is 93.37%. The NB performed worst in the RTG data stream generator with an average accuracy of 58.37% only. As shown in Table 3, the largest CPU time of 1222.36 seconds is consumed by Lev which is very high, whereas ADAW consumed CPU time of 307.43 seconds. The least CPU time is consumed by NB which is about 0.81 seconds. From the graphs in Fig. 5d, it can be easily observed that ADAW is closely followed by AUE and Lev, however, the ADAW gained more accuracy over AUE at some points around 450K and 700K. This gain in the accuracy of ADAW is due to the property of ADAW that allows only newly inserted component classifier to be trained by the recent data chunk and restricts old component classifiers only for testing instead of learning on recent data chunk. By doing this, the ensemble preserves some outdated concepts with it.

The graphs in Fig. 5e depicts the accuracy of all algorithms on the LED data stream generator. For the LED dataset all methods show a relatively low accuracy as compared to other datasets. The accuracies for this dataset ranges between 70% to 75% only. Here, the ADAW outperforms with an average accuracy of 74.15%. The standard deviation of the average accuracies of all selected methods is very small. In LED, the ADAW is immediately followed by DDM and NB with an average accuracy of 74.13% for both. From Table 3, it can be observed that the DWM consumed the highest CPU time of 139.68 seconds and NB has consumed the lowest CPU time of 2.07 seconds as compared to all other evaluated algorithms. The proposed method, ADAW has consumed a considerably moderate amount of CPU time of 60.23 seconds.

The graphs in Fig. 5f are showing the runtime accuracies of the evaluated methods on the LED-Drift artificial dataset. The LED-Drift data stream generator generates data streams with mixed type concept drifts. With the mixed type of concept drifts, the LED-Drift simulates the real-world drifting data stream to a considerable degree. As it can be easily observed from the graphs that the evaluated algorithm can be classifies into two sets, the one set to include those methods which are performing relatively more accurately and consistent towards the introduced drifts at instances 300K, 600K, and 900K. This set includes DWM, Lev, ADAW, AWE, DDM, and AUE. The other set includes those methods which are relatively less consistent and accurate. This set include NB, WMA, HOT, VFDT, and Oza. From the graphs in Fig. 5f, a clear drop in accuracies can be observed for the algorithms belong to the later set. For the LED-Drift dataset, the best average accuracy is shown by ADAW which is 73.84%. Here, the ADAW performs slightly better than AUE, AWE, DDM, DWM, and Lev, which are showing the accuracy of 73.64%, 73.66%, 73.70%, 73.71% and 73.71% respectively. For this dataset, NB has shown the worst performance with 62.45% and it is most inconsistent too. From Table 3, it can observe that the highest CPU time of 132.46 seconds is consumed by DWM and the lowest CPU of 2.07 seconds is consumed by NB, however, the ADAW again consumed the moderate CPU time of 61.17 seconds.

The graphs in Fig. 5g show the prequential accuracies of selected methods and ADAW on the Poker-Hand (Poker) real dataset whose drift type is unknown. The selected methods for this dataset show very low average accuracies as compared to other datasets used for performing empirical evaluation in this work. The average accuracies ranged between 47% to about 50.5% only. Despite of low accuracies, the performance is quite consistent for all methods in the Poker dataset. The ADAW shows the best average accuracy with 51.39% and the worst average accuracy is shown by AWE with 47.61% however the standard deviation of the averages accuracies is very low for the Poker dataset. As given in Table 3, the Oza takes the highest CPU time of 54.94 seconds and the NB consumed only 1.90 seconds for training and testing, however, the takes only 19.37 seconds of CPU time and provides the best accuracy for Poker dataset.

The prequential accuracies of analyzed methods over the Forest Cover Type (Cov) dataset are shown by the graphs in Fig. 5h. The Cov dataset is among the prominent datasets used for evaluating massive data mining methods. For the Cov dataset, the best accuracy is shown by Lev with 92.06% which is slightly better than ADAW that has shown the average accuracy of 91.83%. The NB is the worst performer with an average accuracy of 61.07%, which also performs very inconsistently as its runtime accuracies range from 41% to 80%. From Table 3, it can be noted that the Oza consumed the highest CPU time of 159.07 seconds and for NB CPU time of 4.37 seconds is elapsed, whereas a moderate amount of 63.17 is only consumed by ADAW.

6.2 Statistical analysis

In order to extend our analysis, we performed statistical analysis to get clearer insights into the experimental results. We performed nonparametric related-samples Friedman’s two-way analysis of variance by ranks to observe the statistical significance of accuracies and the CPU time of the experimented algorithms over different datasets. We started with the null hypothesis $h_{0}$ as given in Eq. (11) for average accuracies and CPU time distributions.

$\displaystyle h_{0}=\left\{{{\begin{array}[]{c}{\text{The distributions of AUE% },\text{AWE},}\\ {\text{DDM},\text{DWM},\text{HOT},\text{Lev},\text{NB},}\\ {\text{Oza},\text{VFDT},\text{WMA and}}\\ {\text{ADAW are the same.}}\\ \end{array}}}\right\}$ (11)

Table 4

Statistical observation of related-samples friedman’s two-way analysis of variance by ranks

Performance parameter	Null hypothesis	Significance level	Asymptotic significance two-sided test	Test statistic (chi square)	Degree of freedom (df)	Decision
Accuracy	$h_{0}$	0.05	0.000068 $\approx$ 0	36.52	10	Reject $h_{0}$
CPU time	$h_{0}$	0.05	$\approx$ 0	64.932	10	Reject $h_{0}$

Table 5

Mean ranks of evaluated algorithms

Performance parameter	AUE	AWE	DDM	DWM	HOT	Lev	NB	Oza	VFDT	WMA	ADAW
Accuracy	6.94	3.63	6.00	5.75	5.81	8.19	2.88	5.13	4.06	6.75	10.88
CPU time	8.50	7.75	2.00	6.75	4.75	9.88	1.13	9.50	3.00	5.50	7.25

Table 4 shows the statistical observations of related-samples Friedman’s two-way analysis of variance by ranks. As given in Table 4, the test statistic (Chi-Square) values are 36.52 and 64.93 for accuracies and CPU Times of the different algorithms respectively. Considering the significance level $=$ 0.05, the null hypothesis $h_{0}$ set for both accuracy and CPU time are get rejected as the asymptotic significance is for both are $\approx$ 0.

Table 5 shows the mean ranks of evaluated algorithms for average accuracies and CPU time. Note that for accuracies the higher mean rank is better and for CPU time the lower mean rank is better. From Table 5, it can be noted that ADAW holds 1 ${}^{\text{st}}$ mean rank in terms of accuracy and 5th rank in terms of CPU time among all other evaluated algorithms. Although, the NB holds 1 ${}^{\text{st}}$ rank for CPU Time, but it holds the last rank as far as accuracy is concerned. Figure 6 depicts related-samples Friedman’s two-way analysis of variance by ranks based on the accuracies of the evaluates algorithms.

Figure 6.

Related-samples friedman’s two-way analysis of variance by rank for accuracies of evaluated algorithms.

Figure 7.

Pairwise comparisons of different algorithms for their accuracies.

In addition to Friedman’s test, we also applied the Bonferroni test to statistically perform the multiple comparison test among the evaluated algorithms. Figure 7 shows a graphical representation comparison table that we received after applying the Bonferroni test. This represents depicts the pairwise comparisons of different algorithms for their mean ranks with respect to the accuracies. In the graph of Fig. 7, each node shows the mean rank of evaluated algorithms, the blue edges represent those pairs of algorithms for which there are statistically significant differences among the pairs and the red edges represent those algorithms pairs for which the statistical difference are nonsignificant. On applying the Bonferroni test, we observed that the ADAW performs significantly better than OzaBag, VFDT, NB, and AWE, however, the statistical significances are not enough to draw the same conclusion for rest of the algorithms. We also performed the same kind of statistical analysis for CPU time elapsed by all the algorithms and observed that ADAW is significantly faster than Lev and Oza. For the rest of the methods, the differences are nonsignificant to reach the same conclusion.

7. Conclusion

In this paper, we proposed a novel method called Age Decay Accuracy Weighted (ADAW) for the classification of concept drifting data streams. The ADAW follows an array-based ensemble architecture, where the weights to the component classifiers are assigned and updated based on the remaining age and accuracies for the recent data chunk. The novelty of the ADAW is its architecture and its weight assignment mechanism for the component classifiers. We empirically evaluated the performance of ADAW with ten existing state-of-art classifiers over six large artificial datasets and two large real-world datasets comprised of recurring, gradual, sudden and mixed kinds of drifts. The results show the ADAW performs very well for all kind of drifts and over performs most of the algorithms that we have evaluated. While performing empirical evaluation for different algorithms and datasets, we observed that the ensemble-based methods suffer from accuracy drop in the presence of sudden concept drifts and the drift detection-based methods are less sensitive to the gradual drifts. We also observed that ensemble-based methods are more robust towards abrupt changes as compared to single classifiers. As future work, we are planning to explore the opportunity of adaptiveness in ADAW where we are used a fixed size data chunk. We believe that, by having an adaptive data chunk size, we can reduce the average learning time sufficiently.

References

Aggarwal

C.C.

, Data streams: models and algorithms, Springer Science & Business Media, 2007.

Aggarwal

C.C.

Han

Wang

and Yu

P.S.

, On demand classification of data streams, in: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2004, pp. 503–508.

Bifet

and Kirkby

, Data stream mining a practical approach, 2009.

Gama

, A survey on learning from data streams: current and future trends, Progress in Artificial Intelligence 1(1) (2012), 45–55.

Khan

, Data stream mining: challenges and techniques, in: Tools with Artificial Intelligence (ICTAI), 2010 22nd IEEE International Conference on, IEEE, Vol. 2, 2010, pp. 295–295.

Srivastava

and Bhatia

, Offline vs. online sentiment analysis: issues with sentiment analysis of online micro-texts, International Journal of Information Retrieval Research (IJIRR) 7(4) (2017), 1–18.

Han

Pei

and Kamber

, Data mining: concepts and techniques, Elsevier, 2011.

Muthukrishnan

, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science 1(2) (2005), 117–236.

Minku

L.L.

and Yao

, DDD: a new ensemble approach for dealing with concept drift, IEEE Transactions on Knowledge and Data Engineering 24(4) (2012), 619–633.

10.

Laney

, 3D data management: Controlling data volume, velocity and variety, Meta Group/Gartner, ed, 2001.

11.

Brzezinski

and Stefanowski

, Reacting to different types of concept drift: the accuracy updated ensemble algorithm, IEEE Transactions on Neural Networks and Learning Systems 25(1) (2014), 81–94.

12.

Domingos

and Hulten

, Mining high-speed data streams, in: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2000, pp. 71–80.

13.

Brzeziński

, Mining data streams with concept drift, Master’s thesis, Poznan University of Technology, 2010.

14.

Ditzler

Roveri

Alippi

and Polikar

, Learning in nonstationary environments: a survey, IEEE Computational Intelligence Magazine 10(4) (2015), 12–25.

15.

Kelly

M.G.

Hand

D.J.

and Adams

N.M.

, The impact of changing populations on classifier performance, in: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 1999, pp. 367–371.

16.

Srivastava

and Bhatia

, Ensemble methods for sentiment analysis of on-line micro-texts, in: Recent Advances and Innovations in Engineering (ICRAIE), 2016 International Conference on, IEEE, 2016, pp. 1–6.

17.

Minku

L.L.

White

A.P.

and Yao

, The impact of diversity on online ensemble learning in the presence of concept drift, IEEE Transactions on Knowledge and Data Engineering 22(5) (2010), 730–742.

18.

Žliobaitė

, Learning under concept drift: an overview, arXiv preprint arXiv:1010.4784, 2010.

19.

Brzeziński

and Stefanowski

, Accuracy updated ensemble for data streams with concept drift, Hybrid artificial intelligent systems, 2011, 155–163.

20.

Minku

L.L.

, Online ensemble learning in the presence of concept drift, University of Birmingham, 2011.

21.

Vivekanandan

and Nedunchezhian

, Mining data streams with concept drifts using genetic algorithm, Artificial Intelligence Review 36(3) (2011), 163–178.

22.

Dehghan

Beigy

and ZareMoodi

, A novel concept drift detection method in data streams using ensemble classifiers, Intelligent Data Analysis 20(6) (2016), 1329–1350.

23.

Frías-Blanco

Verdecia-Cabrera

Ortiz-Díaz

and Carvalho

, Fast adaptive stacking of ensembles, in: Proceedings of the 31st Annual ACM Symposium on Applied Computing, ACM, 2016, pp. 929–934.

24.

Sun

Tang

Minku

L.L.

Wang

and Yao

, Online ensemble learning of data streams with gradually evolved classes, IEEE Transactions on Knowledge and Data Engineering 28(6) (2016), 1532–1545.

25.

Kuncheva

L.I.

, Classifier ensembles for changing environments, Multiple Classifier Systems 3077 (2004), 1–15.

26.

Baena-García

del Campo-Ávila

Fidalgo

Bifet

Gavaldà

and Morales-Bueno

, Early drift detection method, 2006.

27.

Elwell

and Polikar

, Incremental learning of concept drift in nonstationary environments, IEEE Transactions on Neural Networks 22(10) (2011), 1517–1531.

28.

Chen

and Xu

, Incremental learning from stream data, IEEE Transactions on Neural Networks 22(12) (2011), 1901–1914.

29.

Gama

Medas

Castillo

and Rodrigues

, Learning with drift detection, in: Brazilian Symposium on Artificial Intelligence, Springer, 2004, pp. 286–295.

30.

Bifet

and Gavalda

, Learning from time-changing data with adaptive windowing, in: Proceedings of the 2007 SIAM International Conference on Data Mining, SIAM, 2007, pp. 443–448.

31.

Kuncheva

L.I.

, Classifier ensembles for detecting concept change in streaming data: Overview and perspectives, in: 2nd Workshop SUEMA, Vol. 2008, 2008, pp. 5–10.

32.

Krawczyk

Minku

L.L.

Gama

Stefanowski

and Woźniak

, Ensemble learning for data stream analysis: a survey, Information Fusion 37 (2017), 132–156.

33.

Schlimmer

J.C.

and Granger

R.H.

, Incremental learning from noisy data, Machine Learning 1(3) (1986), 317–354.

34.

Yang

and Mao

, A self-adaptive sliding window technique for mining data streams, Intelligence Computation and 465 (2013), 689–697.

35.

Kifer

Ben-David

and Gehrke

, Detecting change in data streams, in: Proceedings of the Thirtieth International Conference on Very Large Data Bases-Volume 30, VLDB Endowment, 2004, pp. 180–191.

36.

Klinkenberg

and Joachims

, Detecting Concept Drift with Support Vector Machines, in: ICML, 2000, pp. 487–494.

37.

Hulten

Spencer

and Domingos

, Mining time-changing data streams, in: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2001, pp. 97–106.

38.

Bifet Figuerol

A.C.

and Gavaldà Mestre

, Adaptive parameter-free learning from evolving data streams, 2009.

39.

Pfahringer

Holmes

and Kirkby

, New options for hoeffding trees, in: Australasian Joint Conference on Artificial Intelligence, Springer, 2007, pp. 90–99.

40.

Klinkenberg

and Renz

, Adaptive information filtering: Learning in the presence of concept drifts, Learning for Text Categorization, 1998, 33–40.

41.

Corchs

Fersini

and Gasparini

, Ensemble learning on visual and textual data for social image emotion classification, International Journal of Machine Learning and Cybernetics 10(8) (2019), 2057–2070.

42.

Alqurashi

and Wang

, Correction to: a novel adaptive clustering ensemble method, International Journal of Machine Learning and Cybernetics 10(6) (2019), 1247–1247.

43.

Alqurashi

and Wang

, Clustering ensemble method, International Journal of Machine Learning and Cybernetics 10(6) (2019), 1227–1246.

44.

Elliott

Santosh

and Anderson

, Gradient boosting in crowd ensembles for Q-learning using weight sharing, International Journal of Machine Learning and Cybernetics, 2020, 1–13.

45.

Breiman

, Bagging predictors, Machine Learning 24(2) (1996), 123–140.

46.

Bifet

Holmes

and Pfahringer

, Leveraging bagging for evolving data streams, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2010, pp. 135–150.

47.

Oza

N.C.

, Online bagging and boosting, in: Systems, Man and Cybernetics, 2005 IEEE International Conference on, IEEE, Vol. 3, 2005, pp. 2340–2345.

48.

Littlestone

and Warmuth

M.K.

, The weighted majority algorithm, Information and Computation 108(2) (1994), 212–261.

49.

Kolter

J.Z.

and Maloof

M.A.

, Dynamic weighted majority: an ensemble method for drifting concepts, Journal of Machine Learning Research 8(Dec) (2007), 2755–2790.

50.

Street

W.N.

and Kim

, A streaming ensemble algorithm (SEA) for large-scale classification, in: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2001, pp. 377–382.

51.

Wang

Fan

P.S.

and Han

, Mining concept-drifting data streams using ensemble classifiers, in: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2003, pp. 226–235.

52.

Gomes

H.M.

Barddal

J.P.

Enembreck

and Bifet

, A survey on ensemble learning for data stream classification, ACM Computing Surveys (CSUR) 50(2) (2017), 23.

53.

Domingos

and Hulten

, A general framework for mining massive data streams, Journal of Computational and Graphical Statistics 12(4) (2003), 945–949.

54.

Farid

D.M.

et al., An adaptive ensemble classifier for mining concept drifting data streams, Expert Systems with Applications 40(15) (2013), 5895–5906.

55.

Nishida

, Learning and detecting concept drift, Graduate School of Information Science and Technology, Hokkaido University, 2008.

56.

Alpaydin

, Introduction to machine learning, MIT press, 2014.

57.

Gama

Sebastião

and Rodrigues

P.P.

, On evaluating stream learning algorithms, Machine Learning 90(3) (2013), 317–346.

58.

Bifet

and Frank

, Sentiment knowledge discovery in twitter streaming data, in: International Conference on Discovery Science, Springer, 2010, pp. 1–15.

59.

Breiman

Friedman

Stone

C.J.

and Olshen

R.A.

, Classification and regression trees, CRC press, 1984.

60.

Blackard

J.A.

, Comparison of neural networks and discriminant analysis in predicting forest cover types, 2000.

61.

Cattral

Oppacher

and Deugo

, Evolutionary data mining with automatic rule generalization, Recent Advances in Computers, Computing and Communications 1(1) (2002), 296–300.

62.

Krawczyk

and Woźniak

, Designing cost-sensitive ensemble-genetic approach, in: Image Processing and Communications Challenges 3, Springer, 2011, pp. 227–234.

ADAW: Age decay accuracy weighted ensemble method for drifting data stream mining

Abstract

Keywords

1. Introduction

2.1 Concept drifts

3.1 Windowbased strategies

4.2 Learning and testing strategy of ADAW

5. Data collection and experimental setup

Table 1 Dataset characteristics

5.2 Experimental setup

6. Comparative study and result analysis

Table 2 Average classification accuracies in percentage [%]

6.2 Statistical analysis

References

Table 1
Dataset characteristics

Table 2
Average classification accuracies in percentage [%]