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

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

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

• 摘要4-5
• Abstract5-8
• 1 緒論8-11
• 1.1 時間序列概述8-9
• 1.2 時間序列索引概述9-10
• 1.3 本文工作10
• 1.4 本文結構10-11
• 2 相關工作概述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 中心時間序列算法24-26
• 3 求解中心序列26-36
• 3.1 匹配度理論和剪枝定理26-27
• 3.2 兩條時間序列的中心序列算法27-30
• 3.3 多條時間序列的中心序列算法30-32
• 3.4 實驗驗證32-36
• 3.4.1 兩條時間序列的中心序列實驗32-34
• 3.4.2 多條時間序列的中心序列實驗34-36
• 4 索引技術36-45
• 4.1 降維36-38
• 4.2 上下界序列集38
• 4.3 上下界序列集的有效組合集38-41
• 4.4 建立索引樹41-45
• 5 查詢45-48
• 5.1 索引結構的下界距離45-46
• 5.2 查詢過程46-48
• 6 實驗48-57
• 6.1 數(shù)據(jù)集預處理48-49
• 6.2 下界距離與松緊程度49-52
• 6.3 排除序列能力52-53
• 6.4 時間消耗53-55
• 6.5 參數(shù)討論55-56
• 6.6 本章小結56-57
• 結論57-58
• 參考文獻58-61
• 攻讀碩士學位期間發(fā)表學術論文情況61-62
• 致謝62-63

【參考文獻】

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

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

，

本文編號：707265