王加朋 胡躍明 羅家祥

(華南理工大學(xué) 自動(dòng)化科學(xué)與工程學(xué)院, 廣東 廣州 510640)

一種基于ICDF的支持向量機(jī)參數(shù)快速優(yōu)化方法*

王加朋 胡躍明 羅家祥?

(華南理工大學(xué) 自動(dòng)化科學(xué)與工程學(xué)院, 廣東 廣州 510640)

在高斯核支持向量機(jī) (SVM) 的參數(shù)優(yōu)化中, 針對(duì)以特征空間中的類間距離 (ICDF)為測(cè)度選擇核參數(shù)時(shí)存在計(jì)算量大、耗時(shí)長(zhǎng)的問題, 首先提出并證明了ICDF是高斯核參數(shù)的嚴(yán)格單峰正定函數(shù), 然后根據(jù)該結(jié)論提出了改進(jìn)黃金分割法(MGSA)來快速搜索核參數(shù)在候選集中的最佳值, 在此基礎(chǔ)上提出一種基于MGSA和微分進(jìn)化算法的SVM參數(shù)快速優(yōu)化方法, 最后通過比較實(shí)驗(yàn)驗(yàn)證了所提方法的有效性和快速性.

支持向量機(jī)；類間距離；參數(shù)優(yōu)化；核參數(shù)；改進(jìn)黃金分割法

支持向量機(jī)[1](SVM)作為一種高效的分類技術(shù)已被廣泛應(yīng)用在圖像分類[2]、生物醫(yī)學(xué)[3]、文本分類[4]、故障診斷[5]、人臉表情識(shí)別[6]和電纜溫度計(jì)算[7]等領(lǐng)域.SVM使用核函數(shù)在高維特征空間尋找分離超平面,無論核函數(shù)形式如何,核參數(shù)影響著SVM的分類性能[8- 9].文中關(guān)注應(yīng)用廣泛的高斯核SVM[10].文獻(xiàn)[11]指出了高斯核參數(shù)γ能夠測(cè)量數(shù)據(jù)在高維特征空間的分離性,以及懲罰因子C控制平衡SVM的誤差項(xiàng)和泛化能力,因此選擇最佳參數(shù)組合是建立高效分類性能SVM模型的重要保障.

學(xué)者們已研究了較多SVM的參數(shù)選擇方法.網(wǎng)格搜索法(GS)是傳統(tǒng)的直接方法[12],因其對(duì)所有離散劃分參數(shù)組合的模型進(jìn)行訓(xùn)練比較,該方法計(jì)算量大,且很難確定合適的步長(zhǎng)[9].文獻(xiàn)[9,13- 16]通過對(duì)SVM泛化誤差構(gòu)建估計(jì)函數(shù)或上界提出一些數(shù)值方法,盡管這些方法比網(wǎng)格法搜尋速度更有效,但由于這些泛化上界的非凸性,它們對(duì)初值特別敏感,極易陷入局部最優(yōu)并且要求這些上界必須是可微的.為了克服這些困難,進(jìn)化算法[17- 19]由于對(duì)非凸函數(shù)具有很好的全局搜索能力而被用來優(yōu)化SVM參數(shù),但這些技術(shù)在種群進(jìn)化迭代中需訓(xùn)練大量的SVM模型[11],仍然要耗費(fèi)大量計(jì)算,特別是參數(shù)范圍較大時(shí)尤為突出.

為減少訓(xùn)練SVM次數(shù),依據(jù)顯著分離的特征空間對(duì)SVM分類性能的緊密相關(guān)度[8- 11]和特征空間中的類間距離(ICDF)可以度量特征空間中各類分離程度[20],文獻(xiàn)[11]首次研究了使用一些ICDF作為測(cè)度指標(biāo)來選擇高斯核參數(shù),該方法首先將ICDF最大值對(duì)應(yīng)的參數(shù)作為最佳核參數(shù),然后與候選懲罰因子C值組合訓(xùn)練SVM模型選擇最好的C值.結(jié)果表明該方法與GS有相似的性能但消耗時(shí)間明顯減少,因該方法大量減少了SVM模型的訓(xùn)練次數(shù).然而由于需要對(duì)核參數(shù)候選集依次計(jì)算ICDF值來確定最優(yōu)核參數(shù),除了很難確定合適的采樣步長(zhǎng)外[8],該方法會(huì)遺漏搜索參數(shù)區(qū)間中可能最優(yōu)的連續(xù)值.

