Enhash: A Fast Streaming Algorithm For Concept Drift Detection

We propose Enhash, a fast ensemble learner that detects \textit{concept drift} in a data stream. A stream may consist of abrupt, gradual, virtual, or recurring events, or a mixture of various types of drift. Enhash employs projection hash to insert an incoming sample. We show empirically that the proposed method has competitive performance to existing ensemble learners in much lesser time. Also, Enhash has moderate resource requirements. Experiments relevant to performance comparison were performed on 6 artificial and 4 real data sets consisting of various types of drifts.


Introduction
A data stream environment is often characterized by large volumes of data that flow rapidly and continuously. They are processed in an online fashion to accommodate data that cannot reside in main memory. A streaming data environment is commonly used for tasks such as making recommendations for users on streaming platforms [29], and real-time analysis inside IoT devices [1]. In such a stream, the underlying data distribution may change, and this phenomenon is referred to as concept drift. Formally, the posterior probability of a sample's class changes with time. Consequently, the method must also be able to adapt to the new distribution. To adapt to a new concept, the method may require supplemental or replacement learning. Tuning a model with new information is termed as supplemental learning. Replacement learning refers to the case when the model's old information becomes irrelevant, and is replaced by new information. A shift in the likelihood of observing a data point x within a particular class when class boundaries are altered, is called real concept drift. Concept drift without an overlap of true class boundaries, or an incomplete representation of the actual environment, is referred to as virtual concept drift. In virtual concept drift, one requires supplemental learning, while real concept drift requires replacement learning [13]. The other common way to categorize concept drift is determined by the speed with which changes occur [2]. Hence, drift may be incremental, abrupt or gradual. A reoccurring drift is one that emerges repeatedly. Thus, in order to handle concept drift, a model must be adaptive to non-stationary environments.
Several methods have been recently proposed to handle concept drift in a streaming environment. The most popular of these are ensemble learners [25,11,30,5,14,31,19,18]. As the data stream evolves, an ensemble method selectively retains a few learners to maintain prior knowledge while discarding and adding new learners to learn new knowledge. Thus, an ensemble method is quite flexible, and maintains the stability-plasticity balance [20] i.e. retaining the previous knowledge (stability) and learning new concepts (plasticity).
In this paper, we propose Enhash, an ensemble learner that employs projection hash [15] to handle concept drift. For incoming samples, it generates a hash code such that similar samples tend to hash into the same bucket. A gradual forgetting factor weights the contents of a bucket. Thus, the contents of a bucket are relevant as long as the incoming stream belongs to the concept represented by them.
The rest of the paper is organized as follows. Section 2 discusses the basic principle of some relevant ensemble learners. Section 3 elaborates the proposed ensemble learner. Section 4 highlights the performance metrics used to evaluate the performances of several ensemble learners on artificial and real data sets with varying concept drift. Section 5 discusses the impact of tuning of parameters on the performance of Enhash. Section 6 compares the performances of discussed ensemble learners. Section 7 compares the performance of Enhash with its two different variants and highlights the importance of design choice. Section 8 concludes the aspects of the proposed method.

Related Work
In this section, we discuss some of the widely used ensemble learners for drift detection.
Learn++ [25] is an Adaboost [12,28,27] inspired algorithm, that generates an ensemble of weak classifiers, each trained on a different distribution of training samples. The multiple classifier outputs are combined using weighted majority voting. For incremental learning, Learn++ updates the distribution for subsequent classifiers such that instances from new classes are given more weights.
While Learn++ is suitable for incremental learning, Learn ++ .NSE [11] employs a passive drift detection mechanism to handle non-stationary environments. If the data from a new concept arrives and is misclassified by the existing set of classifiers, then a new classifier is added to handle this misclassification. Learn ++ .NSE is an ensemble-based algorithm that uses weighted majority voting, where the weights are dynamically adjusted based on classifiers' performance.
Accuracy-Weighted Ensemble [31] is an ensemble of weighted classifiers where the weight of a classifier is inversely proportional to its expected error.
Additive Expert Ensemble [18] uses a weighted vote of experts to handle concept drift. The weights of the experts that misclassify a sample are decreased by a multiplicative constant β ∈ [0, 1]. In case the overall prediction is incorrect, new experts are added as well.
Dynamic Weighted Majority (DWM) [19] dynamically adds and removes classifiers to cope with concept drift.
Online bagging and boosting [23] ensemble classifiers are used in combination with different algorithms such as ADaptive WINdowing (ADWIN) [4] for concept drift detection. ADWIN dynamically updates the window by growing it when there is no apparent change, and shrinking it when the data evolves. In general, bagging is more robust to noise than boosting [10,24]. Henceforth, we discuss methods based on online bagging, that approximates batch-bagging by training every base model with K copies of a training sample, where K ∼ Poisson(1). We refer to the combination of online bagging classifiers with ADWIN as Online Bagging-ADWIN.
Leveraging bagging [5] exploits the performance of bagging by increasing randomization. Resampling with replacement is employed in online bagging using Poisson (1). Leveraging bagging increases the weights of this resampling by using a larger value of λ to compute the Poisson distribution. It also increases randomization at the output by using output codes.
Online SMOTE Bagging [30] oversamples a minor class by using SMOTE [9] at each bagging iteration to handle class imbalance. SMOTE generates synthetic examples by interpolating minor class examples.
Adaptive Random Forest, ARF [14] is an adaptation of Random Forest [7] for evolving data streams. It trains a background tree when there is a warning, and replaces the primary model if drift occurs.

