A review on outlier/anomaly detection in time series data <s> CONCLUDING REMARKS AND FUTURE WORK <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> CONCLUDING REMARKS AND FUTURE WORK <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> CONCLUDING REMARKS AND FUTURE WORK <s> In the past few years, clustering has become a popular task associated with time series. The choice of a suitable distance measure is crucial to the clustering process and, given the vast number of distance measures for time series available in the literature and their diverse characteristics, this selection is not straightforward. With the objective of simplifying this task, we propose a multi-label classification framework that provides the means to automatically select the most suitable distance measures for clustering a time series database. This classifier is based on a novel collection of characteristics that describe the main features of the time series databases and provide the predictive information necessary to discriminate between a set of distance measures. In order to test the validity of this classifier, we conduct a complete set of experiments using both synthetic and real time series databases and a set of five common distance measures. The positive results obtained by the designed classification framework for various performance measures indicate that the proposed methodology is useful to simplify the process of distance selection in time series clustering tasks. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> CONCLUDING REMARKS AND FUTURE WORK <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> BIB004 </s> A review on outlier/anomaly detection in time series data <s> CONCLUDING REMARKS AND FUTURE WORK <s> As spacecraft send back increasing amounts of telemetry data, improved anomaly detection systems are needed to lessen the monitoring burden placed on operations engineers and reduce operational risk. Current spacecraft monitoring systems only target a subset of anomaly types and often require costly expert knowledge to develop and maintain due to challenges involving scale and complexity. We demonstrate the effectiveness of Long Short-Term Memory (LSTMs) networks, a type of Recurrent Neural Network (RNN), in overcoming these issues using expert-labeled telemetry anomaly data from the Soil Moisture Active Passive (SMAP) satellite and the Mars Science Laboratory (MSL) rover, Curiosity. We also propose a complementary unsupervised and nonparametric anomaly thresholding approach developed during a pilot implementation of an anomaly detection system for SMAP, and offer false positive mitigation strategies along with other key improvements and lessons learned during development. <s> BIB005
In this paper, an organized overview of outlier detection techniques in time series data has been proposed. Moreover, a taxonomy that categorizes these methods depending on the input data type, the outlier type, and the nature of the detection method has been included. This section first discusses some general remarks about the analyzed techniques, and it then introduces the conclusions regarding the axes of the taxonomy. As seen in previous sections, a broad terminology has been used to refer to the same concept; that is, the outlier in unlabeled time series data. The term outlier has been mainly used in point outlier detection, whereas discord or anomaly have been more frequently used in subsequence outlier detection. In outlier time series detection, both outlier and anomaly have been used. Additionally, these terms are related to the objective of the detection such that outlier is mostly used when detecting unwanted data, whereas anomaly has been when detecting events of interest. In most of the analyzed works, the concept outlier represents an event of interest; that is, the authors mainly focus on extracting the outlier information considered as useful data rather than on cleaning the useless or unwanted data to improve the data quality for further analysis. Most of those who focus on handling unwanted data use iterative techniques and detect point outliers in univariate time series. These outliers are usually removed or replaced by an expected value. Therefore, it might be interesting to extend this type of methods by developing techniques that improve the data quality of multivariate time series data. Despite the variety in terminology and purpose, all of the methods that we have reviewed are based on the same idea: detecting those parts in a time series (point, subsequence, or whole time series) that significantly differ from their expected value. Each author uses different means to obtain this expected value and compute how far it is from the actual observation to decide whether or not it is an outlier. Although some techniques obtain the expected value based on an external or reference set, caution must be taken because it can itself contain outliers and distort the detection. In fact, they are in the limit of the unsupervised Manuscript submitted to ACM converting it into such type is not always the best option. Therefore, outlier detection in an irregularly sampled time series is an interesting future direction line. Having provided some general conclusions, we will now focus on each of the axes. Starting from the first axis, the most remarkable conclusion is that even if most of the analysis has been performed on univariate input time series data, in recent years special emphasis has been placed on multivariate series. However, some techniques analyze each variable independently, even though they have a multivariate time series as input. For the second axis, point outlier detection is the most researched problem due to its simplicity in comparison to the rest. Within this category, it is remarkable that some techniques do not consider the temporal information at all. This can lead to not detecting outliers that violate the temporal correlation of the series. Thus, possible future work may include temporal information to techniques that do not consider it (e.g., BIB001 BIB002 ; BIB004 ) to see if the results improve. Additionally, even if theoretically many techniques can determine if a new data point is an outlier upon arrival, no study has been conducted to analyze whether these methods can really give an immediate response in real time or not. Consequently, an in-depth investigation could be done to analyze the computational cost of outlier detection techniques and to determine whether these methods can be practically used in real-time scenarios. There is also a chance for further incremental algorithm developments to ensure quick responses that adapt to the evolution of the stream. Subsequence outliers and outlier time series have been handled less frequently. Most of the subsequence outlier detection methods find non-periodic and fixed-length outliers. Indeed, there are no techniques that identify periodic subsequence outliers in multivariate time series. This can be a promising area for further investigation and may be of interest in areas such as cybersecurity to detect periodic network attacks, or in credit-fraud detection to detect periodic thefts. Additionally, within techniques that detect subsequence outliers, care must be taken with the way in which clustering is performed because it has been shown that clustering all of the subsequences extracted from a time series by a sliding window produces meaningless results . A straightforward solution could be to use non-overlapping subsequences, but this slicing may miss relevant information when the time series presents a non-periodical structure. Not much work has been carried out on the detection of outlier time series. Other research directions in this line include using different distance measures and creating more effective methods for dealing with time-dependent variables of different lengths. In addition, variables could be represented using other representations than raw data to facilitate comparisons. Within the dissimilarity-based techniques that detect either subsequence or whole time series outliers (e.g., clustering), the dissimilarity measure that is used influences the results obtained. The Euclidean distance accounts for the majority of all published work mentioned in this review due to its computation efficiency. However, other measures, such as DTW, could lead to an improvement in the detection of outliers because they include temporal information. An interesting future research direction would be to observe how different dissimilarity measures influence the outlier detection algorithms in time series data to see if any of them improve the results of the Euclidean distance. In particular, meta-learning approaches such as that proposed by BIB003 could be used as they provide an automatic selection of the most suitable distance measure. In addition to these types of outliers, there could be other types of unexplored outliers. For example, it may be interesting to detect outliers that propagate over time within different variables of a multivariate time series; that is, an outlier may begin in a unique variable and then propagate through other variables in later time steps. As far as we know, this problem has not been addressed yet in the literature, or at least it has not been done under the name of Manuscript submitted to ACM outlier/anomaly detection. Therefore, developing an algorithm capable of detecting outliers caused by the same origin or variable but occurring at different time steps in different variables appears to be a promising direction for future research. Finally, with regard to the nature of the detection method, it should be noted that some univariate techniques (e.g., the distance-based) can easily be generalized to the multivariate case by considering the distance between vectors instead of points. However, complex correlations between the variables in a multivariate time series are not taken into account. This may lead us to not identify observations that look normal in each variable individually but which violate the correlation structure between variables. In addition, when applying a univariate technique separately to each variable in a multivariate time series, the correlation dependencies are ignored. This can be computationally expensive when the number of variables is large. Hence, an extension of the univariate detection techniques applied to multivariate time series should be studied (e.g., BIB005 ;  ) so that the correlations between variables representing complex system behaviors are included.