Concept Drift Detection for Imbalanced Stream Data

Common statistical prediction models often require and assume stationarity in the data. However, in many practical applications, changes in the relationship of the response and predictor variables are regularly observed over time, resulting in the deterioration of the predictive performance of these models. This paper presents Linear Four Rates (LFR), a framework for detecting these concept drifts and subsequently identifying the data points that belong to the new concept (for relearning the model). Unlike conventional concept drift detection approaches, LFR can be applied to both batch and stream data; is not limited by the distribution properties of the predictor variable (e.g., datasets with imbalanced labels); is independent of the underlying statistical-model; and uses user-specified parameters that are intuitively comprehensible. The performance of LFR is compared to benchmark approaches using both simulated and commonly used public datasets that span the gamut of concept drift types. The results show LFR significantly outperforms benchmark approaches in terms of recall, accuracy and delay in detection of concept drifts across datasets.


I. INTRODUCTION
A common challenge when mining data streams is that the data streams are not always strictly stationary, i.e., the concept of data (underlying distribution of incoming data) unpredictably drifts over time. This has encouraged the need to detect these concept drifts in the data streams in a timely manner, be it for business intelligence or as a means to track the performance of statistical prediction models that use these data streams as input.
This paper focuses on detecting concept drifts affecting binary classification models. For a binary classification problem, concept drift is said to occur when the joint distribution P (X t , y t ) changes over time where X t ∈ R d are the d predictor variables at time step t and y t ∈ {0, 1} the corresponding binary response variable. Intuitively, concept drift refers to the scenario when the underlying distribution that generates the response variable changes over time. Popular approaches for detecting concept drift identify the change point [1], [2]. DDM is the most widely used concept drift detection algorithm, that is strictly designed for streaming data [1]. The test statistic DDM employs is the sum of overall classification error (P (t) error ) and its empirical standard deviation (Ŝ (t) error ). DDM focuses on the overall error rate and hence fails to detect a drift unless the sum of false positive and false negatives changes. An example of such a scenario, is when a 2 × 2 confusion matrix changes from 65 5 15 15 to 75 15 5 5 , thus preserving their overall error rate. This limitation is accentuated in imbalanced classification tasks [2], as seen in the example. Unfortunately, this failure to detect a drastic drop in recall of the minority class is often critical. For instance, if the minority class in the above example corresponded to products at a manufacturing plant that were classified as defective, this critical threefold decrease in 'true positive rate' (i.e., from 0.75 to 0.25) would go unnoticed by DDM.
Drift Detection Method for Online Class Imbalance (DDM-OCI) addresses the limitation of DDM when class ratio is imbalanced [2]. However, DDM-OCI triggers a number of false alarms due to an inherent weakness in the model. DDM-OCI assumes that the concept drift in an imbalanced classification task is indicated by the change of underlying true positive rate (i.e., minority-class recall). This hypothesis unfortunately does not consider the case when concept drift occurs without affecting the recall of the minority class. It can be shown that it is possible for concept to drift from an imbalanced class data to balanced class data, while true positive rate (tpr), positive predicted value (ppv) and F1-score remain unchanged. Thus, this type of drift is unlikely to be detected by DDM-OCI unless other rates such as true negative rate (tnr) or negative predicted value (npv) are also considered. Additionally, the test statistic used by DDM-OCI R (t) tpr is not approximately distributed as N (P tpr , P tpr (1 − P tpr ) N tpr ), under the stable concept. Thus, the rationale of constructing confidence levels specified in [1] is not suitable with the null distribution of R (t) tpr . This is the reason DDM-OCI triggers false alarms quickly and frequently.
Early Drift Detection Method (EDDM) achieves better detection results than DDM if the data stream has slow gradual change. EDDM monitors the distance between the two classification errors [3]. PerfSim algorithm considers all the components of a confusion matrix and monitors the cosine similarity coefficient of all components from two batches of data [4]. If the similarity coefficient drops below some user-specified threshold, a concept drift is signified. However, EDDM requires to wait for a minimum of 30 classification errors before calculating the monitoring statistic at each decision point. That is, the length of a time interval between decision points of a drift is a random number depending on 30 appearances of classification errors. It is possible that there is a great many examples between 30 classification errors. PerfSim algorithms is also constrained by the requirement for collecting mini-batch data to calculate monitoring statistics. The method to partition data stream in [3], [4] is either userspecified by practical experience or to be learned before the start of detection. Hence, EDDM and PerfSim are not well suited for streaming environments in which decisions are made instantly. The approach specified in [5] makes use of SVM to monitor three measures: overall accuracy, recall, and precision over time. This aproach too computes the three measures by assuming that the data arrives in batches, on which SVM is learned.
To address the limitations of existing approaches, we present Linear Four Rates (LFR) for detecting the drift of P (X t , y t ). Unlike other proposed approaches, LFR can detect all possible variants of concept drift, even in the presence of imbalanced class labels, as shown in Section IV. LFR outperforms existing approaches in terms of earliest detection of concept drift, with the least false alarms and best recall. Additionally, LFR does not require the data to arrive in batches and is independent of the underlying classifier employed.

