黃雄波

(佛山職業(yè)技術(shù)學(xué)院 電子信息系,廣東 佛山 528000)

時(shí)序數(shù)據(jù)的周期模式發(fā)現(xiàn)算法的遞推改進(jìn)

黃雄波

(佛山職業(yè)技術(shù)學(xué)院 電子信息系,廣東 佛山 528000)

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

時(shí)序數(shù)據(jù);周期模式;諧波分析法;遞推

0 引 言

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

時(shí)序數(shù)據(jù)周期分析的主要任務(wù)就是從已有序列中確定周期項(xiàng)的周期長(zhǎng)度，并以相關(guān)的周期函數(shù)加以定量描述?，F(xiàn)有的時(shí)序數(shù)據(jù)周期分析方法主要有方差分析、相關(guān)分析、諧波分析、小波分析和周期圖分析等方法[3]。近年來，眾多專家學(xué)者對(duì)時(shí)序數(shù)據(jù)的周期模式發(fā)現(xiàn)問題展開了研究，并取得了一系列的成果[4-10]。

鑒于現(xiàn)有的周期模式發(fā)現(xiàn)算法均不具有遞推機(jī)制，文中在諧波分析法的基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了一種具有納新機(jī)制的時(shí)序數(shù)據(jù)周期模式的遞推發(fā)現(xiàn)算法。實(shí)驗(yàn)結(jié)果及分析表明，該算法具有較高的計(jì)算性能，該算法在計(jì)算成本和計(jì)算精度之間還具有良好的伸縮性。

1 相關(guān)基礎(chǔ)知識(shí)

1.1 時(shí)序數(shù)據(jù)的基本模式

時(shí)序數(shù)據(jù)Yt(t=1,2,…,n)的基本結(jié)構(gòu)模式有加法模式、乘法模式和混合模式3種，如式(1)。

(1)

式中，Ht為趨勢(shì)項(xiàng)；Pt為周期項(xiàng)；Xt為隨機(jī)項(xiàng)。

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

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

1.2 諧波分析法

(2)

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

(3)

(4)

又因?yàn)?/p>

(5)

(6)

(7)

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

(8)

2 周期模式發(fā)現(xiàn)算法的遞推改進(jìn)

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

2.1 算法的推導(dǎo)

(1)a0分項(xiàng)的遞推改進(jìn)。

記a0(n),a0(n+1)分別為序列長(zhǎng)度n及n+1的周期項(xiàng)Pt的平均成分，因?yàn)?/p>

(9)

故

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

(10)

而

(11)

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

(12)

(2)ai,bi分項(xiàng)的遞推改進(jìn)。

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

(13)

(14)

根據(jù)矩陣數(shù)量乘法的規(guī)則，式(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)為序列長(zhǎng)度n+1的周期項(xiàng)Pt的傅里葉系數(shù)，又因?yàn)?/p>

η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)中顯式遞推，但是可以通過對(duì){η1(n),η2(n),…,ηk+1(n)},{μ1(n),μ2(n),…,μk(n)}中的各個(gè)分項(xiàng)進(jìn)行單獨(dú)遞推，并把各個(gè)遞推結(jié)果與相應(yīng)的系數(shù)項(xiàng)(隨序列長(zhǎng)度n變化)之積相加，便可快速地求得ai(n+1),bi(n+1),從而也就間接地完成了ai(n),bi(n)到ai(n+1),bi(n+1)之間的遞推。

2.2 算法的設(shè)計(jì)

綜上所述，可設(shè)計(jì)如下的時(shí)序數(shù)據(jù)周期模式的遞推發(fā)現(xiàn)算法。

輸入：時(shí)序數(shù)據(jù)的周期項(xiàng)Pt，Taylor級(jí)數(shù)的展開項(xiàng)數(shù)m，顯著周期的判別閾值ε；

輸出：時(shí)序數(shù)據(jù)的顯著周期項(xiàng)及對(duì)應(yīng)的傅里葉系數(shù)ai,bi。

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

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

步驟4：是否繼續(xù)進(jìn)行數(shù)據(jù)的納新處理？若選擇繼續(xù)，則輸入Pn+1，并跳轉(zhuǎn)步驟5；否則跳轉(zhuǎn)步驟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,轉(zhuǎn)步驟2；

步驟6：算法結(jié)束，輸出顯著周期成分及其對(duì)應(yīng)的傅里葉系數(shù)。

3 實(shí) 驗(yàn)

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

3.1 非遞推算法的實(shí)驗(yàn)結(jié)果

