非線性回歸支持向量機的SMO算法改進

趙長春 姜曉愛

(北京航空航天大學 航空科學與工程學院，北京100191)

金英漢

(西北工業(yè)大學航天學院，西安710072)

支持向量機(SVM，Support Vector Machine)理論是Vapnik等人提出的一種新型的機器學習算法，在分類問題和回歸問題上應用較廣泛.由于SVM訓練中需要求解二次規(guī)劃問題，在訓練大規(guī)模數(shù)據(jù)時占用內存空間較大，文獻［1］提出了序列最小優(yōu)化(SMO，Sequential Minimal Optimization)算法，該算法將問題分解為每次優(yōu)化兩個樣本的Lagrange乘子，避免了求解二次規(guī)劃問題，提高了訓練速度.文獻［2］詳細介紹了SMO回歸算法的實現(xiàn)方法，由于該算法訓練時間較長，出現(xiàn)了許多對SMO算法的改進方法［3－5］，以縮短訓練時間.此外，支持向量機的參數(shù)選擇對訓練模型的精度和訓練速度影響較大，通過選擇最優(yōu)的支持向量機參數(shù)可以提高訓練模型的準確度和訓練效率［6－7］.參數(shù)優(yōu)化方法的實質是利用測試樣本對訓練模型測試的精度來判斷是否得到最優(yōu)參數(shù)，參數(shù)尋優(yōu)的過程就是不斷改變參數(shù)值和用新參數(shù)反復訓練模型的過程.因此，研究提高算法自身的訓練速度的方法，能在很大程度縮短訓練時間.

本文對SMO算法的改進方法進行了研究，提出新的改進算法用于非線性數(shù)據(jù)和非線性函數(shù)的回歸，通過改進優(yōu)化乘子更新方法、采用雙閾值法、預存核函數(shù)、增加停機準則等方法加快了訓練速度，提高了訓練結果穩(wěn)定性，最后對支持向量機參數(shù)選擇方法做了討論.

1 支持向量機回歸

支持向量機回歸的求解方法是將原始最小化問題轉化為求其對偶最大化問題，對于樣本集(xi，yi)，i=1，2，…，l，求解的對偶問題［2］可表示如下:

式中，ε為不敏感損失函數(shù)(示意圖見圖1);C為規(guī)則化參數(shù)，用于平衡回歸函數(shù)的平坦程度;αi，為拉格朗日乘子;k(x，x)=Φ(x)·Φ(x)，ijij記為kij，為滿足Mercer條件的核函數(shù)，Φ(·)為非線性映射.常用的核函數(shù)有線性核函數(shù)、多項式核函數(shù)、徑向基核函數(shù)、Sigmoid核函數(shù)等.

回歸函數(shù)可表示為

式中，b為閾值.

圖1中，ε用于控制回歸逼近誤差范圍，ξ≥0為松弛因子，表示回歸函數(shù)值f(xi)與樣本值yi之差的絕對值|f(xi)－yi|，當絕對值小于或等于ε時，取0，當絕對值大于ε時，取ξ.

圖1 ε不敏感損失函數(shù)示意圖

2 回歸SMO算法理論

作變量代換，令

SMO算法每次只優(yōu)化兩個變量，固定其他變量值，設2 個待優(yōu)化變量分別為，優(yōu)化目標函數(shù)可表示成關于的函數(shù):

式中，η=kuu－2kuv+kvv，當核函數(shù)滿足 Mercer條件時，η≥0成立.

3 SMO算法改進

3.1 采用雙閾值blow和bup

文獻［3］中指出，由于閾值b正確性不確定，使得在優(yōu)化中對已達到最優(yōu)值的乘子更新，浪費執(zhí)行時間，因此采用雙閾值blow和bup的方法對算法做了改進.

令Fi=yi－〈ω，Φ(xi)〉，其中〈·，·〉表示內積，有以下5種情況:

根據(jù)式(9)和式(10)可定義b的上、下界，如下:

由于數(shù)值解原因，通常不可能獲得準確的優(yōu)化結果，因此，通過增加一項正誤差τ獲取近似優(yōu)化結果，重新寫式(12)，如下:

查找違反最優(yōu)條件式(13)的樣本作為待優(yōu)化樣本，即滿足如下條件之一的樣本為待優(yōu)化樣本:

3.2 優(yōu)化乘子更新

由于Fu－Fv的值與b無關，通過其更新乘子可避免乘子優(yōu)化結果受不準確的b值的影響，乘子更新步驟如下:

1)更新優(yōu)化乘子分下面3個步驟.

①按如下式子進行更新:

②如果更新后兩個乘子符號相同則得到本次更新結果，反之，定義調節(jié)變量Δ=2ε/η，如果根據(jù)Δ更新后的乘子和符號不改變，按式(16)進行:

③如果更新后的乘子符號發(fā)生改變，則設置乘子為0或sold，按如下條件進行:

2)約束優(yōu)化乘子范圍.

3.3 停機準則

