A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model. <s> BIB001 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> The problem of finding a specified pattern in a time series database (i.e. query by content) has received much attention and is now a relatively mature field. In contrast, the important problem of enumerating all surprising or interesting patterns has received far less attention. This problem requires a meaningful definition of "surprise", and an efficient search technique. All previous attempts at finding surprising patterns in time series use a very limited notion of surprise, and/or do not scale to massive datasets. To overcome these limitations we introduce a novel technique that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data. <s> BIB002 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Recent advancements in sensor technology have made it possible to collect enormous amounts of data in real time. However, because of the sheer volume of data most of it will never be inspected by an algorithm, much less a human being. One way to mitigate this problem is to perform some type of anomaly (novelty /interestingness/surprisingness) detection and flag unusual patterns for further inspection by humans or more CPU intensive algorithms. Most current solutions are “custom made” for particular domains, such as ECG monitoring, valve pressure monitoring, etc. This customization requires extensive effort by domain expert. Furthermore, hand-crafted systems tend to be very brittle to concept drift. In this demonstration, we will show an online anomaly detection system that does not need to be customized for individual domains, yet performs with exceptionally high precision/recall. The system is based on the recently introduced idea of time series bitmaps. To demonstrate the universality of our system, we will allow testing on independently annotated datasets from domains as diverse as ECGs, Space Shuttle telemetry monitoring, video surveillance, and respiratory data. In addition, we invite attendees to test our system with any dataset available on the web. <s> BIB003 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Despite a dramatic growth of power consumption in households, less attention has been paid to monitoring, analyzing and predicting energy usage. In this paper, we propose a framework to mine raw energy data by transforming time series energy data into a symbol sequence, and then extend a suffix tree data structure as an efficient representation to analyze global structural patterns. Then, we use a clustering algorithm to detect energy pattern outliers which are far from their cluster centroids. To validate our approach, we use real power data collected from a smart apartment testbed during two months. <s> BIB004 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Society is becoming increasingly aware of the impact that our lifestyle choices make on energy usage and the environment. As a result, research attention is being directed toward green technology, environmentally-friendly building designs, and smart grids. This paper looks at the user side of sustainability. In particular, it looks at energy consumption in everyday home environments to examine the relationship between behavioral patterns and energy consumption. It first demonstrates how data mining techniques may be used to find patterns and anomalies in smart home-based energy data. Next, it describes a method to correlate home-based activities with electricity usage. Finally, it describes how this information could inform users about their personal energy consumption and to support activities in a more energy-efficient manner. These approaches are validated by using real energy data collected in a set of smart home testbeds. <s> BIB005 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Periodic pattern detection in time-ordered sequences is an important data mining task, which discovers in the time series all patterns that exhibit temporal regularities. Periodic pattern mining has a large number of applications in real life; it helps understanding the regular trend of the data along time, and enables the forecast and prediction of future events. An interesting related and vital problem that has not received enough attention is to discover outlier periodic patterns in a time series. Outlier patterns are defined as those which are different from the rest of the patterns; outliers are not noise. While noise does not belong to the data and it is mostly eliminated by preprocessing, outliers are actual instances in the data but have exceptional characteristics compared with the majority of the other instances. Outliers are unusual patterns that rarely occur, and, thus, have lesser support (frequency of appearance) in the data. Outlier patterns may hint toward discrepancy in the data such as fraudulent transactions, network intrusion, change in customer behavior, recession in the economy, epidemic and disease biomarkers, severe weather conditions like tornados, etc. We argue that detecting the periodicity of outlier patterns might be more important in many sequences than the periodicity of regular, more frequent patterns. In this paper, we present a robust and time efficient suffix tree-based algorithm capable of detecting the periodicity of outlier patterns in a time series by giving more significance to less frequent yet periodic patterns. Several experiments have been conducted using both real and synthetic data; all aspects of the proposed approach are compared with the existing algorithm InfoMiner; the reported results demonstrate the effectiveness and applicability of the proposed approach. <s> BIB006 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Because of user movements and activities, heartbeats recorded from wearable devices typically feature a large degree of variability in their morphology. Learning problems, which in ECG monitoring often involve learning a user-specific model to describe the heartbeat morphology, become more challenging. <s> BIB007 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> Abstract In the area of time series representation, the Piecewise Aggregate Approximation (PAA) method has established itself quite visibly resulting in a number of useful results. However, the PAA technique usually leads to some losses of information. In order to overcome this issue, we propose a representation approach called Piecewise Aggregate Pattern Representations (PAPR). In the PAPR method, the range of values assumed in the temporal segment is divided into several regions with equal probability. In the sequel, some statistics of the regions, such as the number, the mean and the variance of points falling within each region, are determined. A matrix (pattern) containing all these statistical characteristics is constructed to represent the corresponding segment of the time series. We incorporate the PAPR method into anomaly detection by computing the similarity of patterns and using a Random Walk (RW) model, as a classifier, to determine the similarity values. Finally, the connectivity and anomaly ranks of patterns are obtained with the use of the RW model. The overall anomaly detection approach is referred to as PAPR-RW. Experimental studies are reported for synthetic data sets and two publicly available data sets: electrocardiograms (ECGs) data and the video surveillance data. Compared with the PAA-based method, the PAPR-RW approach exhibits a higher level of robustness and detects anomalies more accurately. <s> BIB008 </s> A review on outlier/anomaly detection in time series data <s> SUBSEQUENCE OUTLIERS <s> The problem of anomaly detection in time series has received a lot of attention in the past two decades. However, existing techniques cannot locate where the anomalies are within anomalous time series, or they require users to provide the length of potential anomalies. To address these limitations, we propose a self-learning online anomaly detection algorithm that automatically identifies anomalous time series, as well as the exact locations where the anomalies occur in the detected time series. In addition, for multivariate time series, it is difficult to detect anomalies due to the following challenges. First, anomalies may occur in only a subset of dimensions (variables). Second, the locations and lengths of anomalous subsequences may be different in different dimensions. Third, some anomalies may look normal in each individual dimension but different with combinations of dimensions. To mitigate these problems, we introduce a multivariate anomaly detection algorithm which detects anomalies and identifies the dimensions and locations of the anomalous subsequences. We evaluate our approaches on several real-world datasets, including two CPU manufacturing data from Intel. We demonstrate that our approach can successfully detect the correct anomalies without requiring any prior knowledge about the data. <s> BIB009
As shown in Fig. 2 , subsequence outliers are the second type of outliers that can be detected in time series data. In this case, the aim is to identify a set of consecutive points that jointly behave unusually. To this end, subsequence outlier detection methods need to consider some key aspects, which are shown in Fig. 14, and which make the detection of subsequence outliers more challenging than point outlier detection. Methods based on fixed-length subsequences need the user to predefine the length, and they commonly obtain the subsequences using a sliding window over the time series. In contrast, methods that allow finding variable-length subsequences do not prespecify this length. A final aspect to consider regarding the length of the subsequence is that the number of subsequences that the method will consider and analyze depends on the chosen length, thus the number of subsequences will be higher when the length is shorter. The second characteristic that subsequence outlier detection methods need to consider is the representation of the data. Since the comparison between subsequences is more challenging and costly than the comparison between points, many techniques rely on a representation of the subsequences rather than using the original raw values. Discretization is a widely used representation method and can be obtained using approaches such as equal-frequency binning (e.g., BIB002 ), equal-width binning (e.g., BIB004 ; BIB005 ; BIB006 ), or SAX (e.g.,  ; BIB009 ). These discretization techniques can also be used as a starting point to obtain other representations, such as bitmaps (e.g., ; BIB003 ). A detailed overview of the existing research regarding outlier detection in discrete sequences can be found in  , which highlights the applicability of those techniques to time series data. Additionally, apart from discretization, raw data has also been used directly to obtain representations based on dictionaries (e.g., BIB007 ), exemplars (e.g., Jones et al. [2016] ), or connectivity values (e.g., BIB008 ). Another issue that has been barely considered in the literature but which makes the detection of subsequence outliers more challenging is that they can be periodic. Periodic subsequence outliers are unusual subsequences that repeat over time (e.g., BIB006 ; BIB001 ). Unlike point outliers where periodicity is not relevant, periodic subsequence outliers are important in areas such as fraud detection because it might be interesting to discover certain periodic anomalous transactions over time. Finally, as opposed to point outlier detection, where some methods did not take into account the temporal dependencies, subsequences consider the temporality by default. In addition, when analyzing subsequence outliers in a streaming context, three cases can occur: i) a single data point arrives, and an answer (i.e., outlier or non-outlier) must be given for a subsequence containing this new point; ii) a subsequence arrives, and it needs to be marked as an outlier or non-outlier; and iii) a batch of data arrives and subsequence outliers need to be found within it. In either case, the literature provides methods that can give an answer in a streaming fashion using sliding windows. However, most of them keep the model fixed and do not adapt to changes in the streaming sequence. We will focus on these incremental techniques because they are more suitable for processing streaming time series.