基于時間序列趨勢轉折點的分段線性表示

摘 要:在充分利用時間序列時變特征的基礎上，以有效地提取序列中的趨勢和壓縮原始數據為目標，提出了基于時間序列趨勢轉折點的分段線性表示方法。該方法在有效地提取序列中的趨勢和壓縮原始數據的同時，能夠隨著時間序列長度的增長對序列進行劃分，具有高效、實現方法簡便、效果直觀的優點，對于不同領域的數據適應性良好。

關鍵詞:時間序列; 分段線性表示; 趨勢轉折點; 擬合誤差

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

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

doi:10.3969/j.issn.1001-3695.2010.06.022

PLR based on time series tendency turning point

SHANG Fu-hua， SUN Da-chen

(School of Computer Information Technology， Daqing Petroleum University， Daqing Heilongjiang 163318， China)

Abstract:Based on time series time-variable characteristic， aimed at extracting the tendency in the time series and compres-sing primary data， introduced a method named PLR based on time series tendency turning point. This method is good at extracting the tendency in the series and compressing primary data， at the same time， it can partition time series as the series growing and has the merit of easily being carried out， remarkable result and suitable ability for the data from different field.

Key words:time series; PLR(piecewise linear representation); tendency turning point; fitting error

時間序列是按時間順序排列的一系列觀測數據，其觀測值按固定的時間間隔采樣。時間序列廣泛存在于商業、經濟、科學工程和社會科學等領域，如股票價格數據、銷售數據、圖像數據、影像數據、手寫體數據、腦掃描數據等都可以看做是時間序列數據[1]。這些數據中隱藏著大量重要的信息，反映的大都是某個待觀察過程在一定時期內的狀態或表現[2]。

面對海量數據，直接去操作一個高維的數據空間是很困難的。因此，需要研究合適的數據表示形式，進行維度約簡，在高效、方便的表示形式上進行有效的挖掘[3]。

幾種主要技術，如離散傅里葉變換、小波變換和奇異值分解等是精確的方法。為提高相似匹配效率，也有學者提倡使用近似方法，可采用有損耗的數據壓縮模式，如分段線性表示(PLR)方法、序列離散化、字符串匹配方法等[3]。其中，分段線性表示方法利用直線段來近似表示時間序列的局部波動，具有時間多解析，而且支持快速的相似性檢索和新的距離，是一種很好的數據壓縮和消除噪聲的方法[4]，而且多數的PLR表示方法支持時間序列的動態增量更新。時間序列的PLR表示方法已經在下列一些領域得到應用[5]:a)快速的相似性搜索;b)支持新的距離度量，包括模糊查找、加權序列、DTW距離，信息反饋等;c)支持文本和數據序列;d)支持新的聚類和分類算法;e)支持奇異檢測。

目前的PLR算法對原始數據分段均采用單一的擬合誤差作為閾值，分段效果不太理想[6]，算法本身的通用性、時間復雜度等性能都有待提高;而時間序列相似性研究中，有效的數據表示是提高相似搜索效率和減少搜索時間的關鍵[7]。由于來自不同領域的時間序列數據具有明顯的數據特征差異，同一時間序列數據在不同的時間段上呈現出來的數據特征也不相同，這些均可看做是數據的波動特征，而波動特征是時間序列趨勢變化的轉折點和時間序列隨時間變化的表現形式，能更好地代表這個時間序列的本質特征。因此，本文認為將這些轉折點作為PLR方法中提取分段點的依據，來對序列數據進行分段線性表示，更能反映時間序列的變化趨式，同時，也能達到對時間序列進行有效壓縮的目的。

1 時間序列的分段線性表示

Keogh在文獻[5]中提出了一種時間序列分段線性表示方法，這種方法能夠對時間序列進行有效的壓縮，在一定程度上能反映時間序列的變化趨式，因而在時間序列數據挖掘中得到大量的應用。在Keogh的分段線表示方法中，分段近似的目標是使原時間序列與其線性近似表示之間的殘差平方和最小，在這種目標函數的限制下，不能保證時間序列的每一分段內只具有一種基本趨勢，也就是只具有上升、下降或平穩中的一種，因此將導致時間序列的某些點的基本趨勢被錯誤提取[8]。

