在線臨近支持向量回歸機(jī)算法

吳 青，李明明，李飛燕

(西安郵電大學(xué) 自動化學(xué)院，陜西 西安 710121)

時間序列預(yù)測方法可以根據(jù)收集到的歷史數(shù)據(jù)建模，從而預(yù)測未來某一時刻或時段內(nèi)可能的結(jié)果，它是動態(tài)系統(tǒng)建模技術(shù)的核心方法之一[1-2]。特別是在多步超前預(yù)測過程中，應(yīng)用時間序列預(yù)測方法能夠根據(jù)在時間序列中觀察到的規(guī)律預(yù)測未來多步的可能結(jié)果[3]，對于動態(tài)系統(tǒng)建模研究越來越重要[4-5]。

經(jīng)典的時間序列預(yù)測方法有平均數(shù)法、指數(shù)平滑法和季節(jié)性趨勢法等，但是，這些方法被應(yīng)用于預(yù)測自然界中大量存在的非線性、非平穩(wěn)的復(fù)雜數(shù)據(jù)時，泛化性能較差[6-7]。為了改善經(jīng)典時間序列預(yù)測方法存在的問題，研究者們提出了神經(jīng)網(wǎng)絡(luò)方法。在實際應(yīng)用中發(fā)現(xiàn)，神經(jīng)網(wǎng)絡(luò)方法具有不錯的逼近能力，但是，也存在著過擬合以及容易陷入局部最優(yōu)解等問題[8]。

針對神經(jīng)網(wǎng)絡(luò)方法存在的不足，研究者們開始將支持向量機(jī)[9](Support Vector Machine,SVM)技術(shù)應(yīng)用于時間序列預(yù)測和動態(tài)系統(tǒng)建模過程中。Vapnik等人提出的SVM技術(shù)[9]是一種基于統(tǒng)計學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，其克服了傳統(tǒng)分類方法的一些缺點，當(dāng)被應(yīng)用于處理小樣本、高維度、局部極小值等問題時，具有較好的泛化性能，但是，SVM的模型最后均需要轉(zhuǎn)化為一個二次規(guī)劃問題，計算復(fù)雜度較高。為了提高算法的效率，一方面，可以采用序列最小優(yōu)化(Sequential Minimal Optimization，SMO)算法、Chunking算法和Osuna算法等算法對模型求解，以提高模型的訓(xùn)練速度[10]。另一方面，針對在訓(xùn)練時由于樣本冗余所造成的計算效率低下問題，可以根據(jù)數(shù)據(jù)集中支持向量的分布特性，利用Fisher判別方法縮減訓(xùn)練樣本的數(shù)量，從而提升算法的運算速度[11]。

為了將SVM拓展到回歸問題中，Vapnik等人引入不敏感損失函數(shù)，提出了支持向量回歸機(jī)[12](Support Vector Regression，SVR)算法。近年來，SVR被廣泛應(yīng)用于各種回歸問題中，包括天氣預(yù)測、股票市場和房地產(chǎn)定價等，并展現(xiàn)出了較好的預(yù)測性能[13]，但是，SVR算法的運算速度較慢。

為了進(jìn)一步提高算法的速度，Suykens等在SVM方法的基礎(chǔ)上，提出了最小二乘支持向量機(jī)[14](Least Square Support Vector Machine,LS-SVM)算法。LS-SVM算法將經(jīng)典SVM算法中的損失函數(shù)替換為平方損失，把約束條件中的不等號變?yōu)榈忍枺⒆罱K通過求解一個優(yōu)化方程組來得到原始問題的最優(yōu)解，這個過程避免了復(fù)雜的二次規(guī)劃問題，極大地降低了計算成本。另外，F(xiàn)ung等[15]提出了臨近支持向量機(jī)(Proximal Support Vector Machine,PSVM)算法。PSVM的原理是將兩類樣本盡量集中在兩個平行超平面附近，并使得兩個類別的超平面間隔最大化，與LS-SVM算法相同，PSVM算法同樣避免了求解二次規(guī)劃問題，通過直接求解線性方程組，極大地提高了算法的訓(xùn)練速度。杜等[16]將PSVM算法推廣到處理回歸問題中，提出了臨近支持向量回歸機(jī)(Proximal Support Vector Machine Regression,PSVR)算法，并利用人工數(shù)據(jù)集與真實數(shù)據(jù)集驗證了PSVR算法的預(yù)測性能。為了實現(xiàn)基于SVR算法的在線序列預(yù)測，文獻(xiàn)[17]提出在線支持向量回歸機(jī)(Online Support Vector Machine Regression,OL-SVR)算法，其核心思想是在訓(xùn)練過程中，通過增加新樣本并刪除舊樣本來更新現(xiàn)有的樣本數(shù)據(jù)，但是，這種思路導(dǎo)致訓(xùn)練速度較慢。為了提高訓(xùn)練速度，文獻(xiàn)[18]在最小二乘支持向量回歸機(jī)(Least Square Support Vector Regression,LS-SVR)算法的基礎(chǔ)上，根據(jù)求解過程中核矩陣本身的特點，提出了在線最小二乘支持向量回歸機(jī)方法；王等學(xué)者[19]提出了在線稀疏最小二乘支持向量回歸機(jī)算法，提高了訓(xùn)練速度，但是，該方法的預(yù)測精度不如OLS-SVR算法；文獻(xiàn)[20]結(jié)合魯棒學(xué)習(xí)方法，提出了在線魯棒最小二乘支持向量回歸機(jī)算法，改善了OLS-SVR算法易受噪聲點影響的問題，但是，該算法需要訓(xùn)練的時間較長。

