基于遺傳算法的支持向量機的參數優化*

曹　路　歐陽效源

(1.五邑大學信息工程學院　江門　529020)(2.中山大學信息科學與技術學院　廣州　510006)

?

基于遺傳算法的支持向量機的參數優化*

曹路1,2歐陽效源2

(1.五邑大學信息工程學院江門529020)(2.中山大學信息科學與技術學院廣州510006)

摘要支持向量機的性能主要受到核函數的參數和懲罰因子的影響,其中,以高斯核函數作為支持向量機的核函數的應用最為廣泛。論文在研究了懲罰參數C及高斯核函數參數σ對支持向量機分類性能影響的基礎上,利用網格搜索法和遺傳算法對基于RBF核的SVM進行了參數優化,并通過UCI數據集進行了驗證。實驗結果顯示,遺傳算法相較于網格搜索算法具有更快的搜索速度,在實際運用中更加高效。

關鍵詞支持向量機; 核函數; 參數; 遺傳算法

Class NumberTP273

1　引言

傳統的統計研究方法都是建立在大數定理基礎上的漸近理論,要求學習樣本數足夠多。然而在實際應用中,這一前提往往得不到保證。20世紀60年代V.Vapnik等提出的支持向量機(Support Vector Machine,SVM)是以統計學習理論為基礎的機器學習方法,它通過尋求結構化風險最小來提高學習的泛化能力,即使在小樣本的情況下,也能獲得良好性能;同時,SVM克服了傳統分類器過學習、局部極值和維數災難等缺點,在理論和實際應用中表現出很多優越的性能[1]。

SVM是一種基于核函數的學習方法,通過引入核函數,SVM將低維空間不可分的數據映射到高維空間。但核函數的選取并沒有公認統一的方法。常用的核函數有線性核函數,多項式核函數,高斯核函數和多項式核函數,其中以高斯核應用最為廣泛[2]。本文主要討論了懲罰參數C及高斯核函數參數σ對支持向量機性能的影響,并運用遺傳算法對參數進行尋優得到最優參數。

2　支持向量機理論

支持向量機的基本思想為:尋找一個最優超平面,使得該超平面在保證分類精度的同時,最大化超平面兩側的區域,并利用凸優化中的對偶方法將間隔最大化的問題轉化為一個凸二次規劃問題進行求解[3]。

在標準的支持向量分類器中,獨立的超平面可定義為

f(x)=wTx+b=0

(1)

通過引入正則化項和松弛變量ξ,優化問題可以描述為

s.t.yi(wΤxi+b)≥1-ξi,ξi≥0?xi

(2)

其中C為懲罰參數。為求解式(2)的對偶問題可以獲得最優分界面。為了求解非線性情況,SVM通過核函數將原始特征空間中的非線性分界面映射到高維空間中以獲得更好的分類效果。

3　參數對SVM的影響

3.1懲罰參數C的影響

為了測試懲罰參數C對SVM分類器的影響,對兩類符合正態分布的人工數據樣本用SVM進行分類,如圖1所示。采用的兩類數據為均值分別為0和4,方差為1的20*2維的隨機向量。實心圓點和空心方塊分別表示兩類數據,并在樣本集中加入一個噪聲點(坐標為(1,2)),灰色圓點為支持向量。C的取值分別為10,1,0.01和0.25。其中C=0.25是采用3折交叉驗證情況下用網格搜索法獲得的C的最優解,此時分類準確率為97.561%,即41個訓練點有一個點被錯分。

圖1　C取不同值時的分類面和支持向量

懲罰參數C用于控制模型的復雜程度。由圖1可以得到,當C過大時,噪聲對分界面的影響非常大。C越大,對數據集的擬合程度越大。當C取值趨于無窮大時,此時目標函數問題的所有約束條件都要滿足,所有的訓練樣本數據都要正確分類,容易出現過擬合的現象。隨著C的減小,每個訓練點對最大間隔的潛在影響被削弱,越來越多的訓練點成為支持向量在決策中起作用。當C太小,學習機器的復雜度將減小但經驗風險誤差將變大,容易出現欠擬合的情況,不能很好地泛化新數據。

3.2高斯核參數σ的影響

為了測試高斯核參數σ對SVM分類器的影響,對兩類線性不可分的人工數據樣本用高斯核SVM進行分類,如圖2所示。

圖2　σ取不同值時高斯核SVM分類面和支持向量

