,,,

(北京聯(lián)合大學(xué) a.信息學(xué)院;b.自動化學(xué)院,北京 100101)

0 概述

時間序列數(shù)據(jù)正在以一種難以想象的規(guī)模和速度快速增長,已經(jīng)在商業(yè)、醫(yī)藥和科學(xué)研究等領(lǐng)域占據(jù)了大量的存儲空間。對原始數(shù)據(jù)直接進行數(shù)據(jù)挖掘,不僅要花費大量時間,而且由于噪聲點的存在還會導(dǎo)致算法準(zhǔn)確度下降。在通常情況下,需要對原始序列數(shù)據(jù)進行數(shù)據(jù)的高級表示[1],常用方法有奇異值分解[2-3]、離散傅里葉變換[4-5]、離散小波變換[6-7]、主成分分析[8]和分段線性表示[9-10]等。

其中分段線性表示(PLR)方法是使用直線段近似表示時間序列,具有時間多解析性、支持快速相似性搜索和數(shù)據(jù)壓縮度靈活等優(yōu)點。而在分段線性表示方法中,分段點的選擇顯得極為重要。使用提取的分段點可以近似擬合原始數(shù)據(jù)和相似性度量等運算,大大減少運算成本。有許多學(xué)者已經(jīng)在分段點提取方面做出貢獻(xiàn),如文獻(xiàn)[11]提出用等寬度窗口中數(shù)據(jù)的平均值表示時間序列(PAA),文獻(xiàn)[12]提出基于重要點的分段線性方法(PCA)。在國內(nèi),文獻(xiàn)[13]提出根據(jù)相鄰兩點間斜率的變化提取時間序列上的分段點(SEEP),文獻(xiàn)[14]提出基于一階濾波的時間序列分段線性表示方法(SFWF),文獻(xiàn)[15]提出基于序列重要點概念達(dá)到時間序列分割算法(SIP),文獻(xiàn)[16]提出根據(jù)偏離度提取變化點的時間序列分段線性表示(CPA)。

本文給出一種提取時間序列數(shù)據(jù)趨勢轉(zhuǎn)折點算法(FTTO)。首先定義時間序列數(shù)據(jù)4個相鄰數(shù)據(jù)點的運算,隨后討論運算結(jié)果P并且對P值小于零和等于零2種出現(xiàn)趨勢轉(zhuǎn)折點的情況分別進行討論,然后提取原始數(shù)據(jù)中上升、下降和平緩3種基本趨勢轉(zhuǎn)折點。最后將相鄰2個基本趨勢轉(zhuǎn)折點中間的數(shù)據(jù)做坐標(biāo)旋轉(zhuǎn)變換,對旋轉(zhuǎn)變換得到的新的時間序列數(shù)據(jù)使用FTTO算法,得到緩慢上升、快速上升、緩慢下降、快速下降4種拐點。

1 基本定義

定義1(時間序列) 時間序列是有序的信息集合。每一個元素包括記錄信息和時間。長度為n時間序列X記為:

X={,,…,

,…,}

(1)

其中,表示時間序列X在ti時刻記錄的數(shù)據(jù)值為:

xi={a1,a2,…,am},m≥1

(2)

在一般情況下,時間序列的采樣間隔Δt(Δt=ti+1-ti)相等且大于零,也可以將時間序列X簡記為{x1,x2,…,xn}。

定義2(分段線性表示) 時間序列數(shù)據(jù)X記為{x1,x2,…,xn},趨勢轉(zhuǎn)折點集合為{xt1,xt2,…,xti,…,xtn},其中,xt1和xtn分別為時間序列的起始點和終點。其分段線性表示為:

XPLR= {,…,,…,

}

(3)

其中,表示在[ti,t(i+1)]時間段內(nèi)的線性函數(shù)。

定義4在時間序列X中,如果xi是趨勢轉(zhuǎn)折點,那么xi必是局部極值點[15],即xi滿足:

{(xi≥xi+1)∪(xi>xi+1)}∩

