基于動態(tài)規(guī)劃和dtw匹與的時間序列索引方法研究

1、碩士學位論文基于動態(tài)規(guī)劃和DTW匹配的時間序列索引方法研究AResearchontheIndexingMethodofTimeSeriesBasedonDynamicPlanningandDTWWarpingPath學號：21224021完成日期：20150501大連理工大學DalianUniversityofTechnology萬方數(shù)據(jù)大連理工大學碩士學位論文摘要近些年，時間序列在包括金融、生物等領域得到廣泛應用，越來越多的受到學者的

2、關注和研究。在其眾多的研究領域中，時間序列的相似性查詢問題得到了較為廣泛的研究，該問題常常轉(zhuǎn)化為建立時間序列索引問題。盡管動態(tài)時間規(guī)整(DTW)是用于計算時間序列相似性的強有力工具，但是由于該算法不滿足三角不等式，且時間復雜度較高，因此很難直接用于建立時間序列索引。為了解決DTW算法存在的問題，研究者引入了下界(10w—bound)算法，并利用下界距離建立時間序列索引。下界距離嚴格小于等于DTW距離，其與DTW距離的接近程度(tight

3、ness)決定了索引的效果。本文對前人在時間序列索引問題上的研究做了綜合性的回顧與評述，分析了現(xiàn)有算法的優(yōu)點和存在的問題，并提出了一個全新的、基于動態(tài)規(guī)劃的時間序列索引技術，建立了一種新型的索引樹。算法利用DTW匹配關系對序列產(chǎn)生劃分，提出了一種分段的索引結(jié)構，并給出了建立索引結(jié)構的算法。并根據(jù)索引結(jié)構的特點，給出了利用動態(tài)規(guī)劃求解待查序列與索引結(jié)構的下界距離的方法，最后給出了相似性查詢的過程。同時，為了更有效的建立索引，增加分段劃分的