基于多目標演化算法和改進概率分類的重尾時間序列預測

鄒小云 林文學

1(湖北職業技術學院科研處 湖北 孝感 432000)2(湖北職業技術學院繼續教育學院 湖北 孝感 432000)

0 引 言

隨著互聯網和計算機領域的普及和廣泛應用，許多應用領域不斷地產生新的數據流，如金融市場[1]、視頻直播、語音通話和安全監控系統[2]等。數據流有別于傳統的靜態數據，所以傳統數據挖掘技術無法直接用來分析數據流。數據流分析逐漸成為了數據挖掘領域的研究熱點，頻繁模式挖掘[3]、高效用模式挖掘[4]、概念漂移數據分類[5]、數據流異常檢測是其中的重點方向。數據流分類方法要求時間序列的主要特征都出現后才能分類，但在天氣預報、金融市場行情、網絡安全等應用場景中，如果能盡早預測出數據流的趨勢，能夠為決策者帶來巨大的效益。

為了在獲得部分特征的情況下對整個時間序列進行提前預測，Alonso等[6]首次提出了時間序列早期分類的概念，利用基于謂詞的分類器結合boosting算法可以達到早期分類的目的，但該方法的基分類器訓練需要多次掃描樣本。時間序列普通分類問題和早期分類問題之間的差別在于，前者的目標是最大化預測準確率，而后者存在預測準確率和早期性(時間提前量)兩個沖突的目標。時間序列早期分類算法[7-8]主要分為兩個類型：基于Shapelet的分類算法通過搜索時間序列中的Shapelet特征來判斷樣本的分類[9-10]；集成多個分類器評估不同時間戳的預測可靠性，確定預測分類的有效性。

在時間序列早期分類的問題中，早期性和分類準確率是兩個沖突的目標，目前的主要方法是將這兩個目標組合為一個總目標，再通過群體智能技術計算總目標的Pareto最優解[11]。如果使用30%的序列可獲得80%的準確率，或者使用50%的序列可獲得90%的準確率，難以判斷這兩種情況的優劣。在不同的應用場景下，對早期性和準確率兩個目標的要求不同，如安全領域需要盡早檢測出危險，而天氣預報需要在指定天數前盡可能準確地預測出天氣。現有的方法一般通過設置體現偏好的目標重要性參數來調節分類模型，但這種方法需要獲取后驗信息，并通過多次運行分類程序才能完成對參數的調節，顯然無法適用于實時數據流預測的情況。

針對上述問題，本文將早期性和分類準確率作為兩個獨立的目標，采用演化算法同時優化兩個目標，給出不同時間戳的預測準確率和早期性結果，供用戶根據應用場景自行選擇。此外，針對時間序列的重尾分布特點，對高斯過程分類進行了修改，提高對重尾分布時間序列的分類準確率。

1 時間序列預測算法設計

1.1 問題模型

首先給出時間序列預測問題的相關定義。

定義1一個長度為L的時間序列定義為：

TS={(ti,xi)|i=1,2,…,L}

(1)

定義2從時間t截斷的時間序列定義為TSt，記為TSt={(ti,xi)|i=1,2,…,t}。

基于定義1和定義2，給出時間序列預測問題的定義。

定義3假設一個標記時間序列的訓練集為X={(TS1,CL1),(TS2,CL2),…,(TSn,CLn)}，其中：TSi為時間序列；CLi為對應的類標簽。時間序列預測分類問題定義為：根據一部分時間序列TSt*建立從時間序列到類標簽的映射，并能夠盡早預測出新到達樣本的類標簽。

1.2 時間序列早期分類的優化方法設計

本文的目標是獲得一個集合{((h1,h2,…,hL),sγ1),((h1,h2,…,hL),sγ2),…,((h1,h2,…,hL),sγg)}，其中：{h1,h2,…,hL}為分類器序列；sγi為分類器對應的觸發函數；{sγ1,sγ2,…,sγg}為優化的觸發函數集。

本文方法主要分為3個步驟：訓練概率分類器集，選擇指定的觸發函數，優化選擇的觸發函數集。

1.3 訓練分類器

首先訓練一個分類器集，負責預測每個時間戳樣本的類標簽，圖1是訓練分類器的主要流程。在訓練時間戳t的分類器之前，提取X的所有時間序列，然后在時間戳t截斷序列。時間戳t可以是絕對時間，也可以是序列長度的百分比。接著選擇一個度量指標評估時間序列之間的距離，再組成一個距離矩陣。

