Research Of Similarity Search Based On Dynamic Time Warping In Time Series Data Mining

Time series similarity search is the core subroutines of time series data miningalgorithms, and thus the time taken for similarity search has become the bottleneckof restricting the time series mining algorithm. Time series representation methodsand similarity measures are research foundations and have a crucial role to theprocess of similarity search.Dynamic time warping as a method of similarity measure can be effective lyhandle on the time series along the time axis deformation, has good robustness.However, as time series data with massive and high dimensional characteristics,directly dealing with such data in its raw format is expensive in terms of processingand storage cost and may affect the accuracy and reliability of the algorithm. Thus,it is worthy to preprocessing time series in the form of concise and abstract, whilestill preserving the fundamental characteristics of a particular data set.Based on the latest research, this article starting from the time similarity search,studied the time series piecewise linear representation and dynamic time warping,mainly to complete follows:(1) Analysis the status of time series similarity search, representation methodsand similarity measures, further study of the method of time series piecewise linearrepresentation and dynamic time warping distance method.(2) Propose and define the turning point and priority queues. On this basia, putforward a representation method named “Piecewise Linear Representation based onSlope extract Turning Point”. The method can compress time series sequence andmaintain the main character of the origina l sequcnce by selecting turning point asthe priority queue sequence candidate points. Experiments show that the methodachieved good fitting effects and stability in many fields.(3) Analysis the dynamic time warping distance as the similarity measure, thenproposed “search algorithm based on Cascade Lower Bounds of Dynamic TimeWarping”. This method combines multiple lower bound functions and improves thecalculation of the LB_Keogh lower bound function, to achieve earlier terminateeffect. Experimental results show that the method improves the performance ofdynamic time warping in a certain extent.(4) The method “Time Series Similarity search algorithm based on DynamicTime Warping” is proposed based on “Piecewise Linear Representation based onSlope extract Turning Point” and “search algorithm based on Cascade LowerBounds of Dynamic Time Warping”. Similarity searc has a significantlyimprovement of efficiency, when the compression ratio and constraint window being suitable selected.