{(xi>xi+1)∪(xi≥xi+1)}{(xi≤xi+1)∪(xi

{(xi

(4)

定義6(基本趨勢轉(zhuǎn)折點) 時間序列數(shù)據(jù)的趨勢可分為上升、平緩和下降3種基本趨勢,根據(jù)這種趨勢提取的轉(zhuǎn)折點可以被稱為基本趨勢轉(zhuǎn)折點。

定義7(拐點) 緩慢上升、快速上升、緩慢下降和快速下降屬于在一個基本趨勢中單位時間內(nèi)數(shù)據(jù)的變化速率不同,依據(jù)變化速率不同提取的趨勢轉(zhuǎn)折點被稱為拐點。

2 趨勢轉(zhuǎn)折點提取算法與分析

2.1 提取趨勢轉(zhuǎn)折點算法

如圖1所示[15],在時間序列中相鄰3個數(shù)據(jù)點分別為xi、xi+1和xi+2,它們的發(fā)展趨勢共有9種情況。當(dāng)xi+2-xi>0時,即圖1(a)、圖1(b)、圖1(e)這3種情況屬于總體趨勢上升。當(dāng)xi+2-xi<0時,即圖1(f)、圖1(g)、圖(i)這3種情況屬于總體趨勢下降。當(dāng)xi+2-xi=0時,即圖1(c)、圖1(d)、圖1(h)這3種情況屬于總體保持不變。

圖1 時間序列中相鄰3點的變化趨勢

在時間序列X中相鄰的4個數(shù)據(jù)點分別為xi、xi+1、xi+2、xi+3,令：

(xi+2-xi)×(xi+3-xi+1)=P

(8)

當(dāng)P大于零時,在相鄰的4個數(shù)據(jù)點中,前3個數(shù)據(jù)點與后3個數(shù)據(jù)點趨勢相同。當(dāng)P小于零時,在相鄰的4個數(shù)據(jù)點中前后趨勢不同,出現(xiàn)趨勢轉(zhuǎn)折點。當(dāng)P等于零時,相鄰的4個數(shù)據(jù)點中前后趨勢可能不同。下面分別討論P小于、等于零的情況。

1)當(dāng)P小于零時,(xi+2-xi)>0且(xi+3-xi+1)<0,前3點為上升趨勢,分別對應(yīng)圖1(a)、圖1(b)、圖1(e)這3種情況,后3點為下降趨勢。此時4個相鄰數(shù)據(jù)點共有3種分布情況,如圖2所示。依據(jù)定義4,趨勢轉(zhuǎn)折點是局部極值點,當(dāng)上升趨勢轉(zhuǎn)變?yōu)橄陆第厔輹r,趨勢轉(zhuǎn)折點應(yīng)為局部極大值點,所以比較xi+1與xi+2的大小,最大值是趨勢轉(zhuǎn)折點,若相等,則取xi+1作為趨勢轉(zhuǎn)折點。

圖2 4個相鄰數(shù)據(jù)點上升轉(zhuǎn)下降示意圖

2)當(dāng)P小于零時,(xi+2-xi)<0、(xi+2-xi)>0、(xi+2-xi)<0且(xi+3-xi+1)>0,前3點為下降趨勢,分別對應(yīng)圖1(f)、圖1(g)和圖1(i)3種情況,后3點為上升趨勢。此時4個相鄰數(shù)據(jù)點共有3種分布情況,如圖3所示。同理,比較xi+1與xi+2的大小,下降趨勢轉(zhuǎn)變?yōu)樯仙厔?所以局部極小值點是趨勢轉(zhuǎn)折點。若相等,取xi+1作為趨勢轉(zhuǎn)折點。

圖3 4個相鄰數(shù)據(jù)點下降轉(zhuǎn)上升示意圖

3)當(dāng)P等于零時,(xi+2-xi)=0且(xi+3-xi+1)≠0,前3點趨勢為保持不變,后3點趨勢并不確定,如圖4所示,后3點的變化趨勢共有8種情況。由圖4可知，xi+2是2種不同趨勢變化交點,即取xi+2作為趨勢轉(zhuǎn)折點。

圖4 4個相鄰數(shù)據(jù)點保持轉(zhuǎn)變化示意圖

4)當(dāng)P等于零時,(xi+2-xi)≠0且(xi+3-xi+1)=0,前3點趨勢并不確定,后3點趨勢為保持不變,如圖5所示,前3點的變化趨勢共有8種情況。由圖5可以發(fā)現(xiàn),xi+1是2種不同趨勢的變化交點,即取xi+1作為趨勢轉(zhuǎn)折點。

