一種有效的SVM參數(shù)優(yōu)化選擇方法

趙璐華，彭 濤

ZHAO Lu-hua1,2, PENG Tao1

（1. 河南質(zhì)量工程職業(yè)學(xué)院，平頂山 467000；2. 華中科技大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430011）

一種有效的SVM參數(shù)優(yōu)化選擇方法

An effective SVM parameter selection optimazation method

趙璐華1,2，彭 濤1

ZHAO Lu-hua1,2, PENG Tao1

（1. 河南質(zhì)量工程職業(yè)學(xué)院，平頂山 467000；2. 華中科技大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430011）

支持向量機(jī)（SVM)在機(jī)器學(xué)習(xí)中的有著廣泛應(yīng)用，參數(shù)優(yōu)化則是SVM需要解決的重要問題。本文提出了使用多主體進(jìn)化算法(multi-agent genetic algorithm, MAGA)，通過設(shè)計(jì)自學(xué)習(xí)、協(xié)作、變異、競爭四個(gè)遺傳算子，在參數(shù)空間進(jìn)行搜索，實(shí)現(xiàn)SVM參數(shù)的優(yōu)化選擇.仿真算例表明該算法明顯優(yōu)于傳統(tǒng)算法。

SVM；multi-agent；遺傳算法；參數(shù)優(yōu)化

0 引言

支持向量機(jī)(support vector machines, SVM)[1]是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)之上發(fā)展起來的新一代機(jī)器學(xué)習(xí)算法，它能較好的解決傳統(tǒng)機(jī)器學(xué)習(xí)算法難以解決的小樣本、高維、學(xué)習(xí)機(jī)器的結(jié)構(gòu)、學(xué)習(xí)算法的局性收斂等問題，目前在復(fù)雜系統(tǒng)建模、預(yù)測(cè)、控制、時(shí)間序列分析、函數(shù)估計(jì)和模式識(shí)別等各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。但是如何選擇合適的參數(shù)則是支持向量機(jī)算法理論和應(yīng)用中需要解決的主要問題，直接影響SVM的性能，對(duì)支持向量機(jī)的發(fā)展有重要的理論和實(shí)際意義。對(duì)于回歸型支持向量機(jī)則首先需要確定三個(gè)自由參數(shù)[2]：不敏感值，正則化參數(shù)以及核參數(shù)，然后才能采用支持向量估計(jì)方法進(jìn)行回歸估計(jì)。

一般研究人員采用既直觀又簡單的試驗(yàn)確定參數(shù)來獲得較優(yōu)參數(shù)，這種方法需要大量的試驗(yàn)，而且通常得不到的最優(yōu)參數(shù)。經(jīng)典的“留一法”[2]（Leave-One-Out）采用的是方法是先根據(jù)人工選擇近似最優(yōu)值參數(shù)范圍，然后在參數(shù)集合上進(jìn)行窮舉搜索得到最優(yōu)參數(shù)，計(jì)算量相對(duì)較大，而且人工選擇范圍相對(duì)較難。Chapelle[3]提出用梯度下降法來完成SVM參數(shù)的自動(dòng)選擇，該方法在計(jì)算時(shí)間上有明顯的改善，但是GD對(duì)初始點(diǎn)要求比較高，而且比較容易陷于局部最優(yōu)解，而且初值選擇不當(dāng)，則更難獲得局部最優(yōu)解。Keerthy[4]采用擬牛頓法進(jìn)行Gaussian核函數(shù)SVM模型的參數(shù)優(yōu)化。Leung[5]提出了基于實(shí)值遺傳算法（genetic algorithm, GA）實(shí)現(xiàn)了SVM模型參數(shù)的自動(dòng)選擇，該方法基于遺傳算法的隱含并行高效性和全局最優(yōu)的性能選擇了SVM模型參數(shù)，提高了SVM的構(gòu)造效率，而且進(jìn)一步提高了分類器的識(shí)別率。但是GA算法存在適應(yīng)度函數(shù)的適應(yīng)性是局部的，同時(shí)沒有考慮到生物之間協(xié)同的可能性，還不具備后天的學(xué)習(xí)能力等局限性。邵信光[6]提出了基于粒子群算法的SVM參數(shù)優(yōu)化方法，該方法是通過個(gè)體之間的協(xié)作來尋找最優(yōu)值的，其主要優(yōu)點(diǎn)是較易實(shí)現(xiàn)。

