A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Time series data are often subject to uncontrolled or unexpected interventions, from which various types of outlying observations are produced. Outliers in time series, depending on their nature, may have a moderate to significant impact on the effectiveness of the Standard methodology for time series analysis with respect to model identification, estimation, and forecasting. In this article we use an iterative outlier detection and adjustment procedure to obtain joint estimates of model parameters and outlier effects. Four types of outliers are considered, and the issues of spurious and masking effects are discussed. The major differences between this procedure and those proposed in earlier literature include (a) the types and effects of outliers are obtained based on less contaminated estimates of model parameters, (b) the outlier effects are estimated simultaneously using multiple regression, and (c) the model parameters and the outlier effects are estimated jointly. The sampling behavior of the test s... <s> BIB001 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> One of the central tasks in managing, monitoring and mining data streams is that of identifying outliers. There is a long history of study of various outliers in statistics and databases, and a recent focus on mining outliers in data streams. Here, we adopt the notion of "deviants" from Jagadish et al. (1999) as outliers. Deviants are based on one of the most fundamental statistical concept of standard deviation (or variance). Formally, deviants are defined based on a representation sparsity metric, i.e., deviants are values whose removal from the dataset leads to an improved compressed representation of the remaining items. Thus, deviants are not global maxima/minima, but rather these are appropriate local aberrations. Deviants are known to be of great mining value in time series databases. We present first-known algorithms for identifying deviants on massive data streams. Our algorithms monitor streams using very small space (polylogarithmic in data size) and are able to quickly find deviants at any instant, as the data stream evolves over time. For all versions of this problem - uni- vs multivariate time series, optimal vs near-optimal vs heuristic solutions, offline vs streaming - our algorithms have the same framework of maintaining a hierarchical set of candidate deviants that are updated as the time series data gets progressively revealed. We show experimentally using real network traffic data (SNMP aggregate time series) as well as synthetic data that our algorithm is remarkably accurate in determining the deviants. <s> BIB002 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> In this article we use projection pursuit methods to develop a procedure for detecting outliers in a multivariate time series. We show that testing for outliers in some projection directions can be more powerful than testing the multivariate series directly. The optimal directions for detecting outliers are found by numerical optimization of the kurtosis coefficient of the projected series. We propose an iterative procedure to detect and handle multiple outliers based on a univariate search in these optimal directions. In contrast with the existing methods, the proposed procedure can identify outliers without prespecifying a vector ARMA model for the data. The good performance of the proposed method is illustrated in a Monte Carlo study and in a real data analysis. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> In multivariate time series, outlying data may be often observed that do not fit the common pattern. Occurrences of outliers are unpredictable events that may severely distort the analysis of the multivariate time series. For instance, model building, seasonality assessment, and forecasting may be seriously affected by undetected outliers. The structure dependence of the multivariate time series gives rise to the well-known smearing and masking phenomena that prevent using most outliers' identification techniques. It may be noticed, however, that a convenient way for representing multiple outliers consists of superimposing a deterministic disturbance to a gaussian multivariate time series. Then outliers may be modeled as nongaussian time series components. Independent component analysis is a recently developed tool that is likely to be able to extract possible outlier patterns. In practice, independent component analysis may be used to analyze multivariate observable time series and separate regular and outlying unobservable components. In the factor models framework too, it is shown that independent component analysis is a useful tool for detection of outliers in multivariate time series. Some algorithms that perform independent component analysis are compared. It has been found that all algorithms are effective in detecting various types of outliers, such as patches, level shifts, and isolated outliers, even at the beginning or the end of the stretch of observations. Also, there is no appreciable difference in the ability of different algorithms to display the outlying observations pattern. <s> BIB004 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Detection of anomalies in multivariate time series is an important data mining task with potential applications in medical diagnosis, ecosystem modeling, and network traffic monitoring. In this paper, we present a robust graph-based algorithm for detecting anomalies in noisy multivariate time series data. A key feature of the algorithm is the alignment of kernel matrices constructed from the time series. The aligned kernel enables the algorithm to capture the dependence relationship between different time series and to support the discovery of different types of anomalies (including subsequence-based and local anomalies). We have performed extensive experiments to demonstrate the effectiveness of the proposed algorithm. We also present a case study that shows the utility of applying our algorithm to detect ecosystem disturbances in Earth science data. <s> BIB005 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Anomaly detection in multivariate time series is an important data mining task with applications to ecosystem modeling, network traffic monitoring, medical diagnosis, and other domains. This paper presents a robust algorithm for detecting anomalies in noisy multivariate time series data by employing a kernel matrix alignment method to capture the dependence relationships among variables in the time series. Anomalies are found by performing a random walk traversal on the graph induced by the aligned kernel matrix. We show that the algorithm is flexible enough to handle different types of time series anomalies including subsequence-based and local anomalies. Our framework can also be used to characterize the anomalies found in a target time series in terms of the anomalies present in other time series. We have performed extensive experiments to empirically demonstrate the effectiveness of our algorithm. A case study is also presented to illustrate the ability of the algorithm to detect ecosystem disturbances in Earth science data. <s> BIB006 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Outlier detection in vehicle traffic data is a practical problem that has gained traction lately due to an increasing capability to track moving vehicles in city roads. In contrast to other applications, this particular domain includes a very dynamic dimension: time. Many existing algorithms have studied the problem of outlier detection at a single instant in time. This study proposes a method for detecting temporal outliers with an emphasis on historical similarity trends between data points. Outliers are calculated from drastic changes in the trends. Experiments with real world traffic data show that this approach is effective and efficient. <s> BIB007 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> This paper proposes to use autoencoders with nonlinear dimensionality reduction in the anomaly detection task. The authors apply dimensionality reduction by using an autoencoder onto both artificial data and real data, and compare it with linear PCA and kernel PCA to clarify its property. The artificial data is generated from Lorenz system, and the real data is the spacecrafts' telemetry data. This paper demonstrates that autoencoders are able to detect subtle anomalies which linear PCA fails. Also, autoencoders can increase their accuracy by extending them to denoising autoenconders. Moreover, autoencoders can be useful as nonlinear techniques without complex computation as kernel PCA requires. Finaly, the authors examine the learned features in the hidden layer of autoencoders, and present that autoencoders learn the normal state properly and activate differently with anomalous input. <s> BIB008 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> We developed a heat detection algorithm for pasture-based dairy cows.Our algorithm uses data from accelerometer attached to the cow collars.We present the overall accuracy of 82-100% with 100% sensitivity. This study was conducted to investigate the detection of heat events in pasture-based dairy cows fitted with on-animal sensors using unsupervised learning. Accelerometer data from the cow collars were used to identify increased activity levels in cows associated with recorded heat events. Time series data from the accelerometers were first segmented into windows before features were extracted. K-means clustering algorithm was then applied across the windows for grouping. The groups were labelled in terms of their activity intensity: high, medium and low. An activity index level (AIxL) was then derived from a count of activity intensity labels over time. Change detection techniques were then applied on AIxL to find very high activity events. Detected events in AIxL were compared with recorded heat events and observed significant associations between the increased activities through high AIxL values and the observed heat events. We achieved overall accuracy of 82-100% with 100% sensitivity when change detection technique is applied to activity index level. <s> BIB009 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> The problem of mining a network of time series data naturally arises in many research areas including energy system, quantitative finance, bioinformatics, environmental monitoring, traffic monitoring, etc. Among others, two emerging challenges shared by manifold applications are (1) the modeling of temporal-spatial dependence with contextual information and (2) the design of efficient learning algorithms for big data (exceedingly long sequence) analytics. In this paper, we study a Contextual Hidden Markov Model (CHMM) that describes infinite temporal dependence and contextual spatial relations in an unified framework. More importantly, to make model training feasible for growing number of data samples, we develop an Online Expectation-Maximization (OEM) algorithm that avoids the usual forward-backward pass of the entire time sequence. Two typical applications, missing value recovery and novelty detection, are considered to test CHMM and the online algorithm. Experiments are conducted on real world data collected from power distribution network monitoring. We compare CHMM with other popular methods and the results not only justify the benefit of incorporating temporal-spatial and contextual information, but also demonstrate the effectiveness of the proposed OEM algorithm. <s> BIB010 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Anomaly detection in time series has attracted considerable attention due to its importance in many real-world applications including intrusion detection, energy management and finance. Most approaches for detecting outliers rely on either manually set thresholds or assumptions on the distribution of data according to Chandola, Banerjee and Kumar. Here, we propose a new approach to detect outliers in streaming univariate time series based on Extreme Value Theory that does not require to hand-set thresholds and makes no assumption on the distribution: the main parameter is only the risk, controlling the number of false positives. Our approach can be used for outlier detection, but more generally for automatically setting thresholds, making it useful in wide number of situations. We also experiment our algorithms on various real-world datasets which confirm its soundness and efficiency. <s> BIB011 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Outlier detection is a very essential problem in a variety of application areas. Many detection methods are deficient for high-dimensional time series data sets containing both isolated and assembled outliers. In this paper, we propose an Outlier Detection method based on Cross-correlation Analysis (ODCA). ODCA consists of three key parts. They are data preprocessing, outlier analysis, and outlier rank. First, we investigate a linear interpolation method to convert assembled outliers into isolated ones. Second, a detection mechanism based on the cross-correlation analysis is proposed for translating the high-dimensional data sets into 1-D cross-correlation function, according to which the isolated outlier is determined. Finally, a multilevel Otsu’s method is adopted to help us select the rank thresholds adaptively and output the abnormal samples at different levels. To illustrate the effectiveness of the ODCA algorithm, four experiments are performed using several high-dimensional time series data sets, which include two small-scale sets and two large-scale sets. Furthermore, we compare the proposed algorithm with the detection methods based on wavelet analysis, bilateral filtering, particle swarm optimization, auto-regression, and extreme learning machine. In addition, we discuss the robustness of the ODCA algorithm. The statistical results show that the ODCA algorithm is much better than existing mainstream methods in both effectiveness and time complexity. <s> BIB012 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Due to the continued digitization of industrial and societal processes, including the deployment of networked sensors, we are witnessing a rapid proliferation of time-ordered observations, known as time series. For example, the behavior of drivers can be captured by GPS or accelerometer as a time series of speeds, directions, and accelerations. We propose a framework for outlier detection in time series that, for example, can be used for identifying dangerous driving behavior and hazardous road locations. Specifically, we first propose a method that generates statistical features to enrich the feature space of raw time series. Next, we utilize an autoencoder to reconstruct the enriched time series. The autoencoder performs dimensionality reduction to capture, using a small feature space, the most representative features of the enriched time series. As a result, the reconstructed time series only capture representative features, whereas outliers often have non-representative features. Therefore, deviations of the enriched time series from the reconstructed time series can be taken as indicators of outliers. We propose and study autoencoders based on convolutional neural networks and long-short term memory neural networks. In addition, we show that embedding of contextual information into the framework has the potential to further improve the accuracy of identifying outliers. We report on empirical studies with multiple time series data sets, which offers insight into the design properties of the proposed framework, indicating that it is effective at detecting outliers. <s> BIB013 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Industry devices (i.e., entities) such as server machines, spacecrafts, engines, etc., are typically monitored with multivariate time series, whose anomaly detection is critical for an entity's service quality management. However, due to the complex temporal dependence and stochasticity of multivariate time series, their anomaly detection remains a big challenge. This paper proposes OmniAnomaly, a stochastic recurrent neural network for multivariate time series anomaly detection that works well robustly for various devices. Its core idea is to capture the normal patterns of multivariate time series by learning their robust representations with key techniques such as stochastic variable connection and planar normalizing flow, reconstruct input data by the representations, and use the reconstruction probabilities to determine anomalies. Moreover, for a detected entity anomaly, OmniAnomaly can provide interpretations based on the reconstruction probabilities of its constituent univariate time series. The evaluation experiments are conducted on two public datasets from aerospace and a new server machine dataset (collected and released by us) from an Internet company. OmniAnomaly achieves an overall F1-Score of 0.86 in three real-world datasets, signicantly outperforming the best performing baseline method by 0.09. The interpretation accuracy for OmniAnomaly is up to 0.89. <s> BIB014 </s> A review on outlier/anomaly detection in time series data <s> Multivariate time series <s> Traditional distance and density-based anomaly detection techniques are unable to detect periodic and seasonality related point anomalies which occur commonly in streaming data, leaving a big gap in time series anomaly detection in the current era of the IoT. To address this problem, we present a novel deep learning-based anomaly detection approach (DeepAnT) for time series data, which is equally applicable to the non-streaming cases. DeepAnT is capable of detecting a wide range of anomalies, i.e., point anomalies, contextual anomalies, and discords in time series data. In contrast to the anomaly detection methods where anomalies are learned, DeepAnT uses unlabeled data to capture and learn the data distribution that is used to forecast the normal behavior of a time series. DeepAnT consists of two modules: time series predictor and anomaly detector. The time series predictor module uses deep convolutional neural network (CNN) to predict the next time stamp on the defined horizon. This module takes a window of time series (used as a context) and attempts to predict the next time stamp. The predicted value is then passed to the anomaly detector module, which is responsible for tagging the corresponding time stamp as normal or abnormal. DeepAnT can be trained even without removing the anomalies from the given data set. Generally, in deep learning-based approaches, a lot of data are required to train a model. Whereas in DeepAnT, a model can be trained on relatively small data set while achieving good generalization capabilities due to the effective parameter sharing of the CNN. As the anomaly detection in DeepAnT is unsupervised, it does not rely on anomaly labels at the time of model generation. Therefore, this approach can be directly applied to real-life scenarios where it is practically impossible to label a big stream of data coming from heterogeneous sensors comprising of both normal as well as anomalous points. We have performed a detailed evaluation of 15 algorithms on 10 anomaly detection benchmarks, which contain a total of 433 real and synthetic time series. Experiments show that DeepAnT outperforms the state-of-the-art anomaly detection methods in most of the cases, while performing on par with others. <s> BIB015
The input time series is sometimes a multivariate time series with possibly correlated variables rather than a univariate time series. As opposed to the univariate time series case, the detection method used to identify point outliers in multivariate time series can deal not only with a single variable (Section 3.2.1) but also with more than one variable simultaneously (Section 3.2.2). Additionally, a point outlier in a multivariate time series can affect one (univariate point) or more than one (multivariate point, a vector at time t) variables (see Fig. 3b ). As will be seen in the following sections, some multivariate techniques are able to detect univariate point outliers and (similarly) some univariate techniques can be used to detect multivariate point outliers. The characteristics mentioned in Fig. 6 will also be highlighted. (1). Additionally, the authors present a dynamic thresholding approach in which some smoothed residuals of the model obtained from past data are used to determine the threshold at each time step. Correlation dependencies between the variables are not considered when applying univariate techniques to each time-dependent variable, leading to a loss of information. To overcome this problem, and at the same time to leverage that univariate detection techniques are highly developed, some researchers apply a preprocessing method to the multivariate time series to find a new set of uncorrelated variables where univariate techniques can be applied. These methods are based on dimensionality reduction techniques, and as depicted in Fig. 11 , the multivariate series is simplified into a representation of lower dimension before applying univariate detection techniques. Since the new series are combinations of the initial input variables, the identified outliers are multivariate; that is, they affect more than one variable. Alternatively, BIB003 suggest reducing the dimensionality with projection pursuit, which aims to find the best projections to identify outliers. The authors mathematically prove that the optimal directions are those that maximize or minimize the kurtosis coefficient of the projected time series. Univariate statistical tests BIB001  ] are then applied iteratively to each projected univariate time series for multivariate point outlier detection. Similarly, BIB004 propose using Independent Component Analysis (ICA) to obtain a set of unobservable independent nonGaussian variables, assuming that the observed data has been generated by a linear combination of those variables. Outliers are identified in each new series independently if equation (1) is satisfied for x it = µ i and τ i = 4.47σ i , where µ i is the mean and σ i the standard error of the ith new variable. Other techniques reduce the input multivariate time series into a single time-dependent variable rather than into a set of uncorrelated variables. BIB012 define the transformed univariate series using the cross-correlation function between adjacent vectors in time; that is, x t −1 and x t . Point outliers are iteratively identified in this new series as those that have a low correlation with their adjacent multivariate points. The threshold value τ is determined at each iteration by the multilevel Otsu's method. BIB009 also transformed the multivariate time series into a univariate series using a transformation specifically designed for the application domain considered. Point outliers are identified using equation (1) and the 3-sigma rule. The main characteristics of the univariate techniques analyzed for point outlier detection in multivariate time series are described in Table 3 in chronological order. Most of them are non-iterative. In addition, point outliers are events of interest for almost all the researchers. Particularly, note that the transformation methods proposed by Galeano et al. [2006] and BIB012 are specific for outlier detection and not general dimensionality reduction techniques. As far as the characteristics mentioned in Fig. 6  where x t is the actual k-dimensional data point, andx t its expected value. Note that this is a generalization of the definition given for the model-based techniques in univariate time series and that the intuition is repeated (refer to equation (1) and Table 1 ). In fact,x t can be obtained using estimation models-which use past, current, and future values-or prediction models-which only use past values (see Fig. 13 ). Within the estimation model-based category, autoencoders are one of the most commonly used methods. Autoencoders are a type of neural network that learns only the most significant features of a training set used as the reference of normality. Since outliers often correspond to non-representative features, autoencoders fail to reconstruct them, providing large errors in (4). BIB008 use this method, where the input of the autoencoder is a single multivariate point of the time series. The temporal correlation between the observations within each variable is not considered in this approximation. Therefore, to account for temporal dependencies, BIB013 propose extracting features within overlapping sliding windows (e.g., statistical features or the difference between the Euclidean norms of two consecutive time windows) before applying the autoencoder. BIB014 suggest a more complex approach based on a Variational AutoEncoder (VAE) with a Gated Recurrent Unit (GRU). The input of the model is a sequence of observations containing x t and l preceding observations to it. The output is the reconstructed x t (x t ). Additionally, they apply extreme value theory BIB011 in the reference of normality to automatically select the threshold value. Apart from using autoencoders,x t can also be derived from the general trend estimation of multiple co-evolving time series.  use a non-parametric model that considers both the temporal correlation between the values within each variable and inter-series relatedness in a unified manner to estimate that trend. In this case, even though the trend of each variable is estimated using the multivariate time series, univariate point outliers are identified within each variable using equation (1) instead of k-dimensional data points. The other model-based techniques that can be used to obtainx t in equation (4) are the prediction model-based techniques (see Fig. 13b ). Techniques within this category also fit a model to a multivariate time series, but the expected values are the predictions for the future made on the basis of past values. For example, the Contextual Hidden Markov Model (CHMM) incrementally captures both the temporal dependencies and the correlations between the variables in a multivariate time series BIB010 ]. The temporal dependence is modeled by a basic HMM, and the correlation between the variables is included into the model by adding an extra layer to the HMM network. The DeepAnt algorithm BIB015 ] mentioned in Section 3.1 is also capable of detecting point outliers in multivariate time series using the CNN prediction model. Once the model is learned, the next timestamp is predicted using a window of previous observations as input. All of these estimation and prediction model-based techniques can theoretically be employed in a streaming context using sliding windows because no subsequent points to x t are needed. As with univariate time series, the estimationbased methods need to consider at least the newly arrived point x t (k 2 = 0 in Table 1) , so prediction-based techniques Manuscript submitted to ACM are more appropriate for detecting outliers in a streaming fashion. Additionally, these model-based techniques all use a fixed model, and they do not adapt to changes over time, except for the proposal of BIB010 , which is incrementally updated. The dissimilarity-based methods will be discussed next. These techniques are based on computing the pairwise dissimilarity between multivariate points or their representations, without the need for fitting a model. Therefore, for a predefined threshold τ , x t is a point outlier if: where x t is the actual k-dimensional point,x t its expected value, and s measures the dissimilarity between two multivariate points. These methods do not usually use the raw data directly, but instead use different representation methods. For example, BIB005 BIB006 represent the data using a graph where nodes are the multivariate points of the series and the edges the similarity values between them computed with the Radial Basis Function (RBF). The idea is to apply a random walk model in the graph to detect the nodes that are dissimilar to the others (i.e., hardly accessible in the graph). By contrast, BIB007 propose recording the historical similarity and dissimilarity values between the variables in a vector. The aim is to analyze the dissimilarity of consecutive points over time and detect changes using ||.|| 1 . The last group depicted in Fig. 12 refers to the histogramming approach, where the term deviant has also been used in the context of multivariate series (see the definition given in (3)). BIB002 extend the technique for deviant detection explained in Section 3.1 to multivariate time series by treating the measurements collected at the same timestamp as a vector. Similar to the univariate case, the method aims to detect the vectors that should be removed so that the compressed representation (histogram) of the remaining data is improved. The authors propose an algorithm for both streaming and non-streaming series to find approximate optimal deviants. The main characteristics of the multivariate techniques analyzed for point outlier detection in multivariate time series are depicted in Table 4 in chronological order. Even if most of them find multivariate point outliers, some use the multivariate information to identify point outliers that only affect a single variable (i.e., univariate point outliers). All of the analyzed techniques are non-iterative, and outliers represent events of interest for the researchers. In addition, most of them obtain different results if they are applied to a shuffled version of the time series. Although all these methods can detect outliers in a streaming context, few are incremental or updated as new data arrives.  This section presents some of the detection techniques that have been used in the literature to detect subsequence outliers in multivariate time series data. The nature of these methods can be either univariate (Section 4.2.1) or multivariate (Section 4.2.2), and they can detect subsequence outliers that affect either one variable (univariate subsequence outliers) or multiple variables, which are all aligned (multivariate subsequence outliers).