II. PROBLEM FORMULATION
Given that detection of concept drift is equivalent to detecting a change-point in P (X t , y t ), an intuitive approach is to test the statistical hypothesis upon the multivariate variable (X t , y t ) in the data stream [6], [7], [8]. The limitation of this approach is that the performance of the statistical power degrades when the dimension (d) of X t is extremely large or if the magnitude of the drift small. Hence, to overcome these limitations, the proposed approach identifies the change in P (f (X t ), y t ) wheref is the classifier used for prediction. This is motivated by the fact that any drift of P (f (X t ), y t ) would imply a drift in P (X t , y t ), with probability 1.
Letf (X t ) =ŷ t be a binary classifier for the given data stream (X t , y t ). We define the corresponding 2 × 2 confusion probability matrix (CP ) forf to be The four characteristic rates (True Positive Rate, True Negative Rate, Positive Predicted Value, Negative Predicted Value) can be computed as follows: P tpr = T P/(T P + F N ), P tnr = T N/(T N + F P ), P ppv = T P/(F P + T P ) and P npv = T N/(T N + F N ). All the mentioned characteristic rates in P = {P tpr , P tnr , P ppv , P npv } are equal to 1, if there is no misclassification.
Under a stable concept (i.e., P (X t , y t ) remains unchanged), {P tpr , P tnr , P ppv , P npv } remains the same. Thus, a significant change of any P , implies a change in underlying joint distribution (y t ,ŷ t ), or concept. It is worth noting that at every time step t, for any possible (y t ,ŷ t ) pair, only two of the four empirical rates in P will change and these two rates are referred to as "influenced by (y t ,ŷ t )". Also, note that in certain applications the detection of concept drift is not of interest and thus unnecessarily alarmed if all empirical rates in P are increasing. This is because it suggests that an old model learned from historical data performs even better in classifications of current data stream. We do not use this assumption in this paper, but all methodologies and arguments we propose below can be easily adapted for this assumption.