目標問題與其對偶問題的對偶間隙為0時，達到全局最優(yōu)解，但數(shù)值求解只能得到近似全局最優(yōu)解，因此將對偶間隙作為停機準則，設定訓練精度在達到預定值后停止計算［8－9］，減少訓練時間.

定義如下關系:

記目標優(yōu)化問題為函數(shù) U(ω，ξ，ξ*)，對偶問題為函數(shù)W()，則函數(shù)表達式為

停機準則計算式為

當σ小于給定精度后停止訓練，能縮短訓練時間，將σ停機準則和式(14)的違反條件共同判斷停止訓練條件.

3.4 核函數(shù)矩陣計算和存儲

在訓練過程中，為避免重復計算核函數(shù)，訓練開始時進行核函數(shù)矩陣存儲.核函數(shù)矩陣是對稱矩陣，存儲時只需存儲對稱部分，假設有N個樣本，則可用大小N(N+1)/2的一維數(shù)組aJ存儲核函數(shù)矩陣，從主對角元素開始按主對角線方向順序存儲矩陣元素，如圖2所示，元素kmn在矩陣中的位置與在數(shù)組aJ中位置對應關系如下:

式中，J為一維數(shù)組元素的下標;m，n分別為核函數(shù)矩陣元素kmn的行號和列號.核函數(shù)矩陣對稱，只需計算主對角線和其上方的元素，其下方的元素與上方元素對稱.規(guī)定m≤n，如果m＞n，交換m和n的值后再計算.

圖2 核矩陣元素存儲

3.5 改進的SMO算法描述

改進后的SMO算法具體步驟如下:

2)從整個樣本中隨機選擇一個樣本i，令blow=yi－ ε，bup=yi+ ε，ilow=i，iup=i.

3)SMO算法采用內、外兩層循環(huán)選擇待優(yōu)化樣本，步驟如下:

4)優(yōu)化乘子更新步驟:采用3.2節(jié)乘子更新法更新優(yōu)化樣本的乘子.如果優(yōu)化乘子的改變量大于一定值，則更新優(yōu)化樣本乘子和界內樣本的誤差值 Fi=yi－〈ω，Φ(xi)〉，并按式(11)在界內樣本中尋找新的 blow，bup，ilow，iup.

5)在界內樣本或所有樣本遍歷循環(huán)完成若干次迭代后計算一次停機準則σ值.

6)為防止優(yōu)化程序出現(xiàn)死循環(huán)，當滿足以下3個條件之一就結束算法:優(yōu)化成功的樣本數(shù)量為0、停機準則σ小于給定精度、迭代次數(shù)大于給定次數(shù);如果沒有滿足條件的，則轉3).

4 仿真實驗及結果分析

將改進的算法與原始的SMO算法做對比，實驗使用兩個不同的擬合數(shù)據(jù).通過對比達到相同停機準則時的時間和測試均方根誤差(RMSE，Root Mean Square Error)來評價兩個算法的優(yōu)越性，RMSE表達式為

式中，N為測試樣本總數(shù);yi為樣本目標值;為回歸值.

4.1 仿真實驗1

選取文獻［10］中的訓練樣本作為算例，該數(shù)據(jù)具有非線性特點，樣本如下:

所選擇的測試樣本如下:

選用徑向基核函數(shù)，表達式如下:

參數(shù)設置基本原則:優(yōu)化的參數(shù)對(C，γ2)的組合有很多［7］，樣本數(shù)據(jù)變動趨勢較平坦時，γ2取較大值，常取大于1的值;反之，取較小值，常取小于1的值;C值用于平衡回歸函數(shù)平坦程度，一般取樣本均值附近的值;ε控制回歸函數(shù)逼近誤差范圍，根據(jù)實際需求取值;較小的τ值會增加訓練時間，取值應當比ε取值小1～2個數(shù)量級;σ取值決定了訓練精度，不宜過小，否則會增加訓練時間.

根據(jù)上述基本原則和多次實驗設置參數(shù):C=4，γ2=2.1，ε =0.3，τ=0.000 1.采用在不同停機準則值下所用的訓練時間和RMSE值作對比，表1為2種算法的對比.

表1 2種算法比較

從表1可以看出，與原始算法相比，改進后的算法訓練時間明顯縮短，但隨著停機準則σ值減小而增加，因為停機準則σ值越小表示對偶間隙值越小，則訓練時間會增加;2種算法的RMSE值隨停機準則σ值減小而減小，在相同訓練精度條件下，改進的算法能有效加快訓練速度.

用改進的SMO算法訓練非線性數(shù)據(jù)的回歸結果如圖3所示，從圖中可看出，SMO算法對非線性數(shù)據(jù)擬合效果較好.

4.2 仿真實驗2

選擇函數(shù)進行擬合，函數(shù)表達式如下:

產(chǎn)生100個隨機數(shù)點X，代入式(26)得到Y，組成訓練樣本(X，Y)，產(chǎn)生100個點隨機數(shù)Xt，代入式(26)得到 Yt，組成測試樣本(Xt，Yt).

