增量式Huber-支持向量回歸機(jī)算法研究

周曉劍, 肖 丹, 付 裕

(1.南京郵電大學(xué) 管理學(xué)院,江蘇 南京 210023; 2.廈門大學(xué) 信息學(xué)院,福建 廈門 361005)

0 引言

支持向量機(jī)(Support Vector Machine，SVM)是數(shù)據(jù)挖掘中的一項(xiàng)重要的技術(shù)，由Vapnik于20世紀(jì)90年代年首先提出的，是建立在統(tǒng)計(jì)學(xué)習(xí)理論(Statistical Learning Theory，SLT)中的VC維理論以及結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的基礎(chǔ)之上的，它的本質(zhì)是求解凸二次規(guī)劃問題，與傳統(tǒng)的學(xué)習(xí)方法相比，支持向量機(jī)在解決小樣本、非線性和高維分類問題中有顯著的優(yōu)勢(shì)[1～3]。

支持向量回歸機(jī)(Support Vector Regression，SVR)是支持向量機(jī)(SVM)用于解決回歸問題的推廣形式。樣本訓(xùn)練時(shí)，隨著樣本數(shù)的增加，學(xué)習(xí)難度逐漸增大[4]。在實(shí)際的回歸問題中，樣本通常是增量在線提供的，此時(shí)，若采用SVR一次性建模算法，每當(dāng)樣本數(shù)據(jù)集變動(dòng)，即使只是增加一個(gè)樣本，均需要從頭開始學(xué)習(xí)、重新建模，但是這樣建模成本較高[5]。與之不同的是，增量式算法的學(xué)習(xí)過程不是一次離線完成的，而是逐一加入數(shù)據(jù)不斷優(yōu)化的過程，在處理新增樣本時(shí)，不用重新建模即可完成新數(shù)據(jù)的學(xué)習(xí)[6]。

SVR的增量算法通?；讦?不敏感損失函數(shù)，即增量式ε-SVR算法[7]。ε-不敏感損失函數(shù)潛在的缺點(diǎn)是它對(duì)大的異常值非常敏感，而Huber損失函數(shù)對(duì)噪聲的容忍能力較強(qiáng)，能夠較好地抑制異常值對(duì)計(jì)算結(jié)果的影響，所以在有噪聲的情況下Huber損失函數(shù)是比ε-不敏感損失函數(shù)更好的選擇[8,9]。周曉劍等[10]研究了一種新的SMO算法，用于求解非半正定核Huber-SVR問題。為使Huber-SVR更具魯棒性，周曉劍等[11]還深入研究了Huber-SVR中參數(shù)與輸入噪聲之間的關(guān)系。由于Huber-SVR具有更強(qiáng)的魯棒性和建模性能，本文提出了一種基于Huber損失函數(shù)的增量式Huber-SVR算法，該算法能夠連續(xù)不斷地將新樣本的信息集成到之前已經(jīng)訓(xùn)練好了的模型中，而不是對(duì)所有樣本重新建模，極大地提高了建模效率。

本文第二部分首先介紹了Huber-SVR的基本形式以及求解此問題的最優(yōu)化條件即KKT條件；第三部分重點(diǎn)闡述了增量式Huber-SVR算法的數(shù)學(xué)原理以及具體的算法步驟；第四部分是實(shí)驗(yàn)部分，通過對(duì)比增量式Huber-SVR算法，增量式ε-SVR算法和增量式RBF算法對(duì)四個(gè)真實(shí)樣本數(shù)據(jù)集的回歸預(yù)測(cè)來驗(yàn)證本文所提算法。最后得出結(jié)論：增量式Huber-SVR算法對(duì)真實(shí)數(shù)據(jù)的回歸預(yù)測(cè)精度比另外兩種算法更高；第五部分對(duì)本文所做研究進(jìn)行了總結(jié)，并對(duì)今后研究方向進(jìn)行了展望。

1 Huber-SVR基本形式和KKT條件

1.1 Huber-SVR基本形式

(1)Huber損失函數(shù)[12]：

(1)

其中μ為損失函數(shù)的參數(shù)，ξ為真實(shí)值與預(yù)測(cè)值之間的偏差。

(2)Huber-SVR原始問題：

數(shù)據(jù)集T={(xI,yI),…,(xI,yI)}中xi是輸入，yi是輸出，線性回歸問題的目標(biāo)就是尋找空間Rn×Rn上的一個(gè)超平面f(x)=wTΦ(x)+b，其中：輸入xi被函數(shù)Φ映射到一個(gè)高維再生核希爾伯特空間，w是權(quán)系數(shù)向量，b是偏置，使得超平面與訓(xùn)練樣本集T中訓(xùn)練樣本點(diǎn)的偏離最小。

