Research On Time Series Anomaly Subsequence Detection Algorithm

In real life,time series data can be seen in most fields,such as: ECG,EEG,factory sensor data,network traffic data and financial data.These data always contains some data that are inconsistent with most of the other data and cont ain important information.In data mining field,these inconsistent and small amounts of data are always called abnormal data.And these abnormal data can be further divided into abnormal points and abnormal sub-sequences.In this topic,we mainly focus on the detection of abnormal subsequences.The abnormal subsequence detection is to detect subsequences different from most other subsequences by the design algorithm.At present,the abnormal subsequence detection algorithm can directly target the original time series data,and can also be used for other representations of the original time series,such as: Symbolic Aggregate Approximation(SAX),Piecewise Aggregate Pattern Representation(PAA),Piecewise Aggregate Pattern Representation(PAPR)and so on.Since the time series is always high-dimensional data.The abnormal subsequence detection on the original data often requires a large running time.Although the detection algorithms on the reduction dimension data can improve the detection efficiency,the loss of trend information of time series may lead to low detection accuracy.This paper proposes two anomaly subsequence detection algorithms.These two algorithms can improve the efficiency and effectiveness without losing the time series trend information.By analyzing the characteristic of similar subsequence,most of data points are similar.Propose a time series representation based on time point sets.First,the numerical space of the time series is divided into several equal probability numerical intervals,then count the time points sets corresponding to the data points in each numerical interval,then the data structure,interval table(ITable)is used to represent the calculated set of time points.Similar subsequence in time series must have a similar interval table.An extended interval table(EITable)can be obtained by merging the interval table corresponding to each subsequence in the data set.Based on the EITable,it can be calculated whether a subsequence follows the distribution of most of non-self match subsequences in the data set.Then we can infer the anomaly of the subsequence.By analyzing the similarity calculation process of Dynamic Time Warping(DTW)algorithm and the method of the DTW algorithm to deal with the time drift problem.This paper proposes a time series anomaly subsequence detection algorithm based on dynamic local density estimation.In our approach,first randomly divide the subsequence into disjoint dynamic time segments;then adopts multiple random hash function quickly estimates the similar data points in the corresponding dynamic time segments.The number of data points with similar relationship is the local density of the data points.The local density of data points is used to judge whether data points are abnormal.Then,we can infer the anomaly degree of time series based on the local density of all data points in time series.In this paper,we design some experiments to verify the effectiveness of the proposed method based on some selected time series data.And we design some experiments to compared compare with the proposed two anomaly subsequence detection algorithms and some classic anomaly detection algorithms.A large of comparative experiments results show that the proposed methods are effective and efficient.