圖1 分類器訓練程序的流程

不同的學習算法對輸入數據的格式具有特定要求，動態時間歸整(Dynamic Time Warping, DTW)采用動態規劃方法來進行時間規整的計算，尤其適用于不同長度、不同節奏的時間序列，所以本文采用DTW度量時間序列之間的距離。采用改進的貝葉斯分類器輸出時間戳t的樣本關于每個類的隸屬度。

1.4 定義觸發函數

圖2 時間序列預測分類的流程圖

圖2中觸發函數的輸出為0或者1。如果觸發函數判斷預測結果的可靠度高，則選擇當前預測準確率最高的分類方案；如果觸發函數判斷預測結果不可靠，那么等待、收集更多的時間序列。線性觸發函數定義為：

(2)

觸發函數集內所有函數的形狀均相同，區別在于γ參數不同，因此需要計算優化預測準確率和預測提前量的γ參數。

1.5 最優觸發函數集

γ參數向量是決定觸發函數(式(2))的關鍵，如果γi設為[-1,1]內的隨機數，則可能出現重復值，并且其觸發函數獲得的預測準確率和早期性并非最優值。

1)評價觸發函數的質量。為了評價觸發函數的預測準確率和早期性，采用兩個被廣泛使用的評價指標，評估早期性質量的方法為：

(3)

(4)

(5)

然后使用元啟發式算法求解多目標優化問題。采用多目標優化的理由主要有三點：(1)如果將兩個目標組合成一個優化問題，那么Ca和Ce必須縮放到相同的區間，才能使兩個目標間保持平衡。(2)兩個目標組合優化問題需要預先分配權重，該參數難以確定。(3)為了權衡兩個目標的關系，需要多次運行程序，而多目標優化程序通過一次運行即可獲得一組非支配解集。本文將非支配解集輸出供用戶根據具體的應用場景選擇。

1.6 結構設計

本文目標是為用戶提供一組分類器和觸發函數的集合{((h1,h2,…,hL),sγ1),((h1,h2,…,hL),sγ2),…,((h1,h2,…,hL),sγg)}。圖3是本文時間序列預測方法的結構，用戶根據實際需求選擇滿足其預測準確率和早期性的最佳觸發函數sγ*，本文算法基于觸發函數sγ*和分類器(h1,h2,…,hL)來預測新時間序列的分類。

圖3 時間序列預測方法的結構

2 概率分類器設計

設計開發了高斯過程分類器預測時間序列的分類概率，并針對重尾分布型時間序列進行了改進。將貝葉斯分類器和半參數模型結合，能夠自適應調節模型的參數，并提高對時間序列中風險數據的預測能力。

2.1 時間序列的貝葉斯分類器模型

設yi(s)表示子集Si的訓練函數，設ci∈{1,2,…,G}為對應的類標簽。假設類g的觀察樣本滿足相同的平均函數ηg(s)和協方差函數γg(s,t)，觀察樣本可以是動態或靜態的。設πg表示觀察樣本屬于類g的先驗概率，分類器的目標是學習一個預測模型，將新觀察樣本y分配到G中的一個類。貝葉斯分類器的最優規則是最大化類g的后驗概率：

(6)

式中：p(y|g)表示樣本y的類標簽為g的似然概率。

以網格形式記錄序列函數曲線，設yit=y(sit)表示位置sit(t=1,2,…,ni)、第i個樣本的觀察函數。新的觀察樣本表示為向量形式y，將式(6)的p(y|g)替換為f(y|g)，其中f(·|g)表示類g的分布密度。式(6)的分類隸屬度后驗信息提供了分類不確定性的重要信息，該信息對于風險預測具有巨大的價值。傳統的高斯過程分類生成每個曲線的極限后驗概率，對于錯誤分類表現出過度置信，導致對重尾分布存在過度置信的問題。為了解決這個問題，本文對高斯過程分類做出修改，簡稱為改進的高斯過程分類器(Improved Gaussian Classifier,IGC)，IGC不僅降低了重尾分布數據的分類錯誤率，同時所估計的后驗概率分布能夠準確地反映樣本在類中的不確定性。

