基于動(dòng)態(tài)規(guī)劃和DTW匹與的時(shí)間序列索引方法研究.pdf

1、近些年，時(shí)間序列在包括金融、生物等領(lǐng)域得到廣泛應(yīng)用，越來越多的受到學(xué)者的關(guān)注和研究。在其眾多的研究領(lǐng)域中，時(shí)間序列的相似性查詢問題得到了較為廣泛的研究，該問題常常轉(zhuǎn)化為建立時(shí)間序列索引問題。盡管動(dòng)態(tài)時(shí)間規(guī)整(DTW)是用于計(jì)算時(shí)間序列相似性的強(qiáng)有力工具，但是由于該算法不滿足三角不等式，且時(shí)間復(fù)雜度較高，因此很難直接用于建立時(shí)間序列索引。為了解決DTW算法存在的問題，研究者引入了下界(low-bound)算法，并利用下界距離建立時(shí)間序列索

2、引。下界距離嚴(yán)格小于等于DTW距離，其與DTW距離的接近程度（tightness）決定了索引的效果。
　　本文對(duì)前人在時(shí)間序列索引問題上的研究做了綜合性的回顧與評(píng)述，分析了現(xiàn)有算法的優(yōu)點(diǎn)和存在的問題，并提出了一個(gè)全新的、基于動(dòng)態(tài)規(guī)劃的時(shí)間序列索引技術(shù)，建立了一種新型的索引樹。算法利用DTW匹配關(guān)系對(duì)序列產(chǎn)生劃分，提出了一種分段的索引結(jié)構(gòu)，并給出了建立索引結(jié)構(gòu)的算法。并根據(jù)索引結(jié)構(gòu)的特點(diǎn)，給出了利用動(dòng)態(tài)規(guī)劃求解待查序列與索引結(jié)構(gòu)的下

3、界距離的方法，最后給出了相似性查詢的過程。同時(shí)，為了更有效的建立索引，增加分段劃分的有效性，提高索引效果，本文還提出了一種新型的計(jì)算兩條時(shí)間序列中心的算法，并利用該算法為DBA算法求解初始解，從而優(yōu)化了DBA算法求解多條時(shí)間序列的中心序列的效果。實(shí)驗(yàn)部分證明了本文提出的中心序列算法能夠求解得到更有效的中心序列，在規(guī)整窗口較大時(shí)，本文的索引算法有著更接近DTW距離的下界距離，能夠更有效的排除距離較大的序列，其索引效果要好于現(xiàn)有的索引算法。