時序數據的周期模式發現算法的遞推改進

黃雄波

(佛山職業技術學院 電子信息系,廣東 佛山 528000)

時序數據的周期模式發現算法的遞推改進

黃雄波

(佛山職業技術學院 電子信息系,廣東 佛山 528000)

從時序數據中識別和提取出周期成分對掌握事物的內在發展規律有著重要的現實意義。在諧波分析法的基礎上，提出了一種具有納新機制的時序數據周期模式的遞推發現算法。該算法通過對諧波分析法的傅里葉系數作Taylor級數的展開，得到了一系列相關的冪函數多項式，在此基礎上，基于矩陣數量乘法的規則，將這些多項式解耦為可遞推的表達式，進而推導出一種重復計算量極少的遞推算法。數值實驗驗證了算法的有效性和穩定性，而且該算法在計算成本和計算精度之間還具有良好的伸縮性。

時序數據;周期模式;諧波分析法;遞推

0 引 言

時序數據就是將某一事物現象在不同時刻上的不同取值，按照時間的先后順序排列而成的序列。一般地，時序數據可分解為趨勢項、周期項及隨機項三種成分。其中，趨勢項反映了事物的長期動態過程，周期項反映了事物有規則的重復性變動，而隨機項是屬于具有一定統計規律的無規則變化[1-2]。受地球繞太陽公轉以及地球本身自轉等原因，自然界的事物普遍具有周期特性，據此，從時序數據中識別和提取出周期成分對掌握事物的內在發展規律有著重要的現實意義。

時序數據周期分析的主要任務就是從已有序列中確定周期項的周期長度，并以相關的周期函數加以定量描述。現有的時序數據周期分析方法主要有方差分析、相關分析、諧波分析、小波分析和周期圖分析等方法[3]。近年來，眾多專家學者對時序數據的周期模式發現問題展開了研究，并取得了一系列的成果[4-10]。

鑒于現有的周期模式發現算法均不具有遞推機制，文中在諧波分析法的基礎上，設計實現了一種具有納新機制的時序數據周期模式的遞推發現算法。實驗結果及分析表明，該算法具有較高的計算性能，該算法在計算成本和計算精度之間還具有良好的伸縮性。

1 相關基礎知識

1.1 時序數據的基本模式

時序數據Yt(t=1,2,…,n)的基本結構模式有加法模式、乘法模式和混合模式3種，如式(1)。

(1)

式中，Ht為趨勢項；Pt為周期項；Xt為隨機項。

若時序數據的周期項和隨機項均不隨著趨勢項的增長(衰減)而加劇(減弱)變化，則可選用加法模式來描述時序數據，反之，應選用乘法模式，而混合模式則適用于僅有周期項或隨機項緊隨趨勢項變化的場合。

時序數據的建模過程一般為：把序列數據分解為趨勢、周期和隨機三種成分，然后分別對每種成分進行擬合，最后從式(1)中選取某種合適的模式把這三種擬合結果組合在一起，從而得到時序數據的整體建模函數[11-12]。在實際應用中，趨勢項、周期項及隨機項這三種成分交錯在一起，究竟先分離哪種成分要視具體情況而定，較好的做法是根據各種成分在序列中的輕重地位從重至輕依次分離。這里，將著重對周期成分占優的時序數據進行研究。

1.2 諧波分析法

(2)

根據最小二乘法和三角函數的正交特性[13]，以得到如式(3)所示的各諧波傅里葉系數求解表達式。

(3)

(4)

又因為

(5)

(6)

(7)

把式(5)～(7)代入式(4)，化簡后，有：

(8)

2 周期模式發現算法的遞推改進

隨著時間的推移，時序數據也面臨著數據納新的問題，即不斷地有新的數據補充至原有的序列中。從式(3)中易知，由于各諧波對應的傅里葉系數的求解表達式中均顯式地包含序列長度n，因而在數據納新的過程中，序列長度n不斷地在遞增變化，這就導致了傅里葉系數需要反復地重新計算。為了有效地提升數據納新過程中時序數據周期模式發現的計算效能，有必要對式(3)進行遞推計算的改進。

2.1 算法的推導

(1)a0分項的遞推改進。

記a0(n),a0(n+1)分別為序列長度n及n+1的周期項Pt的平均成分，因為

(9)

故

P1+P2+…+Pn=na0(n)

(10)

而

(11)

把式(10)代入式(11)，便可得到如下所示的遞推表達式。

(12)

(2)ai,bi分項的遞推改進。

記ai(n)和bi(n)為序列長度n的周期項Pt的傅里葉系數，分別對ai(n),bi(n)求解表達式中的正弦、余弦函數作Taylor級數的展開，并寫成矩陣形式。有：