表1 非遞推算法的計(jì)算耗時(shí) ms

3.2 遞推算法的實(shí)驗(yàn)結(jié)果

應(yīng)用新設(shè)計(jì)的遞推算法來對(duì)上述的太陽黑子數(shù)序列進(jìn)行周期模式發(fā)現(xiàn)，并分別用前10項(xiàng)、前15項(xiàng)的Taylor級(jí)數(shù)進(jìn)行了2次獨(dú)立的遞推計(jì)算，相應(yīng)的實(shí)驗(yàn)結(jié)果如表3～5所示(表中m為泰勒級(jí)數(shù))。

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

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

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

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

表4 用前10項(xiàng)Taylor級(jí)數(shù)遞推所求得的 各諧波成分及其貢獻(xiàn)比例

表5 用前15項(xiàng)Taylor級(jí)數(shù)遞推所求得的 各諧波成分及其貢獻(xiàn)比例

圖1是非遞推算法與遞推算法(取前15項(xiàng)的Taylor級(jí)數(shù))的計(jì)算耗時(shí)對(duì)比示意圖。

圖1 非遞推算法與遞推算法的計(jì)算耗時(shí)對(duì)比

綜上所述，文中設(shè)計(jì)的遞推算法具有優(yōu)秀的計(jì)算效能及良好的計(jì)算精度。

4 結(jié)束語

在時(shí)序數(shù)據(jù)的分析與建模過程中，研究相應(yīng)的遞推算法有著重要的現(xiàn)實(shí)意義。文中基于諧波分析法，設(shè)計(jì)實(shí)現(xiàn)了一種具有遞推計(jì)算功能的時(shí)序數(shù)據(jù)的周期模式發(fā)現(xiàn)算法。該算法的優(yōu)點(diǎn)是，在遞推過程中可以增加Taylor級(jí)數(shù)的項(xiàng)數(shù)來提高計(jì)算精度，而對(duì)應(yīng)的計(jì)算耗時(shí)卻沒有顯著增加。

為了強(qiáng)調(diào)新近數(shù)據(jù)的作用，漸漸遺忘陳舊數(shù)據(jù)的影響，下一步的主要工作有：研究帶有遺忘因子的時(shí)序數(shù)據(jù)的周期模式的遞推發(fā)現(xiàn)算法，同時(shí)研究有效的積累誤差消除方法，以便更好地提升算法的計(jì)算精度。

[1]EndersW.應(yīng)用計(jì)量經(jīng)濟(jì)學(xué):時(shí)間序列分析[M].第3版.北京:機(jī)械工業(yè)出版社,2012．

[2] 王 燕.應(yīng)用時(shí)間序列分析[M].第3版.北京:中國人民大學(xué)出版社,2012．

[3] 郭 龍.時(shí)間序列數(shù)據(jù)的周期性研究[D]．成都:電子科技大學(xué)，2013．

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

[5] 王紅瑞，劉達(dá)通，王 成，等.基于季節(jié)調(diào)整和趨勢(shì)分解的水文序列小波周期分析模型及其應(yīng)用[J]．應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào)，2013，21(5):823-836．

[6] 李曉光，宋寶燕，于 戈，等.基于小波的時(shí)間序列流偽周期檢測(cè)方法[J]．軟件學(xué)報(bào)，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] 王文舉，張桂喜.經(jīng)濟(jì)預(yù)測(cè)、決策與對(duì)策[M].第2版.北京:首都經(jīng)濟(jì)貿(mào)易大學(xué)出版社,2013．

[12] 黃雄波.時(shí)序數(shù)據(jù)趨勢(shì)項(xiàng)的分段擬合[J]．計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24(2):174-179．

[13] 李慶揚(yáng)，王能超，易大義.數(shù)值分析[M].北京:清華大學(xué)出版社,2008．

[14] 唐 潔.功率譜分析方法在周期分析中的應(yīng)用[J]．陜西理工學(xué)院學(xué)報(bào):自然科學(xué)版，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

時(shí)間：2016-01-26

廣東省科技計(jì)劃工業(yè)攻關(guān)項(xiàng)目(2011B010200031)；佛山職業(yè)技術(shù)學(xué)院校級(jí)重點(diǎn)科研項(xiàng)目(2011KY006)作者簡(jiǎn)介：黃雄波(1975-)，男，博士研究生，副教授，CCF會(huì)員，研究方向?yàn)闀r(shí)間序列分析及數(shù)字圖像處理。

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