Dynamic Weighted Majority for Incremental Learning of Imbalanced Data Streams with Concept Drift

1 Introduction

In the online learning process, the underlying data distribution may change over time. This phenomenon is known as concept drift or non-stationary environment [Ditzler et al., 2015]. To deal with it, one must confront the problem of stability-plasticity dilemma [Ditzler and Polikar, 2013]. That is, an algorithm has to balance the learning focus between the past information and the incoming distribution changes. Based on Bayes' theorem, the concept drift can occur in three of four components in the Bayes' formula and the rest one can be obtained by the other three [Ditzler et al., 2015]:

∗Yiu-ming Cheung is the corresponding author. This work was supported by the National Natural Science Foundation of China with the Grant Numbers: 61672444 and 61272366, by the SZSTI Grant: JCYJ20160531194006833, and by the Faculty Research Grant of Hong Kong Baptist University (HKBU) with the Project Codes: FRG2/16-17/051 and FRG2/15-16/049.

• Data distribution p(x): It is also called virtual drift. The distribution of x changes without affecting the decision hyperplane.
• Posterior probability p(y|x): It is also called real drift. The decision hyperplane is shifted because the conditional probability changes.
• Class prior p(y): It affects the imbalance ratio that the position of the minority class and the majority class may be switched.

These three types of drifts may occur separately or simultaneously at any time in the data stream. Let us take fault diagnosis as an example that the faulty samples are the minority class [Wang et al., 2013b]. If the percentages of producing different types of samples change, it corresponds to the drift of p(x). If the standard to diagnose a fault is improved so that more samples are identified as faults sometime, it corresponds to the drift of p(y|x). Furthermore, if the cause of the fault is not fixed, the number of the faulty samples will increase and finally becomes the majority class, it corresponds to the drift of p(y).

Classifying imbalanced data is another challenging problem [He and Garcia, 2009; Branco et al., 2016]. Directly applying standard learning algorithm tends to ignore the minority class samples because of their subtle influence on the accuracy of an algorithm. Evidently, the problem will become more complicated if concept drift occurs together with class imbalance. When the concept of the minority class drifts, it is difficult to learn the new concept because the minority class samples seldom appear in the data stream. Thus far, only several methods have been proposed to tackle the problem of concept drift with class imbalance. In the literature, adaptive methods [Gao et al., 2007; Wu et al., 2014] and ensemble methods [Elwell and Polikar, 2011; Krawczyk et al., 2017] are two major groups. The former updates the classifier on the current chunk, while the latter builds a model for each chunk and combines them as an ensemble. As for the issue of imbalance, adaptive methods collect the minority class samples in the past chunks and integrate them into the training samples in the current chunk for minority class augmentation. However, it is not always effective because the concept of the minority class may vary over time if concept drift of p(y) occurs. By contrast, ensemble methods usually apply imbalance oriented learner as the base classifier in the ensemble. However, it is hard to weigh the base classifiers trained on different timestamps and maintain a limited number of classifiers to prevent the number of base classifiers infinitely increasing.

In this paper, we propose a new chunk-based incremental learning method called Dynamic Weighted Majority for Imbalance Learning (DWMIL) to deal with binary class imbalanced data streams with concept drift. It utilizes an ensemble framework with dynamic base classifier weighting. The classifier weights depend on the imbalance aware error of the classifier tested on the current chunk. The classifier with smaller error will receive higher weight in the ensemble because it may be trained on the chunk with similar concept as the current one. The classifier weights are naturally reduced over time based on the accumulated testing error. The advantages of DWMIL are four-fold:

• It can remain stable for stationary streams and quickly adapt to the new concept for non-stationary environment.
• The method is totally incremental. No previous data needs to be stored to help prediction. Therefore, the method does not suffer from memory problems.
• The number of stored classifiers is much less than the current timestamp. The dated classifiers will be discarded so that the ensemble size will not expand infinitely.
• It is simple and efficient. Only one thresholding parameter is needed. The computational cost is very low compared with the other methods.

The main contributions of this paper are summarized below:

