發(fā)布時間：2017-07-15 23:18

  本文關鍵詞：基于DTW距離的時間序列相似性查詢和shapelets分類算法研究

  更多相關文章： 時間序列 相似性查詢 分類 動態(tài)時間彎曲距離 滑動窗口分段表示 高效子序列匹配

【摘要】：隨著時間序列挖掘相關技術的不斷發(fā)展,如何權衡算法效率與準確性成為研究人員關注的焦點。由于時間序列的高維性和復雜性特點,通常難以既高效又準確地對時間序列進行分析和處理。因此在不丟失關鍵信息的前提下,對時間序列進行適當?shù)慕稻S處理,降低算法中對數(shù)據(jù)維度依賴性極大的運算復雜度,以獲得高效與準確兩者的平衡有一定的理論意義和應用價值。本文分析了時間序列挖掘算法的特點,重點對相似性查詢和分類的關鍵技術進行了研究,分析比對了經(jīng)典算法以及其存在的問題,提出基于滑動窗口分段的下界距離算法和基于高效子序列匹配的shapelets轉化分類算法,從理論和實際數(shù)據(jù)兩方面證明了改進算法的可行性和有效性。主要工作如下:(1)時間序列基礎算法分析。針對時間序列挖掘中的表示方法和距離度量方法進行了總結與分析,列舉相應的經(jīng)典算法進行詳細說明,并對其進行比較。介紹并分析了時間序列相似性查詢與分類的研究目的、算法原理、實際應用等相關內容。(2)提出基于滑動窗口分段的下界距離算法。下界距離算法在提高時間序列相似性查詢效率、減少冗余計算等方面起非常重要的作用,現(xiàn)有的基于點對累積近似表示法的下界算法,相似度計算的時間代價較小,但當時間序列振幅波動較大時,往往不能緊致地擬合時間序列。針對這一問題,在下界算法中引入滑動窗口分段表示法,提出一種基于滑動窗口分段的動態(tài)時間彎曲下界算法,構建擬合度更高的上下邊界曲線,對時間序列進行過濾,篩除相似性較差的時間序列。該算法能夠有效地簡化時間序列相似度的計算過程,降低運算復雜度,提高相似性查詢效率,且當時間序列的振幅波動較大時,取得較高計算精度與效率。(3)提出基于高效子序列匹配的shapelets轉化分類算法。由于大量復雜的距離計算,使得整個分類過程效率非常低,會耗費大量時間,現(xiàn)有的優(yōu)化算法都無法徹底解決這個問題。針對這一問題,在shapelets分類算法中引入點對累積近似表示法和一種高效子序列匹配算法,提出一種基于高效子序列匹配的shapelets轉化分類算法,先用點對累積近似表示法對數(shù)據(jù)進行適當?shù)慕稻S處理,之后用子序列匹配算法簡化分類過程。高效子序列匹配算法可以與shapelets分類算法有效地結合,能夠在保證較高分類準確度的同時,較好的簡化算法計算過程,提高分類效率。
【關鍵詞】：時間序列 相似性查詢 分類 動態(tài)時間彎曲距離 滑動窗口分段表示 高效子序列匹配
【學位授予單位】：太原理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP311.13
【目錄】：