針對(duì)上述存在大量計(jì)算ICDF值的問題,并結(jié)合進(jìn)化算法可搜索參數(shù)連續(xù)值的優(yōu)點(diǎn)[21],文中提出了一種基于ICDF的SVM參數(shù)快速優(yōu)化方法.首先證明了ICDF是關(guān)于高斯核參數(shù)的嚴(yán)格單峰正定函數(shù)；然后根據(jù)該結(jié)論提出了改進(jìn)黃金分割算法(MGSA)在核參數(shù)大區(qū)間候選離散值集中快速搜索最佳值,并結(jié)合MGSA和進(jìn)化算法給出了一種快速搜索SVM參數(shù)的混合方法框架；最后具體選擇一種自適應(yīng)進(jìn)化算法(SADE)[22]進(jìn)行試驗(yàn),以驗(yàn)證所提算法的有效性.

符號(hào)和假定:sgn( )是符號(hào)函數(shù);‖ ‖表示Euclidean范數(shù);x=0+表示x是正的且從右邊趨向于0;x=+∞表示x是正的且趨向于正無窮大;U(a,b)表示a的b鄰域,即{x|a-b

1 相關(guān)基礎(chǔ)

1.1 SVM及其參數(shù)優(yōu)化問題

本節(jié)對(duì)SVM及其參數(shù)優(yōu)化問題作簡(jiǎn)要的介紹，詳細(xì)內(nèi)容可參考文獻(xiàn)[1],給定訓(xùn)練樣本數(shù)據(jù)和類別標(biāo)簽對(duì)(xi,yi)，其中i=1,2,…,l,xi是n維訓(xùn)練數(shù)據(jù),類別標(biāo)簽yi∈{+1,-1}.SVM基本思想是將訓(xùn)練樣本通過非線性映射φ(·)映射到高維Hilbert空間中，從而在這種高維特征空間中構(gòu)建最佳判別超平面函數(shù)為式(1):

f(x)=sgn(wTφ(x)+b)

(1)

其中，w表示垂直于最佳分離超平面的權(quán)值向量，b為偏置項(xiàng).根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，最優(yōu)的參數(shù)w和b,可通過最小化式(2)結(jié)構(gòu)風(fēng)險(xiǎn)得到:

(2)

s.t.yi(wTzi+b)≥1-ξi,ξi≥0.

其中,zi=φ(xi)是映射到高維空間的高維特征向量，C>0為懲罰因子,ξi為松弛變量.

為了得到分離超平面，可以通過求解上述問題(2)的對(duì)偶問題(3)來解決:

(3)

s.t. 0≤αi≤C,yTα=0.

(4)

核函數(shù)有多種形式[11]，文中僅研究應(yīng)用廣泛的高斯核，表達(dá)如式(5)所示.

K(x,xi)=e-γ‖x-xi‖

(5)

文獻(xiàn)[9,11]指出高斯核參數(shù)決定了數(shù)據(jù)映射到高維特征空間的分離性,懲罰因子平衡SVM訓(xùn)練誤差項(xiàng)和泛化能力,因此這兩個(gè)參數(shù)的選擇直接影響SVM的性能,文中研究有效選擇最優(yōu)的參數(shù)組合的方法.

1.2 特征空間中的類間距離(ICDF)

文獻(xiàn)[11,20]對(duì)以樣本數(shù)據(jù)在特征空間中的類間距離(ICDF)作為選擇高斯核參數(shù)的度量指標(biāo)已做了相關(guān)研究，指出了以兩類樣本在高維特征空間中對(duì)應(yīng)中心點(diǎn)的Euclidean距離作為指標(biāo)分類效果更好,文中研究采用這一指標(biāo)，同樣記為ICDF,對(duì)于兩類數(shù)據(jù)x和y，特征空間中的類間距離計(jì)算如式(6)所示.將核函數(shù)式(5)代入式(6)中可得特征空間中的距離函數(shù)ICDF關(guān)于高斯核參數(shù)的表達(dá)式(7).

(6)

(7)

在利用ICDF進(jìn)行SVM核參數(shù)選擇時(shí),當(dāng)前研究方法[11,20- 21]是將給定的核參數(shù)大區(qū)間[2-L，2L](其中L為足夠大正整數(shù))離散化為候選值集{2-L，2-L+1，…，2L},然后依次計(jì)算每個(gè)候選值相應(yīng)的距離函數(shù)ICDF值,選取最大ICDF值對(duì)應(yīng)的候選值為最好核參數(shù),這種方法簡(jiǎn)記為ICDF-one-by-one.該方法需要大量計(jì)算ICDF函數(shù)值,且單次計(jì)算式(7)的復(fù)雜度是O(max{m2,mn,n2}),當(dāng)訓(xùn)練樣本較多時(shí),計(jì)算量大且耗時(shí)長(zhǎng).針對(duì)該不足,文中將研究ICDF與核參數(shù)的性質(zhì)并提出在離散候選集中快速選擇核參數(shù)最優(yōu)值的MGSA法;此外,為防止遺漏搜索更好的連續(xù)值,將借鑒文獻(xiàn)[21]縮短搜索區(qū)間(覆蓋候選集中性能最優(yōu)核參數(shù))的思想,結(jié)合MGSA和進(jìn)化算法設(shè)計(jì)一種快速搜索SVM最優(yōu)參數(shù)組合的混合方法框架.

2 基于ICDF的SVM參數(shù)優(yōu)化方法

2.1 ICDF的性質(zhì)

定義1[23]設(shè)函數(shù)g(x):R→R,閉區(qū)間[a,b]?R，如果存在β∈[a,b],使得g(x)在[a,β]上嚴(yán)格單調(diào)遞增(或嚴(yán)格單調(diào)遞減)且在[β,b]上嚴(yán)格單調(diào)遞減(或嚴(yán)格單調(diào)遞增)，那么稱函數(shù)g(x)為在區(qū)間[a,b]上的嚴(yán)格單峰函數(shù),區(qū)間[a,b]是函數(shù)g(x)嚴(yán)格單峰區(qū)間.

引理1[24](Rolle’s Theorem定理)如果實(shí)值函數(shù)f(x)在閉區(qū)間[a,b]上是連續(xù)的,在開區(qū)間(a,b)是連續(xù)可微的，且f(a)=f(b)，那么至少存在一個(gè)c∈(a,b)數(shù)使得導(dǎo)數(shù)f′(c)=0.

定理1 對(duì)在高維特征空間線性可分的兩類，距離函數(shù)ICDF(式(7))是關(guān)于高斯核參數(shù)的嚴(yán)格單峰正定函數(shù),即距離存在唯一最大值點(diǎn),設(shè)在γ0處取得,距離函數(shù)在區(qū)間(0,γ0)上嚴(yán)格單調(diào)遞增,在區(qū)間(γ0,+∞)上嚴(yán)格單調(diào)遞減.

證明根據(jù)距離函數(shù)式(6)的定義表達(dá)式，由數(shù)學(xué)知識(shí)很容易知道距離函數(shù)式(7)關(guān)于高斯核參數(shù)在區(qū)間(0,+∞)是非負(fù)、連續(xù)和可微的.

d(γ)>0

(8)

對(duì)距離函數(shù)(式(7))計(jì)算兩個(gè)極限值，容易得到式(9)和式(10)：

d(0+)>0

(9)

d(+∞)>0

(10)

根據(jù)距離函數(shù)式(7)的連續(xù)性質(zhì)，對(duì)于給定一個(gè)任意小正數(shù)ε，必存在兩個(gè)數(shù)σ1、σ2，分別位于鄰域σ1∈U(0,δ1)和區(qū)間σ2∈U(δ2,+∞),其中0<δ1≤δ2，使得

d(σ1)=ε

(11)

d(σ2)=ε

(12)

此時(shí)對(duì)距離函數(shù)(式(7))在區(qū)間(σ1，σ2)上應(yīng)用引理1，則至少存在一個(gè)正數(shù)ξ∈(σ1，σ2)，使得距離函數(shù)式(7)在此點(diǎn)的導(dǎo)數(shù)為零，得到式(13):

d′(ξ)=0

(13)

式(13)中導(dǎo)函數(shù)計(jì)算如式(14):

(14)

(15)

(16)

注意到指數(shù)函數(shù)E(γ)=e-γ在區(qū)間(0,+∞)上嚴(yán)格單調(diào)遞減，且值域?yàn)?0,1).這一性質(zhì)在下面推導(dǎo)中要使用.