• We propose an effective and efficient online learning method DWMIL for imbalanced data stream classification with concept drift.
• Dynamic Weighted Majority (DWM) is extended to the chunk-by-chunk version with more robust performance.

2 RelatedWork

For adaptive methods, Gao et al. [Gao et al., 2007] proposed to accumulate the minority class samples in the current chunk with all past chunks, while carrying on undersampling on the majority class samples to balance the classes. A bagging like ensemble framework is then used for classification. However, it suffers frommemory limitation to store the past data and lacks of the ability to quickly adapt to the new concept. As an improvement, SERA [Chen and He, 2009] and REA [Chen and He, 2011] select only parts of the minority class samples from the past chunks based on the similarity to the minority class samples in the current chunk. Moreover, HUWRS.IP [Hoens and Chawla, 2012] calculates the Hellinger distance between the samples in the current and the past chunks to detect the concept drift. The distance is used as the weight of the base classifier built on different feature subspaces in the ensemble. To handle the imbalance problem, HUWRS.IP

creates a Na¨ıve Bayes classifier on the current chunk to select the similar minority class samples from the past chunks. DFGW-IS [Wu et al., 2014] further improves HUWRS.IP by incorporating the importance sampling technique to collect the positive class samples from the past chunks. In summary, these methods assume that the minority class does not change, and they can therefore utilize the past information. However, from the practical viewpoint, if p(y) changes over time, the past minority class may not be the same as the current minority class.

The ensemble methods usually adopt an incremental fashion, i.e. the data in the past is not saved, because the information of the past data is kept by the base classifiers in the ensemble. Learn++.CDS and Learn++.NIE [Ditzler and Polikar, 2013] create one base classifier for each chunk and use the ensemble to predict the incoming data. The base classifiers are weighed by a time decay function and their performance on the current chunk. ESOS-ELM [Mirza et al., 2015] uses the ensemble of extreme learning machine, where the weight matrices trained on each chunk are stored for ensemble. When the concept drift is detected by a change detector, the ensemble model will be reinitialized.

The methods mentioned above consider the concept drifts provided that the imbalance ratio is fixed. On the other hand, the effect of class prior drift for online learning from imbalanced data has been studied by some researchers. Wang et al. studied the effect of imbalance ratio change and proposed to adjust the training process by dynamic sampling rates [Wang et al., 2015; 2016]. CBCE [Sun et al., 2016] focuses the class evolution problem for multi-class classification. It uses oneversus-rest strategy to create one classifier for each class, and conducts undersampling for the majority class. [Wang et al., 2013a] is the only work to study and analyze the case that class prior drift happens together with the other kinds of concept drift, where a drift detector is proposed with an imbalance detector to deal with the joint concept drift.

3 ProposedMethod

At timestamp t-1, DWMIL maintains m classifiers in the set H(t-1) = {H(t-1) 1 , ..., H (t-1) m } trained on the data chunks from timestamp 1 to t-1. When DWMIL receives a new data chunk D(t) at timestamp t, it learns a new classifier H on the current data chunk and merges H with H(t-1) to form H(t) . The classifiers trained on each chunk are associated with the vector of weights, denoted as w(t) = [w(t) 1 , ...,w(t) m ]T , which measures the importance of the classifiers in the ensemble. When the new classifier H is created, its initial weight is set at 1 and m is increased by 1. In order to adapt to new concept and make the previously learned classifiers less influential in the ensemble, the weight w(t) j for classifier H(t) j is reduced on each timestamp after it is created:

where j = 1, ...,m-1 and ϵ(t) j is the testing error of H(t) j on the current data chunk D(t) . The error ϵ(t) j can be calculated by any error function like F1 or G-mean. Thus, the weights of the classifiers trained on the past chunks are reduced based on the their performance on the current data chunk. Since this weight reduction is accumulated over time, the weight w(t) j is actually equals to:

