朱鋼樑

（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院 南京 210016）

1 引言

時間序列預(yù)測（TSP）是機器學(xué)習(xí)和數(shù)據(jù)工程領(lǐng)域中一個重要且活躍的研究課題，在許多數(shù)據(jù)挖掘應(yīng)用中具有不可或缺的重要性。一般而言，時間序列涉及各種研究領(lǐng)域，例如：經(jīng)濟（股票價格，失業(yè)率和工業(yè)生產(chǎn)），流行病學(xué)（傳染病病例率），醫(yī)學(xué)（心電圖和腦電圖）和氣象學(xué)（溫度，風(fēng)速和降雨量）［1］。許多研究關(guān)心的是平穩(wěn)時間序列預(yù)測而不是非平穩(wěn)時間序列預(yù)測。然而，實際的時間序列幾乎都是非平穩(wěn)的，限制了平穩(wěn)時間序列技術(shù)在實際生產(chǎn)生活中的應(yīng)用。因此，對非平穩(wěn)時間序列預(yù)測的研究變得重要和有價值［2～4］。

在過去的幾十年，神經(jīng)網(wǎng)絡(luò)（NN）憑借其非參數(shù)，數(shù)據(jù)驅(qū)動和任何線性和非線性函數(shù)的通用逼近的理論特性，引起了時間序列領(lǐng)域的研究人員的極大關(guān)注［5］。隨著大量研究人員證明了基于神經(jīng)網(wǎng)絡(luò)的預(yù)測系統(tǒng)的優(yōu)越性［6］，越來越多的研究已經(jīng)開始在神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上設(shè)計時間序列預(yù)測模型［6～11］。然而，對前饋神經(jīng)網(wǎng)絡(luò)（FNNs）參數(shù)的訓(xùn)練將耗費大量時間并導(dǎo)致不同參數(shù)層之間的依賴性?；谔荻认陆档姆椒ǎ?2］作為迭代訓(xùn)練參數(shù)的常用方法，通常非常耗時，并且當(dāng)應(yīng)用于大多數(shù)前饋神經(jīng)網(wǎng)路時，容易使網(wǎng)絡(luò)陷入局部最小值。近幾年，黃廣斌等提出了一種新的FNNs學(xué)習(xí)框架，稱為極限學(xué)習(xí)機（ELM）［13］。ELM是在單隱藏層前饋神經(jīng)網(wǎng)絡(luò)（SLFNs）的基礎(chǔ)上專門開發(fā)的。在ELM中，連接輸入層和隱藏層的權(quán)重以及隱藏層的偏差值在學(xué)習(xí)之前隨機生成，并且在學(xué)習(xí)過程中保持固定。同時，連接隱藏層和輸出層的權(quán)重通過分析計算得到。與傳統(tǒng)的FNNs相比，ELM具有一些重要且有意義的特征［14］：1）效率高，即ELM的學(xué)習(xí)速度極快；2）穩(wěn)健性，即，在大多數(shù)情況下，ELM具有比基于梯度下降的學(xué)習(xí)（例如反向傳播（BP））更好的泛化性能；3）最優(yōu)性，即傳統(tǒng)的基于梯度下降的學(xué)習(xí)算法可能面臨陷入局部最優(yōu)，不正確的學(xué)習(xí)率和過度擬合等問題，ELM將直接得到最優(yōu)解而不會遇到這些問題。