The Proposed Method
Several recent methods employ hashing for online learning and outlier detection [26,16]. We propose Enhash, an ensemble learner, that employs hashing for concept drift detection. Let x t ∈ R d represent a sample from a data stream S at time step t and let y ∈ {1, 2, ..., C} represent its corresponding concept, where C is the total number of concepts. Further, let us assume a family of hash functions H such that ∀h l ∈ H, it maps x t to an integer value. The hash code h l (x t ) is assigned to x t by hash function h l . A bucket is a set of samples with the same hash code; both these terms are used interchangeably. The total number of samples in bucket h l (x t ) is denoted by N h l (xt) . Further assume that N samples have been seen and hashed from the stream so far. Amongst N , N c samples belong to the concept class c such that c=C c=1 N c = N . Based on the evidence from the data stream seen so far, the probability of bucket h l (x t+1 ) is given by and prior for class c is given by p(c) = N c /N . Assuming, (N h l (xt+1) ) c represents the samples of concept c in bucket h l (x t+1 ). Hence, the likelihood of x t+1 belonging to concept c in bucket h l (x t+1 ) is given by The probability of x t+1 belonging to class c is given by Equation (3) is simply the normalization of counts in bucket h l (x t+1 ).
To predict the concept class of x t+1 , an ensemble of L such hash functions can be employed and the weight for each concept class is computed aŝ and the concept class is predicted aŝ y = arg max c∈{1,..,C}p c To accommodate an incoming sample of class c, the bucket is updated as Enhash utilizes a simple strategy as described above to build an ensemble learner for concept drift detection. In Enhash, the projection hash family is selected as a base learner. Here, a hash function involves the dot product of hyperplane w (l) and sample x t . It is defined as where, bin-width is quantization width, w (l) j and bias (l) can be sampled from any desired distribution. In our implementation, w Effectively, each h l (7) divides the space into equally spaced unbounded regions of size bin-width (earlier referred to as bucket). Equation (3) computes the probability of each concept class in a region. An ensemble of hash functions makes all the regions bounded. The weight of a concept class in the bounded region is computed using (4). An absolute value of concept class is assigned to each region in (5). Figure 1a shows the arrangement of randomly generated hyperplanes. The solid line in Figure 1b shows the inferred decision boundary (learned distribution) after an absolute assignment of concept class to every bounded region. The dashed line in Figure 1b depicts the true decision boundary (true distribution).
Assuming at time step t, Figure 1b shows the current stage of learner. At step t+1, a new sample x t+1 arrives (gray sample in Figure 1c). After updating the bucket (6), the learned distribution shifts and moves towards the true distribution. Hence, Enhash accommodates virtual drift present in the data stream. Figure 1d depicts the real drift when the true distribution evolves. This requires forgetting some of the previously learned information. Suppose that sample x t+∆t hashes to bucket h l (x t+∆t ) at time say, t + ∆t. Assume that previously, x t from a different concept, was hashed to this bucket. In order to accommodate forgetting, Enhash employs a decay factor multiplier to p(c|h l (x t+∆t )) (4) while weighting a bounded region.p where λ is the decay rate. The update rule for the bucket (5) is also changed to reflect the new concept class as follows Setting λ = 0 will reduce these equations to the base case.
In order to break ties in p(c|h l (x t )), the class weight in the region is also weighted by the distance of the sample x t from the mean of class samples in bucket and remaining ties are broken arbitrarily.