where l is the timestamp when H(t) j is created. As 1-ϵ(τ) j ≤ 1, the classifier weight is getting smaller over time according to its error on each chunk after it is created. Then, the classifiers with weight less than the threshold θ are removed and the counter m is also reduced according to the number of classifiers left. If a classifier is going to be removed, there are two factors that make its weight lower than θ. One is that the classifier is trained on a very early timestamp that makes the production in Equation (1) small. The other is that the concept changes in recent chunks and the testing error of the classifier is large on those chunks. Thus, this kind of classifier is less likely to provide positive effects to the prediction on the current and following chunks. Finally, the model predicts the incoming data x in D(t+1) by the ensemble of H(t) associated with w(t) :

The training process of the proposed method DWMIL is shown in Algorithm 1. In DWMIL, we use UnderBagging as the base learner to train imbalanced data as shown in Algorithm2. In each bagging iteration, we carry on undersampling on the majority class to make the training data balanced.

The relations between DWMIL and the existing methods are discussed as follows:

• Relation with Dynamic Weighted Majority (DWM) [Kolter and Maloof, 2007]: Both DWMIL and DWM keep a number of classifiers during learning the data streams. Despite the use of the imbalance oriented classifier UnderBagging as the base classifier in DWMIL, DWMIL has some other improvements over DWM. DWM processes the data one-by-one and updates the classifiers on every p incoming samples. If the data stream is imbalanced, the occurrence frequency of the minority class sample will be very low. Thus, updating a long sequence of majority class sample will be likely to make the model biased. By contrast, processing the imbalanced data stream chunk-by-chunk as DWMIL does will be more stable. DWM decides to create a new classifier according to the prediction performance of a single sample. If the data is imbalance, the probability that the sample belongs to the majority class is much higher than the minority class, and the probability to misclassify a majority class sample is low. Thus, the chance to create new classifiers on imbalanced data stream is low. It turns out that it may not efficiently adapt to the new concept. In comparison, DWMIL creates a new classifier for each chunk to learn the new concept in time. Besides, in DWM, the weights are reduced by a fixed parameter β and actually reduced again after normalization. Instead, DWMIL reduces the weight based on the performance without any

Algorithm 1 Train DWMIL

• Input: Data chunk at timestamp t: D(t) = {xi ∈ X, yi ∈ Y}, i = 1, ...,N, threshold for deleting base classifiers θ, base classifier set H(t-1) = {H(t-1) 1 , ..., H (t-1) m }, weight of base classifiers w(t-1) , number of base classifiers m, ensemble size T .
• 1: for i ← 1 to N do
• 2: Predict xi by the ensemble classifier:

• 3: end for
• 4: for j ← 1 to mdo
• 5: Calculate the error ϵ(t) j for classifier H(t-1) j on D(t) ;
• 6: Update weight of base classifiers: w(t) j ← (1- ϵ(t) j )w(t-1) j ;
• 7: end for
• 8: Remove classifiers with weights less than θ:

Output: Base classifier set H(t) , weight of base classifiers w(t) , number of base classifiers m, prediction ¯y.

Algorithm 2 UnderBagging

Input: Data D = {xi ∈ X, yi ∈ Y}, i = 1, ...,N, the number of positive samples Np, the number of negative samples Nn, ensemble size T .

• 1: for t ← 1 to T do
• 2: if Np < Nn then

3:

Ns ← Np;

• 4: else
• 5: Ns ← Nn;
• 6: end if
• 7: Dp ←Bootstrap Ns positive samples;
• 8: Dn ←Bootstrap Ns negative samples;
• 9: ht ←BaseLearner({Dp,Dn});
• 10: end for
• normalization. Thus, a classifier can last longer to contribute to the prediction if the current concept is similar to the one when the classifier is created.
• Relation with Learn++ framework [Elwell and Polikar, 2011]: Both Learn++ and DWMIL create classifiers for each chunk and use classification error to adjust the weights. However, Learn++ uses a time decay function σ to reduce the weights of the classifiers trained on the past chunks. This σ depends on two free parameters: a and b, where different values of them will produce diverse results. In DWMIL, the weight reduction only depends on the performance of the classifiers without free

Output: Base classifier H(x) = sign(∑Tt=1 ht(x));