為了兼顧預(yù)測精度和預(yù)測效率兩個方面，本文擬提出一種在線臨近支持向量回歸機(jī)(Online Proximal Support Vector Machine Regression,OL-PSVR)算法。在PSVR算法的基礎(chǔ)上，利用在線學(xué)習(xí)來更新樣本數(shù)據(jù)以及核矩陣。然后，利用一個證券股票數(shù)據(jù)集與3個加州大學(xué)歐文分校(University of California Irvine，UCI)數(shù)據(jù)庫的數(shù)據(jù)集進(jìn)行實驗，從預(yù)測精度和預(yù)測效率兩個方面與OL-SVR算法、OLS-SVR算法以及在線序列核極限學(xué)習(xí)機(jī)[21](Online Sequential Extreme Learning Machine with Kernel,OS-KELM)算法等3種算法進(jìn)行比較，以驗證算法的可行性和有效性。

1 PSVR算法

PSVR算法的決策函數(shù)可以通過求解一個優(yōu)化問題得到。該優(yōu)化問題可以表示為

(1)

式中：ξ表示松馳變量；e為元素均為1的n維列向量；C為懲罰參數(shù)；(ω,b)為待求解的增廣權(quán)向量。

式(1)中優(yōu)化問題的Lagrange函數(shù)形式為

(2)

式中，α為拉格朗日乘子向量。

根據(jù)Karush-Kuhn-Tucker(KKT)條件[16]，令各變量的偏導(dǎo)為0，可以得到方程組

(3)

(4)

進(jìn)一步，有

(5)

式中，I為單位矩陣。

令H=[A,e]，則有

(6)

當(dāng)輸入樣本數(shù)目大于樣本維數(shù)時，由于式(6)涉及到一個m×n維的矩陣求逆，可以利用SMW(Sherman-Morrison-Woodbury)公式[16]降低矩陣維數(shù)。由此可以得到

(7)

所以，可以將PSVR方法的決策函數(shù)表示為

f(x)=ωTx+b=(Ax+e)Tα

(8)

對于非線性臨近支持向量回歸機(jī)，可以通過引入核函數(shù)，使用K(A,AT)來代替約束等式中的A，則可以將式(1)的優(yōu)化問題轉(zhuǎn)化為

(9)

記K(A,AT)=K，與線性情況類似，通過構(gòu)造Lagrange函數(shù)，并根據(jù)KKT條件可以得到

(10)

b=eTα

(11)

化解式(10)，可得

(12)

令G=[Ke]，可得

(13)

由此得到非線性PSVR算法的決策函數(shù)為

f(x)=ωTx+b=(KK(A,x)+e)Tα

(14)

PSVR算法的主要問題是，一方面，無法對在線更新數(shù)據(jù)進(jìn)行預(yù)測；另一方面，其核矩陣隨著數(shù)據(jù)的增多而急劇增大，影響了算法的效率。

2 OL-PSVR算法

為了改善PSVR無法對時間序列數(shù)據(jù)進(jìn)行預(yù)測的問題，引入在線學(xué)習(xí)方法更新樣本，提出OL-PSVR方法。

2.1 在線學(xué)習(xí)

在線學(xué)習(xí)通過增量學(xué)習(xí)和減量學(xué)習(xí)保證訓(xùn)練樣本數(shù)目的恒定。為了說明固定窗口的在線序列預(yù)測方法，提出以下假設(shè)。