Implementation Details
Algorithm 1 gives Enhash's pseudo-code. We refer to an instance of the ensemble as an estimator. The parameter bin-width determines the granularity of the buckets, and λ represents the rate of decay that accounts for gradual forgetting [17]. Every estimator l generates a hash code for incoming stream samples and hashes them into bucket b (l) . The hash code for a sample x is compute using (7). The timestamp when a sample of class y was last hashed into a bucket is an infinitely indexable 2D-array. An infinitely indexable ND-array is a data structure that has N dimensions and can store values at any arbitrary combinations of indexes in those dimensions. In practice, an infinitely indexable ND-array can be created using maps or dictionaries. The recent access time of the hash code b (l) can be retrieved by selecting the maximum value in tstamp (l) [b (l) ]. The count of samples in bucket b (l) is stored in another infinitely indexable 2D-array counts (l) at an index counts (l) [b (l) ]. The information required to break the ties during prediction is stored in sCounts (l) and sAcc (l) . The variable sCounts (l) , an infinitely indexable 2D-array, keeps track of the number of samples from every class y falling into the bucket b (l) . sAcc (l) , an infinitely indexable 3D-array, stores the class-wise vector sum of all the samples falling into the bucket b (l) . The last dimension in this array belongs to the features in the dataset. Enhash has two phases. In the first one, Enhash predicts the class of a new sample. Assuming that sample x falls into bucket b (l) , its distance from all the cluster centers in the bucket is computed (steps 18 and 19). The variable cweights accumulates the prediction for a sample x via each estimator. This variable is also an infinitely indexable array so that it can accommodate unseen class labels. To get the prediction for sample x from an estimator l, a decayed value of count (weighted by distance) is computed (step 21). The decay factor 2 −λ∆t1 , depends upon the decay parameter λ and the difference of the current time and the last access time of bucket b (l) . The decay factor determines whether the previous value in counts (l) [b (l) ] is relevant or not, and hence, introducing the forgetting effect in the algorithm. In effect, if the difference in the time is large, then decay is almost zero, and this emulates local replacement in the bucket b (l) [8]. On the other hand, λ reduces the effect of samples (possibly, of the same concept) hashing into a bucket. The higher is the value of λ, then more is the rate of decay. Collectively, λ, and time difference play an important role in drift detection. The log-transformed value of the prediction is added to cweights. A pseudo-count of 1 is added during log-transformation to handle 0 or near-zero values in prediction. After accumulating predictions from every estimator, a class with maximum weight is designated as the class of sample x (step 30).
In the second phase, the information is updated in the variables to accommodate recent changes in the concept. Assume that a recent sample belongs to class y.
is set to the current timestamp. Further, to update the effective count in bucket for class y in counts (l) [b (l) ][y], the present value is decayed by the difference of the current time and the last seen time of sample from class y and then incremented by 1 (steps [24][25]. This introduces the forgetting phenomenon during updates and also handles spurious changes. For example, if a bucket was accustomed to seeing samples from a particular class and the sudden arrival of a sample from another class that had not been seen by the bucket for a long time, it would not alter the bucket's prediction abruptly. However, after seeing a few samples from the new class, the bucket's confidence will grow gradually towards the recent trends. The value in In essence, samples with a similar concept are most likely to have the same hash code and hence, share the bucket. For an evolving stream, thus, different buckets are populated. The weight associated with the bucket is gradually incremented when samples of the same concept arrive. The contents of a bucket are more relevant when the concept reoccurs in the near future than in a faraway future. Formally, the temporal nature of the posterior distribution of a sample x belonging to a class y is modeled as the Bayes posterior probability P (y|x) = P (y)P (x|y)/P (x). Let n and n y denote the count of total samples and samples of a class y, respectively. In the proposed method, for a given estimator l, P (y) = n y /n, P (x|y) = counts

Time Complexity Analysis
There are three important steps in Algorithm 1, namely, the computation of hash function (step 17), prediction of class (steps [18][19][20][21][22], and update of model parameters counts (l) ← infinitely indexable 2D-array 8: tstamp (l) ← infinitely indexable 2D-array 9: sCounts (l) ← infinitely indexable 2D-array 10: sAcc (l) ← infinitely indexable 3D-array 11: Run: (x, y) ← next(S) 14: t ← t + 1 15: cweights ← array initialized with 0s 16: for l ∈ {1, ..., L} do 17: b (l) = generate hash code using (7) for estimator l 18: (steps [23][24][25][26][27][28]. In Enhash, the hash function computation is the dot product of a sample with weight parameters (7). Let the time required to compute the hash function be given by ψ(d) = O(d). The prediction of a sample's class involves the computation of distances from cluster centers in the bucket (10). Assuming that, Enhash has observed C concept classes so far; then, the time required for prediction is given by The update of the model involves updating the timestamp of the bucket, the effective count of the concept class in the bucket, the total samples hashed into the bucket, and accumulation of samples. Effective counts are also normalized in the update step which depends upon C. Say, the time required to update model parameter is given by ζ(d, C) = O(d + C). Thus, an estimator takes time of order . These steps are repeated by all L estimators, and hence, the total time complexity of Enhash, for an arbitrary data set and hyper-parameters settings, is given by O(L * d * C).
Thus, for a fixed setting of hyper-parameter L, the time complexity of Enhash to process a newly arrived sample for an arbitrary data set is given by O(d * C). However, it can be argued that for a fixed data set, the dimension of data d and number of concept classes C are fixed. Hence, Enhash will effectively take only a constant time, O(1), in the processing of a new sample.

Experimental Setup
Enhash's performance on concept drift detection was compared with some of the widely used ensemble learners. These include Learn++ [25], Learn ++ .NSE [11], Accuracy-Weighted Ensemble (AWE) [31], Additive Expert Ensemble (AEE) [18], DWM [19], Online Bagging-ADWIN (OB) [4,23], Leveraging Bagging [5], Online SMOTE Bagging (OSMOTEB) [30], and ARF [14]. The implementation of these methods is available in scikit-multiflow python package [22]. A fixed value of estimators was used for all the methods. For methods such as Accuracy-Weighted Ensemble, Learn ++ .NSE, Learn++, Leveraging Bagging, and Online Bagging-ADWIN, the maximum size of window was set min(5000, 0.1 * n), where n is the total number of samples. For the rest of the parameters, the default value was used for all the methods.

Evaluation metrics for performance comparison
We evaluated all the experiments in terms of time, memory consumption, and classifiers' performance. The memory consumption is measured in terms of RAM-hours [6]. Every GB of RAM employed for an hour defines one RAM-hour. The performance of a classifier is measured in terms of accuracy/error, Kappa M, and Kappa Temporal [3]. Kappa M, and Kappa Temporal handle imbalanced data streams, and data streams that have temporal dependencies, respectively. We evaluated the classifiers' performance using the Interleaved Test-Train strategy [21]. This strategy is commonly employed for incremental learning since every sample is used as a test and a training point as it arrives.

Tuning of parameters for Enhash
The hyperparameters that govern the performance of Enhash constitute L (number of estimators), and bin-width (quantization parameter). Even though the decay rate λ is also one of the hyperparameters, its value does not require much tuning, and usually, λ = 0.015 is preferred [26]. However, making λ = 0 is equivalent to removing the forgetting phenomenon and hence, worsens the performance (discussed further in Section 7).

Constraints to tune L
In Figure 2, it is shown empirically that with an increase in the value of L, the performance of Enhash eventually saturates. The time taken by Enhash also increases with L. This may be attributed to the fact that for every sample arriving at time t, the insertion involves calculating the hash code of the sample for every estimator l. It should be emphasized that, as shown empirically in Figure 2, only a few estimators are needed to achieve optimum performance. Further, the increase in time due to an increase in L can be reduced through a parallel implementation of Enhash. In that case, evaluation of a hash code for a sample for each l can be done independently of others. Consequently, a moderate value of L = 10 is used to perform all the experiments.

Constraints to tune bin-width
The parameter bin-width divides the space into equally spaced unbounded regions of size bin-width. The smaller is the value of bin-width, the more granular is the division of space. In other words, for smaller values of bin-width, the possible values of different hash codes (or buckets) increase rapidly. In the worst case, every sample may fall into a different bucket. Thus, the overall cost to store the contents of all buckets for every estimator grows exponentially. Figure 3 shows empirically the effect of bin-width on memory consumption. The figure highlights that for small values of bin-width, the overall memory requirement is extremely high. Also, the prediction of the concept for the sample may be arbitrary for extremely small values of bin-width since there is no neighborhood information in the bucket. As a result, for every new sample, a new concept may be falsely predicted. On the other extreme, for large values of bin-width, samples from different classes may lead to frequent collision. As a result of this, the concept of an arriving sample may not be predicted correctly due to confusion in the bucket. Thus, in general, an intermediate range of values for bin-width ∈ {0.01, 0.1} is more suitable for all data sets.   Table 2 Error (in %) is reported to compare the performance of Enhash with other methods. For a given data set, the method with the least error is in boldface. Due to implementation constraint, Learn ++ .NSE could not run for the outdoorStream data set.

Experimental Results
For all methods, the number of estimators is considered as 10. In addition for Enhash, bin-width was set to {0.1, 0.01} and λ was set to 0.015. Tables 2, 3, and 4 compare the performance of the methods in terms of error, KappaM, and KappaT respectively using Interleaved Test-Train strategy. For these measures, the performance of the proposed method was superior to Accuracy-Weighted Ensemble (AWE), and Additive Expert Ensemble (AEE) on 8 data sets, DWM, Learn ++ .NSE, Online SMOTE Bagging (OSMOTEB), and Online Bagging-ADWIN (OB) on 7 data sets, Learn++,  Table 4 KappaT is reported to compare the performances of the methods. The highest value of KappaT in each row is highlighted.
and Leveraging Bagging (LB) on 6 data sets, and ARF on 5 data sets. The performance of Enhash supersedes all other methods for 4 data sets -mixedDrift, mov-ingSquares, interchangingRBF, and outdoorStream. Other evaluation criteria are speed (Table 5) and RAM-hours (Table 6). Table 5 reports the overall time (in hrs) taken by each method for a given data set. For a majority of the data sets, Enhash takes the least time. For instance, it took only 0.339 hrs for the mixedDrift data set, followed by Learn ++ .NSE, which took 0.627 hrs. Notably, OSMOTEB took more than 185 hrs.
In terms of speed, DWM, Learn ++ .NSE, and Learn++ are comparable to Enhash. In terms of accuracy, however, Enhash supersedes the individual methods on the majority of the data sets. Our findings were consistent across all commonly used evaluation metrics namely error, KappaM, and KappaT. For instance, DWM requires 0.038 hrs on the interchangingRBF data set as compared to 0.132 hrs needed by Enhash. However, the error of Enhash is 2.72%, while DWM has an error of 7.02%.
The overall closest competitors of Enhash in terms of evaluation measures error, KappaM, and KappaT are ARF, LB, and OB. Enhash's speed and RAM-hours' requirement are almost insignificant when compared with other methods. For instance,  In summary, DWM has relatively poor performance in detecting virtual drifts but fairs well in abrupt and incremental drifts. Learn++ is exceptionally well in detecting virtual drift but severely under-performs in abrupt and incremental drifts. LB and ARF suffer in detecting incremental drifts. However, LB and ARF have an overall satisfactory performance. Enhash performs relatively well on all data sets. Enhash has a superior performance on a data set consisting of three different kinds of drifts, namely incremental, virtual, and abrupt drifts. Although Enhash falls short in detecting abrupt drifts, but the performance gap is not very significant.  Table 7 Ablation study of Enhash. The performance of Enhash is compared with its two different variants-1. Enhash with λ = 0 (referred to as Enhash-lambda0), and 2. Enhash when ties in concept class assignments are not broken by considering the distance of an incoming sample from the mean of classes in the bucket (referred to as Enhash-noWeights).

Ablation study
Enhash is built by modifying (5) and (6). The two major changes in Enhash from these are the inclusion of a forgetting factor and a heuristic for tie braking mechanism to reduce the false positives. In this section, we assess the impact of these changes, which make Enhash suitable for the concept drift detection. Table 7 compares the performances of Enhash with its two variants -Enhash-lambda0 and Enhash-noWeights. Enhash-lambda0 refers to the variant when λ = 0 or equivalently, the forgetting phenomenon is not accounted. Enhash-noWeights refers to the variant of Enhash when ties in the assignment of concept class are broken randomly. In other words, the distance (10) of an incoming sample from the mean of the classes in the bucket is not used to determine the class in case of ties. The values of the other hyperparameters are the same as that in Section 6. Table 7 shows that the performance of Enhash is much superior to its both variants for the majority of the data sets. The sub-optimal results of Enhash-noWeights may be attributed to the fact that when the same count of samples from different classes is present in the same bucket, the class for an incoming sample gets assigned randomly.

Conclusions
We conclude that Enhash supersedes other methods in terms of speed since the algorithm effectively requires only O(1) running time for each sample on a given estimator. In addition, the performance of Enhash in terms of error, KappaM, and KappaT is better or comparable to others for majority data sets. These data sets constitute abrupt, gradual, virtual, and reoccurring drift phenomena. The closest competitor of Enhash in terms of performance is the Adaptive Random Forest. Notably, Enhash requires, on an average 10 times lesser RAM-hours than that of Adaptive Random Forest.

Funding
Not applicable

Competing interests
The authors declare that they have no known competing interests.

Availability of data and material
The data sets are available on https://github.com/vlosing/driftDatasets.

Author's contributions
Aashi Jindal: Design of this study, Methodology, Software. Prashant Gupta: Design of this study, Methodology, Software, Investigation. Jayadeva: Conceptualization of this study, Design. Debarka Sengupta: Conceptualization of this study, Design.