多主體進(jìn)化算法[7,8](multi-agent genetic algorithm, MAGA)是從智能體的角度出發(fā)，把進(jìn)化算法中的個(gè)體作為一個(gè)具有局部感知、競爭協(xié)作和自學(xué)習(xí)能的智能體，通過智能體與環(huán)境以及智能體間的相互作用達(dá)到全局優(yōu)化的目的。這種方法在搜索空間較大時(shí)，由于考慮到進(jìn)化過程中個(gè)體的協(xié)作性及學(xué)習(xí)能力，搜索效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的遺傳算法。該方法已經(jīng)應(yīng)用于函數(shù)優(yōu)化，多目標(biāo)優(yōu)化，組合優(yōu)化等理論問題，并解決了時(shí)延受限組播，VLSI布局等實(shí)際問題。

本文提出了基于智能體遺傳算法的回歸型支持向量機(jī)參數(shù)優(yōu)化方法，利用多主體進(jìn)行計(jì)算快速全局的搜索能力實(shí)現(xiàn)模型的優(yōu)化選擇，并采用兩個(gè)常見的函數(shù)算例進(jìn)行算法測(cè)試，表明該算法的優(yōu)越性。

1 支持向量機(jī)的基本算法描述

其中L(.)表示損失函數(shù)。通過核函數(shù)把非線性數(shù)據(jù)映射到高維空間，在高維空間進(jìn)行線性回歸。二次規(guī)劃優(yōu)化形式可以轉(zhuǎn)化為：

由此可以知道，在回歸型支持型向量機(jī)中，正則化參數(shù)c，以及核參數(shù)σ均是需要選擇的，為了SVM具有良好應(yīng)用能力，有必要使用優(yōu)化算法對(duì)該上述參數(shù)進(jìn)行調(diào)整。

2 基于智能體遺傳算法的回歸型 SVM參數(shù)優(yōu)化

SVM的參數(shù)優(yōu)化實(shí)質(zhì)是一個(gè)目標(biāo)優(yōu)化問題，首先確定SVM參數(shù)優(yōu)化的性能評(píng)價(jià)指標(biāo)，然后在搜索空間進(jìn)行搜索，求解出最優(yōu)參數(shù)。多主體進(jìn)化是一種基于協(xié)同組織進(jìn)化原理的優(yōu)化算法，其在超高維函數(shù)優(yōu)化、多目標(biāo)優(yōu)化及分解函數(shù)優(yōu)化上有巨大潛力，并證明有較強(qiáng)的收斂性[8]。故本文采用多主體進(jìn)化算法來實(shí)現(xiàn)SVM的參數(shù)優(yōu)化。

2.1 回歸型SVM參數(shù)優(yōu)化性能指標(biāo)

對(duì)于回歸型參數(shù)優(yōu)化性能指標(biāo)是參數(shù)優(yōu)化的基礎(chǔ)，一般采用推廣能力估計(jì)的方法。常用的方法有留一法、k-fold交叉驗(yàn)證法、支持向量率法、VC維方法。由于留一法的簡潔實(shí)用性，一般采用該方法進(jìn)行誤差檢驗(yàn)。

留一過程中首先得確定其誤差數(shù)的上界，由半徑-間隔界反映，表示為[10]

至此，可由標(biāo)準(zhǔn)SVM算法求得其α和β值，故Gaussian核函數(shù)SVM的問題是優(yōu)化正則化參數(shù)c和核函數(shù)參數(shù)σ，使得W最大而T最小。

2.2 智能體遺傳算法的原理

