趙朝賀

（1.安徽省電力設(shè)計院有限公司，安徽 合肥 230601）

一種改進(jìn)的支持向量機參數(shù)優(yōu)化方法

趙朝賀1

（1.安徽省電力設(shè)計院有限公司，安徽 合肥 230601）

為了保證支持向量機在提高核參數(shù)尋優(yōu)效率的同時，擁有較高的學(xué)習(xí)精度，深入研究了核參數(shù)對支持向量機分類的影響，分析了網(wǎng)格搜索法和雙線性搜索法的優(yōu)缺點，并以此為基礎(chǔ)提出了一種改進(jìn)的參數(shù)優(yōu)化方法。實驗結(jié)果表明，該算法在保證支持向量機獲得較高學(xué)習(xí)精度的同時能大大縮短參數(shù)尋優(yōu)的時間，證明了該算法的優(yōu)越性。

支持向量機；RBF核函數(shù)；參數(shù)優(yōu)化；網(wǎng)格搜索；雙線性搜索

支持向量機（SVM）是基于小樣本統(tǒng)計理論提出的一種新的機器學(xué)習(xí)方法，在處理小樣本、非線性及高維向量上展現(xiàn)出其獨特的優(yōu)勢，已成為機器學(xué)習(xí)、模式識別、信息提取等領(lǐng)域的研究熱點，受到眾多研究者的廣泛關(guān)注。實踐證明，核參數(shù)和懲罰系數(shù)對SVM性能有著很大的影響，只有選擇合適的核函數(shù)及其參數(shù)才能得到具有良好推廣能力的SVM分類器[1]。

當(dāng)前國際上對核參數(shù)的選擇還未形成統(tǒng)一模式，主要靠經(jīng)驗和試算來解決，包括實驗法、網(wǎng)格搜索法、雙線性搜索法、遺傳算法和粒子群算法等。其中，實驗法耗時且難以獲得最優(yōu)參數(shù)，網(wǎng)格搜索法精度高但非常耗時，雙線性搜索法效率高但精度一般，遺傳算法和粒子群算法較為復(fù)雜且容易陷入局部最優(yōu)。綜合考慮以上常用參數(shù)尋優(yōu)算法的優(yōu)缺點，提出了一種改進(jìn)的參數(shù)尋優(yōu)方法。它能在大幅度減少參數(shù)尋優(yōu)時間的同時，使SVM獲取較高的學(xué)習(xí)精度。

1 SVM理論基礎(chǔ)

SVM的原理是用分離超平面作為分離數(shù)據(jù)的線性函數(shù)，解決非線性分類問題，即升維與線性化[2]。其最優(yōu)分類形式為：搜索一個分類超平面，能讓兩類無錯誤地分開，且樣本的分類間隔最大。其基本的數(shù)學(xué)公式為：在條件的約束下，求函數(shù)的極小值。其中，w為超平面的法向量；b為超平面的平移量；C為懲罰系數(shù)，目的是控制誤差ξ邊界的平衡。

引入拉格朗日乘子αi，解算上述優(yōu)化問題得到分類函數(shù)為：

根據(jù)泛函數(shù)理論，在滿足K(x·xi)=φ(x)·φ(xi)條件下，解算上述問題獲得最終分類函數(shù)為：

其中，核函數(shù)K(x·xi)有多種形式：線性核K(x·y)=x·y；多項式核K(x·xi)=(x·xi+1)d，d是自然數(shù)；RBF核（Gaussian徑向基核）γ＞0； Sigmoid核K(x·xi)=tanh(v(x·xi)+c)。

2 核參數(shù)對SVM的影響

2.1 核參數(shù)對SVM推廣能力的影響

