時間序列相似性度量的研究

陳為滿 馬佩勛

（長沙民政職業技術學院,湖南長沙 410004）

時間序列相似性度量的研究

陳為滿 馬佩勛

（長沙民政職業技術學院,湖南長沙 410004）

數據流上漸進、實時地進行子序列匹配成為一個極具價值和挑戰性的問題。文中對已有的主要度量函數Lp-norms、DTW、LCSS、EDR和ERP等進行了分析和對比，從理論上歸納出其特性，對ERP算法進行了改進，大量的模擬和真實數據實驗表明：改進的ERP算法在解決此類問題上具有高效性。

時間序列；相似性度量；數據流；子序列匹配

1.引言

隨著計算機和網絡技術的飛速發展，在與人們生活息息相關的各種領域中涌現出各類海量流數據，如每天股票市場的波動、氣象研究中的氣溫、移動對象跟蹤、某病人每個時刻心跳變化、從傳感器網絡獲取各種數據等，對這些數據進行分析，可揭示事物變化、發展規律，為科學決策提供依據。對這類數據進行分析時存在著一個基本的問題：從數據流中找出與指定查詢序列相似的序列，即子序列匹配（Subsequence Matching）。如何衡量兩序列匹配即相似成為其中的關鍵問題。時間序列的相似性度量是時間序列數據挖掘研究中的一個重要問題，能反映數據中基本的相似性，這一點為時間序列的相似性檢索、分類、預測等尤其可取。合理的相似性度量能提高數據挖掘的有效性和準確性。本文對已有的度量函數主要包括Lp-norms［1］、DTW［2,4,5,7］、最長公共字串（Longest Common Subsequence,LCSS）［3］、實序列編輯距離（Editdistance on real Sequence,EDR）和實補償編輯距離（Edit Distance with Real enalty,ERP）［6］等進行了分析和比較，改進ERP算法，并通過大量的時間序列驗證實驗，評估了其效率，最后給出比較實驗結果。

2.時間序列與相似性度量

2.1 時間序列

定義1：時間序列（Time series）。時間序列是指帶有時間標記的數據根據時間順序排列而得到的數據列值的集合，記時間序列 S=＜ （v1,t1）,（v2,t2）,…,（vn,tn）〉，其中si=（vi,ti）表示在ti時刻數據值為vi的序列元素，并且i＜j＜=＞ti＜tj，一般情況下序列元素的采樣時間相等，故 S簡記為S=＜s1,s2,…,sn＞。同時vi可以是多種類型，包括離散符號、結構數據、多媒體數據等等，本文只考慮實數值的情形。

定義2：時間序列相似（Time Series Similarity）。給定一個查詢序列Q=＜q1,q2,…,qn＞，一個數據序列S=＜s1,s2,…,sn＞，如果序列Q和序列S滿足dist（Q,S）≤ε，則說明時間序列Q和S是相似的。其中，ε是時序相似門限值，dist（Q,S）是一個距離函數。

2.2 相似性度量

時間序列相似性度量是高效時序相似搜索技術的基礎．建立何種度量函數來實現時序相似度量非常關鍵，這里不但要考慮各種度量函數的特性，還應該考慮具體應用領域的實際需求。研究主要集中在兩個方面：一方面是對距離函數的選擇，即定義時間序列間不同的相似性測度，以盡量符合實際應用問題；另一方面是研究提高檢索效率的不同機制，通過裁減或建立索引等提高查詢效率。已有的相似性度量函數包括：Lp-norms、DTW、LCSS、EDR和ERP等。典型的相似性測度多采用歐幾里德距離,但歐氏距離測度存在局限性,要求序列的長度相等，對數據在時間軸上的形變缺乏辨識能力和對噪聲的魯棒性，DTW支持平移，能實現高精度的非等長匹配，LCSS對異常和噪音有較強的適應能力，EDR和ERP都支持平移，且ERP利用三角不等式，綜合了Lp和DTWD優點，五個基本的度量函數特性對比如下表1。

表1：各度量函數的對比

2.3 改進的ERP算法思路