圖3 非線性數(shù)據(jù)回歸結果(C=4，γ2=2.1)

選用徑向基核函數(shù)，根據(jù)參數(shù)選擇基本原則和多次實驗設置參數(shù):σ = －2，ε =0.01，τ =0.001.分別固定C值和固定γ2值，在這2種情況下對比2種算法的支持向量數(shù)目、訓練時間、RMSE值.

從表2、表3可以看出，能得到較小RMSE值的最佳C值為1～1.5之間，最佳 γ2值為0.1;選取最佳 C和 γ2時，2種算法都能得到較小的RMSE值和較少的支持向量，較小的γ2值和較大的C值都會增加訓練時間;與原始SMO算法相比，在達到相同的訓練精度條件下，改進的算法明顯縮短訓練時間;原始算法使用了隨機選擇優(yōu)化樣本的方法，所以訓練結果不穩(wěn)定，同時也增加了訓練時間，而改進后的算法使訓練結果具有穩(wěn)定性，使訓練速度更快.

用改進的SMO算法對非線性函數(shù)回歸的結果見圖4，從圖中可看出，SMO算法對非線性函數(shù)回歸效果較好，隨機測試樣本測試誤差較小.

表2 固定C=1.2情況下2種算法比較

表3 固定γ2=0.1情況下2種算法比較

圖4 非線性函數(shù)回歸結果(C=1.2，γ2=0.1)

5 結論

通過仿真實驗，驗證了支持向量機算法具有較強的非線性數(shù)據(jù)擬合功能，改進的SMO算法在訓練速度和結果穩(wěn)定性上得到提高.

實驗表明，參數(shù)C和γ2，停機準則σ值對訓練模型精度和訓練速度影響較大，參數(shù)選擇具有數(shù)據(jù)依賴性，仿真實驗1中數(shù)據(jù)分布值域廣，數(shù)據(jù)變化趨勢較平坦，則γ2取較大值，仿真實驗2中數(shù)據(jù)分布值域窄，數(shù)據(jù)變化較劇烈，則γ2取較小值，參數(shù) C取值大致位于最大值和最小值的中間;停機準則σ值越小，訓練時間越長，精度越高，可根據(jù)訓練要求取不同值，如何更好地選擇參數(shù)C和γ2是值得繼續(xù)研究的方向.

References)

［1］ Platt J C.Fast training of support vector machines using sequential minimal optimization［R］.MSR-TR-98-14，1998

［2］ Smola A J，Scholkopf B.A tutorial on support vector regression［R］.NC2-TR-1998-030，1998

［3］ Shevade S K，Keerthi S S，Bhattacharyya C，et al.Improvements to SMO algorithm for SVM regression［J］.IEEE Transactions on Neural Networks，2000，11(5):1188 －1193

［4］ Flake G W，Lawrence S.Efficient SVM regression training with SMO［J］.Machine Learning，2002，46(1-3):271 －290

［5］ 張浩然，韓正之.回歸支持向量機的改進序列最小優(yōu)化學習算法［J］.軟件學報，2003，14(12):2006 －2013 Zhang Haoran，Han Zhengzhi.An improved sequential minimal optimization learning algorithm for regression support vector machine［J］.Journal of Software，2003，14(12):2006 －2013(in Chinese)

［6］ 劉勝，李妍妍.自適應GA-SVM參數(shù)選擇算法研究［J］.哈爾濱工程大學學報，2007，28(4):398 －402 Liu Sheng，Li Yanyan.Parameter selection algorithm for support Vector machines based on adaptive genetic algorithm ［J］.Journal of Harbin Engineering University，2007，28(4):398 － 402(in Chinese)

［7］ 閆國華，朱永生.支持向量機回歸的參數(shù)選擇方法［J］.計算機工程，2009，35(14):218 －220 Yan Guohua，Zhu Yongsheng.Parameters selection method for support vector machine regression ［J］.Computer Engineering，2009，35(14):218 －220(in Chinese)

［8］ 董磊，任章，李清東.基于SMO-SVR的飛機舵面損傷故障趨勢預測 ［J］.北京航空航天大學學報，2012，38(10):1300－1305 Dong Lei，Ren Zhang，Li Qingdong.Fault prediction for aircraft control surface damage based on SMO-SVR ［J］.Journal of Beijing University of Aeronautics and Astronautics，2012，38(10):1300－1305(in Chinese)

［9］ 王書舟，傘冶，張允昌.基于支持向量機改進 SMO算法的直升機旋翼自轉著陸過程建模［J］.航空學報，2009，30(1):46－51 Wang Shuzhou，San Ye，Zhang Yunchang.Modeling for landing process of helicopter with rotator self-rotating based on modified SMO algorithm of support vector machine［J］.Acta Aeronautica et Astronautica Sinica，2009，30(1):46 －51(in Chinese)

［10］ 王定成.支持向量機建模預測與控制［M］.北京:氣象出版社，2009:48－49 Wang Dingcheng.Prediction and control based on support vector machine modelling［M］.Beijing:Meteorological Press，2009:48－49(in Chinese)