III. CONCEPT DRIFT DETECTION FRAMEWORK
Given the efficacy of the P (where, ∈ {tpr, tnr, ppv, npv}) to detect concept drift, the proposed concept drift detection framework uses estimators of the rates in P as test statistics to conduct statistical hypothesis testing at each time step. Specifially, the framework at each time step t conducts statistical tests with the following null and alternative hypotheses: H A : ∃ , P (estimator of P (t−1) ) = P (estimator of P (t) ).
The concept is stable under H 0 and is considered to have drifted if H 0 is rejected. The idea is to compare the statistical significance level of the running test statistic under H 0 at each time step to the user defined warning (δ ) and detection ( ) significance levels. This type of test is called "continuing test" [9] and in our problem all time stamps are decision points of acceptance or rejection. Then when the concept is stable, false alarms on P will be triggered unnecessarily once in every 1/ time steps in the long run. In this paper, we assume the spacing of decision points is fixed. Accordingly, the familiywise error rate and its cost in our continuing test can be controlled by using a simultaneous inference method such as classical Bonferroni corrections on . In a more general case where the spacings of decision points are unequal and test statistics are strongly positive correlated, we should instead consider the average run length of the test [10] or more powerful alternatives that controls the familywise error rate.
A naïve implementation of the "continuing test" framework (Naïve Four Rates) would be to useP (t) (empirical rate of P (t) ), as the estimators and test statistics. But as shown in Section III-C, there are better estimates ofP (t) .
In the following section, Linear Four Rates (LFR) algorithm will be used to elaborate on the concept drift detection framework. LFR differs from Naïve Four Rates (NFR) in terms of the estimator used. However, both LFR as well as NFR perform better than DDM and DDM-OCI due to the more comprehensive detection framework utilized.
A. Linear Four Rates algorithm (LFR) 1) Algorithm Outline: LFR uses modified rates R (t) as the test statistics for P (t) . R (t) is a modified version of the empirical rateP (t) . At each t, R (t) is updated as : is essentially a linear combination of classifier's previous performance R (t−1) and current performance 1 {yt=ŷt} , where η is a time decay factor for weighting the classifier's performance at current instance. R (t) has been used as a class imbalance detector and as a revised recall test statistic in [11] [2]. The probabilistic characteristic of our test statistic R are investigated in § III-A2. The pseudocode of the framework (using R (t) as an estimator of P (t) for required test statistic), is detailed in Algorithm 1.
The three user defined parameters are the time decaying factor (η ), warning significance level (δ ) and detection significance level ( ) for each rate. Time decaying factor is Algorithm 1 Linear Four Rates method (LFR) Input: Data: {(X t , y t )} ∞ t=1 where X t ∈ R d and y t ∈ {0, 1} Binary classifierf (·); Time decaying factors η * ; Warn significance level δ * ; Detect significance level * . Output: Detected concept drift time (t cd ). 1: for each ∈ {tpr, tnr, ppv, npv} do 6: if ( is influenced by (y t ,ŷ t )) then 7: 10: end if 11: if ( ∈ {tpr, tnr}) then 12: end if 32: end for a weight in [0, 1] to evaluate performance of classifierf at current instance predictionf (X t ). Given that the detection methodology is conducting hypothesis testing at each time step, δ and are interpretable statistical significance levels, i.e., type I error (false alarm rate), in standard testing framework. In practice, allowable false warning rate and false detection rate in applications such as quality control of the moving assembly line are guidelines to help the user choose the parameters δ and . For the fair comparison, η is set to the same value of 0.9 as in [2], for all experiments of this paper. The optimal selection of η is domain dependent and can be pre-learned if necessary.
Theorem 1 in Section III-A2 shows that under the stable concept, R (t) is a geometrically weighted sum of i.i.d Bernoulli random variables, which emphasizes the most recent prediction accuracy and places exponentially decaying weights on the historical prediction accuracies. By taking advantage of this weighting scheme, R (t) is more sensitive to concept drifts, foreshadowing the non-stationarity of classifier's performance.
Standing on Theorem 1, we are able to overcome the shortcoming of [2] and construct a more reliable running confidence interval for R (t) to control the type-I error .
R (t) is distributed as geometrically weighted sum of Bernoulli random variables. Bhati et. al investigates the closed-form distribution function of R (t) for the special case P = 0.5 [12]. However, a closed-form distribution function for other values of P is unattainable. Alternatively, according to Theorem 1, a reasonable empirical distribution can also be independently obtained by Monte Carlo simulation for given P , N and time decaying factor η. The pseudocode for the Monte Carlo sampling procedure is provided in Algorithm 2. As P is unknown,P is used as its surrogate to generate the empirical distribution of R (t) . Based on the empirical distribution, the lower and upper quantile for the given significance level α, serves as the required (warning/detect) bounds. The selection ofP as the best surrogate of P , is supported by Lemma 1.
δ and denote warning and detection significance levels respectively, where δ > . The corresponding warn.bd and detect.bd are obtained from Monte Carlo simulations as described. The bounds of four rates {tpr, tnr, ppv, npv} of the framework, can be independently set based on importance, by having distinct . For instance, in some imbalanced classification tasks, performance of the classifier on the minority class is a higher priority than on the majority class.
Having computed the bounds, the framework considers that a concept drift is likely to occur and sets the warning signal (warn.time ← t), when any R All examples stored between warn.time and detect.time are extracted to relearn a new classifier since the stored examples are considered samples of the new concept. In case the number of stored examples is too few to relearn a reasonable classifier, one will have to wait for sufficient training examples. However, if R (t) cross the corresponding warning bounds warn.bd, but fail to reach detect.bd, previous warning flag will be erased. After detecting concept drift, R (t) ,P (t) , C (t) are reset to their initial values, so that a new monitoring cycle can restart.
2) Analysis: The following theorems investigate the statistical properties of LFR test statistic R (t) .
Theorem 1: For any , R (T ) is a geometrically weighted sum of Bernoulli random variables, when there is a stable concept up to time T : i.e., iid ∼ Bernoulli(P ) and P is the underlying rate.
Proof: Among total T time steps, suppose R (t) is changed according to line 7 at time step T 1 , . . . , T N where T 1 < T 2 < Generate N independent Bernoulli random variables forms a empirical distributionF (R) , find α−level quantile as the lower bound lb ← quantile(F (R), α) and (1 − α)−level quantile as the upper bound ub ← quantile(F (R), 1 − α) · · · < T N ≤ T . Hence, Proof:P (T ) is an unbiased estimator of P . This is Bernoulli random variables realized at time T i with parameter P . By factorization theorem,P (t) is a sufficient statistic. Also, If E(g(P (T ) )) = 0 ∀P , it implies g( i N ) = 0 ∀i because E(g(P (T ) )) is a polynomial of P 1 − P . Thereby P (g(P (T ) ) = 0) = 1 andP (T ) is a complete sufficient statistic by definition.
By Lehmann-Scheffe Theorem,P (T ) is the unique UMVUE.
The complexity of Linear Four Rates (LFR) detection algorithm is O(1) at each time step. The LFR algorithm can be optimized by using a BoundT able precomputed by Algorithm 2. The 4 dimensional BoundT able with varying input (P , η, δ, N ) can itself be precomputed and stored before running Algorithm 1. It is unnecessary to spend any computational resource on quantiles calculation during stream monitoring because observer can find a closestP toP (t) from BoundT able to look up lower and upper quantiles. Thus, LFR algorithm takes O(1) to test drift occurrence at each time point and suits with streaming environment.

