基于極值點特征的時間序列相似性查詢方法

摘 要:為了提高時間序列子序列匹配的準確度和效率，提出了基于極值點特征的時間序列相似性查詢方法。首先識別出時間序列中的極值特征點，根據極值點使用多層次極值劃分法對長序列進行劃分;然后對劃分得到的多層次子序列集使用改進的動態時間彎曲方法與查詢序列進行相似性匹配;最后找到與查詢序列最相似的子序列。實驗表明，此方法在保證準確度的情況下大大提高了相似性搜索過程的效率。

關鍵詞:時間序列; 相似性查詢; 數據挖掘

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2010)06-2068-03

doi:10.3969/j.issn.1001-3695.2010.06.020

Time series similarity matching algorithm based on extreme points

WU Xue-yan1，2， HUANG Dao-ping1， MO Zan2

(1. College of Automation Science Engineering， South China University of Technology， Guangzhou 510640， China; 2.School of Management， Guangdong University of Technology， Guangzhou 510520， China)

Abstract:In order to improve the accuracy of time series subsequence similarity matching， this paper proposed time-series similarity matching algorithm based on the extreme points. First of all， the algorithm recognized the extreme points of the time series and used the multi-level extreme segmentation method to divide the long sequence. Then put forward an improved dynamic time warping method to do similarity matching between the multi-level subsequence set and the query sequence. At last found the most similar subsequence to the query sequence.Experiments reveal that this method greatly increases the efficiency of similarity matching with ensuring the accuracy.

Key words:time series; similarity matching; data mining

0 引言

時間序列是一類重要的時間數據對象，它能夠非常容易地從科學或金融應用過程中獲取(如心電圖、日氣溫、周銷售額、基金和股票的價格)。時間序列是按時間順序排列的一系列觀察值，其特征包括數據尺寸、高維度和不斷更新。

近年來時間序列數據的大量使用已經引發了在數據挖掘領域的各種研究。然而無論是分類、聚類還是關聯規則挖掘，都需要解決時間序列的相似度問題。相似性搜索是時間序列數據挖掘的研究基礎[1，2]。時間序列存在各種復雜變形(如平移、伸縮、間斷等)，且變形時間和變形程度均無法預料，而廣泛采用的歐氏距離及其改進對時間軸的變形非常敏感，一些輕微的改變就會導致歐氏距離發生很大變化[ 1～3]，因此，動態時間彎曲(dynamic time warping)技術已經越來越多地使用在時間序列的相似性度量研究中。雖然動態時間彎曲技術的穩定性已經得到廣泛驗證[4]，但是它的計算復雜性限制了其進一步應用。

在時間序列數據，尤其是金融時間序列中，最值得關注的往往是序列中的一些特征點。基于特征點的重要意義，本文提出一種提取重要極值點的方法，依據重要特征點對時間序列進行分段表示;然后在此基礎上使用一種改進的DTW方法進行相似性度量。通過實驗表明，本文提出的方法在保證計算準確度的同時大大提高了運算效率。

1 相關研究現狀

時間序列相似性查詢最早由Agrawal等人[5]在1993年提出，現已成為數據挖掘領域的一個熱點問題。時間序列相似性查詢分為全序列匹配和子序列匹配兩種方式。在全序列匹配中，查詢序列與被查詢序列的長度相同;在子序列匹配中，查詢序列Q和長序列P被給定，任務是在序列P中尋找與序列Q相匹配的子序列。