圖1 在線學(xué)習(xí)樣本更新示意圖

2.2 OL-PSVR

由式(12)和式(13)式可知，非線性的PSVR算法的解可以通過求解一組方程得到。該方程組為

(15)

式中，K=K(A,AT)。

(16)

對于時間序列預(yù)測問題，PSVR算法求解矩陣的規(guī)模會隨著樣本數(shù)目的增加而急劇增大，為此，引入在線學(xué)習(xí)進(jìn)行樣本更新。假設(shè)存在一個固定大小的時間滑動窗口，其中包含N個存儲單元，可以在特定的時刻加載訓(xùn)練樣本。

假設(shè)在時刻k，更新中的訓(xùn)練樣本集表示為{A(k),Y(k)}，其中，A(k)=[xk,xk+1,…,xk+N-1]T表示時刻k的樣本屬性，Y(k)=[yk,yk+1,…,yk+N-1]T表示k時刻的樣本標(biāo)簽。隨著時間的變化，可以利用時間滑動窗口對時刻k+1的訓(xùn)練樣本進(jìn)行更新和轉(zhuǎn)換。

矩陣S、α和偏差項b都是關(guān)于時刻k的函數(shù)，可以將時刻k的S、α和偏差項b分別表示為

(17)

α(k)=[αk,αk+1,…,αk+N-1]T

(18)

b(k)=bk

(19)

式中，I為N維的單位矩陣。

式(17)、式(18)、式(19)結(jié)合式(16)可得

(S(k)+eeT)α(k)=Y(k)

(20)

b(k)=eTα(k)

(21)

根據(jù)式(20)和式(21)，可以得到

α(k)=(S(k)+eeT)-1Y(k)

(22)

在時刻k+1，若添加一個新的樣本xnew，則將矩陣S(k)更新為一個新的矩陣S(k+1)，這樣就可以有效地控制核矩陣的維度。

更新后的新矩陣可以表示為

(23)

式中，M(k)表示第k輪的S矩陣去掉一個舊樣本后的新矩陣，表達(dá)式為

Knew1=[K(xnew,xk+1)…K(xnew,xk+N)]T

同理，當(dāng)預(yù)測步長變?yōu)閔(N>h>1)時，新添加的樣本數(shù)目大于1，則相應(yīng)地將矩陣S(k)更新為

(24)

式中，M(k*)表示第k輪的S矩陣去掉h(N>h>1)個樣本后的新矩陣，表達(dá)式為

其中，xnew(h)為第h個加入的樣本。

根據(jù)式(21)、式(22)以及式(24)可以得到α(k+1)和b(k+1)，并記φ(x)為x映射到特征空間的向量，則k+1輪的決策函數(shù)可以表示為

(25)

l=1,2,…,h

3 實驗結(jié)果及分析

3.1 實驗設(shè)置

為了評價所提算法的性能，對UCI數(shù)據(jù)庫中的Air Quality數(shù)據(jù)集、Beijing PM2.5數(shù)據(jù)集和Parking Birmingham數(shù)據(jù)集3個數(shù)據(jù)集，以及Northeast Securities數(shù)據(jù)集進(jìn)行實驗，并將所提算法與已有的OL-SVR算法[17]、OLS-SVR算法[18]以及OS-KELM算法[21]等3種在線序列預(yù)測算法進(jìn)行比較。

實驗中，設(shè)置時間滑動窗口N=100。4種算法的核函數(shù)均采用高斯核

式中，σ為核參數(shù)。

另外，4種算法的性能都依賴于參數(shù)選擇，將網(wǎng)格搜索法與五折交叉驗證結(jié)合起來選取最優(yōu)參數(shù)。需要選取的最優(yōu)參數(shù)包括高斯核參數(shù)2-2≤σ≤24和懲罰參數(shù)C∈{2-2,2-1,…,210}。為了公平地比較算法的預(yù)測性能，對于相同的數(shù)據(jù)集，4種算法均選用相應(yīng)的最優(yōu)參數(shù)進(jìn)行驗證。

選擇平均絕對誤差[6](Mean Absolute Deviation，MAE)、均方根誤差[6](Root Mean Squared Error，RMSE)、平均絕對百分比誤差[6](Mean Absolute Percentage Error，MAPE)和泰爾不等式系數(shù)[6](Theil Inequality Coefficient，TIC)等4種評價指標(biāo)來評價不同算法的預(yù)測精度。這4種評價指標(biāo)值越小，表示算法的預(yù)測精度越高。