B. Naïve Four Rates algorithm (NFR)
For the purpose of comparison, this section details the characteristics of a naïve implementation of the proposed framework that usesP (t) as the test statistic. A benefit of choosing this test statistic, is that there exists a closed-form distribution as shown in Lemma 1. Using the same strategy of LFR algorithm, NFR algorithm monitors the four ratesP the warning / detection alarms set whenP (t) exceeds the expected bounds.
The main difference with respect to LFR is the estimation of P used to find null distribution. LFR algorithm usesP (t) as a surrogate of unknown P while NFR algorithm usesP (t) , whereP (t) is a running average of all previousP (t) . This update rule allows old prediction performance contributes more to the estimate of P and recent predictions contributes less. Thus,P (t) is more robust in terms of estimating the underlying P when concept drift occurs. Additionally,P (t) is still a MSE-consistent estimator under the stable concept presented in Lemma 2.
Lemma 2: Assume the setting in Theorem 1. Under the stable concept up to T , for any ∈ {tpr, tnr, ppv, npv},P (T ) in NFR algorithm is a MSE-consistent estimator of P .
Proof: Among total T time steps, supposeP (t) is changed at time step T 1 , . . . , T N where T 1 < T 2 < · · · < T N ≤ T . Hence,P By IID assumption of indicators, we obtain where the last limit hold by the fact that N → ∞ as T → ∞. Thus, as E(P (T ) ) − P = 0 and VAR(P (T ) ) → 0,P (T ) is a MSE-consistent estimator.

