A review on outlier/anomaly detection in time series data <s> Subsequence outliers <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> BIB001 </s> A review on outlier/anomaly detection in time series data <s> Subsequence outliers <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> BIB002 </s> A review on outlier/anomaly detection in time series data <s> Subsequence outliers <s> We present a new algorithm for detecting anomalies in realvalued multidimensional time series. Our algorithm uses an exemplar-based model that is used to detect anomalies in single dimensions of the time series and a function that predicts one dimension from a related one to detect anomalies in multiple dimensions. The algorithm is shown to work on a variety of dierent types of time series as well as to detect a variety of dierent types of anomalies. We compare our algorithm to other algorithms for both one-dimensional and multidimensional time series and demonstrate that it improves over the state-of-the-art. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> Subsequence outliers <s> It is becoming increasingly common for organizations to collect very large amounts of data over time, and to need to detect unusual or anomalous time series. For example, Yahoo has banks of mail servers that are monitored over time. Many measurements on server performance are collected every hour for each of thousands of servers. We wish to identify servers that are behaving unusually. We compute a vector of features on each time series, measuring characteristics of the series. The features may include lag correlation, strength of seasonality, spectral entropy, etc. Then we use a principal component decomposition on the features, and use various bivariate outlier detection methods applied to the first two principal components. This enables the most unusual series, based on their feature vectors, to be identified. The bivariate outlier detection methods used are based on highest density regions and α-hulls. <s> BIB004 </s> A review on outlier/anomaly detection in time series data <s> Subsequence outliers <s> In the last decade, outlier detection for temporal data has received much attention from data mining and machine learning communities. While other works have addressed this problem by two-way approaches (similarity and clustering), we propose in this paper an embedded technique dealing with both methods simultaneously. We reformulate the task of outlier detection as a weighted clustering problem based on entropy and dynamic time warping for time series. The outliers are then detected by an optimization problem of a new proposed cost function adapted to this kind of data. Finally, we provide some experimental results for validating our proposal and comparing it with other methods of detection. <s> BIB005 </s> A review on outlier/anomaly detection in time series data <s> Subsequence outliers <s> We consider the problem of learning to detect anomalous time series from an unlabeled data set, possibly contaminated with anomalies in the training data. This scenario is important for applications in medicine, economics, or industrial quality control, in which labeling is difficult and requires expensive expert knowledge, and anomalous data is difficult to obtain. This article presents a novel method for unsupervised anomaly detection based on the shapelet transformation for time series. Our approach learns representative features that describe the shape of time series stemming from the normal class, and simultaneously learns to accurately detect anomalous time series. An objective function is proposed that encourages learning of a feature representation in which the normal time series lie within a compact hypersphere of the feature space, whereas anomalous observations will lie outside of a decision boundary. This objective is optimized by a block-coordinate descent procedure. Our method can efficiently detect anomalous time series in unseen test data without retraining the model by reusing the learned feature representation. We demonstrate on multiple benchmark data sets that our approach reliably detects anomalous time series, and is more robust than competing methods when the training instances contain anomalous time series. <s> BIB006 </s> A review on outlier/anomaly detection in time series data <s> Subsequence 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> BIB007
 Model-based Dissimilarity-based Estimation Prediction Fig. 19 . Types of methods for detecting subsequence outliers in multivariate time series. The first type of technique to be discussed is the model-based technique. As mentioned in previous sections, the aim is to detect the subsequences that are far from their expected value, which can be obtained using an estimation model or a prediction model. A subsequence S = x p , ..., x p+n−1 of length n is an outlier if for a predefined threshold τ . Within the techniques based on estimation models, the approach proposed by BIB003 intends to find pairs of related variables using a set of nonlinear functions. Once this is done, a value in a variable can be estimated using observations from another variable (past and future with respect to x t ). These functions are learned using an external multivariate time series as the reference of normality (see Fig. 17 ). Estimations and error calculations can then be done for new time series. Within this new series, a subsequence in one variable is estimated using the learned functions and data from another variable. In contrast, the CNN method described by BIB007 is a prediction model-based technique, which is a direct extension of the method explained in Section 4.1 to detect time-aligned outliers that affect multiple variables. The second group corresponds to the dissimilarity-based techniques, a generalization of equation (7) that finds unusual subsequences in a multivariate time series based on the pairwise dissimilarity calculation between subsequences or their representations. Unlike in the univariate subsequence outlier detection, this type of technique has barely been used in multivariate series. In the only example, BIB001 BIB002 extend their method for point outliers (Section 3.2.2) to obtain how dissimilar is a node representing a fixed-length subsequence with the others. This dissimilarity value is obtained by applying a random walk model in the graph, and the computation of the pairwise similarity between those nodes is also based on the RBF. A summary of the multivariate techniques analyzed for subsequence outlier detection is given in Table 7 . In all of the cases, the subsequence outliers represent an event of interest. In addition, the techniques find non-periodic outliers of fixed-length without using a discretization technique. Some of the key aspects presented for the subsequence outliers (see Fig. 14) can also appear when attempting to detect outlier time series. First, each time-dependent variable in a multivariate time series can have a different length. Second, representation methods such as discretization can also be used to facilitate the comparisons between variables. In addition, all of the outlier time series detection methods can theoretically be applied in a streaming context using sliding windows. However, in contrast to subsequences, the property of temporality is not necessarily considered by these methods. This section will examine the techniques that detect outlier time series, following the diagram given in Fig. 20 . The first type of technique to be discussed is based on dimensionality reduction. As mentioned in the previous sections, the aim of these techniques is to reduce the dimensionality of the input multivariate time series into a set of Manuscript submitted to ACM uncorrelated variables. As shown in Fig. 21 , BIB004 propose reducing the dimensionality by extracting some representative statistical features from each time series (e.g., mean, and first order of autocorrelation) and then applying PCA. Outlier time series are detected by their deviation from the highest density region in the PCA space, which is defined by the first two principal components. use clustering in that PCA space to detect outlier time series by measuring the deviation between the cluster centroids and the points that represent the time series. Instead of applying a detection technique in a lower space, original raw data can also be used directly. Indeed, the dissimilarity-based techniques in Fig. 20 directly analyze the pairwise dissimilarity between the time series. The most common approach within this category is clustering. The intuition is similar to that depicted in Fig. 18 , but whole time series are considered instead of subsequences. In this case, the reference of normality is the same multivariate time series. Given that the well-known k-means clustering algorithm is not useful for unsynchronized variables because it uses the Euclidean distance,  propose using Phased k-means in unsynchronized periodic multivariate time series. This technique is a modification of k-means so that the phase of each time-dependent variable to its closest centroid is adjusted prior to dissimilarity calculation at every iteration. Once a set of representative time series centroids is generated, the outliers are identified using equation (7) and cross-correlation as the similarity measure between time series. BIB005 also use clustering but in this case based on the Dynamic Time Warping (DTW) measure, which allows the series to be warped and shifted in time and have different lengths. The method optimizes an objective function by both minimizing the within-cluster distances using the DTW measure and maximizing the negative entropy of some weights that are assigned to each time series. Time series that increase the within-cluster distances to their closest cluster have smaller weights. Specifically, time series with small weights are considered to be outliers. Other dissimilarity-based techniques are based on shapelets, which are representative time series subsequences  ]. BIB006 use them to describe the shape of normal variables and detect outlier timedependent variables in a multivariate time series. The shapelets are learned using an external time series as the reference of normality. The idea is to measure the dissimilarity that each learned shapelet has with a variable using the Euclidean distance. Subsequences of outlier variables are dissimilar to the learned shapelets. A summary of the techniques used for outlier time series detection is provided in Table 8 . All of these techniques intend to find events of interest and none is iterative. Unlike the subsequences, the length of the series is always specified. The approach proposed by BIB005 is the only one that can deal with time series with variables of different lengths. The works reviewed in this section directly use raw data and consider temporality. 