Yasushi等人[6]提出了基于動態時間彎曲的快速相似性搜索(FTW)算法，它是在動態時間彎曲(DTW)算法上的改進。FTW算法使用動態規劃方法對彎曲路徑進行篩選，在提高算法效率的基礎上增強了計算近似距離的準確度。Nguyen等人[7]提出了一種提高時間序列相似性匹配性能的新方法。他們首先使用符號聚集近似(SAX)方法將初始時間序列轉換為符號化的字符串，然后對字符串進行模式匹配，最后使用分段線性近似方法(PLA)進行處理。Michael等人[8]提出了一種快速時間序列評估(FTSE)的方法。FTSE是一個技術框架，通過設置不同的閾值可以應用于多種技術，并且可以提升時間序列相似性匹配的性能。文獻[9]中提出了一種有效的分級子序列匹配的方法。在這個方法中，查詢序列和被查詢序列都進行了分段，然后使用LB_Keogh作為下界對候選的匹配序列集進行篩減，從而提高了子序列匹配的效率。Lu等人[10]提出了基于位操作的快速時間序列相似度匹配(FSMBO)方法。FSMBO算法是對DTW算法在效率上的改進，通過對查詢序列和被查詢序列進行位變換和位操作，在使用DTW算法之前對候選匹配序列集進行剪枝，在保證準確度的前提下提高了時間序列相似性匹配的效率。Fu等人[11]提出了針對股票市場時間序列進行模式匹配的方法。該方法首先對時間序列提取感知重要點(PIP)，然后在感知重要點的基礎上提出了基于模板匹配的方法和基于規則匹配的方法。文獻[12]中提出了一種新穎的時間序列匹配算法(TWED)。TWED方法在時間序列匹配過程中加入了圖形化的編輯操作，并且使用了動態規劃算法。通過設置參數，該算法可以控制時間軸的彈性伸縮尺度。

2 基于極值點特征的時間序列相似性查詢方法

2.1 算法的主要思想

本文提出的方法是用來解決時間序列的子序列匹配問題。該問題定義如下:設有序列S={s1，s2，…，sn}和Q={q1，q2，…，qm}序列。其中n>m，要求在序列S中尋找與序列Q最相似的子序列。時間序列的子序列匹配需要解決兩個關鍵的問題:對序列S的子序列劃分和相似性度量函數的設定。

從目前的研究現狀來看，從序列S中獲取子序列的方法一般有三種:a)對序列S進行等距離分段，分段的長度一般設為m;b)使用長度為m的滑動窗口對序列S進行子序列選取;c)使用特定的序列分段方法對序列S進行分段。方法a)簡單易行，但是得到的子序列信息不完整且存在較大誤差。方法b)得到的子序列集很完整但是數據量太大，影響了相似性搜索的執行效率。因此，很多研究者會根據時間序列對象來設計特定的子序列獲取方法。對于時間序列來說，尤其是金融時間序列，人們往往非常關注它的形態和重要的極值點信息，本文提出的多層次極值劃分法就是利用重要的極值點對序列S進行子序列獲取，并且該方法的多層次性較大程度地滿足了子序列獲取完整性的要求。

在相似性度量函數的選取上，由于歐式距離對于時間軸的變形非常敏感，近年來動態時間彎曲(DTW)技術的使用越來越廣泛，但是它的計算復雜度較高。因此，大量的文獻都是在動態時間彎曲技術的基礎上進行改進，并且大部分的改進都是在使用DTW算法之前加入預先的篩選剪枝過程。本文也提出一種對DTW的改進方法，通過實驗驗證，該算法在保證準確度的情況下大大提高了相似性搜索過程的效率。

2.2 多層次極值劃分法(MLES)

該方法主要由三部分組成:a)重要性標志算法(EIIR)。該算法將輸出重要性標志序列TAG，對序列中的每個點按等級標志重要性。b)極值點判斷算法(JEP)。該算法用來判斷某一點是不是極值點。c)多層次分段獲取算法(MSR)。該算法根據EIIR得到的序列TAG產生各個層次的分段信息。下面分別對這三部分進行介紹。

2.2.1 重要性標志算法(EIIR)

設有序列S={s1，s2，…，sn}，其序列長度為n。cyc是用戶定義的參數，表示極值的計算鄰域范圍。如果cyc設置為3，則表示在序列點前后三個點的范圍內進行計算。對序列S中的點在參數cyc設置的鄰域范圍內使用JEP算法進行計算，根據計算結果修改輸出序列TAG中的值。最后，得到輸出結果序列TAG={tag1，tag2，…，tagn}，tagi表示序列S中的點si的重要程度。該算法的偽碼如下:

function EIIR(S，cyc)

input:sequence S[1，2，…，n]

integer cyc

output: List TAG

begin

initial TAG

for i=1 to cyc

for j=1 to n

if TAG[j]=i-1 and JEP(S，i，j)=1

then TAG[j]=TAG[j]+1

else

if TAG[j]=-(i-1) and JEP(S，i，j)=-1

then TAG[j]=TAG[j]-1

endif

endif

endfor