C. Comparison between NFR and LFR
To empirically compare the test statistics of NFR and LFR, we use Figure 1 to illustrate a single run of both LFR and NFR algorithm on the same synthetic streaming data {(y t ,ŷ t )} T t=1 . The data stream of pairs {(y t ,ŷ t )} T t=1 with one change-point at T /2 is generated by sampling from two confusion probability matrices CP (1) and CP (2) . The two concepts are characterized by CP (1) and CP (2) respectively. The type of drift is determined by particular settings of (CP (1) , CP (2) ). In this example, to generate a balanced stream of pairs {(y t ,ŷ t )} T t=1 representing the scenario that overall accuracy of classifier drops but P tpr remains constant, It is clear that the test statistic R (t) in LFR algorithm has a larger variance thanP (t) for each rate. LFR algorithm reports an earlier detection at t = 5167 (true detection point t=5000) when compared to NFR in this run, even though (LF R) < (N F R) . This observation matches well with the rationale of constructing R (t) , described in §III-A1, to gain detection sensitivity through introducing large variances. To rigorously compare detection performance of R (t) andP (t) , more investigations are provided below.
Power characteristics of two competing test statistics R (t) (LFR) andP (t) (NFR), are compared empirically on synthetic data. We denote byβ R (t) andβP (t) the power estimates of R andP (t) respectively. Theβ R (t) andβP (t) against varying time lag k and q are presented in Figure 2. Figure 2 indicates that neither R (t) norP (t) dominates all the time because R (t) (red surface) achieves a larger statistical power when the time lag K is small but a smaller power when K is large. This is because the update rule line 7 enables the estimator R (t) to shift from p to q at an exponential rate which leads the power dominance in a short lag. The price is that limiting distributions of R (t) under both null and alternative have larger variances thanP (t) and thus limiting power, when K is large and |p − q | is small, is degraded.
In order to compare sensitivities of R (t) andP (t) with regard to detecting concept drift in more general settings, we used ∆β =β R (t) −βP (t) . The result is illustrated in Figure   0 2000  3. Except when, p = q , we see that for any fixed pair of (p , q ), ∆β > 0 when K is small and ∆β ≤ 0 when K is large. This is because ∆β decreases, as time lag K increases. This suggests that LFR is preferable if earlier detection is highly desired. The alarms are more likely to be triggered in the earliest time after the occurrence of concept drift. Earlier detection allows observer to adjust the model and avoid costs of incorrect predictions immediately. On the other hand, if observers are only concerned with detecting the occurrence of drift in the data stream but unconcerned with its detection promptness, then NFR algorithm provides a higher power test statistic to detect the drift. This is becauseP In the long run, as K → ∞, To guide the selection between LFR and NFR, Figure 4 is a heatmap of limiting power estimates on all (p , q ) pairs using K = 200. We can see thatβ R is already close to 1 for K = 200, when p and q are significantly different.

IV. EXPERIMENTS
In this section, we compared the detection performance of LFR to NFR, DDM and DDM-OCI approaches using both synthetic data and public datasets. We considered 3 simulated class-balance datasets, 3 simulated class-imbalance datasets and 4 public datasets to demonstrate LFR algorithm performs well across various types of concept drifts, including those where the baseline performs poorly.
To generalize the performance and evaluate confidences of algorithms, we utilize the bootstrapping technique. For each synthetic dataset, we generate 100 data streams of {(y t ,ŷ t )} T t=1 rather than {(X t , y t )} T t=1 so that comparison of detection algorithms is independent of classifiers employed; For each public dataset, the order of (X t , y t ) pairs within each concept are permutated to create 100 bootstrapped dataset streams. Each stream is fed to all detection algorithms to obtain single-run detections for each method. To illustrate the accuracy of the prediction, we use overlapped histograms to visualize the distribution of detection points obtained from the concept drift detection models across the 100 runs. To avoid redundancy, we present 6 histograms out of 10 experiments and remaining ones are similar. As shown below, LFR consistently outperformed the baseline approaches. When compared to NFR, LFR correctly identifies more true drift points with higher probability and smaller number of false alarms even with a smaller .

A. Synthetic Data
Numerous experiments were run on synthetic data, covering various types of concept drift. In each bootstrap, a data stream of pairs {(y t ,ŷ t )} T t=1 with one change-point at T /2 is generated by using the same mechanism introduced in §III-C. The objective of detection algorithms is to identify the change-point T /2. Six challenging and interesting scenarios are discussed below.

