Font Size: a A A

The Research Of Similarity Search Based On Dynamic Time Warping In Time Series

Posted on:2018-05-30Degree:MasterType:Thesis
Country:ChinaCandidate:P L LiFull Text:PDF
GTID:2348330569486223Subject:Information and Communication Engineering
Abstract/Summary:PDF Full Text Request
Time series similarity search is a critical task of time series data mining,and time series representation method and similarity measure method are critical contents of time series similarity search.Time series representation method determines the selection of similarity pattern measurement method,and the similarity pattern measurement directly affects the time series search method.Dynamic time warping can effectively deal with the time series along the time axis of the deformation and other issues,with good robustness.However,time series data are often produced continuously,and the search for similarity directly takes up a lot of storage space.Therefore,it is necessary to preprocess the time series data before the similarity search,and the shape feature of the original time series is expressed in the form of concise and abstract by time series representation.In this way,the search work can be carried out effectively.After analyzing the latest research on time series data mining both at home and abroad,this thesis focuses on the method of time series segmentation linear representation and the similarity search method based on dynamic time warping similarity measure.These works have been done as follows:1.In this thesis,the definition of important data points,and an error-bound piecewise linear representation method based on important data points are proposed,which solved the problem of high computational complexity and large local fitting error.In this method,the important data points of the time series are taken as the segmentation points,and all kinds of fitting errors after segmenting are especially considered.In particular,the single point fitting error is too large,and the main feature of sequence can be extracted at the same time.The experiment results show that the method can effectively reduce the fitting error effect of the post segment sequence while effectively reducing the time series dimension.2.The lower bound function based on dynamic time warping is analyzed,in order to solve the problem of lower bound tightness and pruning power,the first two kinds of lower bound functions are extended,and two better lower bound functions are proposed.Then,under the global constraint,the two extended lower bound functions are cascaded to obtain a cascade lower bound function.Finally,the similarity search is proposed by combining the proposed piecewise linear representation method with the cascade lower bound function.Experiments show that the similarity search can improve the efficiency of similarity search effectively by using the lower bound function.
Keywords/Search Tags:time series, similarity search, dynamic time warping, lower bound function, piecewise linear representation
PDF Full Text Request
Related items