給定一個查詢序列Q=＜q1,q2,…,qn＞，一個數據序列 S=＜s1,s2,…,sn＞，則 ERP 為：

給定序列 Q=＜q1,q2,…,qm＞和 S=＜s1,s2,…,sn＞,S［ts,te］表示匹配的子序列，ts、te分別表示起點和終點，用sp（t,i）表示匹配序列的起點位置，存儲在cell（t,i）中，D（S［ts,te］,Q）表示子序列S［ts,te］與Q的ERP值，則D（S［ts,te］,Q）和 sp（t,i）：

于是D（S［ts,te］,Q）的起點位置ts=sp（te,m）。

3.實驗

表2：子序列匹配

本節給出相關的實驗結果及分析，實驗主要分為兩部分：有效性測試和效率測試。測試環境為Intel 1.66GHz,1GRAM,Windows XP 和 Visual C++6.0，測試數據集包括真實數據集和模擬數據集，其中模擬數據集符合隨機游走 （Random Walk）模型:pi=pi-1+xi,xi是［0,10］的隨機數。有效性測試中，我們使用［8］中的濕度數據集在查詢序列長度為300、ε門限值為30的情況下進行測試，表2顯示了各種度量函數的匹配結果。

效率測試中，采用［8］中的數據集和模擬數據集進行測試。維數對算法效率的影響實驗中，利用［8］中的溫度、濕度、光照強度和電壓數據集，圖1中顯示：隨著維數的增加，Lp-norms運行時間大幅度增加，而ERP耗時最少而且增幅不大，DTW、EDR和LCSS三種度量函數在維數增加的時候耗時和走勢差不多。查詢序列長度對算法效率的影響實驗中，采用［8］中的濕度數據集，隨序列長度增加，Lp-norms運行時間成線性增長，EDR和LCSS增長較之緩慢，DTW和改進的ERP耗時平穩，但改進的ERP只有DTW的一半。綜合效率測試實驗，改進的ERP在數據流的子序列匹配中隨維數和序列長度增加而效率平穩，這正和其度量函數設計的原理相吻合。

圖1：維數對性能的影響

圖2：查詢序列長度對性能的影響

4.結束語

本文研究了數據流上的子序列匹配問題，分析和對比了Lp-norms、DTW、LCSS、EDR和ERP等五個度量函數，并通過大量實驗得出各個度量函數的效率，從中得出改進的ERP度量函數在解決此類問題中有絕對的優勢。

［1］Lei Chen,Raymond Ng.On The Marriage of Lp-norms and Edit Distance［M］.VLDB,2004.792-800.

［2］ D.J.Berndt and J.Clifford.Using dynamic time warping to find patterns in time series［M］.KDD Workshop,1994.359－370.

［3］ Michail Vlachos,George Kollios,Dimitrios Gunopulos.Discovering Similar Multidimensional Trajectories［M］.ICDE,2002.

［4］ 翁穎鈞,朱仲英.基于動態時間彎曲的時序數據聚類算法的研究［J］.計算機仿真,2004,21（3）.

［5］ S.-C.Chen and R.L.Kashyap.A spatio temporal semantic model for multimedia presentations and multimedia database systems［J］.TKDE,2001,13（4）.

［6］ Lei Chen,M.Tamer O¨zsu,Vincent Oria.Robust and Fast imilarity Search for Moving Object Trajectories［M］.SIGMOD,2005.

［7］ 安鎮宙,楊鑒.一種新的基于并行分段裁剪的DTW算法［J］.計算機工程與應用，2007，43（15）:35-38.

［8］ Yasushi Sakurai,christos Faloutsos,Masashi Yamam.Stream Monitoring under Time Warping Distance［M］.ICDE,2007.

TP391

B

1671-5136（2011）02-0109-03

2011-04-18

陳為滿（1983－），男，湖南婁底人，長沙民政職業技術學院軟件學院助教，理學碩士。研究方向：軟件開發、項目管理和數據挖掘；馬佩勛（1978－），男，湖南湘潭人，長沙民政職業技術學院軟件學院講師、工學碩士。研究方向：軟件開發與項目管理、企業應用集成。