大量的學者提出了很多、新的時間序列的分段線性表示方法，主要有基于特征點的分段線性表示方法[6]、基于時態邊緣算子的時間序列分段線性表示[4]、基于重要點的時間序列趨勢特征提取的方法[8]等。在這些研究方法中都表明，在進行分段線性表示原始時間序列數據的同時，原序列中的一些重要數據點是必須被保留的，如達到一定變化幅度的極值點、邊緣幅度變化劇烈的點或是局部極值點和拐點，因為這些數據點保存著時間序列變化的主要特征模式。而在這些研究中，位于相鄰的重要數據點之間的變化趨勢卻有待進一步細化，也就是必須找出趨勢變化的轉折點，這些轉折點是上升、下降或平穩趨勢的端點，而這些轉折點間的數據可以通過直線插補的方法來代替，從而完成數據壓縮的任務。因此，本文提出了基于時間序列趨勢轉折點的分段線性表示方法，該方法可以全面地提取出時間序列中趨勢變化的轉折點。

2 基于時間序列趨勢轉折點的分段線性表示

2.1 時間序列趨勢轉折點

時間序列趨勢轉折點主要體現在以下的兩種情況:

a)波動幅度達到一定程度的極值點，也就是幅度變化劇烈且相鄰的極值點。相關文獻已經證實了極值點帶有較多的信息[6，8]。

對于波動幅度達到一定程度的極值點的判斷，依據文獻[6]中的定義1，確定特征點的方法，給定常數R和時間序列{X=(v1，t1)，…，(vn，tn)}，如果Xm是一個波動幅度達到一定程度的極值點，應滿足如下條件:

(a)它必須是時間序列的一個極值點，X1和Xn除外。

(b)如果Xm >Xm-1，則Xm/Xm-1>R必須成立;否則，如果XmR必須成立。

通過以上方法得到的時間序列中的數據點代表了時間序列的變化趨勢，是本文尋找的趨勢變化轉折點中的一種。

b)短時間大波動數據點，也就是波動幅度達到一定程度的相鄰點，并且這些點不是極值點。

對于短時間內大波動時間序列數據的判斷:

假設當前點的值與其直接相鄰的前一個點的值相減的絕對值為Q，當前點的值與其直接相鄰的下一個點的值相減的絕對值為P，當Q不為0時，如果P/Q>K或P/Q<1/K，則認為是短時間內大波動數據，K為一個指定的數據;當Q為0且P不為0時，則也認為是短時間內大波動數據，如圖1所示。

a、b、c位置相鄰的三點:Q=|b-a|，P=|b-c|，滿足上述條件時，a、b、c三點就是短時間大波動的數據點。其中b是這種變化趨勢的轉折點;而與b相類似的這種變化趨勢的轉折點就是本文尋找的另一種趨勢變化轉折點。

通過以上兩種方法確定的時間序列中的數據點，代表了時間序列的變化趨勢，這里稱之為時間序列的趨勢轉折點。

通過第一種方法得到的趨勢轉折點，有效地反映了時間序列在相鄰的局部極值點之間的變化趨勢;而通過第二種方法得到的趨勢轉折點，則有效地反映了時間序列在相鄰的非局部極值點之間的變化趨勢，從而完成了用兩種尺度來描述時間序列變化趨勢的任務;更為重要的是，以趨勢變化轉折點來反映時間序列的變化特征，充分利用了時間序列數據自身的時變特征，為PLR方法中分段點的選擇提供了理論依據。

2.2 基于趨勢轉折點的分段線性表示

通過2.1節中的兩種方法得到時間序列的趨勢轉折點，在這些相鄰的點之間進行直線插補，就得出了本文提出的基于時間序列趨勢轉折點的分段線性表示。其算法步驟如下:

a)對原始時間序列進行掃描。在這一過程中，記錄原始時間序列的趨勢轉折點，即波動幅度達到一定程度的極值點和短時間大波動的非極值數據點。

b)對于每一對趨勢轉折點進行直線插補，以這樣的直線代替原來的曲線數據。

在充分利用了時間序列數據自身的時變特征的基礎上，本方法有效地對時間序數據進行了維數的約簡，是一種支持時間序列動態增長的方法。本方法還具有實現方法簡便、直觀和運算效高的優點。

3 實驗

3.1 實驗數據

本文中的數據集選擇來自不同領域的時間序列數據集:海洋溫度數據ocean、油田測井數據中的自然伽碼數據GR和語音數據speech。

3.2 實驗方法

本文選擇兩種主要的時間序列線性分段算法作為比較對象:a)基于PAA(piecewise aggregate approximation)的分段線性表示[9，10];b)基于特征點的分段線性表示[6]。

