Research On Similarity Measurement Method Of Time Series Data Based On Dynamic Time Warping

Time series data was widely existed in all fields of life,and similarity measurement algorithms for time series are an important research contents of machine learning,which are widely used in biological sequence analysis,outlier detection and other fields.DTW is an important time series similarity measurement algorithm,which has good elasticity and robustness.But at the same time,DTW has some problems of such as high algorithm time complexity,pathological alignment,and so on.Existing research has many improved algorithms for DTW.Among them,The SPDTW algorithm considers limiting the range of the alignment path matrix to reduce the amount of calculation of the distance measurement process,and the LDTW algorithm solves the problem of the DTW algorithm timing alignment method treating the instance characteristics equally and ignoring its local discrimination characteristics by considering the categories between time series.But the above two improved algorithms of DTW have their own shortcomings.After theoretical analysis and experimental verification,this thesis proposes the SPLDTW algorithm.In the process of iteratively generating a weight matrix in the training set,the algorithm generates a sparse path matrix between sequences of the same type and a sparse path matrix between sequences of different types according to the type of sequences in the training set,and iterates the weights on the generated sparse path matrix matrix.Then,the generated weight matrix is used in the K-nearest neighbor classification process of the test set.The proposed algorithm is simulated and verified on the UCR data set,the experimental results show that the SP-LDTW and LDTW algorithm have the same classification accuracy,but the process time cost of SP-LDTW in generating the weight matrix is significantly lower than the LDTW algorithm.And proved the effectiveness of LDTW based on sparse path matrix in reducing time consumption.In order to further improve the efficiency of the SP-LDTW algorithm,in the process of training the weight matrix,the influence of different thresholds on the generation of sparse path matrix is explored.For the SP-LDTW algorithm which based on threshold,Firstly,a suitable threshold is learned through the cross-validation method in the training set.Secondly,the selected threshold is applied to the training of the weight matrix and the subsequent K nearest neighbor classification.Finally,simulation verification was performed on the UCR data set.The experimental results show that the threshold-based SP-LDTW algorithm in generating the weight matrix has a significantly lower process time than the SP-LDTW algorithm,while the accuracy of K-nearest neighbor classification of SP-LDTW algorithm on the upper threshold of some data sets is higher than that of SPLDTW algorithm.In this thesis,the improved DTW algorithm is studied and analyzed,and to improve the defects of the SPDTW algorithm and the LDTW algorithm,the SP-LDTW algorithm is proposed.After experimental verification,it is shows that the algorithm can significantly reduce the time overhead of generating the weight matrix which compared to LDTW algorithm.At the same time,the accuracy of K nearest neighbor classification is improved on some data sets.