實驗環(huán)境為AMD Ryzen5 4600U內(nèi)核(2.10 GHz)且內(nèi)存為16 GB的筆記本計算機(jī)，使用MATLAB R2016a編寫程序。

3.2 使用的數(shù)據(jù)集

Air Quality數(shù)據(jù)集選自UCI數(shù)據(jù)庫，包含空氣質(zhì)量化學(xué)多傳感器設(shè)備的9 358個小時的響應(yīng)數(shù)據(jù)，采樣于意大利一座城市內(nèi)道路高度嚴(yán)重污染地區(qū)，記錄時間為2004年3月至2005年2月。選取前1 055個數(shù)據(jù)進(jìn)行實驗。

Northeast Securities數(shù)據(jù)集為中國證券股票數(shù)據(jù)集中的東北證券公司數(shù)據(jù)，下載于網(wǎng)易財經(jīng)官網(wǎng)，包含2017年11月1日到2019年6月24日的400個歷史交易日行情，共計1 199個數(shù)據(jù)。

Beijing PM2.5數(shù)據(jù)集選自UCI數(shù)據(jù)庫，包含了美國駐北京大使館每小時PM2.5的數(shù)據(jù)和來自北京首都國際機(jī)場每小時的氣象數(shù)據(jù)，共計43 824個數(shù)據(jù)。數(shù)據(jù)采集的時間段為2010年1月1日至2014年12月31日。選取前1 108個數(shù)據(jù)進(jìn)行實驗。

Parking Birmingham數(shù)據(jù)集選自UCI數(shù)據(jù)庫，由伯明翰市議會NCP運營的伯明翰停車場收集。用于預(yù)測停車場的占用率，包含35 717個數(shù)據(jù)，采集時間段為2016年10日至2016年12月19日。選取前1 200個數(shù)據(jù)進(jìn)行實驗。

實驗采用的4個數(shù)據(jù)集的具體信息如表1所示。

表1 數(shù)據(jù)集信息

3.3 實驗結(jié)果

設(shè)置預(yù)測步長h分別為1、5和10，在不同的預(yù)測步長條件下，4種算法對4個數(shù)據(jù)集的預(yù)測性能結(jié)果如表2所示。

表2 4種算法不同步長條件下的預(yù)測性能

表2的實驗結(jié)果顯示，從預(yù)測精度上看，當(dāng)h為1時，OL-PSVR算法在Air Quality、Beijing PM2.5以及Parking Birmingham等3個數(shù)據(jù)集上預(yù)測精度與OLS-SVR算法和OS-KELM算法相當(dāng)，高于OL-SVR算法；OL-PSVR算法僅在Northeast Securities數(shù)據(jù)集上的預(yù)測精度低于OS-KELM算法，這是因為，OS-KELM算法是一種單隱含層神經(jīng)網(wǎng)絡(luò)，相比于OL-PSVR算法，其預(yù)測的偶然性較大。當(dāng)h為5時，OL-PSVR算法在4個數(shù)據(jù)集上的預(yù)測精度均是最高的，僅在Air Quality數(shù)據(jù)集上MAPE值低于OLS-SVR算法，這是由于數(shù)據(jù)的偶然性。當(dāng)h為10時，OL-PSVR算法在4個數(shù)據(jù)集上的所有指標(biāo)值均低于其他3種算法。這說明隨著預(yù)測步長增大，OL-PSVR算法顯示出更好的預(yù)測精度。

從預(yù)測效率上看，當(dāng)h為1和5時，OS-KELM算法的預(yù)測速度最快。當(dāng)h=10時，OL-PSVR算法的預(yù)測速度與OS-KELM算法相當(dāng)。這說明當(dāng)預(yù)測步長增大時，OL-PSVR算法的預(yù)測速度增幅最大。

通過觀察表2中的數(shù)據(jù)可以發(fā)現(xiàn)，在步長h分別為1、5和10的條件下，OL-PSVR算法、OL-SVR算法、OLS-SVR算法以及OL-KELM算法等4種算法對Beijing PM2.5數(shù)據(jù)集預(yù)測的誤差指標(biāo)值差異最大，為了直觀地展示4種不同算法預(yù)測的誤差，選取4種不同算法對Beijing PM2.5數(shù)據(jù)集的預(yù)測來進(jìn)行展示。在不同預(yù)測步長條件下，4種算法對Beijing PM2.5數(shù)據(jù)集的預(yù)測誤差如圖2所示。