在基于PAA的分段線性表示算法中，用長度相同的時間窗口分割時間序列，每個窗口內的時間序列用窗口內數據值的平均值來表示，這里的輸入參數為窗口的長度。PAA方法可以使用更為靈活的距離度量，包括加權Euclidian距離、DTW的精確索引，而且PAA允許執行比索引項更短的查詢，這種能力是DFT、DTW和SVD所不具備的。從可以使用的距離度量、性能和效果的綜合評價來看，以上所提到的方法中，在多數情況下PAA是較優的方法[11]，所以本文選擇基于PAA的分段線性表示算法作為比較的對象之一。

在基于特征點的分段線性表示算法[6]中，當相鄰的局部極值點達到一定的波動幅度后，就被定義為特征點，在這些相鄰的特征點之間進行直線擬合，就得到了這條時間序列數據基于特征點的分段線性表示，這里命名為PLR_CE。本文中提出的趨勢轉折點在包括基于特征點的分段線性表示算法[6]中的特征點的同時，還包括時間序列中的相鄰數據變化幅度達到一定幅度的非局部極值點，所以本文選擇基于特征點的分段線性表示算法作為另一個比較的對象。本文提出的方法，這里命名為PLR_TP。

在本文提出的分段線性表示方法中，對于每一個分段中的所有點用一條連接兩個端點的直線所代替，盡管這條直線與這些點較為接近，但存在誤差。這里定義第i段上的誤差為:在同一時刻，擬合直線上的對應點的值與原曲線上對應點的值相減，得出對應點的誤差e，將這些誤差e取平方后再相加，得出代數和Ei;對于分成多段的時間序列，每一段上的誤差相加求和，再取它的平方根，而后再除以原時間序列的長度，就得出了整條時間序列的誤差E，這是衡量維數約簡后的序列與原時間序列擬合效果的重要標準。

在本文所選擇的數據集上，驗證各種算法的運行狀況，比較三種算法對于每一種數據的表示效果。

3.2.1 PLR_TP的適應能力

對來自不同領域的三種數據集中的每一種數據集，運用本文提出的算法，通過對算法中波動點的波動幅度的調整，在一定的擬合誤差的限制條件下，求出對于同一時間序列整體變化特征的體現效果，并進行以下實驗結果的對比:

a)對于長度為1 020的語音數據speech，原序列曲線和擬合后的序列曲線如圖2所示。

圖2(a)為原序列的曲線，擬合后的序列曲線如圖2(b)的曲線。圖中符號o是本文算法中提取出的有效波動點，兩個相鄰符號o之間為直線插補后的直線。

原時間序列長度為1 020，時間序列約簡后的長度為245，而擬合誤差為7.340 6。

b)對于長度為1 001的海洋溫度數據ocean，原序列曲線和擬合后的序列曲線如圖3所示。

圖3(a)為原序列的曲線，擬合后的序列曲線如圖3(b)的曲線。圖中符號o是本文算法中提取出的有效波動點，兩個相鄰符號o之間為直線插補后的直線。

原時間序列長度為1 001，時間序列約簡后的長度為207，而擬合誤差為0.003 4。

c)對于長度為1 000的油田測井數據中的自然伽碼數據GR，原序列曲線和擬合后的序列曲線如圖4所示。

圖4(a)為原序列的曲線，擬合后的序列曲線如圖4(b)的曲線。圖中符號o是本文算法中提取出的有效波動點，兩個相鄰符號o之間為直線插補后的直線。

原時間序列長度為1 000，時間序列約簡后的長度為96，而擬合誤差為0.036。以上實驗結果的對比數據如表1所示。

表1 實驗結果對比

數據原序列長度序列約簡后的長度擬合誤差

speech1 0202457.340 6

ocean1 0012070.003 4

GR1 000960.036

在時間序列表示過程中，整條序列的擬合誤差說明了經過處理后的序列與原序列之間的差別程度，而這種誤差是必然存在的。當擬合誤差過大，說明這種序列表示某些趨勢被錯誤提取了;而擬合誤差過小，經過處理后的序列的長度必然與原序列的長度接近，達不到有效壓縮原序列的目的。

通過以上的實驗結果對比，可以得出本算法具有很強的靈活性，對不同領域的時間序列數據均能達到有效的維數約簡和表示原時間序列的目標。

3.2.2 相同的壓縮率下，比較三種算法的擬合誤差

由于語音數據speech和海洋溫度數據ocean在序列變化上差別較大，這里分別選用這兩種數據作為這三種算法比較過程中的驗證數據。