可以看到,當C=10,σ=0.05時,決策邊界過于簡單,決策邊界不能很好地彎曲從而圍住方塊數據;而當C=10,σ=20時,幾乎所有的訓練點都成為支持向量,決策面過于復雜;當C=10,σ=1時,模型的效果較好。很明顯,在高斯核中,增加σ會增加邊界的復雜度。只有選取適合的參數(C,σ),在擬合數據和泛化數據之間達到一種折衷,模型才能有較好的性能。

圖3是選取UCI數據庫中glass數據集進行的測試,得到的是測試精度隨參數(C,σ)變化的曲線圖。從圖3(a)圖可知,當懲罰參數在3附近時,能獲得最佳分類精度;從圖3(b)圖中可知,取不同的σ值,預測分類時出現不同的精度。人造數據集和標準數據集均說明,要想得到分類精度較好的SVM學習模型,必須對參數(C,σ)進行優化。

4　參數優化方法

4.1網格搜索法

網格搜索法首先將C和σ設定一個區間范圍,設定步進值;然后在該區間分別取M個值和N個值,組成M×N個不同的(C,σ)參數,利用訓練數據集樣本分別訓練出不同的支持向量機;然后通過測試數據集來估計其學習精確度,從而在M×N個(C,σ)參數中選出模型學習精度最好的一組參數C和σ作為最優參數[4]。

采用網格搜索在某種小步長情況下可以獲得學習模型的最高分類準確率,即獲得全局最優解。但要獲得全局最優解(步長較小),其計算量比較大,特別是大范圍搜索計算花費時間更長。通過對基本的網格搜索法進行改進,可以大大減少計算量,節省計算時間。其基本思想是:首先用較大的步長在某個區間范圍進行搜索,尋找出最優參數(此時縮小了搜索范圍);然后以最優參數為中心,在附近的一定范圍內以更小步長進行更細小的網格搜索,可得到更加精確的結果。

圖3　參數對SVM的影響

4.2遺傳算法

遺傳算法(Genetic Algorithm,GA)起源于對生物系統研究的計算機模擬研究,是模擬生物界遺傳形式和參考生物進化理論而形成的一種可以并行隨機搜索的優化方法,它把自然界生物自然選擇優秀個體的方法引入到優化參數問題形成的串聯編碼的群體中,參照自然界適者生存的選擇辦法,按照所選擇的適應度函數對個體進行測試和選擇,通過選擇、交叉、和變異等步驟對個體進行篩選,使適應度好的個體得以保留[5]。通過歸一化的計算方法,將適應度大小轉換為概率問題,對應地,概率大的個體被選中的概率大,即對應上面的適應度好的個體得以保留,概率小的對應個體淘汰的概率也會更大,而新的個體繼承上一代的信息后,又進一步進化,這樣往復循環,直至選擇出最優參數。

4.3兩種優化算法比較

網格搜索法的優點是算法構造簡單,可以并行處理數據,每個參數的SVM訓練都是獨立的,缺點是效率低,計算量過大,參數多時計算量呈現次方增長,如兩個參數時計算次數為O(n2)。遺傳算法的優點是擅長解決全局最優化問題,算法魯棒性強,過程簡單,并可與問題領域無關進行快速搜索,擴展性好。本文將通過實驗說明遺傳算法在尋優方面的優勢。

5　實驗

本實驗的數據來源于標準數據庫UCI數據集,實驗數據集的描述見表1。實驗中將數據按比例提取一部分數據作為訓練數據,另一部分作為測試數據;接著對數據進行歸一化處理,訓練優化參數C和σ;然后對訓練數據集訓練數據,構建模型,建立SVM;下一步測試測試集數據,比較分類準確率和尋優時間。表2為基于高斯核的SVM參數優化的網格搜索法和遺傳算法的比較。

表1　數據集描述

表2　基于RBF核參數優化算法的比較

從表2中顯示,網格搜索法和遺傳算法在搜索精度上沒有明顯的差別,但是優化參數的搜索速度不相同。很明顯地,遺傳算法的搜索速度更快,這在實際運用有巨大的優勢。因此,遺傳算法相對于網格搜索法,在基于RBF核的SVM分類器的參數優化運用中具有更好的可行性。

6　結語

本文在研究了懲罰參數C及高斯核函數參數σ對支持向量機分類性能影響的基礎上,利用網格搜索法和遺傳算法對基于RBF核的SVM進行了參數優化,并通過UCI數據集進行了驗證。實驗結果顯示,遺傳算法相較于網格搜索算法有更快的搜索速度,在實際運用更加高效。然而遺傳算法容易受到隨機的初值影響,其效果與適應度函數的選擇有關,利用改進的遺傳算法對支持向量的參數進行優化是下一步的工作計劃。