當(dāng)SVR中的損失函數(shù)取Huber損失函數(shù)時(shí)，就構(gòu)成了Huber-支持向量回歸機(jī)。Huber-支持向量回歸機(jī)(Huber-SVR)的原始問題如下:

(2)

其中(*)是變量有*符號(hào)或沒有*符號(hào)的縮寫，ξ(*)是非負(fù)松弛變量，C是懲罰參數(shù)。

(3)Huber-SVR對(duì)偶模型:

利用對(duì)偶模型，引入朗格朗日乘子求解原問題，對(duì)偶問題如下：

(3)

其中Qij=Φ(xi)TΦ(xj)=K(xi,xj)，K是核函數(shù)，回歸方程可以寫為：

(4)

(5)

把式(3)化簡(jiǎn)為:

(6)

根據(jù)凸優(yōu)化理論，式(6)等價(jià)于如下的拉格朗日函數(shù):

(7)

1.2 KKT條件

根據(jù)凸最優(yōu)化理論，式(7)解的充要條件，KKT條件如下:

(8)

(9)

函數(shù)間隔：

(10)

由(8)，(9)，(10)得:

(11)

2 增量式Huber-SVR算法

增量算法思想：新增樣本xC，先判斷新樣本xC是否滿足KKT條件，如果滿足，則把xC加入相應(yīng)的集合，結(jié)束；如果xC不滿足KKT條件：然后不斷改變新樣本xC的值，直到新樣本xC滿足KKT條件，同時(shí)原訓(xùn)練集中的所有樣本也滿足KKT條件。

新樣本xC的θC影響著原樣本的θi和h(xi)，所以xC的加入可能會(huì)使一些樣本發(fā)生移動(dòng)，不滿足原集合的KKT條件，但滿足另一集合的KKT條件。

2.1 增量關(guān)系

本小節(jié)介紹的是增量ΔθC發(fā)生變化時(shí)，而沒有引起樣本在S集，E1集和E2集之間移動(dòng)時(shí)，增量ΔθC和與Δh(xi)和Δθi之間的關(guān)系。

由式子(10)得:

(12)

(13)

i∈S時(shí)，要保持樣本不發(fā)生移動(dòng)，h(xi)≡0，所以由(12),(13)得:

(14)

S中的樣本:S={s1,s2,…,sS}

(15)

把(14)用矩陣形式表示如下:

(16)

(17)

(18)

令：

H=R-1

(19)

(20)

(21)

即:

Δb=βbΔθC

(22)

Δθj=βjΔθC,?j∈s

(23)

Δh(xj)=0,?j∈s

(24)

從式子(22)，(23)可以看出當(dāng)時(shí)，ΔθC是如何影響Δθi和Δb的值。把(23)擴(kuò)展到所有樣本時(shí)，因?yàn)镋1和E2中的θ值為常數(shù)，所以i?S時(shí)，Δθi=0，因此(21)式隱含著，當(dāng)i?S時(shí)，βi≡0。

當(dāng)i?S時(shí)，定義集合N:

N=EI∪E2={n1,n2,…,nn}

(25)

由式子(11)(12)(21)可知:

(26)

所以，令:

(27)

最后得到:

(28)

Δθi=0,i?S

(29)

當(dāng)i∈S時(shí)，Δh(xi)=0，所以γ≡0。

當(dāng)S是空集時(shí)，根據(jù)式子(12)，(13)，(27)得:

Δh(xn)=Δb,n∈E1∪E2

(30)

由以上分析可知：當(dāng)新樣xC加入，沒有引起其他集合中樣本發(fā)生移動(dòng)時(shí)：

知道ΔθC的值，根據(jù)式子(22)(23)得知，當(dāng)i∈S時(shí)，可以更新訓(xùn)練集S中樣本i的和b的值，同時(shí)，Δh(xi)=0；給定ΔθC的值，由式(28)，(29)可知，當(dāng)i?S時(shí)，可更新樣本i的h(xi)，同時(shí)，Δθi=0。

2.2 樣本的移動(dòng)

在θC不斷變化的過程中，隨著ΔθC的變化，Δθi，Δh(i)也在隨之變化，當(dāng)ΔθC到達(dá)一個(gè)臨界值時(shí)，會(huì)使得樣本在S集，E1集，E2集中相互移動(dòng)，導(dǎo)致各集合中組成分發(fā)生變動(dòng)。為了解決這個(gè)問題，采取的措施是，求得ΔθC變動(dòng)引起樣本在S集，E1和E2集中變化的最小值，使得每次只有一個(gè)樣本在集合之間移動(dòng)，即求得最小調(diào)整增量ΔθC。

具體需要考慮以下幾種情況：

情況1新樣本xC滿足KKT條件

(1)xC加入S集：