1) Balanced Dataset:
In balanced datasets, P (y t = 0) = P (y t = 1) is required in underlying data generation. Classbalance data are the most typical scenario in classification task and hence investigated with following three representative experiments. 2) Imbalanced Dataset: For imbalanced datasets, we used the same data generation mechanism as balanced case but make P (y t = 0) and P (y t = 1) imbalanced. We considered the following three interesting types of concept drifts given many attentions to in real applications. . Without loss of generality, let y = 1 be the minority class. It is also noteworthy that P tpr and P ppv are unchanged after drift occurrence. Hence, many detectors in imbalance data learning society, using F1 score as a measure to monitor classifier performance, is unable to alarm this type of drift. However, Fig. 7 shows that LFR performs very well by dominating both high early detection rate and trivial false alarms. Besides, DDM and DDM-OCI has no detection after changepoint due to the increment of (1 − P error ) and P tpr , respectively. Overlapping histograms comparing detection timestamps on Imbal-ance1 dataset in which class ratio transits from 1:1 to 9:1 but F 1−score remains unchanged. Number of counts of LFR is above the top bar of each bin. 1) Datasets: SEA Concepts dataset is used in [14]. The dataset is available at http://www.liaad.up.pt/kdus/products/ datasets-for-concept-drift, and is widely used as a testbed by concept drift detection algorithms. Rotating Hyperplane dataset is created by [15].The dataset and specific (k, t) pairs of each concept are available at http://www.win.tue.nl/ ∼ mpechen/data/ DriftSets/. USENET1 and USENET2 datasets, used in [16], are available at http://mlkd.csd.auth.gr/concept drift.html. They are stream collections of messages from different newsgroups (e.g. medicine, space, baseball) to a user. The difference between USENET1 and USENET2 is the magnitude of drift. The user in USENET1 has a sharper topic shift than the one in USENET2.
All above datasets are in form of {X t , y t } T t=1 and their key features are summarized in Table I. Other details such as the imbalance status and type of drift of each dataset are available through above links.
2) Evaluation: In SEA Concepts Dataset experiment, Fig. 8 shows that LFR dominates other three approaches in terms of early detections and fewer false or delayed detections.  Fig. 9 shows that LFR has a dominant performance on the Rotation Hyperplane Dataset experiment. At the second true drift time point, the underlying concept change is very minor. Hence the drift is neglected by all detection algorithms.
In USENET1 dataset experiment, Fig. 10 indicates LFR dominates other approaches and all drift points are alarmed. Similarly, in USENET2 dataset experiment, LFR also outperforms other approaches but detections are delayed with longer time lag. The decrement of superiority of LFR, from USENET1 to USENET2 is due to decrements of magnitude of concept drifts.

C. summary statistics
In general, the best algorithm will have the minimal number of false alarms and maximal number of early detections, whereas poor algorithms give large number of false alarms, missing or severely delayed true detections. A summary of the counts of correct detections at true drift timestamp and counts of false detections during false detection period for the Parameters Detect Sig. Warn Sig. Decay LFR = 1/100K δ = 1/100 η = 0.9 NFR = 1/1K δ = 0.025 η = 0.9 DDM α detect = 3 αwarn = 2 η = 0.9 DDM-OCI α detect = 20 αwarn = 10 η = 0.9   Tables II and  Table III.
False detection period refers to the period preceding the data points that belong to the new concept. For the synthetically generated datasets in §IV-A, there were two concepts spanning the T data points, such that the false detection period is defined as [0, T /2). For the datasets specified in §IV-B, if there were more than two concepts, the false detection period corresponds to the range from the concept midway up to the next true drift point. Each bin in the histograms correspond to 200 time steps in §IV-A and dataset-dependent in §IV-B. Since it has been observed in [17], [18] that false alarms may have a smaller influence on predictive performance than late drift detections, the true detection period in our experiments refers to the period spanning next 200 time steps (1 bin) after T /2 in §IV-A and the period spanning 1 bin after each true drfit point in §IV-B. Other parameter settings of detection algorithms are summarized in Table IV and V. They are particularly selected to show the dominating performance of LFR, i.e. the smallest allowable type-I error but the largest statistical power, over benchmark algorithms.
As sumarized in Table II, LFR fared best in terms of recall of true change point detecion across the various datasets. Equally importantly, LFR had the the highest precision with regard to detecting change points by producing the least amount of false detection and delayed detection (Table III).

V. CONCLUSION
The paper presents a concept drift detection framework (LFR) for detecting the occurance of a concept drift and identifies the data points that belong to the new concept. The versitality of LFR allows it to work with both batch and stream datasets, imbalanced data sets and it uses user-specified parameters that are intuitively comprehensible, unlike other popular concept drift detection approaches. LFR significantly outperforms existing benchmark approaches in terms of early detection of concept drifts, high detection rate and low false alarm rate across the types of concept drifts.