Research On Similarity Measurement Of Time Series Based On DTW Algorithm

Dynamic Time Warping(DTW)is a commonly used algorithm for similarity measure in the time series.It overcomes the defect of "point-to-point" matching of Euclidean distance by means of "one-to-many" matching method,and can measure time series of different lengths and obtain higher matching accuracy.DTW is robust to time series migration and amplitude variation,so it has been widely used in different fields.However,DTW algorithm has high complexity and requires a large amount of computation time,which limits its application in large-scale data.In addition,DTW ignores the local shape of the time series,which may lead to unreasonable matching and reduce the accuracy of time series with complex changes.To solve the above problems,this thesis improves the dynamic time warping algorithm form different perspectives,and the work is as follows:(1)In order to solve the problem of large computation and high complexity of the traditional DTW algorithm without reducing classification accuracy,Extreme Weighting Dynamic Time Warping(EWDTW)based on local extrema points of time series was proposed.In the algorithm,local extremal approximations was used to represent the original time series in order to reduce the dimensionality,and then adaptive cost weights were set for each point based on the position,value and type during the DTW process,which effectively improved the pathological alignment of the sequences and reduced the computational complexity.The experiments results on some UCR dataset show that the EWDTW algorithm improves the computing efficiency,and the classification accuracy is higher than several traditional DTW algorithms,also it has good measurement performance for different types of time series,especially for long time series.(2)LEDTW is a derived algorithm of DTW which can effectively improve the computational efficiency.In order to maintain LEDTW’s high computation efficiency and improve its low measurement accuracy in short and medium time series,an improved LEDTW algorithm based on local extreme point characteristics(FLEDTW)was proposed.The algorithm labeled the local extreme points of the original time series,segmented the time series according to the location of the local extreme points,and then carried out linear fitting for the adjacent points.Then,the size of the extreme point,the slope of the left fitting line segment,the slope of the right fitting line segment and the position of the extreme point are selected as the four-dimensional features of the point.The four-dimensional features of all local extreme points are extracted to form an extreme feature matrix.The similar distances of the maximum and minimum matrices are measured separately,and their sum is defined as the measured distance of FLEDTW.The algorithm does not need any parameters.In the process of calculating the optimal dynamic bending path,the four-dimensional feature can effectively improve the low measurement accuracy of the sequence due to excessive stretching or compression.The algorithm maintains LEDTW’s high computation efficiency.The experiments results on the short,medium and long time series of UCR data sets show that the algorithm effectively improves the classification accuracy of LEDTW,and the computational complexity on medium and long time series is the same as that of LEDTW.(3)In order to improve the measurement effect of DTW algorithm on complex time series,a dynamic time warping algorithm based on time series decomposition(SFDTW)was proposed.In the algorithm,time series was decomposed into filter signal,slope signal and wave signal.The filter signal reflects the overall trend of time series,the slope signal reflects the change of slope of time series,and the fluctuation signal reflects the change of local details of time series.In the similarity measurement process,the weight parameters of decomposed signals were adjusted according to the actual demand and the characteristics of time series to get a better similarity measurement effect.By adjusting the length of filter window and the weight of wave signal,the algorithm can effectively reduce or eliminate noise pollution and has strong robustness.Experimental results show that the algorithm can effectively improve the alignment effect and classification accuracy,and is suitable for different types of time series data.