首先考慮在區(qū)間(ξ,+∞)上Γ(γ)的符號(hào)，設(shè)對(duì)于給定任意正數(shù)Δ>0,

(17)

第一個(gè)小于號(hào)利用指數(shù)函數(shù)的上述性質(zhì),第二個(gè)等號(hào)是將式(16)移項(xiàng)代入計(jì)算得到,最后一步使用指數(shù)函數(shù)的上述性質(zhì),從等式(14)可以看出,距離函數(shù)導(dǎo)數(shù)的符號(hào)和式(15)所示的Γ(γ)的符號(hào)相同,在區(qū)間(ξ,+∞)上，根據(jù)式(17)可知Γ(γ)<0，所以在該區(qū)間有d′(γ)<0,說明距離函數(shù)式(7)在該區(qū)間(ξ,+∞)上嚴(yán)格單調(diào)遞減.

同理，可以類似地推導(dǎo)出在區(qū)間(0,ξ)上，Γ(ξ-Δ)>0，所以有d′(γ)>0,說明距離函數(shù)(式(7))在該區(qū)間(0,ξ)上嚴(yán)格單調(diào)遞增.綜上所述,根據(jù)定義1,距離函數(shù)(式(7))在(0,+∞)上是嚴(yán)格單峰正定函數(shù)，且在γ0=ξ處取得唯一最大值.證畢.