parameters. Furthermore, in Learn++, the weights depend not only on the current chunk, but also the chunks from the classifier that is created to the current chunk. Under the circumstances, it may produce bias. Specifically, if one classifier performs very well on the chunk where it is created, it will receive continuously higher weights in the following several chunks. If the concept changes, the high weight of the classifier trained on old concept will hinder the prediction. In addition, Learn++ keeps all classifiers over time. The accumulated classifiers will increase the computational burden if the data stream is very long or even life long, because it needs to evaluate the performance of all past classifiers on the current chunk. By contrast, DWMIL discards the dated or useless classifiers to increase the computational efficiency.

4 Experimental Results

To evaluate the effectiveness and efficiency of DWMIL 1 , we compare it with four other state-of-the-art methods, which are designed for imbalanced data stream with concept drift, on four synthetic data sets and two real data sets.

4.1 Experiment Settings

The compared methods and their settings are described as follows. Learn++.NIE (LPN) [Ditzler and Polikar, 2013] and Recursive Ensemble Approach (REA) [Chen and He, 2009] are selected as a representative of ensemble methods and adaptive methods, respectively. Class-Based ensemble for Class Evolution (CBCE) [Sun et al., 2016] with drift detector DDM [Wang et al., 2013a] is selected as the representative of active drift detection methods. We also compare the original version of Dynamic Weighted Majority (DWM) [Kolter and Maloof, 2007], which is not essentially designed for imbalanced data stream. Accordingly, we adopt the Undersampling Online Bagging (UOB) technique [Wang et al., 2015] for DWM. The parameters of the compared methods are set at the recommended values in the literature. For DWMIL, LPN and DWM, the number of base classifiers in the ensemble T is set at 11 to prevent draw result. For DWMIL, the threshold to remove the dated classifier θ is set at 0.001. As discussed in [Kolter and Maloof, 2007], the value of θ has nearly no influence to the accuracy, and it only affects the number of stored classifiers. Geometric mean (G-mean) error ϵgm = 1 - √TPR · TNR is chosen as the error function used in LPN and DWMIL, where TPR is the true positive rate and TNR is the true negative rate. In fact, any other error functions like F1 measure can also be used as the error function. Here, we only adopt G-mean error as the error function due to space limitation. CART [Breiman et al., 1984] is used as the learner of the base classifier for all methods. All results are averaged by 10 runs of the experiments. We use G-mean and Area Under Curve (AUC) as the evaluation metrics to compare all methods. The test-then-train strategy is adopted to evaluate the performance of the methods on each chunk.

1 Source code and data sets used in the experiments can be obtained from https://github.com/lylylytc/dwmil

4.2 Data Sets

In the experiments, we utilize four synthetic data sets and two real data sets, whose information is summarized in Table 1. The percentage of the minority class samples in each chunk is fixed at 5% of the chunk size.

Moving Gaussian: This data stream consists of two Gaussian distributed classes with identity covariance and 2 dimensions. The initial coordinates of the mean of the two classes are [5,0] and [7,0]. The two classes gradually move to [-5,0] and [-3,0] from the first to the last chunk.

SEA [Street and Kim, 2001]: It contains three attributes ranging from 0 to 10. Only the first two attributes are related to the class that is determined by attr1 + attr2 ≤ α. The third attribute is treated as noise. The control parameter α is set at 15 for the first 1/3 and the last 1/3 chunks, and 5 for the second 1/3 chunks.

Hyper Plane [Street and Kim, 2001]: The gradually changed concepts are calculated by f(x) = ∑d-1 i=1 ai · xi+xi+1 xi , where the dimension d = 10 and ai is used to control the decision hyperplane.

Checkerboard [Ditzler and Polikar, 2013]: It is a nonlinear XOR classification problem. The data stream is produced by selecting from a size-fixed window in the rotating checkerboard.

Electricity [Kolter and Maloof, 2007]: This data set contains the changes of electricity price according to the time and demand in New South Wales, Australian. The class label is determined by the change of price over the last 24 hours.

Weather [Ditzler and Polikar, 2013]: This data set contains the weather information over 50 years in Bellevue and Nebraska. The task is to predict whether a day is rainy or not.

4.3 Comparative Results

