本文關(guān)鍵詞：基于動(dòng)態(tài)規(guī)劃和DTW匹配的時(shí)間序列索引方法研究

  更多相關(guān)文章： 時(shí)間序列索引 動(dòng)態(tài)時(shí)間規(guī)整 下界距離 中心時(shí)間序列

【摘要】：近些年,時(shí)間序列在包括金融、生物等領(lǐng)域得到廣泛應(yīng)用,越來(lái)越多的受到學(xué)者的關(guān)注和研究。在其眾多的研究領(lǐng)域中,時(shí)間序列的相似性查詢問(wèn)題得到了較為廣泛的研究,該問(wèn)題常常轉(zhuǎn)化為建立時(shí)間序列索引問(wèn)題。盡管動(dòng)態(tài)時(shí)間規(guī)整(DTW)是用于計(jì)算時(shí)間序列相似性的強(qiáng)有力工具,但是由于該算法不滿足三角不等式,且時(shí)間復(fù)雜度較高,因此很難直接用于建立時(shí)間序列索引。為了解決DTW算法存在的問(wèn)題,研究者引入了下界(low-bound)算法,并利用下界距離建立時(shí)間序列索引。下界距離嚴(yán)格小于等于DTW距離,其與DTW距離的接近程度(tightness)決定了索引的效果。本文對(duì)前人在時(shí)間序列索引問(wèn)題上的研究做了綜合性的回顧與評(píng)述,分析了現(xiàn)有算法的優(yōu)點(diǎn)和存在的問(wèn)題,并提出了一個(gè)全新的、基于動(dòng)態(tài)規(guī)劃的時(shí)間序列索引技術(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)的下界距離的方法,最后給出了相似性查詢的過(guò)程。同時(shí),為了更有效的建立索引,增加分段劃分的有效性,提高索引效果,本文還提出了一種新型的計(jì)算兩條時(shí)間序列中心的算法,并利用該算法為DBA算法求解初始解,從而優(yōu)化了DBA算法求解多條時(shí)間序列的中心序列的效果。實(shí)驗(yàn)部分證明了本文提出的中心序列算法能夠求解得到更有效的中心序列,在規(guī)整窗口較大時(shí),本文的索引算法有著更接近DTW距離的下界距離,能夠更有效的排除距離較大的序列,其索引效果要好于現(xiàn)有的索引算法。
【關(guān)鍵詞】：時(shí)間序列索引 動(dòng)態(tài)時(shí)間規(guī)整 下界距離 中心時(shí)間序列
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O211.61
【目錄】：

• 摘要4-5
• Abstract5-8
• 1 緒論8-11
• 1.1 時(shí)間序列概述8-9
• 1.2 時(shí)間序列索引概述9-10
• 1.3 本文工作10
• 1.4 本文結(jié)構(gòu)10-11
• 2 相關(guān)工作概述11-26
• 2.1 相似度衡量算法11-15
• 2.1.1 歐氏距離11-12
• 2.1.2 DTW距離12-15
• 2.2 下界距離算法15-21
• 2.2.1 LB_Yi下界距離15-16
• 2.2.2 LB_Kim下界距離16-17
• 2.2.3 LB_Keogh下界距離17-18
• 2.2.4 LB_NKim下界距離18-20
• 2.2.5 LB_NKeogh下界距離20-21
• 2.3 索引算法21-24
• 2.3.1 PAA降維介紹22-23
• 2.3.2 Keogh索引23-24
• 2.4 中心時(shí)間序列算法24-26
• 3 求解中心序列26-36
• 3.1 匹配度理論和剪枝定理26-27
• 3.2 兩條時(shí)間序列的中心序列算法27-30
• 3.3 多條時(shí)間序列的中心序列算法30-32
• 3.4 實(shí)驗(yàn)驗(yàn)證32-36
• 3.4.1 兩條時(shí)間序列的中心序列實(shí)驗(yàn)32-34
• 3.4.2 多條時(shí)間序列的中心序列實(shí)驗(yàn)34-36
• 4 索引技術(shù)36-45
• 4.1 降維36-38
• 4.2 上下界序列集38
• 4.3 上下界序列集的有效組合集38-41
• 4.4 建立索引樹(shù)41-45
• 5 查詢45-48
• 5.1 索引結(jié)構(gòu)的下界距離45-46
• 5.2 查詢過(guò)程46-48
• 6 實(shí)驗(yàn)48-57
• 6.1 數(shù)據(jù)集預(yù)處理48-49
• 6.2 下界距離與松緊程度49-52
• 6.3 排除序列能力52-53
• 6.4 時(shí)間消耗53-55
• 6.5 參數(shù)討論55-56
• 6.6 本章小結(jié)56-57
• 結(jié)論57-58
• 參考文獻(xiàn)58-61
• 攻讀碩士學(xué)位期間發(fā)表學(xué)術(shù)論文情況61-62
• 致謝62-63

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 李海林;郭崇慧;;時(shí)間序列數(shù)據(jù)挖掘中特征表示與相似性度量研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2013年05期

，

本文編號(hào)：707265