(31)

(2)xC加入E1集:

(32)

(3)xC加入E2集

(33)

情況2i∈S，樣本點(diǎn)從S集移到E1集或者E2集，分別是:

(1)樣本點(diǎn)從S集移到E1集:

Δθi=C-θi

(34)

(2)樣本點(diǎn)從S集移到E2集

Δθi=-C-θi

(35)

樣本點(diǎn)從S集移到E1集時(shí)，這些樣本的θi值會(huì)逐漸增加到邊界值C；樣本點(diǎn)從S集移到E2集，這些樣本的θi值會(huì)逐漸減小到邊界值-C;

(36)

情況3i?S，樣本點(diǎn)從E1集或者E2集移到S集：

樣本點(diǎn)移到S集合時(shí)，最終h(xi)=0，所以:

(37)

最后，結(jié)合三種情況計(jì)算當(dāng)只有一個(gè)樣本點(diǎn)在集合之間移動(dòng)時(shí)的最小增量ΔθC:

q=sign(-h(xC))

(38)

(39)

2.3 逆矩陣的更新

定義(S+1)×(S+1)維分塊矩陣B:

(40)

(41)

根據(jù)分塊矩陣求逆的方法，集合S中增加一個(gè)樣本xt時(shí)，矩陣更新如下：

(1)第一個(gè)樣本更新如下:

(42)

(2)向H中繼續(xù)增加新樣本，更新如下:

(43)

(44)

γt=Rtt+[1RS1t…RSSt]β

(45)

當(dāng)新樣本加入S集合時(shí)，β的更新如式子(19)所示，γt是式子(27)中γ的最后一個(gè)元素。

(3)集合S中減少一個(gè)樣本點(diǎn)時(shí)，矩陣更新如下:

(46)

當(dāng)索引i、j為0時(shí)，指的是b這一項(xiàng)。

2.4 算法初始化

本文增量算法模型的構(gòu)建是通過兩個(gè)樣本建立最初的模型，然后在此基礎(chǔ)上進(jìn)行模型的更新。初始模型建立使用增量算法，即從頭開始使用增量算法提供完整的解決方案。給定兩個(gè)樣本訓(xùn)練集，表示為：T={(x1,y1),(x2,y2)}，且y1≥y2，對(duì)偶問題式子(6)的解如下:

(47)

θ2=-θ1

(48)

b=(y1-y2)/2

(49)

2.5 算法步驟

增量式Huber-SVR算法:

輸入：

數(shù)據(jù)集T={(x1,y1),…,(xl,yl)};

系數(shù){θi,i=1,2,…,l},和h(xi)偏置b；

將樣本分成S集，E1集和E2集；

矩陣H；

新樣本xC。

輸出：

新的系數(shù)θi,h(xi),i=1,2,…,l以及θC，h(xC)和偏置b；

更新后得到的新的S集，E1集和E2集；

更新后的矩陣H。

算法步驟：

1、初始化令θC=0；

2、計(jì)算h(xC)；

3、如果h(xC)=0，把新樣本加入到S集，更新矩陣H，結(jié)束；

4、如果新樣本不滿足KKT條件：

(1)令q=sign-(h(xC)),計(jì)算最小增量ΔθC，使得恰有一個(gè)樣本在S集，E1集和E2集之間移動(dòng)。

(2)做如下更新：

直到滿足下列條件之一：

③原訓(xùn)練集中的一個(gè)樣本i發(fā)生移動(dòng)：

如果h(xi)new=0，則把樣本從E1集或E2集移入S集。

更新矩陣H；

5、返回4。

6、算法結(jié)束后輸出h(xC)，b，θC，θi，h(xi),i=1,2,…,l矩陣H，S集，E1集和E2集。

3 實(shí)驗(yàn)及其結(jié)果

3.1 實(shí)驗(yàn)?zāi)康?/h3>

驗(yàn)證本文提出的增量式Huber-SVR算法的可行性，將該算法與應(yīng)用較廣泛的增量式ε-SVR算法和文獻(xiàn)13中的增量式RBF學(xué)習(xí)算法[13]進(jìn)行比較，將三種算法應(yīng)用于實(shí)際數(shù)據(jù)中，比較三種算法的預(yù)測(cè)性能。

