The detection of temporal abnormal patterns over streaming data is challenging due to volatile data properties and lacking real-time labels. The abnormal patterns are usually hidden in the temporal context, which can not be detected by evaluating single points. Furthermore, the normal state evolves over time due to concept drift. A single model does not fit all data over time. Autoencoders are recently applied for unsupervised anomaly detection. However, they usually get expired and invalid after distributional drifts in the data stream. In this paper, we propose an autoencoder-based approach (STAD) for anomaly detection under concept drift. In particular, we use a state-transition-based model to map diferent data distributions in each period of the data stream into states, thereby addressing the model adaptation problem in an interpretable way. We empirically demonstrate the state transition process and evaluate the anomaly detection performance on the Covid-19 dataset of Germany.
Anomaly detection in streaming data is gaining traction in the current big data research. Despite
the high demand in a variety of real-world applications [
Recently, autoencoders have been employed for anomaly detection in an unsupervised manner
[
Another major challenge of anomaly detection in streaming data is distinguishing between abnormal patterns and concept drifts. Once the data stream drifts to a novel distribution, a stationary model trained only on outdated data may detect most of the upcoming data undesirably as anomalies.
Given the severe problems, our goal is to consider the concept drift detection and anomaly
detection as a whole, adapt the model to the latest data distribution, and detect anomalies only
concerning the temporal context where they are located. Previous concept drift researches
focus on detecting changes of the joint probability (, ) under supervised setting, namely,
the decision boundary changes along with the distributional changes in the input data [
In this paper, we propose STAD (State-Transition-aware Anomaly Detection). In STAD, data distribution in a time period is defined as a states. We use state transitions to model the concept drifts between periods. As autoencoders are well studied for non-linear time series anomaly detection, we are motivated to extend the state transition paradigm to autoencoders. We follow the standard usage of autoencoders for anomaly detection and novelly couple the detection of concept drifts and anomalies with the informative latent representation of autoencoders. An existing autoencoder can be reused when a data concept reappears in the stream. A state transition is triggered by the detection of concept drift, and this will further guide the reuse or adaptation of autoencoders for the next period. The states quantify the uncertainty caused by concept drifts and raise interpretability in understanding the decision of autoencoders and changes in the data stream.
Let = {}∈N be a D-dimensional data stream, where denotes the observation at
timestamp . The data stream contains unlabeled anomalies as well as distributional changes
caused by concept drifts. Instead of explicitly categorizing diferent concept drift types [
Imitating the automata theory, we formulate concept drifts in streaming data with a state transition model ℳ = ⟨ , , ⟩ where is a multivariate data stream, = {1, 2, ..., } is a set of states ( is the user-defined maximum number of states that can be maintained), is a set of transition functions : { ⇒ }(, ∈ , ̸= ). For each state = ⟨, ⟩( = 1, ..., ), is the empirically estimated distribution in latent space, is the autoencoder trained on the new concept data. In this work, we assume that suficient data after the concept drift is available to learn and .
Considering that no information about the upcoming new concept is accessible, despite a potential high error rate, we still keep using the previous model for anomaly detection until the model adaptation is finished. Or in other words, the previous model is used during the upcoming drift period. For distributional stationary data streams where no concept drift occurs, there will be only a single state without transition, and the model reduces to a single conventional autoencoder. 2.1.3. Anomaly An observed data snippet + = {, ..., +}(, ∈ N) is abnormal if it is significantly deviated from its temporal neighbors (data snippets in the same state). The significance of the deviation can be determined by thresholding or statistical techniques. Both concept drifts and anomaly snippets are distributionally deviate from their temporal neighbors. In our study, we distinguish them in terms of length. After the concept drifts, we assume that the data distribution stays stationary in the new concept for a significantly longer period. In contrast, the data stream returns to the previous distribution after a short anomaly snippet.
Given a D-dimensional data stream = {}∈N, we aim to identify any period [, + ] where the corresponding data snippet + is abnormal. The detection process should be unsupervised and in real-time. We also detect concept drifts in the data stream and switch to an existing autoencoder or train a new one on the newly arrived data.
ℒ ′
In this section, we propose STAD, a state-transition-aware anomaly detection model, which employs autoencoders as the base model. The latent representations of autoencoders are used to detect concept drifts, which consequently trigger state transitions. An overview of STAD is shown in Figure 1.
Let : R encoder maps a snippet + of the multivariate streaming data into a H-dimensional latent representation ∈ R , while the decoder reconstructs the same format snippet ′+ from → R and : R → R be the encoder and decoder of an autoencoder. The , where is the snippet length and , ∈ N. A common assumption for anomaly detection using autoencoders is that pure normal data are available for the initial model training. The reconstruction error + = |+ −
′+| indicates the goodness of fit to the normal data.
In the test phase, abnormal snippets will cause larger reconstruction errors than normal data
such that they are separable. The encoder and decoder can be implemented with a variety of
deep models [
In real-time, the latent representations of the autoencoder are accumulated for concept drift
detection. Existing concept drift detection approaches mostly work in the original space,
targeting linear separable concept drifts. Considering the complex concept drifts in multivariate
streaming data, even non-linear distributional changes can be observed in the autoencoder latent
space. We perform dimension-wise two-sample Kolmogorov–Smirnov test (KS-test) [
Modeling reoccurring data distributions (e.g., seasonal changes), coupling autoencoders with drift detection, and reusing models based on the distributional features can increase the eficiency of updating a deep model in real-time. In STAD, for each period between two concept drifts in the data stream, the data distribution, as well as the corresponding autoencoder are represented in a fixed-length queue . The first state 0 ∈ represents the beginning period of the data stream before the first concept drift. After every new concept drift, a new autoencoder will be trained from scratch if no existing element in the queue fits the current data distribution; otherwise, the state will transit to the existing one and reuse the corresponding autoencoder. In our study, we assume that suficient data after the concept drifts can be accumulated to initialize a new autoencoder. In future work, we plan to discover state transitions with limited data (e.g., tolerantly reusing existing autoencoders).
To compare the distributional similarity between the newly arrived latent representation and the distributions of existing states {| = 1, ..., }, we employ the symmetrized Kullback–Leibler Divergence. The similarity between and an existing state distribution is defined as (, ) = (||) + (||)
∈ℒ
= ∑︁ () ()
()
+ ()
()
()
The next step is to estimate the corresponding probability distributions from the sequence of
latent representations. In [
ℎ ∈ℒ ∑︀=1 ( = 1...) and the density of a given period is estimated by () = (). Hence, Equation 2 can be converted to
∑︁ =1... (, ) = ()
+ () () () () () (2) (3) (4) ◁ Equation 4 ◁ : Trained on new concept data Algorithm 2 State Transition Procedure 1: function StateTransition(ℎ, ℒ, , ) 2: = DensityEstimation(ℒ) 3: if {(, )} ≤ then =⟨,⟩∈ ← ∪ (ℎ ⇒ ) return end if For a newly detected concept with distribution , if there exists a state ( ∈ [1, ]) with corresponding probability distribution satisfies (, ) ≤ , where is a tolerant factor, and is not the direct last state, the concept drift can be treated as a reoccurrance of the existing concept, therefore the corresponding autoencoder can be reused, and the state transfers to the existing state. If no autoencoder is reusable, a new one will be trained on the latest arrived data after concept drift. To prevent an explosion in the number of states, the state transition model ℳ = ⟨ , , ⟩ only maintains the latest states. The state transition procedure is described in Algorithm 2.
We carry out a case study using the Covid-19 daily infection case dataset of Germany2, where
the waves of the epidemic can be considered as human-interpretable concept drifts and the
public holidays with abnormal statistic numbers are the anomalies. The Covid dataset (Figure 2)
contains daily new infection cases and death cases in Germany from March 2020 to April
2021. The data stream follows a 7-day period and fluctuates with the trend depending on the
development of the epidemic, seasons, and local prevention policies. The LSTM-autoencoder
and scoring function in [
Detected drifts 1,500 1,000 detected drifts are near significant changes in the evolution of the epidemic. The threshold of KL-divergence is set to 0.0025. The size of the new bufer ℒ is 14. As shown in Figure 3, no reusable autoencoder is found for the first three concept drifts such that three new states with corresponding new autoencoders are created. After the concept drift near March 2021, the upcoming data in ℒ has KL-divergence below with state 2 (end September to early December), therefore it triggers a backward state transition to 2.
In the test phase, we manually labeled 11 weeks containing public holidays in Germany as abnormal snapshots and ranked the anomaly scores in the periods corresponding to each state. In the evaluation of recall in the ranking list, we got 18% for @1, 54% for @5 and 90% for @10. A major reason is that some data points from the beginning of concept drifts are mistakenly alarmed as anomalies before the model update. In the follow-up work, we aim to reduce the false positive detection of anomalies by distinguishing concept drifts and abnormal snapshots by their length.
0 1 2 3
We have proposed an autoencoder-based streaming data anomaly detection approach STAD, which uses the latent representation to detect concept drift and model state transitions between diferent data distributions in the data stream. With a demo experiment, we showed the statetransition-aware anomaly detection process during the stream evolution. However, there are still open challenges. In the current work, we assume that suficient data are available for online training. However, the states of some periods in the real data stream are too short, such that the data for training a new model in real-time is not suficient. One future work is to discover eficient strategies for reusing autoencoders for such cases. Another further research direction is to discover semantic explanations for each state, which helps the human better understand the model as well as the changes of data.