基于一次指數(shù)預(yù)測算法的動態(tài)規(guī)劃分割算法

◇西南石油大學(xué) 趙春蘭 羅 銀 何 婷

時間序列分割在變異點檢測、變化趨勢檢測及數(shù)據(jù)預(yù)處理等方面都具有重要作用。針對經(jīng)典動態(tài)規(guī)劃分段算法未考慮時間序列數(shù)據(jù)之間的相互影響，提出一種基于一次指數(shù)平滑預(yù)測算法和動態(tài)規(guī)劃算法相結(jié)合的多元時間序列分割方法。利用一次指數(shù)平滑預(yù)測算法對所有多元時間序列分割片段進(jìn)行預(yù)測，計算分割代價；再根據(jù)分割代價，運用動態(tài)規(guī)劃算法對多元時間序列數(shù)據(jù)進(jìn)行分割，得到全局最優(yōu)的分割結(jié)果。對仿真多元時間序列數(shù)據(jù)進(jìn)行分割，將新方法結(jié)果與已有算法結(jié)果進(jìn)行比較，新方法分割度量值為0.0155，較已有算法減少了0.0293，說明該分割方法得到的分割結(jié)果有較高的準(zhǔn)確度。

1 引言

時間序列數(shù)據(jù)是指在一定時間段內(nèi)按照時間先后順序排列的由時間和所對應(yīng)的觀察值所組成的有序數(shù)據(jù)集，廣泛存在于農(nóng)業(yè)、工業(yè)、醫(yī)學(xué)、氣象、金融、交通、通信等重要領(lǐng)域[1-4]。時間序列分割算法可以作為數(shù)據(jù)預(yù)處理的一個子程序，可以為后面的數(shù)據(jù)挖掘提供巨大便利，還可以讓分析者得到更精確的分析結(jié)果[5-7]。

故本文在經(jīng)典的動態(tài)規(guī)劃算法上進(jìn)行改進(jìn)，考慮時間序列數(shù)據(jù)具有動態(tài)性、連續(xù)性的特點，在已有的多元時序數(shù)據(jù)的基礎(chǔ)上，使用一次指數(shù)平滑預(yù)測算法來預(yù)測下一時刻的數(shù)據(jù)，并計算預(yù)測值與實際值之間的預(yù)測誤差，根據(jù)分割誤差計算分割代價，再使用動態(tài)規(guī)劃算法根據(jù)分割代價選擇分割點。

2 相關(guān)原理

2.1 時間序列分割

2.2 一次指數(shù)平滑法

2.3 時間序列分割的評價指標(biāo)

3 基于一次指數(shù)平滑預(yù)測的動態(tài)規(guī)劃分割算法

為了實現(xiàn)對多元時間序列的分割，本文首先根據(jù)一次指數(shù)平滑預(yù)測算法計算所有片段的誤差；然后，對時間序列數(shù)據(jù)進(jìn)行動態(tài)規(guī)劃分割。該分割方法具體實現(xiàn)過程如圖1所示。

圖1 基于一次指數(shù)平滑預(yù)測的動態(tài)規(guī)劃分割算法思維圖

3.1 利用一次指數(shù)平滑法計算所有片段的誤差

3.2 動態(tài)規(guī)劃分割

3.3 回溯

在計算得到了所有分割片段的最優(yōu)分割的分割代價及其分割邊界后，根據(jù)施瓦茨的貝葉斯信息準(zhǔn)則[9]，通過回溯確定該多元時間序列最優(yōu)的分割階數(shù)及分割邊界。

4 實驗分析

4.1 多元合成數(shù)據(jù)集實驗

由模型可知，生成的5維時間序列由3個子片段構(gòu)成，實際分段位置為40、100、150，其中150是最后一個時間點。生成的5維時間序列數(shù)據(jù)集及實際分段位置如圖2所示。

圖2 生成的5維時間序列及其實際分段位置

圖3 分割結(jié)果

4.2 氣象數(shù)據(jù)實驗

本文以Guo等人[1]和 Sun等人[3]論文里用的多元氣象時間序列，阿雷西博地區(qū)（Arecibo）2013年10月1日00:00到2013年10月2日00:00監(jiān)測結(jié)果統(tǒng)計數(shù)據(jù)作為原始數(shù)據(jù)，以風(fēng)速、風(fēng)向、陣風(fēng)為初始評價指標(biāo)，如表1所示。

表1 阿雷西博地區(qū)（Arecibo）2013年10月1日00:00到2013年10月2日00:00監(jiān)測數(shù)據(jù)

在該實驗中，經(jīng)過z_score標(biāo)準(zhǔn)化處理后，令分割階數(shù)的最大值，應(yīng)用該分割方法對數(shù)據(jù)集進(jìn)行分割，獲得時的分割情況。當(dāng)分割階數(shù)取不同值時，對應(yīng)的數(shù)值變化如圖4（a）所示。

圖4 分割結(jié)果

在Guo等人[1]的論文中，使用基于貝葉斯信息準(zhǔn)則的動態(tài)規(guī)劃分割對該多元氣象數(shù)據(jù)進(jìn)行分割，其最優(yōu)分割階數(shù)為2，分割點位置在第134個時間點；在Sun等人[3]的論文中，使用基于動態(tài)因子模型的多元時間序列分割方法對相同多元氣象數(shù)據(jù)進(jìn)行了分割，其預(yù)設(shè)分割階數(shù)為2時的分割點在第133個時間點處。以上兩種分割方法的分割結(jié)果與本文提出分割方法的結(jié)果對比如表2所示。本文提出的分割算法與這兩種分割方法得到的分割結(jié)果相似，由此可以看出，本文提出的基于一次指數(shù)平滑預(yù)測的動態(tài)規(guī)劃分割算法適用于分割多元時間序列數(shù)據(jù)。對氣象數(shù)據(jù)進(jìn)行分段，能夠?qū)Σ煌瑫r段的氣象數(shù)據(jù)進(jìn)行比較，使數(shù)據(jù)的分析更加全面、直觀，有助于深化對氣象變化規(guī)律的認(rèn)識，使氣象服務(wù)更加精準(zhǔn)，有效減輕由氣象災(zāi)害帶來的損失。

表2 三種分割方法結(jié)果對比

5 結(jié)束語

本文在已有的經(jīng)典動態(tài)規(guī)劃分段的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一次指數(shù)滑動預(yù)測算法和動態(tài)規(guī)劃算法相結(jié)合的多元時間序列分割方法。首先，使用一次指數(shù)平滑預(yù)測算法對數(shù)據(jù)進(jìn)行預(yù)測并計算其分割代價；然后，根據(jù)分割代價使用動態(tài)規(guī)劃算法找出使得全局分割代價最小的分割結(jié)果。該方法考慮到了時間序列是一個連續(xù)的、動態(tài)的過程，下一個時刻的數(shù)據(jù)會受到前一時刻數(shù)據(jù)的影響，且常常是多維的，而一次指數(shù)滑動預(yù)測算法得到的預(yù)測值包含了時間序列中全部的歷史數(shù)據(jù)信息，且可以對多維時序數(shù)據(jù)進(jìn)行預(yù)測，使得預(yù)測結(jié)果具有良好的適應(yīng)性。同時，基于動態(tài)規(guī)劃算法的分割能夠根據(jù)分割代價求得多元時間序列數(shù)據(jù)的全局最優(yōu)的分割邊界。