鄒小云 林文學

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

0 引 言

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

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

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

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

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 時間序列早期分類的優(yōu)化方法設計

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

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

1.3 訓練分類器

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

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

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

1.4 定義觸發(fā)函數

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

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

(2)

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

1.5 最優(yōu)觸發(fā)函數集

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

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

(3)

(4)

(5)

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

1.6 結構設計

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

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

2 概率分類器設計

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

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

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

(6)

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

以網格形式記錄序列函數曲線，設yit=y(sit)表示位置sit(t=1,2,…,ni)、第i個樣本的觀察函數。新的觀察樣本表示為向量形式y(tǒng)，將式(6)的p(y|g)替換為f(y|g)，其中f(·|g)表示類g的分布密度。式(6)的分類隸屬度后驗信息提供了分類不確定性的重要信息，該信息對于風險預測具有巨大的價值。傳統(tǒng)的高斯過程分類生成每個曲線的極限后驗概率，對于錯誤分類表現出過度置信，導致對重尾分布存在過度置信的問題。為了解決這個問題，本文對高斯過程分類做出修改，簡稱為改進的高斯過程分類器(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分別表示兩者的縮放矩陣。

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

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

(9)

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

參考文獻[12]的方法將數據投影到一個特征函數的序列來近似式(6)的密度概率，采用基樣條曲線來擬合離散的度量指數，本文方法能夠處理不規(guī)則采樣的數據和多曲線的分類問題。時間序列中存在許多高維數據的情況，因此分類器可能使用高維信息來建模密度，一般通過粗糙懲罰(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 參數設置

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

表1 優(yōu)化算法的參數設置

3.3 對比方法選擇

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

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

表2 對比方法的參數設置

3.4 實驗結果分析

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

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

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

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

3.5 時間序列的預測實驗

(1)搜索的解集。表3所示是3個預測方法對于17個數據集獲得的解集數量統(tǒng)計，表中“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次，統(tǒng)計30次的平均準確率作為實驗結果，如圖5所示。比較NSGA_GC和NSGA_IPA兩個算法，NSGA_IPA對于17個數據集的分類準確率均高于NSGA_GC，反映出本文對于高斯過程分類的改進效果較好。ESC的預測準確率與本文算法較為接近，ESC通過檢測Shapelet實現了較好的分類準確率。但綜合17個數據集的結果，NSGA_IPA的預測分類質量最高，并且提供了豐富的解集供用戶選擇。

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

4 結 語

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

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