核函數(shù)形式的不同決定了SVM模型的差異，用戶總是想使用推廣能力最好的分類模型，但推廣能力卻無法通過確切的值來表示。文獻(xiàn)[3]總結(jié)的常用評估泛化誤差方法中，最為經(jīng)典是交叉驗證法（CV），其基本思想是將訓(xùn)練樣本均勻分為K組，對每個子集作學(xué)習(xí)分類測試，其余K?1個子集作為負(fù)樣本，測試完成后將獲得K個訓(xùn)練模型，K-CV的正確率由這K個模型最終測試集正確率的平均值來表示。通常情況下，K值會大于2，而實際操作中K值一般最小取3，只有當(dāng)樣本數(shù)據(jù)量很小是，K值才可能取2。K?CV能有效避免應(yīng)用中產(chǎn)生過學(xué)習(xí)及欠學(xué)習(xí)的現(xiàn)象，且最終得到的驗證結(jié)果說服力較強。

2.2 核參數(shù)對SVM分類性能的影響

評價SVM分類器的好壞，主要從它的推廣能力和準(zhǔn)確度來考慮。較多相關(guān)文獻(xiàn)證明，選取何種核函數(shù)對SVM分類性能影響不大，主要影響因子是核函數(shù)的參數(shù)及誤差懲罰因子C[4]。核函數(shù)中應(yīng)用表現(xiàn)能力最好的是學(xué)習(xí)能力較強的RBF核函數(shù)，無論維數(shù)高低，樣本數(shù)據(jù)量大小，適用性都表現(xiàn)較好，收斂范圍較寬，是常用核函數(shù)中較為推崇的分類核[5]。因此RBF的核參數(shù)γ以及C便是影響SVM分類性能的主要因素，它們不僅影響SVM分類器的復(fù)雜性還影響著SVM的推廣能力。本文將通過實驗分析參數(shù)(C,γ)對SVM分類性能的影響。

2.2.1 誤差懲罰參數(shù)C的影響

C的作用是在給定的特征子空間中，通過變化SVM分類器的置信域與經(jīng)驗風(fēng)險的比值來推動SVM的推廣能力，直至達(dá)到最好。若C越小，則表明對此模型經(jīng)驗誤差懲罰較輕，SVM分類器的復(fù)雜性降低而經(jīng)驗風(fēng)險增大；若C→∞，則必須要滿足所有約束條件，即表明訓(xùn)練樣本要保證全部無錯誤地被分開。所以一定至少存在一個誤差懲罰參數(shù)C使得SVM的推廣能力達(dá)到最佳。

由圖1可知，當(dāng)C取值較小時分類正確率較低，隨C的增加分類正確率也急劇升高，即SVM的分類能力得到快速提升；當(dāng)C大于某個閾值時，分類正確率變化不大，趨于穩(wěn)定，表明此時SVM的分類性能對C的變換不再敏感。圖1中在logC＞1.0時，SVM分類準(zhǔn)確率已達(dá)到一個較高水平，隨C增加分類正確率只是在某一值附近波動。利用這一現(xiàn)象和推論，可加快C的計算速度，完成C的初始搜索：首先從較小的C開始搜索，逐步增大C的取值，當(dāng)SVM分類正確率不再增加時，認(rèn)為C已處于“好區(qū)”，把該值作為SVM最優(yōu)懲罰參數(shù)的初值。

圖1 分類正確率隨C的變化趨勢

2.2.2 核參數(shù)γ的影響

由于數(shù)據(jù)特征空間、核函數(shù)以及映射函數(shù)三者之間存在一一對應(yīng)的關(guān)系，一旦核函數(shù)被確立，則映射函數(shù)和數(shù)據(jù)特征空間的關(guān)系也就被唯一確定。線性分類超平面的VC維數(shù)以及分離最優(yōu)超平面的最小經(jīng)驗誤差值的大小都由特征子空間的維數(shù)決定。若維數(shù)過高，則導(dǎo)致SVM的最優(yōu)分類超平面變得較復(fù)雜，置信區(qū)間過大而經(jīng)驗風(fēng)險過小；反之亦然。當(dāng)γ取值在兩端時，SVM分類器的推廣能力都不會很好，因此只有合適的核參數(shù)才能將原始樣本空間映射到最佳的特征子空間中，得到合適的、推廣能力最佳的SVM[6]。