3.2 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)選取的數(shù)據(jù)來源于UCI機(jī)器學(xué)習(xí)存儲(chǔ)庫，有“翼型自噪聲數(shù)據(jù)集”，來自西班牙北部的“葡萄酒質(zhì)量數(shù)據(jù)集”，“聯(lián)合循環(huán)電廠數(shù)據(jù)集”和“QSAR水生毒性數(shù)據(jù)集”?！耙硇妥栽肼晹?shù)據(jù)集”共1503條數(shù)據(jù)，每條數(shù)據(jù)包括5個(gè)輸入變量，輸出變量是：壓縮的聲壓級(jí)。“葡萄酒質(zhì)量數(shù)據(jù)集”刪除重復(fù)樣本后包括1359條紅葡萄酒樣品數(shù)據(jù)，輸出變量是：葡萄酒質(zhì)量得分?！奥?lián)合循環(huán)電廠數(shù)據(jù)集”用來預(yù)測(cè)工廠的每小時(shí)凈電能輸出(EP)?！癚SAR水生毒性數(shù)據(jù)集”用于預(yù)測(cè)對(duì)水蚤的急性水生毒性定量響應(yīng)。

實(shí)驗(yàn)中，用以上四個(gè)數(shù)據(jù)集分別進(jìn)行建模，對(duì)增量式Huber-SVR算法，增量式ε-SVR算法和增量式RBF算法的擬合程度進(jìn)行測(cè)試，總共分為12種情形。每次建模時(shí)，在樣本數(shù)據(jù)集中隨機(jī)抽取150個(gè)樣本，其中前100個(gè)樣本作為訓(xùn)練樣本，剩余的50個(gè)樣本作為預(yù)測(cè)的測(cè)試樣本。為了避免偶然因素的影響，在這12種情形下，每種情形分別重復(fù)試驗(yàn)200次，再對(duì)200次的平均結(jié)果進(jìn)行比較，比較三種增量式算法的預(yù)測(cè)性能。

3.3 實(shí)驗(yàn)結(jié)果與分析

表1 增量式Huber-SVR、增量式ε-SVR和增量式RBF算法預(yù)測(cè)結(jié)果比較

設(shè)真實(shí)值為y，預(yù)測(cè)值為f(x)。

(1)平均誤差率：

(2)平均絕對(duì)誤差:

(3)均方根誤差：

從表1中的誤差分析可以看出：在這四組實(shí)驗(yàn)中，增量式Huber-SVR算法的平均誤差率以及AAE和RMSE三項(xiàng)指標(biāo)均小于增量式ε-SVR算法和增量式RBF算法中對(duì)應(yīng)的數(shù)值；這是因?yàn)橄鄬?duì)于ε-不敏感損失函數(shù)，Huber損失函數(shù)更適用于預(yù)測(cè)數(shù)據(jù)有噪聲的情況，而真實(shí)的數(shù)據(jù)常常是有噪聲的，這在實(shí)驗(yàn)結(jié)果當(dāng)中得到了驗(yàn)證。而增量式RBF學(xué)習(xí)算法對(duì)真實(shí)數(shù)據(jù)進(jìn)行回歸預(yù)測(cè)時(shí)，預(yù)測(cè)精度明顯低于兩種增量式SVR算法。所以在用增量式Huber-SVR進(jìn)行回歸預(yù)測(cè)時(shí)，預(yù)測(cè)的誤差率更小，精度也更高。這也更加說明了研究增量式Huber-SVR算法的必要性和該算法的有效性。

4 結(jié)論

增量式Huber-SVR算法在預(yù)測(cè)樣本數(shù)據(jù)集發(fā)生變動(dòng)時(shí)，能夠在預(yù)測(cè)過程中及時(shí)對(duì)模型中的參數(shù)進(jìn)行修正，在之前已經(jīng)建立好了的模型上逐步更新，就能夠得到結(jié)果。該模型結(jié)合了Huber損失函數(shù)的優(yōu)點(diǎn)：當(dāng)訓(xùn)練樣本數(shù)據(jù)分布未知時(shí)，Huber損失函數(shù)具有魯棒性，同時(shí)在有噪聲的情況下Huber損失函數(shù)是比ε損失函數(shù)更好的選擇。本文將增量式Huber-SVR算法，應(yīng)用最為廣泛的增量式ε-SVR算法和增量式RBF算法應(yīng)用于實(shí)際數(shù)據(jù)中進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，在對(duì)真實(shí)的數(shù)據(jù)進(jìn)行回歸預(yù)測(cè)時(shí)，增量式Huber-SVR算法對(duì)真實(shí)數(shù)據(jù)的擬合程度更好，回歸預(yù)測(cè)精度更高，誤差率也較小。增量式Huber-SVR算法的建模雖然取得了一定的成果，但當(dāng)訓(xùn)練數(shù)據(jù)不斷增加到一定程度時(shí)，運(yùn)用增量式算法進(jìn)行回歸預(yù)測(cè)，可能會(huì)出現(xiàn)困難。今后的研究可以考慮在樣本的訓(xùn)練過程中增加一個(gè)新樣本的同時(shí)刪減一個(gè)舊樣本，實(shí)現(xiàn)Huber-SVR的在線學(xué)習(xí)。