The Method Of Similarity Measurement Based On Dynamic Time Waring In Time Series Data

Time series data exists in many fields of production and life,and it's data volume is increasing with the development of information technology.Mining and analyzing time series data to find out the potential knowledge rules is a research hotspot in data mining at present.In the mining and analysis of time series data,the similarity measurement process of two time series is indispensable.Dynamic time warping(DTW)is a common algorithm to measure the similarity of time series.However,due to the existence of the "pathological alignment",the measurement effect of DTW is limited.Dynamic Time Warping Algorithm under Limited Length of The Alignment Path(LDTW)proposed an improved idea to limit the alignment path length generated in the calculation process of DTW algorithm,which effectively suppressed the phenomenon of "pathological alignment".However,at the same time,the time complexity of cubic also brought more computation,and the time cost in the classification process is much higher than other improved algorithms.In order to reduce the amount of calculation of the LDTW algorithm,this thesis analyzed the relationship between the length of the time series data in the algorithm and the number of cumulative cost matrix elements and the parameter that limit the length of the path.Based on the method of limiting the length of alignment path,the control strategy of path length is changed from controlling the length within a certain range to fixing it to a specific value,and this method is called the Dynamic Time Warping Algorithm With Fixed Alignment Path Length(FDTW).This method effectively suppressed the "pathological alignment" phenomenon and maintained the classification accuracy rate similar to LDTW,while reducing the calculation amount of matrix elements and the time cost of classification.The FDTW algorithm reduces the calculation amount of the LDTW algorithm to a certain extent,but it still faces huge classification time cost when the time series data is large.In order to further reduce the calculation amount of the algorithm,this thesis introduces the time series segmented aggregation approximate representation method PAA based on the FDTW algorithm,and uses the PAA algorithm to appropriately reduce the dimension of the time series before measuring the time series to reduce the number of matrix elements,and this method is called the FDTW Algorithm Based on Piecewise Aggregation Approximation(PAA-FDTW).Through experimental research and analysis on the approximate window size of the segmented aggregation on the training dataset,the PAA-FDTW algorithm can achieve a significant reduction in time cost with a small decrease in classification accuracy.