圖5 4個相鄰數(shù)據(jù)點變化轉(zhuǎn)保持示意圖

5)當(dāng)P等于零時,(xi+2-xi)=0且(xi+3-xi+1)=0,前3點與后3點的趨勢相同保持不變,如圖6所示,共有3種情況,趨勢均視為平緩,所以此時無趨勢轉(zhuǎn)折點。

圖6 4個相鄰數(shù)據(jù)點趨勢保持不變示意圖

以上5種情況如表1、表2所示。

表1 當(dāng)P<0時的情況

表2 當(dāng)P=0時的情況

2.2 拐點提取

對原始時間序列數(shù)據(jù)使用以上算法可以得到3種基本趨勢轉(zhuǎn)折點。利用3種基本趨勢轉(zhuǎn)折點還原數(shù)據(jù)。為減少擬合誤差,提高擬合精度,定義閾值Q,Q代表相鄰2個趨勢轉(zhuǎn)折點的距離,即ti-t(i-1),當(dāng)趨勢轉(zhuǎn)折點與前一個轉(zhuǎn)折點間的距離大于Q時,提取拐點。

假設(shè)相鄰2個基本趨勢轉(zhuǎn)折點為xti和xt(i+1),2個趨勢轉(zhuǎn)折點間的數(shù)據(jù)如圖7所示,圖7中共有A和B2個拐點。

圖7 坐標(biāo)轉(zhuǎn)換前原始數(shù)據(jù)示意圖

首先連接相鄰的2個趨勢轉(zhuǎn)折點xti和xt(i+1),以連線作為X軸。其次將2個趨勢轉(zhuǎn)折點之間的原始數(shù)據(jù)與連線的距離作為新的時間序列數(shù)據(jù),如圖8所示。經(jīng)過坐標(biāo)旋轉(zhuǎn)變換后,將緩慢上升、快速上升、緩慢下降和快速下降等拐點的提取問題轉(zhuǎn)換為基本趨勢轉(zhuǎn)折點提取問題。最后對新的時間序列數(shù)據(jù)采用FTTO算法便可提取拐點。因為FTTO算法運算使用相鄰的4個數(shù)據(jù)點,所以距離閾值Q應(yīng)不小于5。

圖8 坐標(biāo)旋轉(zhuǎn)轉(zhuǎn)換后數(shù)據(jù)示意圖

2.3 算法實現(xiàn)步驟

依據(jù)2.1節(jié)與2.2節(jié)提出的趨勢轉(zhuǎn)折點提取算法,實現(xiàn)FTTO算法共分為主函數(shù)和FTTO方法2個部分,如果需要提取拐點減少擬合誤差,則添加FTTO-G方法部分。

主函數(shù)方法描述如下:

輸入時間序列X={x1,x2,…,xn}

Begin

Xc={}{};/*實例化一個序列,存儲趨勢轉(zhuǎn)折點*/

fi=0;/*保存前一個趨勢轉(zhuǎn)折點時間索引*/

se=0;/*保存當(dāng)前趨勢轉(zhuǎn)折點時間索引*/

Xc.add(x1)/*數(shù)據(jù)起始點默認(rèn)為趨勢轉(zhuǎn)折點*/