智能體遺傳算法通過設(shè)計(jì)每個(gè)主體的目的，生存環(huán)境，局部環(huán)境定義，行為來設(shè)計(jì)用來優(yōu)化的主體。將主體定義為待優(yōu)化目標(biāo)的一個(gè)候選解，記為，它的能量等于目標(biāo)函數(shù)取反，即E(p)=-f(p)，其中Q表示變量個(gè)數(shù)。為了實(shí)現(xiàn)主體的局部感知能力，將生存環(huán)境組織成網(wǎng)格狀結(jié)構(gòu)，稱為主體網(wǎng)格，記為G，相應(yīng)的固定在網(wǎng)格點(diǎn)(i,j)不能移動(dòng)的主體記為pi,j，所以主體均與其鄰域的局部主體發(fā)生作用，具體為競爭與協(xié)作，通過擴(kuò)散實(shí)現(xiàn)信息的全局共享，通過自學(xué)習(xí)與變異實(shí)現(xiàn)自身信息的更新。由自學(xué)習(xí)、競爭、協(xié)作與變異四種機(jī)制完成主體的進(jìn)化，進(jìn)行尋優(yōu)。多主體進(jìn)化算法的關(guān)鍵在于算子的設(shè)計(jì)。

主體擁有與所求解問題相關(guān)的知識(shí)，可以利用這些知識(shí)進(jìn)行自學(xué)習(xí)來提高性能，在此用局部搜索來實(shí)現(xiàn)：

2.2.2 協(xié)作算子X(pi,pj)[12]

協(xié)作算子可能理解為主體之間的信息共享，在此先用鄰域正交交叉算子[12]生成主體集合P，|P|=M。再用P中能量最高的主體作為協(xié)作算子的結(jié)果：

2.2.3 變異算子v(P)[13]

變異采用普通的標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)方法：

U(0,1)為(0,1)區(qū)間均勻分布的隨機(jī)數(shù)，Pv為變異概率，Pv=(e1,e2,...,eQ)，且t為進(jìn)化代數(shù)。

2.2.4 競爭算子r(P)[14]

與鄰域主體的競爭只需要與鄰域中能量最大者競爭，記其為Pmax，則競爭行為準(zhǔn)則為：

其中Pnew為通過自學(xué)習(xí)、正交交叉和變異后產(chǎn)生的主體。

2.3 基于智能體遺傳算法的支持向量機(jī)的參數(shù)調(diào)整

為了用智能體遺傳算法優(yōu)化SVM的參數(shù)，首先必須對(duì)參數(shù)進(jìn)行編碼，對(duì)正則化參數(shù)c和核參數(shù) σ的編碼用主體P=(C,σ)表示，定義Bestt和CBestt分別為前t代產(chǎn)生的最優(yōu)主體和第t代產(chǎn)生的最優(yōu)主體，ts為最大能量不變代數(shù)，即ts=max{τ|Bestt=Bestt+τ}，為了改善算法的收斂性能，設(shè)定以最大進(jìn)化代數(shù)tmax與最大能量不變代數(shù)tsmax為雙重進(jìn)化終止準(zhǔn)則。算法的流程如下：

1）令t=0，初始化主體網(wǎng)格G中的所有主體pi,j，由于沒有先驗(yàn)信息，采用隨機(jī)生成方案，即pi,j=rand(P)，P為解的編碼空間，更新Bestt，Bestt+τ，ts ；

2）對(duì)第t代的每個(gè)主體pi,j分別用式3.4～3.7進(jìn)行自學(xué)習(xí)、協(xié)作、變異和競爭，產(chǎn)生新一代主體，其中E(pi,j)由標(biāo)準(zhǔn)SVM算法求得；

3）更新Bestt，Bestt+τ，ts ；

3 仿真算例

3.1 一維函數(shù)算例

圖1 一維函數(shù)SVM仿真算例

3.2 二維函數(shù)算例

圖2 二維函數(shù)SVM仿真算例

3.3 試驗(yàn)結(jié)果分析