endfor

return TAG

end

2.2.2 極值點判斷算法(JEP)

設有序列S={s1，s2，…，sn}，其序列長度為n。m表示當前的計算點為序列S的第m個元素sm，v表示當前的計算鄰域。如果sm比它前面的第v個點sm-v和后面的第v個點sm+v都大，則Flag的取值為1;如果sm比它前面的第v個點sm-v和后面的第v個點sm+v都小，則Flag的取值為-1;否則，Flag的取值為0。該算法的偽碼如下:

function JEP(S，m，v)

input: Sequence S[1，2，…，n]

integer m

integer v

output: Integer Flag

begin

if Sv>=Sv+m and Sv>=Sv-m

then Flag=1

else

if Sv<=Sv+m and Sv<=Sv-m

thenFlag=-1

else Flag=0

endif

endif

end

2.2.3 多層次分段獲取算法(MSR)

通過EIIR算法的計算，可得到序列TAG。序列TAG中的值與序列S中的值一一對應，表示序列S中點的重要程度，值越大重要性越大。對于序列TAG， 將tag1和tagn設置為cyc+1。CP[i]中記錄的是第i層次的分段點，根據分段點可得到第i層次的子序列劃分。例如，有序列S={537.87，558.75，536.37，516.46，537.35，520.69，601.98，570.24，554.04，738.61}，得到的序列TAG={5，3，0，-4，1-1，2，0，-2，5}，那么，根據MSR算法可知CP[2]={537.87，558.75，516.46，738.61}，最終得到的第2層次的子序列可劃分為三個子序列{537.87，558.75}，{558.75，536.37，516.46}，{516.46，537.35，520.69，601.98，570.24，554.04，738.61}。該算法的偽碼如下:

function MSR(S，TAG，c)

input: Sequence S[1，2，…，n]

sequence TAG[1，2，…，n]

integer c

output: Sequence CP[i](1<=i<=c)

begin

for i=1 to c

for j=1 to n

ifTAGj>=i or TAGj<=-i

then add Sj to CP[i]

end if

endfor

return CP[i]

endfor

end

2.3 改進的DTW方法(PDTW)

設有兩條序列Q{q1，q2，…，qm}和R{r1，r2，…，rn}。其中m≤n。根據序列Q和R可建立矩陣M。其中M(i，j)=(qi-rj)2+(i-j)2。在矩陣M中根據以下規則進行路徑搜尋:

a)路徑從M(1，j)開始，初始成本為M(1，j)，其中j=1，2，…，(r-q)。

b)每一步是從M(i，j)到M(k，v)的一個連接，成本為M(k，v)。其中k=i+1，v>j。

c)路徑在M(q，j)結束，其中j=q，(q+1)，…，r。

d)路徑的成本是初始成本與每條連接的成本的總和。

根據以上規則可以在矩陣M中搜尋出多條路徑，選擇成本最小的路徑，并把該路徑的成本值作為序列Q和R的距離。該算法的偽代碼如下:

Function PDTW(M)

input: Matrix M(m，n)

output: ArrayPath(m)

floatvalue

begin

for i=m to 1//從第m行開始循環到第1行

for j=i to min(n，i+n-m+1)

//搜索路徑中第i行可能到達的列

尋找從(i，j)出發具有最小成本的路徑;

把最小成本值寫入M(i，j)

endfor

endfor

把矩陣M第1行中的最小值賦給value

for i=1 to m

把第i行中的最小值的列序號賦給Path(i)

endfor

end

3 實驗結果

本實驗使用滬市2005年1月—2007年12月的每日收盤價格曲線作為長序列S，共計724個點。選擇45條序列作為查詢序列Q進行測試，這45條序列從2008年1月—2009年6月的每日收盤價格曲線中隨機抽取，長度在10～15。

本實驗將本文算法與FSMBO算法進行比較，在文獻[10]中，FSMBO算法被證明具有較好的準確性和運行效率。本文算法的參數設置為cyc=15， FSMBO算法的參數設置為tc=3，ε=0.75。

算法使用VC進行編程實現，所有的實驗在一臺具有Intel雙核2.0 GHz處理器、1 GB內存以及使用Windows XP操作系統的PC上進行。

3.1 準確度