for(i=1;i

/*遍歷原始數(shù)據(jù),相鄰4個點計算P值*/

(xi+2-xi)×(xi+3-xi+1)=P

/*依據(jù)FTTO算法,判斷是否存在趨勢轉(zhuǎn)折點*/

FTTO(P,xi,xi+1,xi+2,xi+3)

/*如果需要提取拐點,則根據(jù)輸入的Q值和相鄰2個轉(zhuǎn)折點間距離判斷是否使用FTTO-G算法*/

if(se-fi>Q)

FTTO-G(fi,se);

/*在提取拐點后,更新fi坐標(biāo)索引*/

fi=se;

Xc.add(xn)

End

FTTO方法描述如下:

輸入P和相鄰的4個數(shù)據(jù)點xi+1、xi+2、xi+3和xi+4

輸出如果輸入數(shù)據(jù)中存在趨勢轉(zhuǎn)折點,則Xc集合中添加轉(zhuǎn)折點,如果輸入數(shù)據(jù)中不存在趨勢轉(zhuǎn)折點,則不向Xc中添加數(shù)據(jù)

Begin

if(P<0)

if(xi+1≥xi+2)

Xc.add(xi+1);se=i+1;

else if(xi+1

Xc.add(xi+2);se=i+2;

else if(xi+3-xi+1>0)

if(xi+1>xi+2)

Xc.add(xi+2);se=i+2

else if(xi+1≤xi+2)

Xc.add(xi+1);se=i+1;

else if(p=0)

if((xi+3-xi+1) ≠0&& (xi+2-xi)=0))

Xc.add(xi+2);se=i+2;

else if((xi+3-xi)=0 && (xi+2-xi)≠0)Xc.add(xi+1);se=i+1;

End

FTTO-G方法描述如下:

輸入前一個趨勢轉(zhuǎn)折點時間坐標(biāo)索引fi,當(dāng)前趨勢轉(zhuǎn)折點時間坐標(biāo)索引se

輸出如果相鄰2個趨勢轉(zhuǎn)折點之間存在拐點,則向Xc中添加數(shù)據(jù),如果相鄰2個趨勢轉(zhuǎn)折點之間不存在拐點,則Xc中數(shù)據(jù)不變

Begin

G={};/*實例存儲新的時間序列數(shù)據(jù)的序列*/

Calclinearequation();/*計算2個轉(zhuǎn)折點間的直線方程*/

for(int?w=fi;w<=se;w++)

G.add(distance(xw));/*計算每個點到直線的距離,并添加到G中*/

for(int??j=0;j

/*對新的時間序列數(shù)據(jù)G,采用FTTO算法,將提取的趨勢轉(zhuǎn)折點添加到XC中*/

(Gj+2-Gj)×(Gji+3-Gj+1)=P

FTTO(P,Gj,Gj+1,Gj+2,Gj+3)

End

本文提出的FTTO算法時間復(fù)雜度為O(6n)。在程序運行過程中,首先需要遍歷原始數(shù)據(jù),計算相鄰的4個數(shù)據(jù)點的值P,之后通過3次判斷得出該算法是否存在趨勢轉(zhuǎn)折點。那么,此時的時間復(fù)雜度T1(n)=O((1+3)×(n-3))=O(4n)。如果需要提取拐點,則增加FTTO-G方法部分。首先計算相鄰2個趨勢轉(zhuǎn)折點間直線方程的斜率與截距。之后遍歷相鄰2個趨勢轉(zhuǎn)折點間數(shù)據(jù),形成新的時間序列數(shù)據(jù),此時的時候復(fù)雜度T2(n)=O(n)。最后對新的時間序列數(shù)據(jù)使用FTTO算法。此時的時間復(fù)雜度T3(n)=O(n)。所以,FTTO算法的時間復(fù)雜度為O(4n+n+n)=O(6n)。

在提取基本趨勢轉(zhuǎn)折點過程中,FTTO算法將相鄰的3個數(shù)據(jù)點作為基本趨勢單元,不依賴任何先驗知識,自動提取數(shù)據(jù)中基本趨勢轉(zhuǎn)折點。在提取拐點過程中,增加相鄰2個基本趨勢轉(zhuǎn)折點間的距離閾值Q,對經(jīng)過坐標(biāo)變換后的數(shù)據(jù)使用FTTO算法提取拐點,從而提高擬合精度。

3 對比實驗

3.1 對比擬合誤差

本文實驗數(shù)據(jù)采用美國加州大學(xué)河濱分校收集整理的UCR時間序列分類數(shù)據(jù)集[17]。選擇SEEP[13]、PAA[11]、CPA[16]算法與本文提出的FTTO算法進行對比,使用不同算法提取數(shù)據(jù)點分段線性表示原始數(shù)據(jù),之后對比擬合誤差。擬合誤差越小,證明算法擬合性能越優(yōu)秀。

在下文實驗中,由于數(shù)據(jù)集中數(shù)據(jù)來自不同領(lǐng)域,首先進行數(shù)據(jù)歸一化處理,數(shù)據(jù)歸一化公式如下:

(5)

文獻(xiàn)[13]提出的SEEP算法是基于斜率提取數(shù)據(jù)點的代表性算法。首先計算連接同一點的左右兩條線段的斜率。之后對比斜率的變化量是否超出閾值d,若大于閾值d,則提取分段點。最終連接分段點得到原始數(shù)據(jù)的分段線性表示。

文獻(xiàn)[11]提出的PAA算法是分段線性表示的經(jīng)典算法。首先使用等寬窗口劃分原始數(shù)據(jù),之后每個窗口內(nèi)使用平均值代替原始數(shù)據(jù),最后得到原始數(shù)據(jù)的分段線性表示。

文獻(xiàn)[16]提出的CPA算法在提取分段點過程中具有良好效果。首先依據(jù)各個數(shù)據(jù)點在局部范圍內(nèi)的偏離程度定義了時間序列數(shù)據(jù)的變化點,之后連接每一個變化點,最后得到原始數(shù)據(jù)的分段線性表示。

以synthetic_control數(shù)據(jù)集中的第一條數(shù)據(jù)為例,比較4種算法的擬合效果。圖9～圖13分別為歸一化原始數(shù)據(jù)、FTTO算法擬合數(shù)據(jù)、SEEP算法擬合數(shù)據(jù)、CPA算法擬合數(shù)據(jù)和PAA算法擬合數(shù)據(jù)效果示意圖。

圖9 原始數(shù)據(jù)效果示意圖

圖10 本文算法FTTO擬合數(shù)據(jù)效果示意圖

圖11 SEEP算法擬合數(shù)據(jù)效果示意圖

圖12 CPA算法擬合數(shù)據(jù)效果示意圖

圖13 PAA算法擬合數(shù)據(jù)效果示意圖

從圖9～圖13對比結(jié)果可以看出,本文提出的FTTO算法能夠提取數(shù)據(jù)主要趨勢轉(zhuǎn)折點達(dá)到保留原始數(shù)據(jù)的趨勢信息的目的。SEEP與CPA算法均存在遺漏提取分段點的情況,PAA算法雖然保存了原始信息的整體趨勢特征,但是丟失了每個窗口內(nèi)的趨勢信息。

4種算法在相同壓縮率情況下擬合誤差對比實驗結(jié)果如表3所示,表3中R表示壓縮率,FTTO算法提取拐點的閾值Q等于5。由于PAA算法的自身特點,實驗過程中PAA算法壓縮率大于且最接近表3中的壓縮率。表3中下劃線表示每行擬合誤差最小值。

表3 擬合誤差對比結(jié)果

從表3可以看出, 在30組時間序列數(shù)據(jù)中,SEEP算法在8類時間序列數(shù)據(jù)中擬合誤差最小,CPA算法在1類時間序列數(shù)據(jù)中擬合誤差最小,本文提出的FTTO算法在21類時間序列數(shù)據(jù)中擬合誤差最小。

3.2 對比分類錯誤率

Keogh團隊公布了在UCR時間序列分類數(shù)據(jù)集上，使用DTW算法在采用1-NN分類的情況下各個數(shù)據(jù)集的分類錯誤率。本文運用SEEP、CPA和FTTO算法對比擬合時間序列數(shù)據(jù)在采用1-NN分類和DTW距離度量情況下的分類錯誤率。對比結(jié)果如表4所示。在表4中,A列是Keogh團隊公布的在原始數(shù)據(jù)上的分類錯誤率。各個數(shù)據(jù)的壓縮率同表3中各個數(shù)據(jù)的壓縮率相等。表4中下劃線代表各行中的最小數(shù)據(jù)。

表4 UCR數(shù)據(jù)集對比分類結(jié)果

在表4中,有17組數(shù)據(jù)顯示使用原始數(shù)據(jù)得到的分類錯誤率最小,使用SEEP算法有2組數(shù)據(jù)的分類錯誤率同原始數(shù)據(jù)相同達(dá)到最小,使用本文提出的FTTO算法在13組數(shù)據(jù)中分類錯誤率最小。并且Keogh團隊公布的使用原始時間序列數(shù)據(jù)的分類錯誤率平均值為0.209 2,使用SEEP算法獲得的分類錯誤率平均值為0.254 0,使用CPA算法獲得的分類錯誤率平均值為0.273 7,使用本文提出的算法FTTO獲得的分類錯誤率平均值為0.175 4,平均分類錯誤率達(dá)到最小。平均分類錯誤率相比原始數(shù)據(jù)的平均分類錯誤率下降0.033 9,整體分類錯誤率明顯下降。

4 結(jié)束語

依據(jù)趨勢轉(zhuǎn)折點在時間序列數(shù)據(jù)中的重要特征,本文提出一種基于數(shù)據(jù)自身趨勢特征提取數(shù)據(jù)轉(zhuǎn)折點的算法(FTTO)。該算法計算簡單,易于實現(xiàn)。通過在UCR時間序列分類數(shù)據(jù)集上與SEEP、CAP和PAA算法對比實驗可以看出,該算法在還原原始序列數(shù)據(jù)時的擬合誤差較小,具有去除干擾噪音數(shù)據(jù)的功能。實驗結(jié)果表明,采用1-NN分類和DTW算法,與SEEP、CAP算法擬合的數(shù)據(jù)和Keogh團隊公布的原始數(shù)據(jù)分類錯誤率相比,FTTO算法整體分類錯誤率最小。

[1] ESLING P,AGON C.Time-series Data Mining[J].ACM Computing Surveys,2012,45(1):11-12.

[2] HU Zhikun,XU Fei,GUI Weihua,et al.Wavelet Matrix Transform for Time-series Similarity Measurement[J].Journal of Central South University of Technology,2009,16(5):802-806.

[3] AGRWAL R,FALOUTSOS C,SWAMI A.Efficient Similarity Search in Sequence Databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms.London,UK:Springer-Verlag,1993:69-84.

[4] RAFIEI D,MENDELZON A O.Querying Time Series Data Based on Similarity[J].IEEE Transactions on Knowledge & Data Engineering,2000,12(5):675-693.

[5] REN J M.Similarity Search over Time Series Data Using Wavelets[C]//Proceedings of the 18th International Conference on Data Engineering.San Jose,USA:IEEE Computer Society Press,2002:212-221.

[6] CHAN K,FU A.Efficient Time Series Matching by Wavelets[C]//Proceedings of the 15th IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,1999:126-133.

[7] KEOGH E J,CHU S,HART D,et al.An Online Algorithm for Segmenting Time Series[C]//Proceedings of IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2002:289-298.

[8] KEOGH E.Exact Indexing of Dynamic Time Warping[C]//Proceedings of the 28th International Conference on Very Large Databases.Hong Kong,China:[s.n.],2002:406-417.

[9] 潘 定,沈鈞毅.時態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)[J].軟件學(xué)報,2007,18(2):246-258.

[10] YI B K,FALOUTSOS C.Fast Time Sequence Indexing for Arbitrary LP Norms[C]//Proceedings of the 26th International Conference on Very Large Data Bases.[S.1.]:Morgan Kaufmann Publishers Inc.,2000:385-394.

[11] KEOGH E,CHAKRABARTI K,PAZZANI M,et al.Dimensionality Reduction for fast Similarity Search in Large Time Series Databases[J].Journal of Knowledge and Information System,2001,3(3):263-286.

[12] PRAT K B,FINK E.Search for Patterns in Compressed Time Series[J].International Journal of Image and Graphics,2002,2(1):89-106.

[13] 詹艷艷,徐榮聰,陳曉云.基于斜率提取邊緣點的時間序列分段線性表示方法[J].計算機科學(xué),2006,33(11):139-142.

[14] 林 意,王智博.基于一階濾波的時間序列分段線性表示方法[J].計算機工程,2016,42(9):151-157.

[15] 周大鐲,李敏強.基于序列重要點的時間序列分割[J].計算機工程,2008,34(23):14-16.

[16] 張 娜,李莉娟.時間序列分段線性表示的幾種算法比較[J].中國西部科技,2009(14):80-81.

[17] CHEN Yanping,KEOGH E.UCR Time Series Classification Archive[EB/OL].[2016-08-07].http://www.cs.ucr.edu/～eamonn/time_series_data/.