圖2 分類正確率隨γ值的變化趨勢

由圖2可知，SVM分類器的分類質(zhì)量直接受核參數(shù)的影響。隨著γ值的增加，SVM分類正確率先由低到高；達(dá)到峰值后便由高到低逐漸下降到趨于穩(wěn)定，此時SVM分類準(zhǔn)確率較低。SVM分類準(zhǔn)確率隨γ值大幅度變化表明核參數(shù)γ可以控制其靈活性，當(dāng)γ值較大時，核函數(shù)則變?yōu)橐粋€常函數(shù)。從分類正確率隨γ的變化趨勢，可明顯看出存在一個峰值，對應(yīng)的γ值此時最佳，說明“好區(qū)”是存在的，關(guān)鍵是選擇最優(yōu)的γ值。

通過實驗分析分類正確率與參數(shù)(C,γ)的關(guān)系，可估計C的最優(yōu)近似值，縮小參數(shù)空間的搜索范圍；再搜索“好區(qū)”的核參數(shù)γ，進(jìn)一步提高搜索參數(shù)(C,γ)的效率和準(zhǔn)確度，從而提高SVM的分類精度。

3 SVM核參數(shù)尋優(yōu)算法

對于RBF核參數(shù)(C,γ)的優(yōu)化選擇有多種，參數(shù)(C,γ)的差異決定了SVM的不同，常見的核參數(shù)尋優(yōu)算法主要有雙線性搜索法[7]和網(wǎng)格搜索法兩種。

3.1 雙線性搜索法

雙線性搜索法計算(C,γ)最優(yōu)組合的原理主要是利用參數(shù)(C,γ)的差異決定SVM的不同這一思想。文獻(xiàn)[7]指出，參數(shù)空間大致可劃分為3種：欠學(xué)習(xí)區(qū)、過學(xué)習(xí)區(qū)和好區(qū)（見圖3）。

大量實驗證明：在以(logC,logγ)為坐標(biāo)的參數(shù)空間中，最優(yōu)的參數(shù)組合(C,γ)會集中在“好區(qū)”直線logγ=logC?log附近，可使SVM分類精度的達(dá)到最高，即圖中“好區(qū)”的虛線附近。因此，雙線性搜索算法實現(xiàn)參數(shù)優(yōu)化的步驟為：

1）利用線性核SVM解算最優(yōu)C，使得此時線性核的SVM學(xué)習(xí)精度最高，把此時解算的C記為

圖3 不同參數(shù)空間的SVM性質(zhì)

3.2 網(wǎng)格搜索法

網(wǎng)格搜索法[8]的原理是將C和γ分別取i和j個值，得到i×j個(C,γ)組合，分別訓(xùn)練各組合參數(shù)，將學(xué)習(xí)精度最高的那對參數(shù)作為搜索的最佳參數(shù)組合，為了得到較高的分類精度，參數(shù)C和γ的步長通常為0．1。

分析上述兩種搜索策略可以看出：以網(wǎng)格搜索算法獲得的參數(shù)組合(C,γ)求解的SVM學(xué)習(xí)精度較高，數(shù)據(jù)計算量大，時間代價昂貴；雙線性搜索算法運算速度較快。在以RBF核為基礎(chǔ)的SVM參數(shù)搜索階段，網(wǎng)格搜索算法代價為O(N2)，雙線性搜索算法代價為O(N)。此外雙線性搜索算法最優(yōu)參數(shù)組合獲取的精度較大程度地依賴于線性核SVM中的準(zhǔn)確度。

3.3 改進(jìn)的參數(shù)搜索法

