基于一次指數預測算法的動態規劃分割算法

◇西南石油大學 趙春蘭 羅 銀 何 婷

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

1 引言

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

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

2 相關原理

2.1 時間序列分割

2.2 一次指數平滑法

2.3 時間序列分割的評價指標

3 基于一次指數平滑預測的動態規劃分割算法

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

圖1 基于一次指數平滑預測的動態規劃分割算法思維圖

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

3.2 動態規劃分割

3.3 回溯

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

4 實驗分析

4.1 多元合成數據集實驗

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

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

圖3 分割結果

4.2 氣象數據實驗

本文以Guo等人[1]和 Sun等人[3]論文里用的多元氣象時間序列，阿雷西博地區（Arecibo）2013年10月1日00:00到2013年10月2日00:00監測結果統計數據作為原始數據，以風速、風向、陣風為初始評價指標，如表1所示。

表1 阿雷西博地區（Arecibo）2013年10月1日00:00到2013年10月2日00:00監測數據

在該實驗中，經過z_score標準化處理后，令分割階數的最大值，應用該分割方法對數據集進行分割，獲得時的分割情況。當分割階數取不同值時，對應的數值變化如圖4（a）所示。

圖4 分割結果

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

表2 三種分割方法結果對比

5 結束語

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