,,,

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

0 概述

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

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

本文給出一種提取時間序列數(shù)據(jù)趨勢轉折點算法(FTTO)。首先定義時間序列數(shù)據(jù)4個相鄰數(shù)據(jù)點的運算,隨后討論運算結果P并且對P值小于零和等于零2種出現(xiàn)趨勢轉折點的情況分別進行討論,然后提取原始數(shù)據(jù)中上升、下降和平緩3種基本趨勢轉折點。最后將相鄰2個基本趨勢轉折點中間的數(shù)據(jù)做坐標旋轉變換,對旋轉變換得到的新的時間序列數(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},趨勢轉折點集合為{xt1,xt2,…,xti,…,xtn},其中,xt1和xtn分別為時間序列的起始點和終點。其分段線性表示為:

XPLR= {,…,,…,

}

(3)

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

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

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

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

{(xi

(4)

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

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

2 趨勢轉折點提取算法與分析

2.1 提取趨勢轉折點算法

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 當P<0時的情況

表2 當P=0時的情況

2.2 拐點提取

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

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

圖7 坐標轉換前原始數(shù)據(jù)示意圖

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

圖8 坐標旋轉轉換后數(shù)據(jù)示意圖

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

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

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

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

Begin

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

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

se=0;/*保存當前趨勢轉折點時間索引*/

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

for(i=1;i

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

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

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

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

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

if(se-fi>Q)

FTTO-G(fi,se);

/*在提取拐點后,更新fi坐標索引*/

fi=se;

Xc.add(xn)

End

FTTO方法描述如下:

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

輸出如果輸入數(shù)據(jù)中存在趨勢轉折點,則Xc集合中添加轉折點,如果輸入數(shù)據(jù)中不存在趨勢轉折點,則不向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方法描述如下:

輸入前一個趨勢轉折點時間坐標索引fi,當前趨勢轉折點時間坐標索引se

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

Begin

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

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

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

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

for(int??j=0;j

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

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

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

End

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

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

3 對比實驗

3.1 對比擬合誤差

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

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

(5)

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

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

文獻[16]提出的CPA算法在提取分段點過程中具有良好效果。首先依據(jù)各個數(shù)據(jù)點在局部范圍內的偏離程度定義了時間序列數(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對比結果可以看出,本文提出的FTTO算法能夠提取數(shù)據(jù)主要趨勢轉折點達到保留原始數(shù)據(jù)的趨勢信息的目的。SEEP與CPA算法均存在遺漏提取分段點的情況,PAA算法雖然保存了原始信息的整體趨勢特征,但是丟失了每個窗口內的趨勢信息。

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

表3 擬合誤差對比結果

從表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距離度量情況下的分類錯誤率。對比結果如表4所示。在表4中,A列是Keogh團隊公布的在原始數(shù)據(jù)上的分類錯誤率。各個數(shù)據(jù)的壓縮率同表3中各個數(shù)據(jù)的壓縮率相等。表4中下劃線代表各行中的最小數(shù)據(jù)。

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

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

4 結束語

依據(jù)趨勢轉折點在時間序列數(shù)據(jù)中的重要特征,本文提出一種基于數(shù)據(jù)自身趨勢特征提取數(shù)據(jù)轉折點的算法(FTTO)。該算法計算簡單,易于實現(xiàn)。通過在UCR時間序列分類數(shù)據(jù)集上與SEEP、CAP和PAA算法對比實驗可以看出,該算法在還原原始序列數(shù)據(jù)時的擬合誤差較小,具有去除干擾噪音數(shù)據(jù)的功能。實驗結果表明,采用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)技術[J].軟件學報,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].計算機科學,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/.