(13)

(14)

根據矩陣數量乘法的規則，式(13)和式(14)可分別化為：

(15)

(16)

η1(n)=[P1+P2+…+Pn],…,ηk+1(n)=[P1+ 22kP2+…+n2kPn]

(17)

μ1(n)=[P1+2P2+…+nPn],…,μk(n)=[P1+22k-1P2+…+n2k-1Pn]

(18)

類似地，記ai(n+1),bi(n+1)為序列長度n+1的周期項Pt的傅里葉系數，又因為

η1(n+1)=η1(n)+Pn+1,…,ηk+1(n+1)=ηk+1(n)+ (n+1)2kPn+1

(19)

μ1(n+1)=μ1(n)+(n+1)Pn+1,…,μk(n+1)=μk(n)+(n+1)2k-1Pn+1

(20)

于是，從式(15)～(20)有：

(21)

從式(21)和式(20)易知，ai(n+1),bi(n+1)雖然不能各自地從ai(n),bi(n)中顯式遞推，但是可以通過對{η1(n),η2(n),…,ηk+1(n)},{μ1(n),μ2(n),…,μk(n)}中的各個分項進行單獨遞推，并把各個遞推結果與相應的系數項(隨序列長度n變化)之積相加，便可快速地求得ai(n+1),bi(n+1),從而也就間接地完成了ai(n),bi(n)到ai(n+1),bi(n+1)之間的遞推。

2.2 算法的設計

綜上所述，可設計如下的時序數據周期模式的遞推發現算法。

輸入：時序數據的周期項Pt，Taylor級數的展開項數m，顯著周期的判別閾值ε；

輸出：時序數據的顯著周期項及對應的傅里葉系數ai,bi。

步驟1：按式(9)、式(17)及式(18)計算已有的n項周期序列Pt的a0(n);η1(n),η2(n),…,ηm(n);μ1(n),μ2(n),…,μm(n)；

步驟2：按式(15)、式(16)計算傅里葉系數ai(n),bi(n)；

步驟4：是否繼續進行數據的納新處理？若選擇繼續，則輸入Pn+1，并跳轉步驟5；否則跳轉步驟6；

步驟5：分別按式(12)、式(19)及式(20)從a0(n);η1(n),η2(n),…，ηm(n);μ1(n),μ2(n),…，μm(n)遞推出

a0(n+1);η1(n+1),η2(n+1),…，ηm(n+1);μ1(n+1),μ2(n+1),…，μm(n+1)。以n+1→n,轉步驟2；

步驟6：算法結束，輸出顯著周期成分及其對應的傅里葉系數。

3 實 驗

為了驗證上述算法的有效性及先進性，文中選取了SIDC(SolarInfluencesDataanalysisCenter)提供的1700年至2000年的平均太陽黑子數來進行周期模式發現的相關實驗，實驗樣本共301個序列數據。實驗的硬件環境為惠普ProDesk490G2MT商用臺式機(CPU:i5-4570 4*3.2GHz;內存4GB;DDR3 1600)，軟件環境及開發工具為Windows8.1+MicrosoftVisualC++2010。實驗的主要目的是考察非遞推算法與遞推算法之間的計算精度及計算效能。

3.1 非遞推算法的實驗結果

表1 非遞推算法的計算耗時 ms

3.2 遞推算法的實驗結果

應用新設計的遞推算法來對上述的太陽黑子數序列進行周期模式發現，并分別用前10項、前15項的Taylor級數進行了2次獨立的遞推計算，相應的實驗結果如表3～5所示(表中m為泰勒級數)。

表2 非遞推算法所求得的各諧波 成分及其貢獻比例

3.3 實驗結果分析

由于諧波Ci的角頻率為iω0，且ω0=2π/n，故諧波Ci對應的周期Ti=2π/(iω0)=n/i。以表2為例，當樣本長度為301時，第30和第27個諧波的貢獻最為顯著，根據301/30≈10,301/27≈11，故有如下結論：太陽黑子數具有10至11年的活動周期，從表2可知，當樣本長度為51、101、151、201及251時上述結論仍然成立，這與其他文獻應用別的周期分析方法所得出的結果是相一致的[14]。

對比表2、表4及表5，當取前10項的Taylor級數進行遞推計算時，其計算誤差隨著遞推步數的增加而增大，特別是遞推至201步后，一些貢獻顯著的諧波也出現了變更(注：經過計算，發生變更的顯著諧波的周期仍然對應著10至11年)；當取前15項的Taylor級數進行遞推計算時，貢獻顯著的諧波成分沒有出現變更，在遞推至301步時，與非遞推的計算結果相比，其計算誤差在5%以內。