采用分類錯誤率和對數損失LogLoss從不同角度評價分類器的性能，LogLoss通過懲罰錯誤分類實現對分類器準確性的量化。LogLoss定義為：

(7)

式中：i表示觀察樣本，如果i屬于類g，那么Iig等于1，否則等于0；pig表示第i個觀察樣本分配到類g的預測概率。

2.2 改進的高斯過程

為了提高式(6)的魯棒性和后驗密度，將式(6)修改為半參數的混合高斯訓練模型，定義為：

(8)

式中：i=1,2,…,Mg，Mg為類g的觀察樣本數量；yi表示第i個觀察樣本的離散響應(長度為ni)；Bi和Ri分別為ni×p和ni×q的樣條基矩陣；β和γi分別為Bi和Ri的系數因子；εi為高斯模型的位移因子；tq和tni分別表示范圍為q和ni的高斯分布；采用多變量的t-分布建模隨機系數和度量誤差，兩者的自由度均設為v；Γ和Λi分別表示兩者的縮放矩陣。

本文的改進模型保留了高斯模型原有的優點，如支持無參數的擬合平均函數，支持通過無結構的協方差矩陣Γ來近似曲線內的協方差結構，支持多種數據分布類型。高斯模型也具有一定的魯棒性，對重尾分布也具有一定的處理能力，這也是本文選擇以高斯分類器為基礎的原因。

對每個類訓練一個魯棒模型，計算新觀察樣本對類的似然來近似式(6)。使用伽瑪-正態混合分布表示多變量t模型，yi的邊緣分布屬于多變量的t-分布，定義為：

(9)

式中：vd為密度函數；設γi|τi～Nq(0,Γ/τi)和εi|γi兩者之間條件獨立，新到達樣本概率τi服從正態分布：τi～Nni(0,Λi/τi)，也服從伽瑪分布：τi～Gamma(v/2,v/2)。

參考文獻[12]的方法將數據投影到一個特征函數的序列來近似式(6)的密度概率，采用基樣條曲線來擬合離散的度量指數，本文方法能夠處理不規則采樣的數據和多曲線的分類問題。時間序列中存在許多高維數據的情況，因此分類器可能使用高維信息來建模密度，一般通過粗糙懲罰(L1泛化)或者稀疏性條件(L2泛化)來解決高維問題。因為本文的分類器在實數數據流的情況下工作，分類效率是一個關鍵的要素，所以本文采用B樣條基進行無參數建模，從而使本文方法的計算效率高于L1泛化和L2泛化高維近似方法。

2.3 改進的高斯過程分類

在時間序列的實際應用中，存在大量重復的觀察樣本，所以觀察樣本之間存在相關性，通過分析相關的觀察樣本，能夠加快時間序列預測的速度。為了考慮觀察樣本間的依賴性，對式(8)進行修改，增加類級別的隨機函數，其系數服從以v為密度函數的t-分布。設yij為第i個類、第j次重復的nij維響應向量，如果每個類包含多次重復，那么將多級分類模型重寫為：

(10)

式中：Dij為nij×r的樣條基矩陣；δi為一個隨機向量。根據多變量t-分布將每個樣本分類；ψ表示高斯分布的偏差。

(11)

(12)

3 實 驗

3.1 實驗數據集

目前主流的時間序列早期分類算法和預測算法均采用UCR時間序列數據庫作為benchmark數據庫。本文從UCR數據庫中選擇17個不同應用場景的數據集，便于與其他算法的結果作比較。這17個數據集的應用場景不同、維度不同且分類數量也不同。將分類器的學習步長定義為時間序列總長度的5%，采用DTW度量時間序列之間的距離。

3.2 參數設置

本文方法包含兩個重要的模塊：雙目標優化算法和分類器的學習算法。分類器采用本文所設計的改進高斯過程分類器。此外，需要通過雙目標優化方法計算非支配解集，多目標優化方法并非本文的研究重點，因此選擇3個被廣泛應用的多目標演化優化算法分別與本文方法集成，評估本文時間序列預測方法的性能。3個雙目標優化算法分別為非支配排序遺傳算法(NSGA-II)、多目標螢火蟲算法(MOFA)和多目標粒子群優化(MOPSO)。3個優化算法與本文方法的結合版本分別簡稱為NSGA_IPA、MOFA_IPA和MOPSO_IPA。表1所示是3個優化算法的參數設置。

表1 優化算法的參數設置