2.2 MGSA算法

考慮在給定高斯核參數(shù)的大區(qū)間[2-L,2L](其中L為足夠大正整數(shù))上,之前的搜索方法是將該區(qū)間離散化為候選值集{2-L,2-L+1,…，2L},然后依次計(jì)算距離ICDF函數(shù)值,選取其最大值對(duì)應(yīng)的核參數(shù).根據(jù)定理1的結(jié)論,距離函數(shù)ICDF式(7)是高斯核參數(shù)的嚴(yán)格單峰正定函數(shù),可以用線性搜索算法,考慮到黃金分割法(GSA)[25]無需計(jì)算導(dǎo)數(shù)信息,為了可以搜索候選離散整數(shù)值,提出一種修改GSA算法(Modified Golden Section Algorithm,MGSA)來快速解決這一問題，減少計(jì)算量.

設(shè)φ(x)=-d(2x)，因此最大化距離函數(shù)d(2x)也就等價(jià)于最小化φ(x)，令a1=-L,b1=L,MGSA流程如下.

算法1 MGSA.

步驟1 初始化k=1,設(shè)置初始區(qū)間[a1,b1]=[-L，L]，設(shè)置精度δ=1.計(jì)算初始觀測(cè)點(diǎn)λ1和μ1為λ1=a1+0.382(b1-a1),μ1=a1+0.618(b1-a1),之后計(jì)算φ(λ1)和φ(μ1).

步驟2 比較函數(shù)值φ(λk)和φ(μk),如果φ(λk)>φ(μk),則轉(zhuǎn)到步驟3;否則,轉(zhuǎn)到步驟4.

步驟3 如果bk-λk≤δ,則轉(zhuǎn)到步驟6;否則,設(shè)置ak+1:=λk,bk+1:=bk,λk+1:=μk,φ(λk+1):=φ(μk)，μk+1:=αk+1+0.618(bk+1-ak+1)..計(jì)算φ(μk+1)并且轉(zhuǎn)到步驟5.

步驟4 如果μk-αk≤δ,則轉(zhuǎn)到步驟6;否則,設(shè)置ak+1:=ak,bk+1:=μk,μk+1:=λk，φ(μk+1):=φ(λk),λk+1:=ak+1+0.382(bk+1-ak+1).計(jì)算φ(λk+1)并且轉(zhuǎn)到步驟5.

步驟5k:=k+1,轉(zhuǎn)到步驟2.

