李迎

(遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,遼寧 大連 116081)

時(shí)間序列(Time Series)挖掘是數(shù)據(jù)挖掘中的一個(gè)重要研究分支，有著廣泛的應(yīng)用價(jià)值。近年來(lái)，時(shí)間序列挖掘在宏觀的經(jīng)濟(jì)預(yù)測(cè)、市場(chǎng)營(yíng)銷(xiāo)、客流量分析、太陽(yáng)黑子數(shù)、月降水量、河流流量、股票價(jià)格變動(dòng)等眾多領(lǐng)域得到了廣泛應(yīng)用[1]。

時(shí)間序列的相似性是衡量?jī)蓚€(gè)時(shí)間序列相似程度的一個(gè)重要指標(biāo)，它是時(shí)間序列聚類(lèi)、分類(lèi)、異常發(fā)現(xiàn)等諸多數(shù)據(jù)挖掘的基礎(chǔ)，也是研究時(shí)間序列挖掘的核心問(wèn)題之一[2]。歐氏距離 (Euclidean)和動(dòng)態(tài)時(shí)間彎曲距離(Dynamic Time Warping)是計(jì)算時(shí)間序列相似性時(shí)經(jīng)常被采用的兩種度量方式。歐氏距離對(duì)時(shí)間軸上的輕微變化非常敏感，一些輕微的變化可能使歐氏距離的變化很大，而動(dòng)態(tài)時(shí)間彎曲距離可以有效地消除歐氏距離這個(gè)缺陷，動(dòng)態(tài)時(shí)間彎曲可以廣泛應(yīng)用在自然科學(xué)、醫(yī)學(xué)、企業(yè)和經(jīng)濟(jì)等方面[3]。SAX(Symbolic Aggregate Approximation)[4]是一種運(yùn)用符號(hào)化方法對(duì)時(shí)間序列進(jìn)行表示、維度約簡(jiǎn)及相似性度量的方法。但SAX方法采用PAA算法將時(shí)間序列平均劃分，不能很好地計(jì)算序列之間的相似度。而利用均分點(diǎn)和關(guān)鍵點(diǎn)對(duì)序列進(jìn)行分段，既考慮了序列本身概率分布的變化,又兼顧到序列形態(tài)的變化。

本文提出一種基于DTW的符號(hào)化時(shí)間序列聚類(lèi)算法，在提取關(guān)鍵點(diǎn)之后，再進(jìn)行符號(hào)化時(shí)間序列，以達(dá)到降維的目的。降維之后得到的符號(hào)序列為不等長(zhǎng)序列，采用動(dòng)態(tài)時(shí)間彎曲距離 (DTW)方法進(jìn)行計(jì)算,魯棒性好。然后通過(guò)DTW得到的距離矩陣構(gòu)建復(fù)雜網(wǎng)絡(luò)，并尋找其社團(tuán)結(jié)構(gòu),實(shí)現(xiàn)了符號(hào)時(shí)間序列聚類(lèi)。本文用DTW方法進(jìn)行相似性度量比KPDIST[4]在聚類(lèi)結(jié)果的準(zhǔn)確率上有較好大提高。

1 相關(guān)知識(shí)

1.1 時(shí)間序列關(guān)鍵點(diǎn)的選取

基于參考文獻(xiàn)[5]可知，時(shí)間序列中的極值點(diǎn) EP成為關(guān)鍵點(diǎn)KP的條件為：

條件1.xi保持極值的時(shí)間段與該序列長(zhǎng)度的比值必須大于某個(gè)閾值C；

條件2.若條件1不滿足，則包含xi的最小序列模式＜xi-1,xi,xi+1＞中,三點(diǎn)連線形成的夾角小于篩選角度α0。

1.2 DTW算法

動(dòng)態(tài)時(shí)間彎曲方法公式如下[3]：

1.3 基于Normal矩陣的譜平分法[6]

