Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> An intrusion detection system (IDS) seeks to identify unauthorized access to computer systems' resources and data. The most common analysis tool that these modern systems apply is the operating system audit trail that provides a fingerprint of system events over time. In this research, the Basic Security Module auditing tool of Sun's Solaris operating environment was used in both an anomaly and misuse detection approach. The anomaly detector consisted of the statistical likelihood analysis of system calls, while the misuse detector was built with a neural network trained on groupings of system calls. This research demonstrates the potential benefits of combining both aspects of detection in future IDSs to decrease false positive and false negative errors. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> Profiling the behavior of programs can be a useful reference for detecting potential intrusions against systems. This paper presents three anomaly detection techniques for profiling program behavior that evolve from memorization to generalization. The goal of monitoring program behavior is to be able to detect potential intrusions by noting irregularities in program behavior. The techniques start from a simple equality matching algorithm for determining anomalous behavior, and evolve to a feed-forward backpropagation neural network for learning program behavior, and finally to an Elman network for recognizing recurrent features in program execution traces. In order to detect future attacks against systems, intrusion detection systems must be able to generalize from past observed behavior. The goal of this research is to employ machine learning techniques that can generalize from past observed behavior to the problem of intrusion detection. The performance of these systems is compared by testing them with data provided by the DARPA Intrusion Detection Evaluation program. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> While dealing with sensitive personnel data, the data have to be maintained to preserve integrity and usefulness. The mechanisms of the natural immune system are very promising in this area, it being an efficient anomaly or change detection system. This paper reports anomaly detection results with single and multidimensional data sets using the negative selection algorithm developed by Forrest et al. (1994). <s> BIB003 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> This paper describes a real-valued representation for the negative selection algorithm and its applications to anomaly detection. In many anomaly detection applications, only positive (normal) samples are available for training purpose. However, conventional classification algorithms need samples for all classes (e.g. normal and abnormal) during the training phase. This approach uses only normal samples to generate abnormal samples, which are used as input to a classification algorithm. This hybrid approach is compared against an anomaly detection technique that uses self-organizing maps to cluster the normal data sets (samples). Experiments are performed with different data sets and some results are reported. <s> BIB004 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> In this work, we introduce the new problem of finding time series discords. Time series discords are subsequences of a longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the most unusual subsequence within a time series. Time series discords have many uses for data mining, including improving the quality of clustering, data cleaning, summarization, and anomaly detection. Discords are particularly attractive as anomaly detectors because they only require one intuitive parameter (the length of the subsequence) unlike most anomaly detection algorithms that typically require many parameters. We evaluate our work with a comprehensive set of experiments. In particular, we demonstrate the utility of discords with objective experiments on domains as diverse as Space Shuttle telemetry monitoring, medicine, surveillance, and industry, and we demonstrate the effectiveness of our discord discovery algorithm with more than one million experiments, on 82 different datasets from diverse domains. <s> BIB005 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> In this work we introduce the new problem of finding time seriesdiscords. Time series discords are subsequences of longer time series that are maximally different to all the rest of the time series subsequences. They thus capture the sense of the most unusual subsequence within a time series. While discords have many uses for data mining, they are particularly attractive as anomaly detectors because they only require one intuitive parameter (the length of the subsequence) unlike most anomaly detection algorithms that typically require many parameters. While the brute force algorithm to discover time series discords is quadratic in the length of the time series, we show a simple algorithm that is three to four orders of magnitude faster than brute force, while guaranteed to produce identical results. We evaluate our work with a comprehensive set of experiments on diverse data sources including electrocardiograms, space telemetry, respiration physiology, anthropological and video datasets. <s> BIB006 </s> Time Series Data Cleaning: A Survey <s> B. ABNORMAL SEQUENCE DETECTION <s> Over the past three decades, there has been a great deal of research on shape analysis, focusing mostly on shape indexing, clustering, and classification. In this work, we introduce the new problem of finding shape discords, the most unusual shapes in a collection. We motivate the problem by considering the utility of shape discords in diverse domains including zoology, anthropology, and medicine. While the brute force search algorithm has quadratic time complexity, we avoid this by using locality-sensitive hashing to estimate similarity between shapes which enables us to reorder the search more efficiently. An extensive experimental evaluation demonstrates that our approach can speed up computation by three to four orders of magnitude. <s> BIB007
Different studies have different definitions of subsequence anomalies. Keogh et al. BIB006 proposed that a subsequence anomaly, that is, a subsequence has the largest distance from its nearest non-overlapping match. With this definition, the simplest calculation method is to calculate the distance between each subsequence with length n and other subsequences. Of course, the time complexity of this calculation method is very high. In the later studies, Keogh et al. BIB005 propose a heuristic algorithm by reordering candidate subsequences and Wei et al. BIB007 argue an acceleration algorithm using local sensitive hash values. In calculating the distance, the Euclidean distance is usually used, and Keogh et al.  further proposes a method using the compression-based similarity measure as the distance function. As shown in Figure 6 , the data is divided into multiple sub-sequences that overlap each other. First, calculate the abnormal score of each window, and then calculate the abnormal score (AS) of the whole test sequence according to the abnormal score (AS) of each window. Window-based techniques can better locate anomalies compared to direct output of the entire time series as outliers. There are two main types of methods based on this technique. One is to maintain a normal database BIB001 , BIB002 , and then compare the test sequence with the sequence in the normal database to determine whether it is abnormal; the other is to build an anomalous database BIB003 , BIB004 and then compare the test sequence with the sequence in the database to detect if it is anomalous.