圖2 不同步長下4種算法對Beijing PM2.5數(shù)據(jù)集的預(yù)測誤差

由圖2可以看出，當(dāng)h=1時，OL-PSVR算法的MAE、RMSE、MAPE和TIC等4個評價指標(biāo)值與OLS-SVR算法幾乎相等；當(dāng)h增大為5時，4個指標(biāo)值均略小于OLS-SVR算法與OL-SVR算法；當(dāng)h增大為10時，4個指標(biāo)值均明顯小于對比算法。可見隨著步長h的增大，相比于其他3種算法，OL-PSVR算法具有更高的預(yù)測精度。這是因為隨著步長的增大，OL-PSVR算法所造成的累計誤差最小。

表2不能清晰地看出預(yù)測時間隨著預(yù)測步長的變化規(guī)律和預(yù)測效率，為此，在步長h分別為1、5和10的條件下，采用OL-PSVR算法、OL-SVR算法、OLS-SVR算法以及OL-KELM算法等4種算法對Air Quality數(shù)據(jù)集、Northeast Securities數(shù)據(jù)集、Beijing PM2.5數(shù)據(jù)集和Parking Birmingham數(shù)據(jù)集4個數(shù)據(jù)集進(jìn)行仿真，不同步長條件下4種算法對4個數(shù)據(jù)集的預(yù)測時間仿真結(jié)果如圖3所示。可以看出，OL-SVR算法預(yù)測所耗費的時間明顯長于其他3種算法，說明該算法的效率明顯低于其他3種算法。而OL-PSVR算法、OS-KELM算法和OLS-SVR算法的預(yù)測效率的差距不明顯。

圖3 不同步長條件下4種算法的預(yù)測時間

(續(xù))圖3 不同步長條件下4種算法的預(yù)測時間

為了更清晰地顯示OL-PSVR算法、OS-KELM算法和OLS-SVR算法預(yù)測效率的差異，僅對比這3種算法的預(yù)測時間。在步長h分別為1、5和10的條件下，OL-PSVR算法、OS-KELM算法和OLS-SVR算法3種算法對Air Quality數(shù)據(jù)集、Northeast Securities數(shù)據(jù)集、Beijing PM2.5數(shù)據(jù)集和Parking Birmingham數(shù)據(jù)集4個數(shù)據(jù)集的預(yù)測時間如圖4所示。可以看出，當(dāng)h分別取1、5和10時，OL-PSVR算法預(yù)測時間明顯比OLS-SVR短；當(dāng)h由1增大到5時，OL-PSVR算法的預(yù)測時間大幅度縮短，h增大到10時與OS-KELM算法的預(yù)測時間幾乎相等。這表明，在進(jìn)行多步預(yù)測時，OL-PSVR算法預(yù)測速度快于OLS-SVR算法和OL-SVR算法，與OS-KELM算法預(yù)測速度相當(dāng)。雖然OL-PSVR算法的預(yù)測時間會隨著h的增大而接近OS-KELM算法，但是，考慮到OL-PSVR算法的預(yù)測精度會隨著h的增大而明顯高于OS-KELM算法，在進(jìn)行多步預(yù)測時，相比于OS-KELM算法、OL-PSVR算法的預(yù)測性能更優(yōu)。

圖4 不同步長條件下3種算法的預(yù)測時間

4 結(jié)語

基于PSVR與在線學(xué)習(xí)提出了OL-PSVR算法，以實現(xiàn)對時間序列數(shù)據(jù)的多步預(yù)測。與經(jīng)典的預(yù)測算法相比，OL-PSVR算法不僅能利用歷史數(shù)據(jù)，還能實時捕獲當(dāng)前數(shù)據(jù)信息并實現(xiàn)數(shù)據(jù)的在線更新，節(jié)省了存儲空間。這意味著當(dāng)預(yù)測樣本數(shù)目較大時，OL-PSVR算法具有較高的訓(xùn)練效率。實驗結(jié)果表明，當(dāng)選用最優(yōu)參數(shù)時，與其他經(jīng)典的在線預(yù)測算法相比，OL-PSVR算法不僅具有預(yù)測精度較高的優(yōu)勢，而且預(yù)測效率高于OLS-SVR算法和OL-SVR算法，與OS-KELM算法相當(dāng)。并且，隨著預(yù)測步長的增大，OL-PSVR算法在保證精度的同時，能夠明顯地提升預(yù)測速度，具有更好的預(yù)測性能。