將一個(gè)時(shí)間序列作為一個(gè)節(jié)點(diǎn)，如果兩個(gè)時(shí)間序列間的相似度大于給定的閾值，則認(rèn)為這兩個(gè)節(jié)點(diǎn)有邊相連，否則它們之間就沒(méi)有邊。這樣就構(gòu)造了時(shí)間序列間的一個(gè)復(fù)雜網(wǎng)絡(luò)G。對(duì)于網(wǎng)絡(luò)G，有其鄰接矩陣A。利用基于Normal矩陣的譜平分方法可以實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分。

2 本文算法實(shí)現(xiàn)

2.1 關(guān)鍵點(diǎn)提取

輸 入 ：時(shí) 間 序 列 X=＜(t1,x1),…(ti,xi),…,(tn,xn)＞(0＜i＜n)篩選夾角 α0，預(yù)設(shè)數(shù)據(jù)壓縮率p;

輸出：關(guān)鍵點(diǎn)集合 KPS=＜KP1,…,KPi,…,KPn＞

(1)根據(jù)推論 1，由 p計(jì)算系數(shù)x;

(2)初 始 化 ，KP1=x1,xN,x2N,… ,xωN,ω 是 均 分 段 數(shù) ，N 是每個(gè)平均分段內(nèi)數(shù)據(jù)的個(gè)數(shù)；

(3)從KP1=x1開(kāi)始判斷時(shí)間序列的單調(diào)性，獲得包含 3個(gè)極值點(diǎn) xi-p,xi,xi+q的局部時(shí)間序列 X=＜xi-p,…,xi-1,xi,xi+1,…,xi+q＞,待考察的極值點(diǎn)為 xi,包含該點(diǎn)的最短時(shí)間序列為＜xi-1,xi,xi+1＞;

(4)計(jì)算max(|xi-xi-1|,|xi-xi+1|),假設(shè)返回|xi-xi+1|;

(7)將點(diǎn) xi并入集合 KPS，更新區(qū)間[u-xσ,u+xσ]; 返回(1)，對(duì)下一極值點(diǎn)進(jìn)行判斷。

2.2 基于DTW的符號(hào)化聚類(lèi)算法

輸入：時(shí)間序列集。

輸出：聚類(lèi)結(jié)果。

(1)對(duì)每個(gè)序列，運(yùn)用上面的算法得到最終的關(guān)鍵點(diǎn)序列；

(2)計(jì)算序列C在各區(qū)間[KPci,KPcj)內(nèi)的均值，并表示為符號(hào)序列；

(3)對(duì)序列C和序列Q的符號(hào)序列進(jìn)行相似性距離計(jì)算（DTW計(jì)算和KPDIST計(jì)算）；

(4)根據(jù)相似度，構(gòu)建復(fù)雜網(wǎng)絡(luò)G；此處要給相似度賦予一個(gè)閾值,相似性小于閾值的點(diǎn)則認(rèn)為無(wú)邊連接。

(5)用Normal矩陣方法FCM算法對(duì)復(fù)雜網(wǎng)絡(luò) G進(jìn)行社團(tuán)劃分，得到聚類(lèi)結(jié)果。

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

本文實(shí)驗(yàn)采用Keogh博士的Synthetic Control和ECG數(shù)據(jù)集。實(shí)驗(yàn)環(huán)境為2.66 GHz CPU Pentium?4 PC機(jī)，1 GB內(nèi)存，操作系統(tǒng)為Windows XP Professional。算法實(shí)現(xiàn)軟環(huán)境為 matlab 7.0和VC++6.0。Synthetic Control數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)為300條，每條時(shí)間序列長(zhǎng)度為60。ECG數(shù)據(jù)集有100個(gè)樣本序列,每條時(shí)間序列長(zhǎng)度為96（http://www.cs.ucr.edu/～eamonn/time_series_data/）。 原 時(shí)間序列維度為60和96，經(jīng)過(guò)關(guān)鍵點(diǎn)提取、符號(hào)化之后，維度大大降低,這為后期處理帶來(lái)了很大的方便。 在本實(shí)驗(yàn)中，關(guān)鍵點(diǎn)提取時(shí)篩選角度為45°，預(yù)設(shè)的壓縮率為80%，劃分了4個(gè)區(qū)間段，用符號(hào)表示時(shí)為a,b,c,d四種字母。由于實(shí)驗(yàn)數(shù)據(jù)的樣本個(gè)數(shù)很多，這里只顯示synthetic control的部分實(shí)驗(yàn)結(jié)果。表1為降維后的前4個(gè)符號(hào)序列實(shí)驗(yàn)結(jié)果。