2.3 SVM參數(shù)優(yōu)化混合算法框架

算法2 所提混合算法框架.

步驟1 設(shè)定高斯核參數(shù)和懲罰因子區(qū)間,γ∈[2-L，2L],C∈[Cmin,Cmax].判斷分類問題類別,如果是二分類問題,轉(zhuǎn)到步驟2;n分類問題(n是大于2的正整數(shù)),轉(zhuǎn)到步驟3.

步驟3n分類問題使用一對(duì)一策略[26],共有n(n-1)/2對(duì)二分類子問題,每一對(duì)i二分類問題,依次使用MGSA算法選擇最優(yōu)高斯核參數(shù),記2ji,其中i=1,2,…,n(n-1)/2.設(shè)定高斯核參數(shù)縮小區(qū)間為[γmin,γmax]=[min{2ji}，max{2ji}],并記[2jmin，2jmax],如果2jmin=2jmax,則設(shè)定[γmin,γmax]=[2jmin-1，2jmax+1].轉(zhuǎn)到步驟4.

步驟4 在高斯核縮小區(qū)間[γmin,γmax]和懲罰因子區(qū)間[Cmin,Cmax],使用進(jìn)化算法選擇最優(yōu)參數(shù)組合解.

步驟5 得到的最優(yōu)參數(shù)組合訓(xùn)練SVM模型(多分類使用一對(duì)一策略[26]).

步驟6 使用訓(xùn)練好的SVM預(yù)測(cè)測(cè)試樣本.

上述所提混合算法框架在階段一采用了基于所證定理1提出的MGSA算法,相比于文獻(xiàn)[11,20- 21]中廣泛采用的ICDF-one-by-one方法,MGSA算法無需依次計(jì)算大量的ICDF值,降低了計(jì)算成本,能夠快速搜索到候選集里最大ICDF值所對(duì)應(yīng)的高斯核參數(shù).所提混合算法框架在階段二中可選擇使用任何進(jìn)化算法搜索最優(yōu)參數(shù)組合.文獻(xiàn)[21]結(jié)合SADE[22]算法優(yōu)化SVM參數(shù)取得了較好的性能,記作ICDF-SADE.文中混合算法框架實(shí)驗(yàn)也采用該進(jìn)化算法,記作MGSA-ICDF-SADE.

SADE算法的自適應(yīng)度函數(shù)選擇SVM的性能測(cè)度函數(shù).SVM性能測(cè)度函數(shù)選擇k次交叉驗(yàn)證平均錯(cuò)分率，記作kCVMR,如式(18)所示:

(18)

其中,MRi表示第i交叉驗(yàn)證錯(cuò)分率,根據(jù)文獻(xiàn)[13,27]的建議,實(shí)驗(yàn)中采用5次交叉驗(yàn)證.

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)定

為驗(yàn)證算法的有效性,采用8個(gè)常用數(shù)據(jù)集進(jìn)行測(cè)試實(shí)驗(yàn).實(shí)驗(yàn)電腦平臺(tái)配置G640 2.8 GHz CUP,4 GB RAM,window 7 32位系統(tǒng),Matlab R2014a環(huán)境.實(shí)驗(yàn)使用的LIBSVM工具箱和數(shù)據(jù)集可在網(wǎng)站上下載[27],根據(jù)文獻(xiàn)[12]建議,所有數(shù)據(jù)集都標(biāo)準(zhǔn)化到[-1,1].所有數(shù)據(jù)集隨機(jī)選擇70%作為訓(xùn)練樣本,30%為測(cè)試樣本.數(shù)據(jù)集基本特性如表1所示.

表1 數(shù)據(jù)集基本特性Table 1 Specifications of these datasets

根據(jù)文獻(xiàn)[12]建議設(shè)定參數(shù)區(qū)間γ∈[2-20，220]，C∈[2-7，27],這些區(qū)間足夠覆蓋具有很高泛化能力的SVM的參數(shù)組合.

文獻(xiàn)[21]驗(yàn)證了ICDF-SADE法在SVM參數(shù)優(yōu)化性能上比GS法和單獨(dú)使用SADE[22]法效果好.為了突出所提算法的快速性,且能保持很好的性能,實(shí)驗(yàn)將比較MGSA-ICDF-SADE法與文獻(xiàn)[21]中的ICDF-SADE法.

