A review on outlier/anomaly detection in time series data <s> Point outliers <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> BIB001 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> In this article we consider the problem of detecting unusual values or outliers from time series data where the process by which the data are created is difficult to model. The main consideration is the fact that data closer in time are more correlated to each other than those farther apart. We propose two variations of a method that uses the median from a neighborhood of a data point and a threshold value to compare the difference between the median and the observed data value. Both variations of the method are fast and can be used for data streams that occur in quick succession such as sensor data on an airplane. <s> BIB002 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Load curve data refers to the electric energy consumption recorded by meters at certain time intervals at delivery points or end user points, and contains vital information for day-to-day operations, system analysis, system visualization, system reliability performance, energy saving and adequacy in system planning. Unfortunately, it is unavoidable that load curves contain corrupted data and missing data due to various random failure factors in meters and transfer processes. This paper presents the B-Spline smoothing and Kernel smoothing based techniques to automatically cleanse corrupted and missing data. In implementation, a man-machine dialogue procedure is proposed to enhance the performance. The experiment results on the real British Columbia Transmission Corporation (BCTC) load curve data demonstrated the effectiveness of the presented solution. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> The deployment of environmental sensors has generated an interest in real-time applications of the data they collect. This research develops a real-time anomaly detection method for environmental data streams that can be used to identify data that deviate from historical patterns. The method is based on an autoregressive data-driven model of the data stream and its corresponding prediction interval. It performs fast, incremental evaluation of data as it becomes available, scales to large quantities of data, and requires no pre-classification of anomalies. Furthermore, this method can be easily deployed on a large heterogeneous sensor network. Sixteen instantiations of this method are compared based on their ability to identify measurement errors in a windspeed data stream from Corpus Christi, Texas. The results indicate that a multilayer perceptron model of the data stream, coupled with replacement of anomalous data points, performs well at identifying erroneous data in this data stream. <s> BIB004 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Wireless sensor network WSN applications require efficient, accurate and timely data analysis in order to facilitate near real-time critical decision-making and situation awareness. Accurate analysis and decision-making relies on the quality of WSN data as well as on the additional information and context. Raw observations collected from sensor nodes, however, may have low data quality and reliability due to limited WSN resources and harsh deployment environments. This article addresses the quality of WSN data focusing on outlier detection. These are defined as observations that do not conform to the expected behaviour of the data. The developed methodology is based on time-series analysis and geostatistics. Experiments with a real data set from the Swiss Alps showed that the developed methodology accurately detected outliers in WSN data taking advantage of their spatial and temporal correlations. It is concluded that the incorporation of tools for outlier detection in WSNs can be based on current statistical methodology. This provides a usable and important tool in a novel scientific field. <s> BIB005 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> This paper proposed the combination of two statistical techniques for the detection and imputation of outliers in time series data. An autoregressive integrated moving average with exogenous inputs (ARIMAX) model is used to extract the characteristics of the time series and to find the residuals. The outliers are detected by performing hypothesis testing on the extrema of the residuals and the anomalous data are imputed using another ARIMAX model. The process is performed in an iterative way because at the beginning the process, the residuals are contaminated by the anomalies and therefore, the ARIMAX model needs to be re-learned on “cleaner” data at every step. We test the algorithm using both synthetic and real data sets and we present the analysis and comments on those results. <s> BIB006 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> In principle, connected sensors allow effortless long-term self-monitoring of health and wellness that can help maintain health and quality of life. However, data collected in the “wild” may be noisy and contain outliers, e.g., due to uncontrolled sources or data from different persons using the same device. The removal of the “outliers” is therefore critical for accurate interpretation of the data. In this paper we study the detection and elimination of outliers in self-weighing time series data obtained from connected weight scales. We examined three techniques: (1) a method based on autoregressive integrated moving average (ARIMA) time series modelling, (2) median absolute deviation (MAD) scale estimate, and (3) a method based on Rosner statistics. We applied these methods to both a data set with real outliers and a clean data set corrupted with simulated outliers. The results suggest that the simple MAD algorithm and ARIMA performed well with both test sets while the Rosner statistics was significantly less effective. In addition, the ARIMA approach appeared to be significantly less sensitive to long periods of missing data than MAD and Rosner statistics. <s> BIB007 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Time series data are generated from almost every domain and anomaly detection becomes extremely important in the last decade. It consists in detecting anomalous patterns through identifying some new and unknown behaviors that are abnormal or inconsistent relative to most of the data. An efficient anomaly detection algorithm has to adapt the detection process for each system condition and each time series behavior. In this paper, we propose an adaptive threshold able to detect anomalies in univariate time series. Our algorithm is based on segmentation and local means and standard deviations. It allows us to simplify time series visualization and to detect new abnormal data as time series jumps within different time series behavior. On synthetic and real datasets the proposed approach shows good ability in detecting abnormalities. <s> BIB008 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Performance and high availability have become increasingly important drivers, amongst other drivers, for user retention in the context of web services such as social networks, and web search. Exogenic and/or endogenic factors often give rise to anomalies, making it very challenging to maintain high availability, while also delivering high performance. Given that service-oriented architectures (SOA) typically have a large number of services, with each service having a large set of metrics, automatic detection of anomalies is non-trivial. ::: Although there exists a large body of prior research in anomaly detection, existing techniques are not applicable in the context of social network data, owing to the inherent seasonal and trend components in the time series data. ::: To this end, we developed two novel statistical techniques for automatically detecting anomalies in cloud infrastructure data. Specifically, the techniques employ statistical learning to detect anomalies in both application, and system metrics. Seasonal decomposition is employed to filter the trend and seasonal components of the time series, followed by the use of robust statistical metrics -- median and median absolute deviation (MAD) -- to accurately detect anomalies, even in the presence of seasonal spikes. ::: We demonstrate the efficacy of the proposed techniques from three different perspectives, viz., capacity planning, user behavior, and supervised learning. In particular, we used production data for evaluation, and we report Precision, Recall, and F-measure in each case. <s> BIB009 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <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> BIB010 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Abstract We are seeing an enormous increase in the availability of streaming, time-series data. Largely driven by the rise of connected real-time data sources, this data presents technical challenges and opportunities. One fundamental capability for streaming analytics is to model each stream in an unsupervised fashion and detect unusual, anomalous behaviors in real-time. Early anomaly detection is valuable, yet it can be difficult to execute reliably in practice. Application constraints require systems to process data in real-time, not batches. Streaming data inherently exhibits concept drift, favoring algorithms that learn continuously. Furthermore, the massive number of independent streams in practice requires that anomaly detectors be fully automated. In this paper we propose a novel anomaly detection algorithm that meets these constraints. The technique is based on an online sequence memory algorithm called Hierarchical Temporal Memory (HTM). We also present results using the Numenta Anomaly Benchmark (NAB), a benchmark containing real-world data streams with labeled anomalies. The benchmark, the first of its kind, provides a controlled open-source environment for testing anomaly detection algorithms on streaming data. We present results and analysis for a wide range of algorithms on this benchmark, and discuss future challenges for the emerging field of streaming analytics. <s> BIB011 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Anomalies in time-series data give essential and often actionable information in many applications. In this paper we consider a model-free anomaly detection method for univariate time-series which adapts to non-stationarity in the data stream and provides probabilistic abnormality scores based on the conformal prediction paradigm. Despite its simplicity the method performs on par with complex prediction-based models on the Numenta Anomaly Detection benchmark and the Yahoo! S5 dataset. <s> BIB012 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> With the construction and deployment of seafloor observatories around the world, massive amounts of oceanographic measurement data were gathered and transmitted to data centers. The increase in the amount of observed data not only provides support for marine scientific research but also raises the requirements for data quality control, as scientists must ensure that their research outcomes come from high-quality data. In this paper, we first analyzed and defined data quality problems occurring in the East China Sea Seafloor Observatory System (ECSSOS). We then proposed a method to detect and repair the data quality problems of seafloor observatories. Incorporating data statistics and expert knowledge from domain specialists, the proposed method consists of three parts: a general pretest to preprocess data and provide a router for further processing, data outlier detection methods to label suspect data points, and a data interpolation method to fill up missing and suspect data. The autoregressive integrated moving average (ARIMA) model was improved and applied to seafloor observatory data quality control by using a sliding window and cleaning the input modeling data. Furthermore, a quality control flag system was also proposed and applied to describe data quality control results and processing procedure information. The real observed data in ECSSOS were used to implement and test the proposed method. The results demonstrated that the proposed method performed effectively at detecting and repairing data quality problems for seafloor observatory data. <s> BIB013 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <s> Abstract Recently, incremental and on-line learning gained more attention especially in the context of big data and learning from data streams, conflicting with the traditional assumption of complete data availability. Even though a variety of different methods are available, it often remains unclear which of them is suitable for a specific task and how they perform in comparison to each other. We analyze the key properties of eight popular incremental methods representing different algorithm classes. Thereby, we evaluate them with regards to their on-line classification error as well as to their behavior in the limit. Further, we discuss the often neglected issue of hyperparameter optimization specifically for each method and test how robustly it can be done based on a small set of examples. Our extensive evaluation on data sets with different characteristics gives an overview of the performance with respect to accuracy, convergence speed as well as model complexity, facilitating the choice of the best method for a given application. <s> BIB014 </s> A review on outlier/anomaly detection in time series data <s> Point outliers <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
Model-based Density-based The most popular and intuitive definition for the concept of point outlier is a point that significantly deviates from its expected value. Therefore, given a univariate time series, a point at time t can be declared an outlier if the distance to its expected value is higher than a predefined threshold τ : where x t is the observed data point, andx t is its expected value. This problem is graphically depicted in Fig. 8 , where the observed values within the shadowed area are at most at distance τ from their expected values. Clearly, O3 is the point that differs the most from its expected value, although O1, O2, and O4 are also farther than distance τ (outside the band), so all four are declared outliers. The outlier detection methods based on the strategy described in equation (1) are denominated model-based methods in this paper and are the most common approaches in the literature. Even though each technique computes the expected Manuscript submitted to ACM valuex t and the threshold τ differently, they are all based on fitting a model (either explicitly or implicitly). As shown in Table 1 , ifx t is obtained using previous and subsequent observations to x t (past, current, and future data), then the technique is within the estimation model-based methods. In contrast, ifx t is obtained relying only on previous observations to x t (past data), then the technique is within the prediction model-based methods. In practice, the main difference between using estimation or prediction methods is that techniques within this latter category can be used in streaming time series because they can determine whether or not a new datum is an outlier as soon as it arrives. In the case of estimation methods, this can only be done if, in addition to some points preceding x t , only the current point x t is used to compute the estimated value (k 2 = 0).  The most simple estimation models are based on constant or piecewise constant models, where basic statistics such as the median BIB002 or the Median Absolute Deviation (MAD) BIB007 ] are used to obtain the expected valuex t . These statistics are calculated using the full series or by grouping the data in equal-length segments and cannot be applied in streaming when future data is needed (k 2 > 0). A more sophisticated approach is to utilize unequal-length segments obtained with a segmentation technique. BIB008 use the mean of each segment to determine the expected value of the points within that segment. They also use an adaptive threshold τ i = ασ i , where α is a fixed value and σ i the standard deviation of segment i. Other estimation-based techniques intend to identify data points that are unlikely if a certain fitted model or distribution is assumed to have generated the data. For instance, some authors model the structure of the data using smoothing methods such as B-splines or kernels BIB003 [2014, 2016, 2017] use ARIMA models with exogenous inputs, linear regression or Artificial Neural Networks (ANNs). Although most of these models can also be used in prediction, in this case, the outliers are detected in the residual set using past and future data. Specifically, once the selected model is learned, hypothesis testing is applied over the residuals to detect the outliers. In BIB006  , assuming that the underlying distribution of the residuals is known, the minimum and maximum values are examined simultaneously at each iteration of the algorithm. The hypothesis to be tested is whether an extremum is an outlier (alternative hypothesis) or not (null hypothesis). The detected outliers are corrected, and the process is repeated until no more outliers are detected. In contrast, in BIB009 , the ESD test explained in the previous paragraph is applied but the median and MAD are used for robustness instead of the mean and standard deviation. In contrast to estimation models, techniques based on prediction models fit a model to the time series and obtainx t using only past data; that is, without using the current point x t or any posterior observations. Points that are very different from their predicted values are identified as outliers. Recall that all of the techniques within this category can deal with streaming time series. Within the prediction-based methods, some use a fixed model and thus are not able to adapt to the changes that occur in the data over time. For example, the DeepAnT algorithm that was presented by BIB015 is a deep learning-based outlier detection approach that applies a fixed Convolutional Neural Networks (CNNs) to predict values in the future. Other methods use an autoregressive model BIB004 or an ARIMA model BIB005 , which obtain confidence intervals for the predictions instead of only point estimates. Consequently, these methods implicitly define the value of τ . Other techniques adapt to the evolution of the time series by retraining the model. As the most basic approach, BIB002 describe a method that predicts the valuex t with the median of its past data. More elaborately, BIB013 fit an ARIMA model within a sliding window to compute the prediction interval, so the parameters are refitted each time that the window moves a step forward. Extreme value theory is another prediction-based approach that has been employed to detect point outliers in streaming univariate series, using past data and retraining. Given a fixed risk q, this theory allows us to obtain a threshold value z q,t that adapts itself to the evolution of the data such that P(X t > z q,t ) < q, for any t ≥ 0, assuming that the extreme values follow a Generalized Pareto Distribution (GPD). Incoming data is used to both detect anomalies (X t > z q,t ) and refine z q,t . Even if this notation is valid for upper thresholding, the idea is symmetrical when getting lower-bound thresholds or both upper-and lower-bound thresholds. BIB010 propose two algorithms based on this theory: SPOT, for data following any stationary distribution; and DSPOT, for data that can be subject to concept drift [Gama et al. 2014;  . Some of these prediction-based methods retrain the underlying model periodically, or each time a new point arrives. Therefore, they can adapt to the evolution of the data. However, none of them applies incremental model learning approaches, where the model is not rebuilt from scratch each time but is updated incrementally using only the new information received. This avoids the cost associated with training the models more than once and permits a more gradual adaptation to changes that can occur in the data, which is of special interest in streaming contexts BIB014 . In this sense, and in contrast to the previous approaches,   suggest modeling a univariate time series stream in an incremental fashion. This method uses Student-t processes to compute the prediction interval and updates the covariance matrix with the newly arrived data point. BIB011 use the Hierarchical Temporal Memory (HTM) network, which is also a prediction model-based technique that updates incrementally as new observations arrive. All of these techniques are based on equation (1). However, not all the existing point outlier detection methods rely on that idea, such as the density-based methods, which belong to the second category of methods depicted in Fig. 7 . Techniques within this group consider that points with less than τ neighbors are outliers; that is, when less than τ Manuscript submitted to ACM objects lie within distance R from those points. This could be denoted as where d is most commonly the Euclidean distance, x t is the data point at time stamp t to be analyzed, X is the set of data points, and R ∈ R + . Thus, a point is an outlier if τ p + τ s < τ , where τ p and τ s are the number of preceding and succeeding neighbors (points that appear before and after x t ) at distance lower or equal than R, respectively. The detection of density-based outliers has been widely handled in non-temporal data, but the concept of neighborhood is more complex in time series because the data are ordered. To take temporality into account, Fassetti [2007, 2010] and BIB012 apply this method within a sliding window, which allows us to wheter or not a new value of a streaming time series is an outlier upon arrival. An illustration of this density-based outlier concept is provided in Fig. 9 at two different time steps with R = 0.5, τ = 3, and a sliding window of length 11. When using sliding windows, a point can be an outlier for a window (e.g., O13 at t = 13) but not for another (e.g., I13 at t = 17). However, if a data point has at least τ succeeding neighbors within a window, then it cannot be an outlier for any future evolution (e.g., S4 at t = 13). Histogramming is the last group analyzed in this section. This type of method is based on detecting the points whose removal from the univariate time series results in a histogram representation with lower error than the original, even after the number of buckets has been reduced to account for the separate storage of these points (see Fig. 10 ). The histogram is built by computing the average of the values within each bucket, in which the order of the observations is preserved. Then, given a sequence of points X and a number of buckets B, D ⊂ X is a deviant set if where H * B is the optimal histogram (histogram with lowest approximation error) on X with B buckets, E X () is the total error in the approximation and H * B− |D | is the optimal histogram on X − D with B − |D| buckets.  introduced the term deviant to refer to these point outliers. They proposed a dynamic programming mechanism to produce a histogram consisting of B − |D| buckets and |D| deviants, minimizing its total error. Some years later BIB001 observed that for any bucket, the optimal set of k = |D| deviants always consists of the l highest and remaining k − l lowest values within the bucket, for some l ≤ k. Moreover, they presented not only an optimal algorithm for non-streaming time series but also a closely approximate algorithm and a heuristic approach for the streaming case. To conclude our review of point outlier detection in univariate time series, a summary of the analyzed techniques and their characteristics is provided in Table 2 . This table includes the inherent characteristics of the point outliers in time series data mentioned in Fig. 6 , whether the algorithm is iterative or not, the meaning the point outlier has for the authors, and the term they use to name it. We consider that a method is iterative if it is repeatedly applied on the same set to find the outliers. In this case, the few iterative methods are related to detecting unwanted data and improving the quality of the time series. Caution must be taken with the estimation methods that can theoretically be applied in a streaming time series; that is, those that do not use subsequent observations to the last arrived data point x t (k 2 = 0 in Table 1 ). Although, it may in theory be possible to apply these techniques in streaming contexts, these methods use the last observation received (x t ) and some other past information to calculate its expected value (x t ) and they then decide whether or not it is an outlier. Consequently, they must perform some calculations after the new point has arrived. The cost of this computation depends on the complexity of each method (which has not been analyzed in this paper or in every original works) but may not always guarantee a fast enough response. Thus, in practice, some of these techniques may not be applicable in streaming contexts and prediction methods are more recommendable for these situations.