3.3 對比方法選擇

本文方法的特殊之處是獨立優化預測準確率和早期性兩個目標，而其他許多方法均將多個目標組合為一個單目標的優化算法。

本文方法與最近相關的2個時間序列早期分類方法做比較：CAEC算法[13]、ESC算法[14]。CAEC算法是一種廣義的時間序列預測分類算法，該算法也是一種基于概率的分類程序，而本文方法也是基于概率的分類程序。ESC算法是一種基于Shapelet的時間序列分類算法，該算法與本文方法屬于不同的類型，但其分類準確率好于其他基于Shapelet的算法。表2是這2個算法在實驗中的參數設置。

表2 對比方法的參數設置

3.4 實驗結果分析

每隔5%的時間序列訓練一組分類器，分別使用NSGA-II、MOFA和MOPSO算法作為優化算法，3個優化算法均采用隨機的初始化種群。采用式(3)和式(4)分別計算早期性Ce和預測準確率Ca。

采用超體積指標[15]評估3個優化算法解空間的質量，該指標度量了解空間的體積。解集的超體積指標越大，表示其支配的解空間和覆蓋的區域越大，其性能越好，該指標同時反映了解集的質量和多樣性。統計了3個優化算法對17個數據集最小化Ca和Ce的超體積結果圖，如圖4所示，以(100,100)坐標為參考點，該坐標是最差的可能解。

圖4 3個優化算法最小化成本Ca和Ce的超體積結果比較

圖4并未統計其他3個對比方法，因為它們的目標是以分類準確率為支配目標，在大多數情況下僅獲得了極少的解。從圖中可看出，本文方法和3個優化算法的組合方法均獲得了較多的解集，其中NSGA_IPA的求解質量略好于其他MOFA和MOPSO，因此選擇NSGA_IPA作為實驗方法。

3.5 時間序列的預測實驗

(1)搜索的解集。表3所示是3個預測方法對于17個數據集獲得的解集數量統計，表中“i/j”中i表示非支配解的數量，j表示計算的所有解數量。可看出CAEC計算了固定的總候選解的數量為8，ESC也計算了固定的總候選解的數量為12，本文方法則提供了較多的候選解數量，并且從解集中提取出非支配解供用戶選擇。總體而言，本文計算的解集數量遠高于其他2個算法。

表3 3個預測算法的解集數量

(2)預測準確率的結果。雖然本文的目標是為用戶提供非支配解集，使用戶按照應用需求選擇最合適的解，但本文方法對高斯過程分類進行了改進，有效地提高了重尾分布時間序列的分類性能。CAEC和ESC 2個算法均以最大化分類準確率為支配目標，以早期性為約束條件，所以這2個算法的分類準確率應當較為理想。此外將本文方法和普通高斯過程分類方法結合，組成的算法簡稱為NSGA_GC，比較本文對高斯過程分類的改進效果，NSGA_GC和NSGA_IPA的支配解作為該組實驗的性能結果。4個時間序列早期分類算法對于17個數據集分別進行了預測分類實驗，每組實驗獨立運行30次，統計30次的平均準確率作為實驗結果，如圖5所示。比較NSGA_GC和NSGA_IPA兩個算法，NSGA_IPA對于17個數據集的分類準確率均高于NSGA_GC，反映出本文對于高斯過程分類的改進效果較好。ESC的預測準確率與本文算法較為接近，ESC通過檢測Shapelet實現了較好的分類準確率。但綜合17個數據集的結果，NSGA_IPA的預測分類質量最高，并且提供了豐富的解集供用戶選擇。

圖5 時間序列早期分類的平均準確率

4 結 語

本文將早期性和分類準確率作為2個獨立的目標，采用演化算法同時優化2個目標，給出不同時間戳的預測準確率和早期性結果，供用戶根據應用場景自行選擇。此外，針對時間序列的重尾分布特點，對高斯過程分類進行了修改，提高對重尾分布時間序列的分類準確率，并且優化了時間效率。實驗結果表明，本文算法有效地提高了時間序列的預測準確率，并為用戶提供了豐富的非支配解集。

本文采用了經典的3個多目標優化算法完成了仿真實驗，優化算法是本文時間序列早期分類的一個關鍵部分。未來將針對早期性和預測準確率2個指標研究更加合適的多目標優化算法，以提高算法的總體性能。