[發明專利]一種基于DTW的時間序列相似性預測方法

在審

• 申請號: 201611167179.5
• 申請日: 2016-12-16
• 公開（公告）號: CN106777980A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 陶洋;李鵬亮;熊炫睿;沈敬紅
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京同恒源知識產權代理有限公司11275
• 代理人: 廖曦

技術領域

本發明屬于數據挖掘技術領域，特別是時間序列數據挖掘技術領域，涉及一種基于DTW的時間序列相似性預測方法。

背景技術

動態時間規整(Dynamic Time Warping，DTW)是時間序列的一個強大的相似性度量方法。雖然我們常見的歐氏距離計算簡單、容易理解，但它要求兩條時間序列的長度必須相等，且對時間軸伸縮和彎曲問題無能為力。DTW距離定義了序列之間的最佳對齊匹配關系，支持不同長度時間序列的相似性度量，支持時間軸的伸縮和彎曲。由于DTW距離比歐式距離有更好的魯棒性，因此被廣泛用于時間序列的相似性度量，這是很多時間序列數據挖掘問題的基礎，比如分類和聚類以及預測等。然而，DTW的時間和空間復雜度較高，導致基于DTW的數據挖掘效率很低。因此，如何降低DTW時空復雜度成為了當前的研究重點和難點。

DTW最早是用于語音識別中的一項技術，目前在金融、生物、化學以及機器人等領域都有廣泛的應用，特別是在多媒體數據領域。目前，對DTW進行加速的方法主要有以下兩種：1)添加全局約束。這種方法的目的是對DTW中的規整路徑進行全局約束，即限定一個序列中的點只能同另一序列中位置相近的某些點進行匹配。然而，該方法由于只針對查詢空間進行約束，并未從實質上降低DTW方法的復雜度，且在查詢時，由于查詢范圍的限制，存在誤報情況。2)利用下界距離進行過濾。該方法的主要思想是尋找一種計算更簡單的距離度量來粗略地估計DTW距離，稱為DTW下界距離，通過它可以過濾掉大部分不滿足相似性要求的序列，從而提高查詢效率。然而，該類方法，如果下界距離選取復雜度較高，則會降低整體查詢效率；如果下界距離選取比較簡單，又會降低過濾效果，增大候選集，產生誤報。

傳統的時間序列分析預測方法將時間序列數據匹配到某些數學模型中，然后再對其整體進行分析和預測。但這些數據模型往往對數據有必要的限制，而現實中許多數據不能滿足模型參數要求。基于時間序列相似性的類比合成方法是一種典型的非參數回歸方法，其非參數回歸特性使得它能夠很好的規避上述問題，所以該方法日漸成為時間序列預測領域的研究焦點，然而，傳統的類比合成方法在選取距離度量方法時，大多使用的是歐式距離，由于該方法不能處理時間序列的伸縮，平移等。所以，利用該方法得到的相似序列具有一定的局限性，其用于后期合成預報的參考模式數據質量不高，從而會影響后期預測的準確性。

因此，如何綜合考慮下界距離復雜度與下界距離過濾能力，從而實現時間序列快速而且準確的查詢，進而將其應用到類比合成預測方法中目前來說很少有人進行研究，但具有重要的研究意義。

發明內容

有鑒于此，本發明的目的在于提供一種基于DTW的時間序列相似性預測方法，該方法將目前已知的對DTW進行加速的方法，如LB_Kim、LB_Keogh、逆LB_Keogh和傳統的DTW方法等進行級聯，在不同階段利用不同方法對查詢集進行過濾。同時，為了提高查詢準確性，我們引入z-score標準化，在計算DTW距離之前對查詢序列進行標準化，在讀取數據的過程中，同步進行標準化，進一步提高算法效率。然后，將改進的DTW方法應用到時間序列的類比合成預測方法中，從而提高預測的速度與精度。

為達到上述目的，本發明提供如下技術方案：

一種基于DTW的時間序列相似性預測方法，該方法包括以下步驟：

S1：生成類比模式和參考模式：假設一個一維時間序列為T＝{x₁,x₂,…,x_m,…x_m+k}，先假定已有合適的模式長度k，則生成類比模式C＝{x₁,x₂,…,x_m}和參考模式Q＝{x_m+1,x_m+2,…,x_m+k}，其中類比模式為時間序列T中的歷史數據，參考模式為時間序列最近的發展趨勢；

S2：構造類比模式C的封帶，所述封帶指的是利用全局約束條件得到序列的上下邊界，其邊界所包含的部分；對C進行z-score標準化，z-score標準化是基于原始數據的均值(mean)和標準差(standard deviation)進行數據的標準化，定義如下：

其中，x為X中的數據點，μ為X的均值，σ為X的標準差；選擇z-score標準化的原因是利用z-score標準化方法得到的標準化時間序列的形狀與原始時間序列較為接近，因此其經常被用于時間序列數據挖掘任務中。