參 考 文 獻

[1] Vladimir N. Vapnik.統計學習理論[M].許建華,張學工,譯.北京:電子工業出版社,2004.

Vladi-mir N. Vapnik. Statistical Learning Theory[M]. XU Jianhua, ZHANG Xuegong, translated. Beijing: Electronic Industry Press,2004.

[2] 梁禮明,鐘震,陳召陽.支持向量機核函數選擇研究與仿真[J].計算機工程與科學,2015,6(37):1135-1141.

LIANG Liming, ZHONG Zhen, CHEN Shaoyang. The selection of kernel function and simulation for SVM[J]. Computer Engineering and Science,2015,6(37):1135-1141.

[3] 鄧乃揚,田英杰.支持向量機:理論、算法、與拓展[M].北京:科學出版社,2009.

DENG Naiyang, TIAN Yingjie. Support vector machine: theory, algorithms, and expand[M]. Beijing: Science Press,2009.

[4] 李琳,張曉龍.基于RBF核的SVM學習算法的優化計算[J].計算機工程與應用,2006(29):190-192.

LI Lin, ZHANG Xiaolong. Learning algorithm optimizing on support vector machines based on RBF kernel function[J]. Computer Engineering and Application,2006(29):190-192.

[5] 朱玨鈺,李峰.matlab神經網絡優化的遺傳算法[J].赤峰學院學報(自然科學版),2011,3(27):35-36.

ZHU Jueyu, LI Feng. Genetic algorithm optimization of matlab neural network[J]. Journal of Chifeng University(Natural Sciences),2011,3(27):35-36.

[6] 劉飇,陳春萍,封化民,等.基于Fisher準則的SVM參數選擇算法[J].山東大學學報:理學版,2012,47(7):50-55.

LIU Biao, CHEN Chunping, FENG Huaming, et al. A SVM parameters selection algorithm based on Fisher criterion[J]. Journal of Shangdong University: Natural Science,2012,47(7):50-55.

[7] Olivier Chapelle, Vladimir Vapnik, Olivier Bousquet, et al. Choosing Multiple Parameters for Support Vector Machines[J]. Machine Learning,2002,46(1):131-159.

[8] 王敏,王文劍.一種支持向量機集成的核選擇方法[J].計算機工程與應用,2009,45(27):31-33.

WANG Ming, WANG Wenjian. A integrated selection of kernel function for support vector machine[J]. Computer Engineering and Application,2009,45(27):31-33.

[9] R. Sivaraj. A review of selection methods in genetic algorithm[J]. International Journal of Engineering Science and Technology,2011,3(5):3792-3794.

[10] 奉國和.SVM分類核函數及參數選擇比較[J].計算機工程與應用,2011,47(3):123-125.

FENG Guohe, WANG Wenjian. Parameter optimizing for support vector machine classification[J]. Computer Engineering and Application,2011,47(3):123-125.

收稿日期:2015年10月3日,修回日期:2015年11月27日

基金項目:2014年五邑大學青年基金(編號:2014zk10);2015五邑大學青年基金(編號:2015zk11);2015年江門市科技計劃項目(編號:201501003001556)資助。

作者簡介:曹路,女,碩士,講師,研究方向:模式識別。歐陽效源,男,碩士研究生,研究方向:機器學習及無線通信技術。

中圖分類號TP273

DOI:10.3969/j.issn.1672-9722.2016.04.003

Parameters Optimization of SVM Based on Genetic Algorithm

CAO Lu1,2OUYANG Xiaoyuan2

(1. School of Information Engineering, Wuyi University, Jiangmen529020)(2. School of Information Science and Technology, Sun Yat-sen University, Guangzhou510006)

AbstractThe performance of SVM is mainly affected by the kernel function parameters and penalty parameter. SVM with RBF kernel function is the most widely applications. Using genetic algorithm to select optimum parameter, the paper mainly studies the performance of SVM with penalty parameter C and RBF kernel function parameter σ. Comparing grid search with genetic algorithm for optimum parameter to SVM based on RBF kernel function in experimental results, it is found that genetic algorithm has higher search speed in optimum parameter. Thus, genetic algorithm is more effective in practice.

Key WordsSVM, kernel function, parameter, genetic algorithm