一種改進的支持向量機參數優化方法

趙朝賀

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

一種改進的支持向量機參數優化方法

趙朝賀1

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

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

支持向量機；RBF核函數；參數優化；網格搜索；雙線性搜索

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

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

1 SVM理論基礎

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

引入拉格朗日乘子αi，解算上述優化問題得到分類函數為：

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

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

2 核參數對SVM的影響

2.1 核參數對SVM推廣能力的影響

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

2.2 核參數對SVM分類性能的影響

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

2.2.1 誤差懲罰參數C的影響

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

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

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

2.2.2 核參數γ的影響

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

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

由圖2可知，SVM分類器的分類質量直接受核參數的影響。隨著γ值的增加，SVM分類正確率先由低到高；達到峰值后便由高到低逐漸下降到趨于穩定，此時SVM分類準確率較低。SVM分類準確率隨γ值大幅度變化表明核參數γ可以控制其靈活性，當γ值較大時，核函數則變為一個常函數。從分類正確率隨γ的變化趨勢，可明顯看出存在一個峰值，對應的γ值此時最佳，說明“好區”是存在的，關鍵是選擇最優的γ值。

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

3 SVM核參數尋優算法

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

3.1 雙線性搜索法

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

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

1）利用線性核SVM解算最優C，使得此時線性核的SVM學習精度最高，把此時解算的C記為

圖3 不同參數空間的SVM性質

3.2 網格搜索法

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

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

3.3 改進的參數搜索法

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

4 實驗驗證

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

從表1不難看出，網格搜索法耗時最長，本文算法在保證SVM分類精度的同時，大大縮短了參數尋優的時間。實驗結果表明，對于龐大訓練數據集，本文算法在相對較少的時間內，能夠使SVM分類器獲得較高的學習精度。

表1 3種參數尋優方法比較

[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]．計算機科學,2004,31(8):125-126

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

[5] 宋暉,薛云,張良均．基于SVM分類問題的核函數選擇仿真研究[J]．計算機與現代化,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學習算法的優化計算[J]．計算機工程與應用,2006,42(29):190-192,204

[8] 王興玲,李占斌．基于網格搜索的支持向量機核函數參數的確定[J]．中國海洋大學學報(自然科學版),2005,35(5):859-862 [9] 余國斌,陳愛斌,孫華,等．基于Mean Shift的高分辨率遙感影像分割方法[J]．中南林業科技大學學報,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。

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