本文的主要貢獻(xiàn)在于將核密度估計應(yīng)用于集成系統(tǒng)的動態(tài)剪枝和增量學(xué)習(xí)，提出了一種新的混合時間序列預(yù)測算法，稱之為DEPK&ILK。算法融合了動態(tài)集成剪枝（DEP），增量學(xué)習(xí)（IL）和核密度估計（KDE）。DEPK&ILK算法分為三個子過程：1）集成系統(tǒng)生成（Overproduction）；2）動態(tài)集成剪枝（DEP）；3）增量學(xué)習(xí)（IL）。第一個子過程用于生成集成系統(tǒng)的基學(xué)習(xí)器池。本算法中，基學(xué)習(xí)器為核方 法 的 在 線 序 列 極 限 學(xué) 習(xí) 機（OS-ELMK）［15］。OS-ELMK是在ELM的基礎(chǔ)上不斷改進發(fā)展而來的。ELMK［16］在ELM的基礎(chǔ)上加入核方法，使ELM具有更好的學(xué)習(xí)性能。OS-ELMK則是ELMK的在線學(xué)習(xí)形式。將OS-ELMK作為基學(xué)習(xí)器，可以隨著新數(shù)據(jù)的到來不斷更新原有的參數(shù)，這一特性在時間序列預(yù)測問題上具有重要意義：時間序列的樣本隨著時間順序先后進入模型，并且時間序列的輸出值服從的概率分布往往隨著時間的變化而變化，模型需要不斷的更新才能適應(yīng)新數(shù)據(jù)的預(yù)測，在第三部分的增量學(xué)習(xí)中，將會用到OS-ELMK的在線學(xué)習(xí)特性。算法的第二個子過程為動態(tài)集成剪枝（DEP），稱之為DEPK。在此過程中，算法將利用核密度估計（KDE）［17］來進行集成系統(tǒng)的動態(tài)剪枝。核密度估計在統(tǒng)計學(xué)中是一種非參數(shù)估計，用來對未知分布進行估計。對于每一個待預(yù)測的樣本，所有的基學(xué)習(xí)器對此樣本進行預(yù)測得到一個預(yù)測輸出向量，然后利用核密度估計得到集成系統(tǒng)對此樣本的預(yù)測輸出概率密度圖。接著對每一個基學(xué)習(xí)器，若該學(xué)習(xí)器對樣本的預(yù)測值在概率密度圖上對應(yīng)的概率越大，則該學(xué)習(xí)器越有機會用來預(yù)測樣本的輸出，最終得到剪枝后的集成系統(tǒng)，最后利用該集成系統(tǒng)對樣本進行預(yù)測。算法的第三個子過程為增量學(xué)習(xí)（IL），稱之為ILK。對于一個待預(yù)測的樣本，算法要衡量該樣本是否需要進行增量學(xué)習(xí)。首先算法定義了一個動態(tài)選擇集（XDSEL），XDSEL用來得到待預(yù)測樣本的Kp個最近鄰樣本，寫為XRECO（The Region of Competence）。然后對每一個在XRECO中的樣本，集成系統(tǒng)都能產(chǎn)生一個預(yù)測輸出向量。同樣的，用該向量可以得到該樣本對應(yīng)的核密度估計。若該樣本的真實值在核密度估計上位于小概率區(qū)間（用一個隨機閾值F衡量），表明集成系統(tǒng)沒有足夠的能力來預(yù)測該樣本，則將它并入集合XINCL（該集合用來最終更新集成系統(tǒng)）中。得到最終的集合XINCL后，用該集合去更新集成系統(tǒng)，即對于每一個基學(xué)習(xí)器，都將XINCL并入它們的采樣集中并更新參數(shù)。

2 基于KDE的動態(tài)集成和增量學(xué)習(xí)算法DEPK&ILK

2.1 核密度估計（KDE）

核密度估計用于估計未知的概率密度函數(shù)，屬于Rosenblatt和Emanuel Parzen提出的非參數(shù)測試方法之一［17］。對于一組數(shù)據(jù){ }x1，x2，…，xn，核密度估計通過以下公式得到。

其中，h＞0是平滑參數(shù)，稱為帶寬。Kh(x)=為縮放函數(shù)。為核函數(shù)（非負(fù)、積分為1，符合概率密度性質(zhì)，并且均值為0）。核函數(shù)有多種形式。由于高斯內(nèi)核方便的數(shù)學(xué)性質(zhì)，本算法中，令K(x)=φ(x)，φ(x)為標(biāo)準(zhǔn)正態(tài)概率密度函數(shù)。

2.2 基于KDE的動態(tài)集成剪枝算法DEPK

對于一個待預(yù)測樣本(x，t)，首先得到一個預(yù)測輸出向量：

p為集成系統(tǒng)中基學(xué)習(xí)器的數(shù)量。該向量o表示集成系統(tǒng)對待預(yù)測樣本的預(yù)測輸出向量。得到預(yù)測輸出向量后，計算預(yù)測輸出的核密度估計。

動態(tài)集成剪枝算法DEPK的算法步驟如下：

1）令fh，max=max(fh)；

2）對每一個基學(xué)習(xí)器li，i=1，2，…，p

（1）在區(qū)間[0，fh，max]上隨機產(chǎn)生一個值r；

（2）若r≤fh(oi)，則將li并入剪枝集L′。

3）用得到的剪枝集L′去預(yù)測樣本的輸出值。

2.3 基于KDE的增量學(xué)習(xí)算法ILK

本算法中，首先我們定義動態(tài)選擇集XDSEL，此集合用來產(chǎn)生Kp個待預(yù)測樣本(x，t)的最近鄰樣本集合XRECO（利用K-NN算法得到），用XRECO集合來近似的代表(x，t)，并利用XRECO去實施增量學(xué)習(xí)算法?；贙DE的增量學(xué)習(xí)算法ILK的算法步驟如下。

1）隨機產(chǎn)生一個閾值F；

2）對每一個屬于XRECO的樣本(xk，tk)，k=1，2，…，Kp

（1）計算該樣本在集成系統(tǒng)上的KDEfh，k；

