增量式Huber-支持向量回歸機算法研究

周曉劍, 肖 丹, 付 裕

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

0 引言

支持向量機(Support Vector Machine，SVM)是數據挖掘中的一項重要的技術，由Vapnik于20世紀90年代年首先提出的，是建立在統計學習理論(Statistical Learning Theory，SLT)中的VC維理論以及結構風險最小化原則的基礎之上的，它的本質是求解凸二次規劃問題，與傳統的學習方法相比，支持向量機在解決小樣本、非線性和高維分類問題中有顯著的優勢[1～3]。

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

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

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

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

1.1 Huber-SVR基本形式

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

(1)

其中μ為損失函數的參數，ξ為真實值與預測值之間的偏差。

(2)Huber-SVR原始問題：

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

當SVR中的損失函數取Huber損失函數時，就構成了Huber-支持向量回歸機。Huber-支持向量回歸機(Huber-SVR)的原始問題如下:

(2)

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

(3)Huber-SVR對偶模型:

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

(3)

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

(4)

(5)

把式(3)化簡為:

(6)

根據凸優化理論，式(6)等價于如下的拉格朗日函數:

(7)

1.2 KKT條件

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

(8)

(9)

函數間隔：

(10)

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

(11)

2 增量式Huber-SVR算法

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

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

2.1 增量關系

本小節介紹的是增量ΔθC發生變化時，而沒有引起樣本在S集，E1集和E2集之間移動時，增量ΔθC和與Δh(xi)和Δθi之間的關系。

由式子(10)得:

(12)

(13)

i∈S時，要保持樣本不發生移動，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)可以看出當時，ΔθC是如何影響Δθi和Δb的值。把(23)擴展到所有樣本時，因為E1和E2中的θ值為常數，所以i?S時，Δθi=0，因此(21)式隱含著，當i?S時，βi≡0。

當i?S時，定義集合N:

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

(25)

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

(26)

所以，令:

(27)

最后得到:

(28)

Δθi=0,i?S

(29)

當i∈S時，Δh(xi)=0，所以γ≡0。

當S是空集時，根據式子(12)，(13)，(27)得:

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

(30)

由以上分析可知：當新樣xC加入，沒有引起其他集合中樣本發生移動時：

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

2.2 樣本的移動

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

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

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

(1)xC加入S集：

(31)

(2)xC加入E1集:

(32)

(3)xC加入E2集

(33)

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

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

Δθi=C-θi

(34)

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

Δθi=-C-θi

(35)

樣本點從S集移到E1集時，這些樣本的θi值會逐漸增加到邊界值C；樣本點從S集移到E2集，這些樣本的θi值會逐漸減小到邊界值-C;

(36)

情況3i?S，樣本點從E1集或者E2集移到S集：

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

(37)

最后，結合三種情況計算當只有一個樣本點在集合之間移動時的最小增量ΔθC:

q=sign(-h(xC))

(38)

(39)

2.3 逆矩陣的更新

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

(40)

(41)

根據分塊矩陣求逆的方法，集合S中增加一個樣本xt時，矩陣更新如下：

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

(42)

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

(43)

(44)

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

(45)

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

(3)集合S中減少一個樣本點時，矩陣更新如下:

(46)

當索引i、j為0時，指的是b這一項。

2.4 算法初始化

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

(47)

θ2=-θ1

(48)

b=(y1-y2)/2

(49)

2.5 算法步驟

增量式Huber-SVR算法:

輸入：

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

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

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

矩陣H；

新樣本xC。

輸出：

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

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

更新后的矩陣H。

算法步驟：

1、初始化令θC=0；

2、計算h(xC)；

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

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

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

(2)做如下更新：

直到滿足下列條件之一：

③原訓練集中的一個樣本i發生移動：

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

更新矩陣H；

5、返回4。

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

3 實驗及其結果

3.1 實驗目的

驗證本文提出的增量式Huber-SVR算法的可行性，將該算法與應用較廣泛的增量式ε-SVR算法和文獻13中的增量式RBF學習算法[13]進行比較，將三種算法應用于實際數據中，比較三種算法的預測性能。

3.2 實驗設計

本實驗選取的數據來源于UCI機器學習存儲庫，有“翼型自噪聲數據集”，來自西班牙北部的“葡萄酒質量數據集”，“聯合循環電廠數據集”和“QSAR水生毒性數據集”。“翼型自噪聲數據集”共1503條數據，每條數據包括5個輸入變量，輸出變量是：壓縮的聲壓級。“葡萄酒質量數據集”刪除重復樣本后包括1359條紅葡萄酒樣品數據，輸出變量是：葡萄酒質量得分。“聯合循環電廠數據集”用來預測工廠的每小時凈電能輸出(EP)。“QSAR水生毒性數據集”用于預測對水蚤的急性水生毒性定量響應。

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

3.3 實驗結果與分析

表1 增量式Huber-SVR、增量式ε-SVR和增量式RBF算法預測結果比較

設真實值為y，預測值為f(x)。

(1)平均誤差率：

(2)平均絕對誤差:

(3)均方根誤差：

從表1中的誤差分析可以看出：在這四組實驗中，增量式Huber-SVR算法的平均誤差率以及AAE和RMSE三項指標均小于增量式ε-SVR算法和增量式RBF算法中對應的數值；這是因為相對于ε-不敏感損失函數，Huber損失函數更適用于預測數據有噪聲的情況，而真實的數據常常是有噪聲的，這在實驗結果當中得到了驗證。而增量式RBF學習算法對真實數據進行回歸預測時，預測精度明顯低于兩種增量式SVR算法。所以在用增量式Huber-SVR進行回歸預測時，預測的誤差率更小，精度也更高。這也更加說明了研究增量式Huber-SVR算法的必要性和該算法的有效性。

4 結論

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