將上述算法與使用正交優(yōu)選方法、遺傳算法、以及基于PSO遺傳算法的結(jié)果進(jìn)行比較，一維函數(shù)算例實(shí)驗(yàn)結(jié)果比較如表1所示，二維函數(shù)仿真算例實(shí)驗(yàn)結(jié)果比較如表2所示，從表中可見，利用本文方法所得的SVM模型的支持向量個(gè)數(shù)最少，測(cè)試誤差最小。

表1 一維函數(shù)仿真算例結(jié)果對(duì)比表

表2 二維函數(shù)仿真算例結(jié)果對(duì)比表

4 結(jié)論

本文提出了基于智能體遺傳算法的支持向量機(jī)參數(shù)估計(jì)方法，通過設(shè)計(jì)自學(xué)習(xí)算子、協(xié)同算子，避免了傳統(tǒng)進(jìn)化算法中只考慮基因的競爭因素而未考慮到基因的協(xié)同，加快了收斂速度，提高了變異的有效性，實(shí)現(xiàn)了支持向量機(jī)的參數(shù)優(yōu)選。

[1] Marti Hearst.Support Vector Machines[J].IEEE Transaction On Intelligent Systems,July/August,1998.

[2] Lee J H,Lin C J.Automatic Model Selection for Support Vector Machines[R].Taipei：Taiwan University,2000.

[3] Chapelle O,Vapnik V,Bousquet O,et al.Choosing Multiple Parameters for Support Vector Machines[J].Machine Learning,2002,46(1-3)：131-159.

[4] ZHENG Chunhong,JIAO Licheng.Automatic parameters Selection of SVM based on GA[C].Proc of the 5th World Congress on Intelligent Control and Automation.Piscataway, NJ：IEEE press,2004：2035-2040.

[5] Leung Y W,Wang Y.An orthogonal genetic algorithm with quantization for global numerical optimization[J].IEEE Trans Evolutionary Computation.2001,5(1)：41-53.

[6] 邵信光,楊慧中,陳剛.基于粒子群算法的支持向量機(jī)參數(shù)優(yōu)化及其應(yīng)用[J].控制理論與應(yīng)用.2005,5(23)：740-743.

[7] Zhong Weicai,Liu Jing,Xue Mingzhi,etal.A muti-agent genetical-algorithm for global numerical optimization[J].IEEE Transactions on Systems,Man,and Cybernetics partB：Cybernetics,2004,34(2).

[8] 鐘偉才,劉靜,焦李成.多智能體遺傳算法用于線性系統(tǒng)逼近[J].自動(dòng)化學(xué)報(bào),2004,30(6)：933-938.

[9] F.E.H.Tay,L.-J Cao,Application of support vector machines in financial forecasting[J].Omega.2001,4(9)：309-317.

[10]F. Friedrichs and C.Igel. Evolutionary tuning of multiple SVM parameters[J].Neurocomputing, 64：107 -117,2005.

[11]C.Gagne,M.Schoenauer,M.Sebag,and M.Tomassini.Genetic programming for kernel based learning with co-evolving subsets selection[C].In Proceedings of Parallel Problem Solving in Nature,2006.

[12]T. Phienthrakul and B.Kijsirikul.Evolutionary strategies for multi-scale radial basis function kernels in support vector machines[C].In Proceedings of the Genetic and Evolutionary Computation Conference,pages 905-911,Washington,DC, June 2005.ACM Press.

[13]C.-L.Huang and C.-J.Wang.A GA-based feature selection and parameter optimization for support vector machines.[J]Expert Systems with Applications,31：231-240, 2006.

[14]Smeaton,A.F.,Over,P.,and Kraaij,W.2006. Evaluation campaigns and TRECVid[C].In Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval(MIR 2006),Santa Barbara,California,USA,October 26-27,2006.

TP391.9

A

1009-0134(2010)09-0146-04

10.3969/j.issn.1009-0134.2010.09.45

2009-11-11

趙璐華（1972 -）,女，河南平頂山人，副教授，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)。