SADE算法參數(shù)設(shè)置[21]：種群數(shù)NP=15,重組概率CR=0.9,自適應(yīng)尺度因子變異參數(shù)F0=0.5,最大迭代次數(shù)GM=200,終止條件為達(dá)到最大迭代次數(shù)或者連續(xù)10次迭代的kCVMR值不變.依照文獻(xiàn)[11,20- 21]將高斯核參數(shù)區(qū)間γ∈[2-20，220]離

散劃分為候選集{2-20，2-19,…，220}.

3.2 MGSA對(duì)核參數(shù)區(qū)間選擇有效性驗(yàn)證

為了驗(yàn)證所提混合算法中階段一的MGSA算法的快速性,將該算法與ICDF-one-by-one進(jìn)行比較,實(shí)驗(yàn)結(jié)果如表2所示.

表2 高斯核參數(shù)縮短區(qū)間及所需時(shí)間

Table 2 Shrunk interval of kernel parameter and the time cost

數(shù)據(jù)集核參數(shù)縮短區(qū)間所需時(shí)間/sICDF-oneby-oneMGSADiabetes[2-1,21]387.77123.29Heart[2-4,2-2]35.5110.32Ionosphere[2-4,2-2]148.6146.64Iris[2-1,21]8.732.76Wine[2-2,2-1]17.025.27Glass[20,25]37.6811.68Svmguide2[26,27]162.7249.15Vehicle[2-2,20]792.48250.98

從表2中結(jié)果可以看出,對(duì)所有數(shù)據(jù)集,文中根據(jù)定理1所提出的MGSA法確實(shí)搜索到與之前IC-DF-one-by-one法相同的高斯核參數(shù)縮短區(qū)間,但是在速度上大幅提高,原因在于減少了大量的候選核參數(shù)對(duì)距離函數(shù)ICDF的計(jì)算比較,使得搜索時(shí)間縮短至原來的約1/3.

3.3 MGSA-ICDF-SADE的有效性驗(yàn)證

為了驗(yàn)證所提混合算法框架的有效性,比較了所提MGSA-ICDF-SADE法與文獻(xiàn)[21]中ICDF-SADE法進(jìn)行SVM參數(shù)優(yōu)化的訓(xùn)練時(shí)間和分類測(cè)試性能,實(shí)驗(yàn)結(jié)果如表3所示.

在表3中,對(duì)比了兩種方法對(duì)每個(gè)數(shù)據(jù)集分別運(yùn)行10次時(shí)的測(cè)試精度和訓(xùn)練時(shí)間的均值和方差,記錄格式為:均值±方差.表3中結(jié)果表明,從各數(shù)據(jù)集的測(cè)試精度可看出所提方法很好地保持了搜索參數(shù)組合的SVM性能,但文中所提算法搜索SVM最優(yōu)參數(shù)組合的訓(xùn)練時(shí)間比ICDF-SADE法大幅縮短.

表3 ICDF-SADE和MGSA-ICDF-SADE的測(cè)試精度和訓(xùn)練時(shí)間

圖1給出了在數(shù)據(jù)集Iris上本文所提MGSA-ICDF-SADE法和ICDF-SADE[21]法的訓(xùn)練性能隨時(shí)間變化的情況,圖中兩條線前段訓(xùn)練性能為零的部

圖1 Iris上MGSA-ICDF-SADE與ICDF-SADE的訓(xùn)練性能隨時(shí)間的變化

Fig.1 Training performance vs.time of ICDF-SADE and MGSA-ICDF-SADE on dataset Iris

分是算法通過ICDF計(jì)算選擇最佳核參數(shù)區(qū)間的階段(算法階段一),可以看出所提算法比ICDF-SADE[21]大大縮短了在階段一的計(jì)算時(shí)間,兩者在后面階段因采用了相同的進(jìn)化算法(SADE)而訓(xùn)練性能相當(dāng)，突出了所提算法對(duì)搜索SVM參數(shù)的快速性,且能保持很好的性能.

4 結(jié)語