• 摘要3-5
• ABSTRACT5-10
• 第一章 緒論10-16
• 1.1 研究背景與意義10-11
• 1.2 時間序列研究現(xiàn)狀11-14
• 1.2.1 相似性查詢11-13
• 1.2.2 時間序列分類13-14
• 1.3 本文工作及章節(jié)安排14-16
• 第二章 時間序列與相關算法16-28
• 2.1 時間序列及相關定義16-18
• 2.2 時間序列表示方法18-20
• 2.2.1 非數(shù)據(jù)自適應方法19
• 2.2.2 數(shù)據(jù)自適應方法19-20
• 2.2.3 基于模型的方法20
• 2.3 時間序列相似性度量20-25
• 2.3.1 基于形狀的度量21-22
• 2.3.2 基于編輯的度量22-23
• 2.3.3 基于特征的度量23-24
• 2.3.4 基于模型的度量24-25
• 2.4 時間序列應用25-27
• 2.4.1 時間序列相似性查詢的應用25-26
• 2.4.2 時間序列分類的應用26-27
• 2.5 本章總結27-28
• 第三章 基于滑動窗口分段的動態(tài)時間彎曲下界算法28-40
• 3.1 動態(tài)時間彎曲距離算法28-30
• 3.2 時間序列距離計算中的下界過濾算法30-32
• 3.3 基于滑動窗口分段的動態(tài)時間彎曲下界算法32-35
• 3.3.1 PAA與SW時間序列表示法32-33
• 3.3.2 早棄策略33
• 3.3.3 基于LB_SW算法的相似性查詢33-35
• 3.4 實驗驗證與結果分析35-38
• 3.4.1 實驗平臺和數(shù)據(jù)35
• 3.4.2 實驗結果及分析35-38
• 3.5 本章總結38-40
• 第四章 基于高效子序列匹配的shapelets分類算法40-52
• 4.1 數(shù)據(jù)轉化與shapelets提取40-42
• 4.1.1 圖形轉化時間序列40-41
• 4.1.2 最優(yōu)shapelets的提取41-42
• 4.2 高效子序列匹配算法42-43
• 4.3 基于高效子序列匹配的shapelets分類算法43-46
• 4.4 實驗驗證與結果分析46-51
• 4.4.1 實驗平臺和數(shù)據(jù)46-47
• 4.4.2 實驗結果及分析47-51
• 4.5 本章總結51-52
• 第五章 總結與展望52-54
• 5.1 本文工作總結52-53
• 5.2 未來工作展望53-54
• 參考文獻54-58
• 致謝58-60
• 作者簡歷及攻讀碩士學位期間發(fā)表的學術論文60

【相似文獻】

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

1 劉芬;郭躬德;;基于符號化聚合近似的時間序列相似性復合度量方法[J];計算機應用;2013年01期

2 尹洪勝;劉秀榮;錢建生;華鋼;;時間序列相似性定義延拓[J];計算機工程與應用;2008年25期

3 王國仁;葛健;徐恒宇;鄭若石;;基于二分頻率變換的序列相似性查詢處理技術[J];軟件學報;2006年02期

4 蔣嶸;基于形態(tài)表示的時間序列相似性搜索[J];計算機研究與發(fā)展;2000年05期

5 吳紹春;吳耿鋒;王煒;蔚趙春;;尋找地震相關地區(qū)的時間序列相似性匹配算法[J];軟件學報;2006年02期

6 戴東波;熊峗;朱揚勇;;基于參考集索引的高效序列相似性查找算法[J];軟件學報;2010年04期

7 魏蓮;變換域時間序列相似性搜索[J];河北理工學院學報;2004年04期

8 朱天;白似雪;;基于模式距離度量的時間序列相似性搜索[J];微計算機信息;2007年30期

9 毛云建;杜秀華;;基于形態(tài)特征的時間序列相似性搜索算法[J];計算機仿真;2008年01期

10 劉培華;王立宏;;一種改進的事件序列相似性計算公式[J];計算機工程與應用;2009年07期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 卓明;王麗珍;譚旭;;基于時間序列相似性搜索的預測算法[A];第十九屆全國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2002年

2 邱均平;王菲菲;;時間序列相似性查詢與索引方法研究[A];2009年中國索引學會年會暨學術研討會論文集[C];2009年

3 李鳳敏;李前忠;張俊萍;;基于離散增量和協(xié)變判別式識別小鼠蛋白質亞細胞定位[A];第十一次中國生物物理學術大會暨第九屆全國會員代表大會摘要集[C];2009年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 李俊奎;時間序列相似性問題研究[D];華中科技大學;2008年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 左芳;十二株放線菌系統(tǒng)發(fā)育的研究[D];河北大學;2007年

2 孫宏偉;基于DTW距離的時間序列相似性查詢和shapelets分類算法研究[D];太原理工大學;2016年

3 涂俐蘭;基于快速沃爾什變換的生物序列相似性比對[D];華中科技大學;2004年

4 陳偉;生物信息學中的序列相似性比對算法[D];中國海洋大學;2006年

5 李明亮;時間序列相似性聚類算法研究[D];湖南大學;2010年

6 王克龍;離散小波變換分析蛋白質序列相似性[D];四川大學;2004年

7 劉芳;基于信息離散度的DNA序列相似性分析研究[D];湖南大學;2009年

8 孫達辰;基于DTW的時間序列相似性搜索的研究[D];大慶石油學院;2010年

9 杜洪波;時間序列相似性查詢及異常檢測算法的研究[D];沈陽工業(yè)大學;2008年

10 朱天;關于時間序列相似性及時序規(guī)則發(fā)現(xiàn)的研究[D];南昌大學;2007年

，

本文編號：546233