Motif Extraction Algorithm Of Time Series Based On DTW

Time series, a type of data of great importance, exists widely in such fields as finance, biology, and scientific experiments. In applications such as classification, pattern extraction and anomaly detection, the center of a set of time series (central time series) often requires calculation to present the common pattern. Besides, it is also necessary to find out the central time series in some clustering algorithms, the k-means algorithm, for example. Dynamic Time Warping (DTW) distance has great advantage over the Euclidean distance in measuring the time series. However, how to define central time series based on DTW remains a problem. Some references have attempted to define it and figure out its solutions. In this paper, we propose a novel definition of central time series, which can minimize the sum of the distances between the central time series and all other time series. In this thesis, a new way of defining the time series is proposed, whose virtue resides in minimizing the total distance from the central sequence to other sequences, and is therefore more representative. Then the solutions to the central sequence are discussed respectively under global restriction and local restriction. In view of the particularity of the local restriction, the discussion focuses on the solution under the local restriction and an efficient pruning algorithm is put forward. Finally, the rationality and superiority of the definition and the efficiency of the pruning algorithm under the local restriction are verified by a series of experiments on standard dataset.