在分析兩種搜索算法主要影響因素的基礎(chǔ)上，為了較少計算量和運行時間，提高SVM的分類精度，本文對參數(shù)尋優(yōu)算法進(jìn)行了改進(jìn)，主要步驟為：

4 實驗驗證

為了驗證本文改進(jìn)的參數(shù)搜索算法的效率、有效性以及學(xué)習(xí)精度，分別將網(wǎng)格搜索法、雙線性搜索法和本文參數(shù)搜索算法進(jìn)行比較分析。在Microsoft Windows 7操作系統(tǒng)下，基于VS2008和LibSVM 3．1．7集成開發(fā)環(huán)境編寫了算法實驗程序。實驗數(shù)據(jù)采用基于均值漂移的圖像分割算法[9]獲得的資源三號測繪衛(wèi)星影像分割對象單元，從中選擇330個訓(xùn)練樣本，并將其分成4種類別，選用顏色矩特征作為特征向量進(jìn)行測試。實驗中C值范圍為[2-10,210]、γ值范圍為[210,2-10]，由于傳統(tǒng)方法中步長一般為0．1，而起初SVM的正確率隨C值增加顯著，因此本文算法將C值初始步長設(shè)為1，γ值初始步長擴大100倍，設(shè)定為10，測試中逐次減小參數(shù)(C,γ)的步長。采用K-CV方法對正確率進(jìn)行測試，K值為5，則3種參數(shù)尋優(yōu)算法測試結(jié)果如表1所示。

從表1不難看出，網(wǎng)格搜索法耗時最長，本文算法在保證SVM分類精度的同時，大大縮短了參數(shù)尋優(yōu)的時間。實驗結(jié)果表明，對于龐大訓(xùn)練數(shù)據(jù)集，本文算法在相對較少的時間內(nèi)，能夠使SVM分類器獲得較高的學(xué)習(xí)精度。

表1 3種參數(shù)尋優(yōu)方法比較

[1] Chapelle O, Vapnik V, Bousquet O． Choosing Multiple Parameters for Support Vector Machines[J]．Machine Learning, 2002,46(1/3):131-159

[2] SU C T, YANG C H． Feature Selection for the SVM: an Application to Hypertension Diagnosis[J]．Expert Systems with Applications,2008,34(1):754-763

[3] 宋曉峰,陳德釗,胡上序．支持向量機泛化能力估計若干方法[J]．計算機科學(xué),2004,31(8):125-126

[4] 劉大寧, 楊永樂, 白林． SVM核函數(shù)對分類精度影響的研究[J]．佳木斯大學(xué)學(xué)報(自然科學(xué)版),2012(4):627-630

[5] 宋暉,薛云,張良均．基于SVM分類問題的核函數(shù)選擇仿真研究[J]．計算機與現(xiàn)代化,2011,30(8):133-136

[6] Keerthi S S, LIN C J． Asymptotic Behaviors of Support Vector Machines with Gaussian Kernel[J]．Neural Computation, 2003,15(7):1 667-1 689

[7] 李琳,張曉龍．基于RBF核的SVM學(xué)習(xí)算法的優(yōu)化計算[J]．計算機工程與應(yīng)用,2006,42(29):190-192,204

[8] 王興玲,李占斌．基于網(wǎng)格搜索的支持向量機核函數(shù)參數(shù)的確定[J]．中國海洋大學(xué)學(xué)報(自然科學(xué)版),2005,35(5):859-862 [9] 余國斌,陳愛斌,孫華,等．基于Mean Shift的高分辨率遙感影像分割方法[J]．中南林業(yè)科技大學(xué)學(xué)報,2012,32(10):168-172

P237

B

1672-4623（2017）01-0053-03

10.3969/j.issn.1672-4623.2017.01.016

趙朝賀，碩士，主要從事工程測量及模式識別等方面的研究。

2015-10-26。

項目來源：國家自然科學(xué)基金資助項目（41371438）。