表4 用前10項Taylor級數遞推所求得的 各諧波成分及其貢獻比例

表5 用前15項Taylor級數遞推所求得的 各諧波成分及其貢獻比例

圖1是非遞推算法與遞推算法(取前15項的Taylor級數)的計算耗時對比示意圖。

圖1 非遞推算法與遞推算法的計算耗時對比

綜上所述，文中設計的遞推算法具有優秀的計算效能及良好的計算精度。

4 結束語

在時序數據的分析與建模過程中，研究相應的遞推算法有著重要的現實意義。文中基于諧波分析法，設計實現了一種具有遞推計算功能的時序數據的周期模式發現算法。該算法的優點是，在遞推過程中可以增加Taylor級數的項數來提高計算精度，而對應的計算耗時卻沒有顯著增加。

為了強調新近數據的作用，漸漸遺忘陳舊數據的影響，下一步的主要工作有：研究帶有遺忘因子的時序數據的周期模式的遞推發現算法，同時研究有效的積累誤差消除方法，以便更好地提升算法的計算精度。

[1]EndersW.應用計量經濟學:時間序列分析[M].第3版.北京:機械工業出版社,2012．

[2] 王 燕.應用時間序列分析[M].第3版.北京:中國人民大學出版社,2012．

[3] 郭 龍.時間序列數據的周期性研究[D]．成都:電子科技大學，2013．

[4] 邱敦國，楊紅雨.一種基于雙周期時間序列的短時交通流預測算法[J]．四川大學學報:工程科學版，2013，45(5):64-68．

[5] 王紅瑞，劉達通，王 成，等.基于季節調整和趨勢分解的水文序列小波周期分析模型及其應用[J]．應用基礎與工程科學學報，2013，21(5):823-836．

[6] 李曉光，宋寶燕，于 戈，等.基于小波的時間序列流偽周期檢測方法[J]．軟件學報，2010，21(9):2161-2172．

[7]ReschenhoferE，LinglerM.Detectingsynchronouscyclesinfinancialtimeseriesofunequallength[J]．JournalofEmpiricalFinance，2013，24(12):1-9．

[8]WuShujin，ZhuXiaoyu，XiaoYang.Analysisofapproximatelyperiodictimeseries[J]．ChineseJournalofAppliedProbabilityandStatistics，2015，31(2):199-212．

[9]GharehbaghiA，AskP，BabicA.Apatternrecognitionframeworkfordetectingdynamicchangesoncyclictimeseries[J]．PatternRecognition，2015，48(3):696-708．

[10]SuWeiti，PingXiaoou，TsengYi-Ju，etal．Multipletimeseriesdataprocessingforclassificationwithperiodmergingalgorithm[J]．ProcediaComputerScience，2014，37(8):301-308．

[11] 王文舉，張桂喜.經濟預測、決策與對策[M].第2版.北京:首都經濟貿易大學出版社,2013．

[12] 黃雄波.時序數據趨勢項的分段擬合[J]．計算機系統應用，2015，24(2):174-179．

[13] 李慶揚，王能超，易大義.數值分析[M].北京:清華大學出版社,2008．

[14] 唐 潔.功率譜分析方法在周期分析中的應用[J]．陜西理工學院學報:自然科學版，2013，29(5):71-74．

Recursive Improvement of Periodic Pattern Algorithm of Time Series Data

HUANG Xiong-bo

(Department of Electronic Information,Foshan Professional Technical College,Foshan 528000,China)

To identify and extract the periodic components from time series data has important practical significance for the inherent rule of things.Based on harmonic analysis method,a periodic pattern recursive algorithm of time series data with renewal mechanism was proposed.A series of power function polynomial is obtained by the expansion in Taylor series of Fourier transform coefficients.On this basis,an simple data algorithm is deduced by polynomial decomposition method on the account of rules of matrix multiplication.The numerical simulation shows that the proposed algorithm is efficient and stable.This algorithm also has good scalability between computing cost and calculation accuracy.

time series data;periodic mode;harmonic analysis method;recursion

2015-05-14

2015-08-18

時間：2016-01-26

廣東省科技計劃工業攻關項目(2011B010200031)；佛山職業技術學院校級重點科研項目(2011KY006)作者簡介：黃雄波(1975-)，男，博士研究生，副教授，CCF會員，研究方向為時間序列分析及數字圖像處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1520.040.html

TP311

A

1673-629X(2016)02-0047-05

10.3969/j.issn.1673-629X.2016.02.011