The G-mean and AUC performance on each chunk is shown in Figure 1 and 2. The observation of the experiments on each data set is discussed as follows. The results of data set Moving Gaussian are shown in Figure 1(a) and 2(a). The performance of DWMIL and DWM are comparable through all chunks in terms of G-mean and both of them perform better than LPN. CBCE predicts all samples as negative and therefore receives 0 in G-mean. A plausible reason is that the data set of Moving Gaussian is continuously drifting. Thus, CBCE resets its model on every several samples so that it poorly learns the minority class samples. The performance of REA gradually drops to 0 because the stored past minority class samples are overlapped with the majority class samples in the current chunk due to the distribution moving. Incorporating them into the training set equals to adding noises to the minority class. In terms of AUC, DWMIL shows better performance than the others along all chunks. The results of data set SEA are shown in Figure 1(b) and 2(b). The two significant performance drops correspond to the drifts of the decision hyperplane. In terms of G-mean, DWMIL recovers its performance quickly on the first drift compared with the other methods, which shows the ability of DWMIL to adapt to the new concept. DWM also responds quickly, but it spends around 15 chunks to recover the performance. LPN stays at the valley for around 7 chunks before starting to recover the performance. In terms of AUC, DWMIL and LPN show comparable results and recovery speed. The AUC performance of REA shows good ability to resist concept drift by the stored samples. It is not influenced by the second drift. The results of data set Hyper Plane are shown in Figure 1(c) and 2(c). DWMIL shows slightly better performance than the DMW in terms of G-mean. The AUC performance of DWMIL is close to LPN and both of them are better than DWM, REA and CBCE. The results of data set CheckerBoard are shown in Figure 1(d) and 2(d). In terms of G-mean, DWMIL, REA

and LPN produce similar overall results. However, it can be observed that DWMIL is more stable against concept drifts, while the AUC performance of LPN and REA appear to have small drops frequently. The results of data set Electricity and Weather are shown in Figure 1(e-f) and 2(e-f), respectively. DWMIL shows generally better performance than LPN and REA in terms of G-mean, and comparable performance with them in terms of AUC.

In order to compare the overall performance, the averaged numerical results over all chunks are shown in Table 2 and 3. The significance test is conducted between the best and the second best result by Wilcoxon signed rank test with 95% confidence interval. It can be observed that, for G-mean, DWMIL achieves significantly better results than the other methods on four data sets. For AUC, DWMIL significantly outperforms the other methods on three data sets and has comparable results with LPN without significant difference on the other three data sets. The numerical results show that DWMIL can generally produce better results than the other methods on the data sets with the different kinds of concept drifts.

4.4 Efficiency Analysis

The running time for the compared methods on six data sets is shown in Table 4. The computational cost of DWMIL is the lowest compared with the other methods on four data sets. REA has the lowest cost on data sets Electricity and Weather. The reason is that DWMIL adopts bagging with T decision trees as the base classifier on each chunk while REA adopts single decision tree. Thus, REA is faster for the data sets with a smaller number of samples and chunks. However, REA keeps all the classifiers trained on each chunk and searches kNN of all past minority class samples, thus it is slow when the number of chunks is large. For example, on Checkerboard which has 200 chunks, the cost of REA is around five times as high as the cost of DWMIL. Besides, LPN is generally the third fastest but spends almost double time than DWMIL. It also keeps all the classifiers trained on each chunk and the prediction cost will be increasingly higher over time. CBCE and DWM are the slowest because they are one-by-one learning methods. DWM is even slower than CBCE because it updates an ensemble of classifiers for each incoming sample, while CBCE only updates two binary classifiers.

5 Conclusion

From the practical viewpoint, concept drift and class imbalance are two inevitable problems of learning from data streams. The composition of these two phenomenons will make learning from data stream very challenging. In this paper, we have proposed DWMIL to solve the problem of learning from imbalanced data stream with concept drift. It creates a base classifier for each chunk and weigh them by their performance tested on the current chunk. Thus, a classifier trained recently or on the similar concept as the current chunk will receive high weight in the ensemble to help prediction. Experiments on concept drift data sets have shown that DWMIL performs better and more efficiently compared with its counterparts.