對于ocean和speech序列，經過PAA算法壓縮后的擬合圖如圖5所示。

圖5(a)的曲線為ocean數據，維數約簡后的點數為202;整條曲線的擬合誤差為0.002 2。

圖5(b)的曲線為speech數據，維數約簡后的點數為205;整條曲線的擬合誤差為12.220 2。

對于ocean和speech序列，經過本文提出的算法(PLR_TP)壓縮后的擬合如圖6所示。

圖6(a)的曲線為ocean數據，時間序列約簡后的長度為207;擬合誤差為0.003 4。

圖6(b)的曲線為speech數據，時間序列約簡后的長度為211;擬合誤差為8.292 0。

對于ocean和speech序列，經過基于波動極值點的算法(PLR_CE)壓縮后的擬合如圖7所示。

圖7(a)的曲線為ocean數據，時間序列約簡后的長度為154;擬合誤差為0.156 5。

圖7(b)的曲線為speech數據，時間序列約簡后的長度為198;擬合誤差為80 720.645 0。

在PAA算法中，沒有考慮到時間序列中趨勢變化的轉折點，分段點的選取沒有依據，雖然方法簡單，但對時間序列趨勢起到了平緩的作用，不能有效提取時間序列中趨勢變化的轉折點。在PLR_CE算法中，只考慮到了時間序列趨勢變化轉折點中的極值點，而沒有考慮到非極值點的變化，不但序列的擬合誤差較大，而且對于序列壓縮程度的調整也不夠靈活;在本文提出的PLR_TP算法中，由于考慮到了時間序列趨勢變化的所有情況，對于趨勢變化的轉折點，即上升、下降或平穩趨勢的端點，進行了有效的提取，達到了良好的效果。

4 結束語

本文充分利用時間序列中的時變特征來提取時間序列中的趨勢轉折點，并以這些趨勢轉折點作為時間序列在PLR方法中的分段點來對時間序列數據進行分段線性表示。針對來自不同領域的數據，通過與已有算法相對比，進行了大量的實驗，實驗結果證明本文提出的算法在反映時間序列變化趨式的同時，達到了有效壓縮時間序列數據的目的。本文提出的方法還具有實現方法簡便、效果直觀，對不同種類的數據具有一定的適應能力;同時支持時間序列的動態增長。

參考文獻:

[1]賈澎濤， 林衛， 何華燦. 時間序列的自適應約束分段

線性表示[J]. 計算機工程與應用，2008，44(5):10-13.

[2]黃書劍. 時序數據上的數據挖掘[J]. 軟件學報，2005，15(1):1-8.

[3]潘定， 沈鈞毅. 時態數據挖掘的相似性發現技術[J].軟件學報，2007，18(2): 246-258.

[4]肖輝， 馬海兵， 龔薇. 基于時間邊緣算子的時間序列分段線性表示[J]. 計算機工程與應用，2008，44(9):156-159.

[5]KEOGH E. A fast and robust method for pattern matching in time series databases [C]//Proc of the 9th International Conference on Tools with Artificial Intelligence.1997:578-584.

[6]喻高瞻， 彭宏， 胡勁松，等.時間序列的分段線性表示[J].計算機應用與軟件， 2007，24(12):17-18.

[7]楊治明， 王曉蓉， 游明英，等.時間序列分段線性表示及相似性算法研究[J]. 微型計算機信息，2007，23(21):204-206.

[8]周黔， 吳鐵軍. 基于重要點的時間序列趨勢特征提取方法[J]. 浙江大學學報:工學版，2007，41(11):1782-1787.

[9]KEOGH E J， CHAKRABARTI K， PAZZANI M，et al.Dimensionality reduction for fast similarity search in large time series databases [J].Knowledge Information Systems ，2001，3(3):263-286.

[10]YI B K，FALOUSTSOS C. Fast time sequence indexing for arbitrary Lp norms[C]//Proc of the 26th International Conference on Very Large Data Bases.San Francisco: Morgan Kaufmann Publishers Inc，2000:385-394.

[11]潘定. 持續時態數據挖掘及其實現機制[M]. 北京: 經濟科學出版社，2008.

[12]PERNG C S， WANG Hai-xun， ZHANG S R ， et al. Landmarks: a new model for similarity-based pattern querying in time series databa-ses[C]//Proc of the 16th International Conference on Data Enginee-ring. Washington DC:IEEE Computer Society，2000:33-42.