趙璐華，彭 濤

ZHAO Lu-hua1,2, PENG Tao1

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

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

An effective SVM parameter selection optimazation method

趙璐華1,2，彭 濤1

ZHAO Lu-hua1,2, PENG Tao1

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

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

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

0 引言

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

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

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

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

1 支持向量機的基本算法描述

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

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

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

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

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

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

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

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

2.2 智能體遺傳算法的原理

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

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

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

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

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

變異采用普通的標準正態(tài)分布隨機數(shù)方法：

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

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

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

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

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

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

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

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

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

3 仿真算例

3.1 一維函數(shù)算例

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

3.2 二維函數(shù)算例

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

3.3 試驗結果分析

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

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

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

4 結論

本文提出了基于智能體遺傳算法的支持向量機參數(shù)估計方法，通過設計自學習算子、協(xié)同算子，避免了傳統(tǒng)進化算法中只考慮基因的競爭因素而未考慮到基因的協(xié)同，加快了收斂速度，提高了變異的有效性，實現(xiàn)了支持向量機的參數(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] 邵信光,楊慧中,陳剛.基于粒子群算法的支持向量機參數(shù)優(yōu)化及其應用[J].控制理論與應用.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].自動化學報,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 -）,女，河南平頂山人，副教授，研究方向為計算機應用技術。