基于極值點(diǎn)特征的時間序列相似性查詢方法

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

關(guān)鍵詞:時間序列; 相似性查詢; 數(shù)據(jù)挖掘

中圖分類號:TP391文獻(xiàn)標(biāo)志碼: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 引言

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

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

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

1 相關(guān)研究現(xiàn)狀

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

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

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

2.1 算法的主要思想

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

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

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

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

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

2.2.1 重要性標(biāo)志算法(EIIR)

設(shè)有序列S={s1，s2，…，sn}，其序列長度為n。cyc是用戶定義的參數(shù)，表示極值的計算鄰域范圍。如果cyc設(shè)置為3，則表示在序列點(diǎn)前后三個點(diǎn)的范圍內(nèi)進(jìn)行計算。對序列S中的點(diǎn)在參數(shù)cyc設(shè)置的鄰域范圍內(nèi)使用JEP算法進(jìn)行計算，根據(jù)計算結(jié)果修改輸出序列TAG中的值。最后，得到輸出結(jié)果序列TAG={tag1，tag2，…，tagn}，tagi表示序列S中的點(diǎn)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 極值點(diǎn)判斷算法(JEP)

設(shè)有序列S={s1，s2，…，sn}，其序列長度為n。m表示當(dāng)前的計算點(diǎn)為序列S的第m個元素sm，v表示當(dāng)前的計算鄰域。如果sm比它前面的第v個點(diǎn)sm-v和后面的第v個點(diǎn)sm+v都大，則Flag的取值為1;如果sm比它前面的第v個點(diǎn)sm-v和后面的第v個點(diǎn)sm+v都小，則Flag的取值為-1;否則，F(xiàn)lag的取值為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中的值一一對應(yīng)，表示序列S中點(diǎn)的重要程度，值越大重要性越大。對于序列TAG， 將tag1和tagn設(shè)置為cyc+1。CP[i]中記錄的是第i層次的分段點(diǎn)，根據(jù)分段點(diǎn)可得到第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}，那么，根據(jù)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 改進(jìn)的DTW方法(PDTW)

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

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)結(jié)束，其中j=q，(q+1)，…，r。

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

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

Function PDTW(M)

input: Matrix M(m，n)

output: ArrayPath(m)

floatvalue

begin

for i=m to 1//從第m行開始循環(huán)到第1行

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

//搜索路徑中第i行可能到達(dá)的列

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

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

endfor

endfor

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

for i=1 to m

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

endfor

end

3 實(shí)驗(yàn)結(jié)果

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

本實(shí)驗(yàn)將本文算法與FSMBO算法進(jìn)行比較，在文獻(xiàn)[10]中，F(xiàn)SMBO算法被證明具有較好的準(zhǔn)確性和運(yùn)行效率。本文算法的參數(shù)設(shè)置為cyc=15， FSMBO算法的參數(shù)設(shè)置為tc=3，ε=0.75。

算法使用VC進(jìn)行編程實(shí)現(xiàn)，所有的實(shí)驗(yàn)在一臺具有Intel雙核2.0 GHz處理器、1 GB內(nèi)存以及使用Windows XP操作系統(tǒng)的PC上進(jìn)行。

3.1 準(zhǔn)確度

本實(shí)驗(yàn)使用算法查詢出的匹配序列與查詢序列之間的DTW距離作為準(zhǔn)確度的衡量標(biāo)準(zhǔn)。準(zhǔn)確度比較的結(jié)果展示在圖1和2中。圖1中展示的是FSMBO算法與本文算法得到的匹配結(jié)果的DTW距離之差。圖1表明，兩種算法結(jié)果的DTW距離之差絕大部分是大于0的，說明使用本文算法得到的匹配序列與查詢序列更加相似，本文算法的準(zhǔn)確性較好。圖2中展示的是兩種算法45次匹配結(jié)果的DTW距離之和。圖2表明，本文算法得到的DTW距離總和為0.18，F(xiàn)SMBO算法得到的DTW距離總和為0.55，顯然，本文算法得到的DTW距離總和遠(yuǎn)遠(yuǎn)小于FSMBO算法的結(jié)果。

3.2 運(yùn)行效率

本實(shí)驗(yàn)使用算法每次查詢的運(yùn)行時間作為運(yùn)行效率的衡量標(biāo)準(zhǔn)。運(yùn)行效率比較的結(jié)果展示在圖3和4中。圖3中展示的是FSMBO算法與本文算法的運(yùn)算時間的倍數(shù)關(guān)系，是用FSMBO算法的運(yùn)行時間除以本文算法的運(yùn)行時間。圖3表明，F(xiàn)SMBO算法的運(yùn)行時間是本文算法運(yùn)行時間的2～4倍。圖4中展示的是FSMBO算法與本文算法的平均運(yùn)算時間。圖4表明，本文算法的平均運(yùn)算時間是1184 ms，而FSMBO算法的平均運(yùn)算時間是3364 ms，顯然，本文算法的運(yùn)行效率是優(yōu)于FSMBO算法的。

4 結(jié)束語

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

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

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

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

通過實(shí)驗(yàn)表明，本文算法具有較好的準(zhǔn)確性和運(yùn)行效率。可進(jìn)一步研究將此方法應(yīng)用于動態(tài)的時間數(shù)據(jù)流環(huán)境中。

參考文獻(xiàn):

[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]肖輝，胡運(yùn)發(fā). 基于分段時間彎曲距離的時間序列挖掘[J]. 計算機(jī)研究與發(fā)展，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]武紅江， 趙軍平， 彭勤科， 等. 基于波動特征的時間序列數(shù)據(jù)挖掘[J].控制與決策，2007，22(2):160-163.

[5]AGRAWAL R，F(xiàn)ALOUSTOS 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.