3）所有的基學(xué)習(xí)器都用集合XINCL去更新參數(shù)。

3 實驗和分析

3.1 實驗設(shè)置

為驗證提出的算法的性能，用三個數(shù)據(jù)集：1）國際航空旅客數(shù)（IAP）；2）IBM股票閉市價格（ICS）；3）每月閉市時道瓊斯工業(yè)指數(shù)（MCD）作為時間序列實驗數(shù)據(jù)集。

在利用數(shù)據(jù)集進行預(yù)測之前，首先算法將數(shù)據(jù)集進行歸一化。歸一化過程可以用下面的方程表示：

其中data表示原始數(shù)據(jù)，min表示原數(shù)據(jù)集上的最小值，max表示原數(shù)據(jù)集上的最大值，d at a*表示歸一化后的數(shù)據(jù)。歸一化過程將所有的數(shù)據(jù)歸一化到[0 ，1]之間。

時間序列預(yù)測需要定義時間窗大小，本算法中我們定義時間窗大小為20。定義了時間窗大小后，就可以產(chǎn)生時間序列的數(shù)據(jù)集。本算法定義最后10%的數(shù)據(jù)為測試集，用來衡量最終算法的性能。隨機取50%的樣本為訓(xùn)練集，用來產(chǎn)生基學(xué)習(xí)器的采樣集。再隨機取20%的樣本作為驗證集，用來訓(xùn)練參數(shù)。取剩下的20%的樣本為動態(tài)選擇集XDSEL，產(chǎn)生樣本的k近鄰集合。

對算法的性能評價，我們選擇均方根誤差（RMSE）和平均絕對誤差（MAE）來衡量。

3.2 國際航空旅客數(shù)（IAP）

國際航空旅客數(shù)（IAP）數(shù)據(jù)集按月記錄了從1949年1月～1960年12月，國際航空旅客數(shù)，具有144個數(shù)據(jù)點。圖1為該數(shù)據(jù)集的折線圖?？梢钥吹皆摂?shù)據(jù)集表現(xiàn)出強烈的規(guī)律性。整體上呈現(xiàn)上升趨勢，同時又有周期性的升降。表1和表2為提出的算法與當(dāng)前流行的幾種算法比較的實驗結(jié)果，由于其余算法不需要用到動態(tài)選擇集，因此它們的訓(xùn)練集占了樣本總量的70%。從結(jié)果可以看出，提出的算法無論是RMSE還是MAE，都取得了良好的實驗結(jié)果。

表1 各算法在三個數(shù)據(jù)集上的RMSE表現(xiàn)

圖1 國際航空旅客數(shù)折線圖

3.3 IBM股票閉市價格（ICS）

該數(shù)據(jù)集記錄了從1961年5月17日到1962年11月2日每天IBM股票閉市價格，具有369個數(shù)據(jù)點。圖2為該數(shù)據(jù)集的折線圖。宏觀上看，該數(shù)據(jù)集并沒有表現(xiàn)出強烈的規(guī)律性，原因是股票價格與多種因素有關(guān)。從表中結(jié)果看出，所有的算法在性能表現(xiàn)上差距不大。尤其是ELMK，OS-SVR和提出的算法性能接近，說明提出的算法不能在所有的數(shù)據(jù)集上都有優(yōu)異的表現(xiàn)，這也符合機器學(xué)習(xí)中“沒有免費午餐”定理。

圖2 IBM股票閉市價格折線圖

3.4 每月閉市時道瓊斯工業(yè)指數(shù)（MCD）

該數(shù)據(jù)集按月記錄了從1968年8月到1992年10月閉市時的道瓊斯工業(yè)指數(shù)，具有291個數(shù)據(jù)點。圖3為該數(shù)據(jù)集的折線圖。從圖中看出，此數(shù)據(jù)集上下波動劇烈，兩個波峰之間存在一個周期，但周期性并不明顯。從表1和表2的實驗結(jié)果看出，提出的算法獲得了優(yōu)異的表現(xiàn)，在此數(shù)據(jù)集上有較低的RMSE和MAE。

圖3 每月閉市時道瓊斯工業(yè)指數(shù)折線圖

4 結(jié)語

本文提出了一種基于核密度估計的動態(tài)集成剪枝和增量學(xué)習(xí)算法DEPK&ILK。通過在三個數(shù)據(jù)集上與其他算法的對比實驗，提出的算法具有不錯的預(yù)測效果。提出的算法在數(shù)據(jù)集有較明顯的規(guī)律性時對比其他算法有很大的性能提升。但在處理規(guī)律性不明顯的數(shù)據(jù)集時，與其他算法在性能表現(xiàn)上無法拉開較大差距，如何在規(guī)律性不強的數(shù)據(jù)集上也獲得良好的性能是下一步的研究重點。