Thesis learning -- time series similarity query method based on extreme point characteristics

Write it at the front ：《 Computer application research 》;
author ： Wu Xueyan 、 Huang Daoping （ South China University of Technology ）

1 Abstract

1. The study is ： Time series subsequence matching problem
2. First Identify the extreme points in the sequence , Then according to the extreme point Use Multilevel extreme value division Divide the long sequence .
3. Then, we divide the obtained Multilevel subsequence set Use Improved dynamic time bending method Match the similarity with the query sequence .
4. Finally, find the subsequence that is most similar to the query sequence .

2 introduction

1. There are various complex deformations in time series （ Such as translation 、 Telescopic 、 Discontinuity, etc ）, And the deformation time and degree are unpredictable , European distance and its variants are widely used Very sensitive to the deformation of the timeline , Some slight changes will lead to great changes in European distance .

2. In time series data , Especially hydrological time series , The most noteworthy are often some feature points in the sequence .

3. This paper presents a method of extracting important extreme points , Segment the time series according to the important extreme points ; Then on this basis, an improved DTW Methods to measure the similarity .

3 Research status

3.1 Full sequence matching and subsequence matching

Time series similarity query is divided into Full sequence matching and Subsequence matching Two ways . In full sequence matching , The length of the query sequence is the same as that of the queried sequence ; In subsequence matching , Query sequence Q And query sequence P Given , The task is in sequence P Find and sequence in Q Matching subsequences .

3.2 Three subsequence matching segmentation

3.3 Selection of similarity measurement function

• Euclidean distance is very sensitive to changes in the time axis
• A lot of literature is in DTW On the basis of improvement , And most of the improvements are in use DTW Between algorithms , Add the pre screening and pruning process .
  

4 This paper mainly —— Multi level extreme value division method

4.1 Importance marking algorithm （EIIR）

• cyc It's a user-defined parameter , Represents the calculation neighborhood range of extreme value . If cyc=3, It means that the calculation is carried out within the range of three points before and after the sequence points .
• stay cyc Determine important extreme points within the range .

4.2 Extreme point judgment algorithm （JEP）

4.3 Multilevel segmented Acquisition Algorithm （MSR）