表1 Synthetic Control序列1-4 KP_SAX字符串結(jié)果

表2為Normal矩陣得到的非平凡特征值對(duì)應(yīng)的非平凡特征向量，根據(jù)譜平分算法思想，同一社團(tuán)內(nèi)的節(jié)點(diǎn)相應(yīng)的元素xi非常接近。從特征向量的分析中可以看出，將DTW與復(fù)雜網(wǎng)絡(luò)知識(shí)應(yīng)用在符號(hào)化時(shí)間序列上是一種較好的創(chuàng)新。

由DTW距離矩陣得到的網(wǎng)絡(luò)中，第一非平凡特征值取值為：0.252 9，而通過(guò)KPDIST距離矩陣得到的復(fù)雜網(wǎng)絡(luò)中，第一非平凡特征值取值為：0.125 7，從特征值中就可以初步判斷，DTW得到的特征值更為準(zhǔn)確，這兩個(gè)特征值對(duì)應(yīng)的特征向量的區(qū)間表如表2所示。

表2 synthetic control的特征向量分布表

表3為兩種算法對(duì)同樣數(shù)據(jù)集進(jìn)行聚類(lèi)得到的結(jié)果。數(shù)據(jù)集Synthetic control采用本文方法正確率為76.3%。而利用KPDIST算法正確率為69%；數(shù)據(jù)集ECG，本文的正確率為72%，KPDIST的正確率為65%。

表3 聚類(lèi)結(jié)果

SAX是一種符號(hào)化的時(shí)間序列相似性度量方法，該方法在對(duì)時(shí)間序列劃分時(shí)，采用了PAA算法的均值劃分，得出的結(jié)果不能精確地表示出原時(shí)間序列，故將關(guān)鍵點(diǎn)提取方法與PAA方法相結(jié)合,在對(duì)原序列降維的同時(shí)又能更準(zhǔn)確地表示原時(shí)間序列。本文將復(fù)雜網(wǎng)絡(luò)知識(shí)和時(shí)間序列降維方法相結(jié)合，給出了一種時(shí)間序列的聚類(lèi)方法。該算法用DTW算法計(jì)算時(shí)間序列間的相似度，而后從時(shí)間序列的相似度得到一個(gè)復(fù)雜網(wǎng)絡(luò)，此復(fù)雜網(wǎng)絡(luò)表示了時(shí)間序列相互間的關(guān)系。最后采用Normal矩陣的方法進(jìn)行網(wǎng)絡(luò)劃分，得到一個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。從這個(gè)社團(tuán)結(jié)構(gòu)中已能看出樣本時(shí)間序列的歸屬類(lèi)別，但為了結(jié)果更加清晰，用具體數(shù)字來(lái)體現(xiàn)，所以采用了FCM聚類(lèi)算法進(jìn)行最后的聚類(lèi)。實(shí)驗(yàn)結(jié)果表明，用DTW方法計(jì)算序列之間的相似度結(jié)合在降維后的符號(hào)化時(shí)間序列上比原文KPDIST方法在準(zhǔn)確率上有較好大提高。

[1]毛國(guó)君,段立娟,王實(shí),等.數(shù)據(jù)挖掘原理與算法（第二版）[M].北京：清華大學(xué)出版社，2007.

[2]劉懿,鮑德沛,楊澤紅.新型時(shí)間序列相似性度量方法研究[J].計(jì)算機(jī)應(yīng)用研究,2007,24(5):112-114.

[3]KEOGH E,RATANAMAHATANA C A.Exact indexing of dynamic time warping[J].Springer-Verlag London Ltd,2005,10.1007/s10115-004-0154-9:358-386.

[4]閆秋艷,孟凡榮.一種基于關(guān)鍵點(diǎn)的 SAX改進(jìn)算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(z2):483-490.

[5]杜奕.時(shí)間序列挖掘相關(guān)算法研究及應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2007.

[6]汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006:169-171.