本實驗使用算法查詢出的匹配序列與查詢序列之間的DTW距離作為準確度的衡量標準。準確度比較的結果展示在圖1和2中。圖1中展示的是FSMBO算法與本文算法得到的匹配結果的DTW距離之差。圖1表明，兩種算法結果的DTW距離之差絕大部分是大于0的，說明使用本文算法得到的匹配序列與查詢序列更加相似，本文算法的準確性較好。圖2中展示的是兩種算法45次匹配結果的DTW距離之和。圖2表明，本文算法得到的DTW距離總和為0.18，FSMBO算法得到的DTW距離總和為0.55，顯然，本文算法得到的DTW距離總和遠遠小于FSMBO算法的結果。

3.2 運行效率

本實驗使用算法每次查詢的運行時間作為運行效率的衡量標準。運行效率比較的結果展示在圖3和4中。圖3中展示的是FSMBO算法與本文算法的運算時間的倍數關系，是用FSMBO算法的運行時間除以本文算法的運行時間。圖3表明，FSMBO算法的運行時間是本文算法運行時間的2～4倍。圖4中展示的是FSMBO算法與本文算法的平均運算時間。圖4表明，本文算法的平均運算時間是1184 ms，而FSMBO算法的平均運算時間是3364 ms，顯然，本文算法的運行效率是優于FSMBO算法的。

4 結束語

本文提出了一種新穎的時間序列子序列匹配的方法。該方法分為兩個部分，即多層次極值劃分法(MLES)和改進的DTW方法(PDTW)。MLES主要進行長序列的劃分，PDTW主要進行序列之間的相似度計算。本文算法的特點如下:

a)充分保留了時間序列的重要特征點信息和波形特征。

b)MLES方法得到不同長度的子序列集合，不僅保證了子序列本身的有效性，而且利用多層次性保證了子序列集合的完整性。

c)PDTW方法是對DTW算法的改進，它不僅能夠進行不同長度時間序列之間的相似度計算，而且還具有較快的計算速度。

通過實驗表明，本文算法具有較好的準確性和運行效率。可進一步研究將此方法應用于動態的時間數據流環境中。

參考文獻:

[1]KEOGH E. Data mining and machine learning in time series databa-ses[C]//Proc of the 4th IEEE International Conference on Data Mining.Seattle:[s.n.]，2004.

[2]肖輝，胡運發. 基于分段時間彎曲距離的時間序列挖掘[J]. 計算機研究與發展，2005，42(1):72-78.

[3]CHORIRAT A R， EAMONN K.Making time series classification more accurate using learned constraints[C]//Proc of SIAM International Conference on Data Mining.Florida:[s.n.]，2004.

[4]武紅江， 趙軍平， 彭勤科， 等. 基于波動特征的時間序列數據挖掘[J].控制與決策，2007，22(2):160-163.

[5]AGRAWAL R，FALOUSTOS C，SWAMI A.Efficient similarity search in sequence databases[C]//Proc of the 4th International Conference on Foundations of Data Organization and Algorithms.Berlin:Springer，1993.

[6]YASUSHI S， MASATOSHI Y， CHRISTOS F. FTW: fast Similarity search under the time warping distance[C]//Proc of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.New York:ACM Press，2005:326-337.

[7]NGUYEN Q V， DUONG T A. Combining SAX and piecewise linear approximation to improve similarity search on financial time series[C]//Proc of International Symposium on Information Technology Convergence.2007.

[8]MICHAEL D M， PJIGNESH M P. An efficient and accurate method for evaluating time series similarity[C]//Proc of ACM SIGMOD International Conference on Management of Data.2007.

[9]HAN W S， LEE J， MOON Y S， et al. Ranked subsequence matching in time-series databases[C]//Proc of the 33rd International Conference on Very Large Data Bases.2007:423-434.

[10]LU Kai-fu， LIN Shu-kuan. FSMBO:fast time series similarity matching based on bit operation[C]//Proc of the 9th International Conference for Young Computer Scientists.2008.

[11]FU T C， CHUNG F L， LUK R， et al. Stock time series pattern matching:template-based vs rule-based approaches[J].Engineering Applications of Artificial Intelligence，2007，20(3):347-364.

[12]MARTEAU P F. Time warp edit distance with stiffness adjustment for time series matching[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2009，31(2):306-318.