陳為滿 馬佩勛

（長沙民政職業(yè)技術(shù)學(xué)院,湖南長沙 410004）

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

陳為滿 馬佩勛

（長沙民政職業(yè)技術(shù)學(xué)院,湖南長沙 410004）

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

時間序列；相似性度量；數(shù)據(jù)流；子序列匹配

1.引言

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

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

2.1 時間序列

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

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

2.2 相似性度量

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

表1：各度量函數(shù)的對比

2.3 改進(jìn)的ERP算法思路

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

給定序列 Q=＜q1,q2,…,qm＞和 S=＜s1,s2,…,sn＞,S［ts,te］表示匹配的子序列，ts、te分別表示起點(diǎn)和終點(diǎn)，用sp（t,i）表示匹配序列的起點(diǎn)位置，存儲在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）的起點(diǎn)位置ts=sp（te,m）。

3.實(shí)驗(yàn)

表2：子序列匹配

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

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

圖1：維數(shù)對性能的影響

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

4.結(jié)束語

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

［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］ 翁穎鈞,朱仲英.基于動態(tài)時間彎曲的時序數(shù)據(jù)聚類算法的研究［J］.計(jì)算機(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］ 安鎮(zhèn)宙,楊鑒.一種新的基于并行分段裁剪的DTW算法［J］.計(jì)算機(jī)工程與應(yīng)用，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－），男，湖南婁底人，長沙民政職業(yè)技術(shù)學(xué)院軟件學(xué)院助教，理學(xué)碩士。研究方向：軟件開發(fā)、項(xiàng)目管理和數(shù)據(jù)挖掘；馬佩勛（1978－），男，湖南湘潭人，長沙民政職業(yè)技術(shù)學(xué)院軟件學(xué)院講師、工學(xué)碩士。研究方向：軟件開發(fā)與項(xiàng)目管理、企業(yè)應(yīng)用集成。