文中提出并證明了ICDF是高斯核參數(shù)的嚴(yán)格正單峰函數(shù)這一定理,并據(jù)此提出改進(jìn)的黃金分割法(MGSA)來搜索候選集中的最好核參數(shù),解決了當(dāng)前研究中ICDF作為核參數(shù)選擇指標(biāo)需對(duì)候選集中大量候選參數(shù)依次計(jì)算造成的計(jì)算負(fù)擔(dān)重、耗時(shí)長(zhǎng)難題;然后提出一個(gè)基于MGSA和進(jìn)化算法的快速SVM參數(shù)優(yōu)化方法框架;最后通過比較實(shí)驗(yàn)驗(yàn)證了所提方法的有效性和快速性.結(jié)果表明所提方法具有較高的應(yīng)用潛力.

[1] VAPNIK V.The nature of statistical learning theory [M].New York：Springer Verlag,1995.

[2] CHAPELLE O,HAFFNER P,VAPNIK V.Support vector machines for histogram-based image classification [J].IEEE Transactions on Neural Networks,1999,10(5)：1055- 1064.

[3] YU H,NI J.An improved ensemble learning method for classifying high-dimensional and imbalanced biomedicine data [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2014,11 (4)：657- 666.

[4] LEOPOLD E,KINDERMANN J.Text categorization with support vector machines:how to represent texts in input space [J].Machine Learning,2002,46 (1/2/3)：423- 444.

[5] ZHANG X L,CHEN W,WANG B J.Intelligent fault diagnosis of rotating machinery using support vector machine with ant colony algorithm for synchronous feature selection and parameter optimization [J].Neurocomputing,2015,167：260- 279.

[6] 鄒文杰,王文靜,楊付正.參考中性表情的人臉表情識(shí)別 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,42(5)：115- 121.

ZOU Wen-jie,WANG Wen-jing,YANG Fu-zheng.Facial expression recognition referring to neutral expression [J].Journal of South China University of Technology (Natural Science Edition),2014,42(5)：115- 121.

[7] 牛海清,葉開發(fā),許佳,等.基于粒子群優(yōu)化支持向量機(jī)的電纜溫度計(jì)算 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,44(4)：77- 83.

NIU Hai-qing,YE Kai-fa,XU Jia,et al.Calculation of cable temperature based on support vector machine optimized by particle swarm algorithm [J].Journal of South China University of Technology(Natural Science Edition),2016,44(4)：77- 83.

[8] AYAT N E,CHERIET M,SUEN C Y.Automatic model selection for the optimization of SVM kernels [J].Pattern Recognition,2005,38(10)：1733- 1745.

[9] CHAPELLE O,VAPNIK V,BOUSQUET O,et al.Choosing multiple parameters for support vector machines [J].Machine Learning,2002,46 (1)：131- 159.

[10] KEERTHI S S,LIN C J.Asymptotic behaviors of support vector machines with Gaussian kernel [J].Neural Computation,2003,15(7)：1667- 1689.

[11] WU K P,WANG S D.Choosing the kernel parameters for support vector machines by the inter-cluster distance in the feature space [J].Pattern Recognition,2009,42(5)：710- 717.

[12] HSU C W,LIN C J.A comparison of methods for multiclass support vector machines [J].IEEE Transactions on Neural Networks,2002,13(2)：415- 425.

[13] KEERTHI S S,SINDHWANI V,CHAPELLE O.An efficient method for gradient-based adaptation of hyperparameters in SVM models [J].Advances in Neural Information Processing Systems,2007,19：673- 680.

[14] DUAN K,KEERTHI S S,POO A N.Evaluation of simple performance measures for tuning SVM hyperparameters [J].Neurocomputing,2003,51：41- 59.

[15] ADANKON M M,CHERIET M.Optimizing resources in model selection for support vector machine [J].Pattern Recognition,2007,40 (3)：953- 963.

[16] KEERTHI S S.Efficient tuning of SVM hyperparameters using radius/margin bound and iterative algorithms [J].IEEE Transactions on Neural Networks,2002,13(5)：1225- 1229.

[17] LIN S W,YING K C,CHEN S C,et al.Particle swarm optimization for parameter determination and feature selection of support vector machines [J].Expert Systems with Applications,2008,35(4)：1817- 1824.

[18] CHOU J S,CHENG M Y,WU Y W,et al.Optimizing parameters of support vector machine using fast messy genetic algorithm for dispute classification [J].Expert Systems with Applications,2014,41(8)：3955- 3964.

[19] ZHANG Y,ZHANG P.Machine training and parameter settings with sociale motional optimization algorithm for support vector machine [J].Pattern Recognition Letters,2015,54：36- 42.

[20] BEZDEK C,PAL N R.Some new indexes of cluster validity [J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),1998,28 (3)：301- 315.

[21] ZHANG X,ZHOU J,WANG C,et al.Multi-class support vector machine optimized by inter-cluster distance and self-adaptive deferential evolution [J].Applied Mathematics and Computation,2012,218(9)：4973- 4987.

[22] 顏學(xué)峰,余娟,錢鋒,等.基于改進(jìn)差分進(jìn)化算法的超臨界水氧化動(dòng)力學(xué)參數(shù)估計(jì) [J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,32 (1)：94- 97.

YAN Xue-feng,YU Juan,QIAN Feng,et al.Kinetic parameter estimation of oxidation in supercritical water based on modified differential evolution [J].Journal of East China University of Science and Technology (Natural Science Edition),2006,32 (1)：94- 97.

[23] FINE T.Optimum search for the location of the maximum of a unimodal function [J].IEEE Transactions on Information Theory,1966,12 (2)：103- 111.

[24] APOSTOL T M.Calculus (Second Edition) Vol.1：One-variable calculus with an introduction to linear algebra [M].Waltham：Cambridge University Press,1967.

[25] SUN W Y,YUAN Y X.Optimization theory and methods：Nonlinear programming (Springer Optimization and Its Applications Vol.1) [M].New York：Springer,2006.

[26] KREβEL U.Pairwise classification and support vector machines [C]∥ SCH?LKOPF B,BURGES C J C,SMOLA A J.Advances in Kernel Methods-Support Vector Learning.Cambridge：MIT Press,1999:255- 268.

[27] KAPP M N,SABOURIN R,MAUPIN P.A dynamic model selection strategy for support vector machine classifiers [J].Applied Soft Computing,2012,12 (8)：2550- 2565.

[28] CHANG C C,LIN C J.Libsvm：a library for support vector machines [EB/OL].(2015- 12- 14)[2016- 09- 03].https:∥www.csie.ntu.edu.tw/～cjlin/libsvm/, 2016.

AnICDF-BasedFastParameterOptimizationApproachforSupportVectorMachines

WANGJia-pengHUYue-mingLUOJia-xiang

(School of Automation Science and Engineering, South China University of Technology, Guangzhou 510640, Guangdong, China)

In the process of parameter optimization for support vector machines (SVMs) with Gaussian kernel, inter-cluster distance in feature spaces (ICDF) is an effective measure. However, ICDF may result in heavy computational load and large time consumption. In order to solve this problem, firstly, the theorem that ICDF is a positive strictly-unimodal function about Gaussian kernel parameter is proved. Then, according to this theorem, a modified golden section algorithm (MGSA) is proposed to search a shrunk value fast for kernel parameter in the candidate set. Thus, a fast parameter optimization approach on the basis of both MGSA and differential evolutionary algorithm is presented. Finally, some experiments are carried out to verify the effectiveness and rapidity of the proposed approach.

support vector machine; inter-cluster distance; parameter optimization; kernel parameter; modified golden section algorithm

2016- 09- 07

國家科技重大專項(xiàng)(2014ZX02503-3);國家自然科學(xué)基金資助項(xiàng)目(61573146);華南理工大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2015zz0100)

*Foundationitems： Supported by the National Science and Technology Major Project of the Ministry of Science and Technology of China(2014ZX02503-3) and the National Natural Science Foundation of China(61573146)

王加朋(1985-)，男，博士生，主要從事模式識(shí)別、學(xué)習(xí)控制方向的研究.E-mail:fox007wjp@126.com

?通信作者： 羅家祥(1979-),女,博士,副教授,主要從事優(yōu)化調(diào)度、機(jī)器學(xué)習(xí)研究.E-mail:luojx@scut.edu.cn

1000- 565X(2017)07- 0135- 08

TP 18

10.3969/j.issn.1000-565X.2017.07.019