改進(jìn)蟻群算法在支持向量機(jī)參數(shù)中的應(yīng)用

劉繼承 解 敬 隋殿雪

(東北石油大學(xué)電氣信息工程學(xué)院，黑龍江 大慶 163318)

1 SVM的基本思想與參數(shù)①

SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方法[3]，其基本思想是通過(guò)核函數(shù)將樣本空間映射到特征空間，在特征空間中尋求原樣本的最優(yōu)分類面，得到輸入變量和輸出結(jié)果之間的一種線性或非線性關(guān)系[4]，即尋找SVM進(jìn)行模式分類[5]。

對(duì)線性可分的樣本集(xi，yi)(i=1，2，…，n，n為學(xué)習(xí)樣本數(shù)目)，xi=Rd表示輸入變量，yi∈[-1，+1]為輸出變量。利用非線性映射φ(·)，將輸入空間的數(shù)據(jù)映射到高維特征空間，并構(gòu)造最優(yōu)分類超平面：

f(x)=w·φ(x)+b=0

(1)

式中b——閾值；

w——權(quán)值矢量。

為了使結(jié)構(gòu)風(fēng)險(xiǎn)最小化，分類應(yīng)滿足以下約束：

yi[(w·xi)+b]-1≥0,i=1,2,…,n

(2)

對(duì)于線性不可分的問(wèn)題，引入松弛變量ξi來(lái)構(gòu)建最優(yōu)超平面。允許在一定程度上違反間隔約束優(yōu)化問(wèn)題，則有：

(3)

yi[(w·xi)+b]≥1-ξi,ξi≥0,i=0,1,…,n

(4)

此時(shí)根據(jù)核函數(shù)理論，應(yīng)存在核函數(shù)K=(x，x′)=[Φ(x)，Φ(x′)]，從而使：

(5)

(6)

C≥αi≥0,i=1,2,…,l

(7)

其中，C為誤差的懲罰參數(shù)，αi>0對(duì)應(yīng)的點(diǎn)是支持向量。進(jìn)而構(gòu)造出決策函數(shù)：

b*)

(8)

SVM參數(shù)的確定影響其學(xué)習(xí)和推廣能力[6]。對(duì)于RBF核函數(shù)的SVM來(lái)說(shuō)，其參數(shù)包括懲罰參數(shù)C和核寬度σ。懲罰參數(shù)C是在結(jié)構(gòu)風(fēng)險(xiǎn)和樣本誤差之間的折衷，其值越大，允許的誤差越小；核寬度σ與學(xué)習(xí)樣本的輸入空間范圍或?qū)挾扔嘘P(guān)，樣本的輸入空間越大，σ取值越大。

2 改進(jìn)蟻群算法優(yōu)化SVM參數(shù)

由于蟻群算法全局優(yōu)化參數(shù)的時(shí)間較長(zhǎng)，為了減少優(yōu)化參數(shù)的時(shí)間，筆者有效結(jié)合了交叉驗(yàn)證法和蟻群算法來(lái)優(yōu)化SVM參數(shù)，最終達(dá)到理想的識(shí)別效果。

2.1 交叉驗(yàn)證法

首先將數(shù)據(jù)分成n個(gè)同樣大小的子集；然后選取n-1個(gè)子集作為訓(xùn)練樣本，預(yù)測(cè)那個(gè)沒(méi)有參加訓(xùn)練的子集，共進(jìn)行n次，將全部數(shù)據(jù)中的每個(gè)樣本點(diǎn)都預(yù)測(cè)一遍，但準(zhǔn)確率并不是很穩(wěn)定；最后記錄每次預(yù)測(cè)的(σ,C)，挑選準(zhǔn)確率相對(duì)較高的幾組，運(yùn)用蟻群算法再次尋優(yōu)，得到最佳參數(shù)，進(jìn)而得到滿意的識(shí)別結(jié)果。

2.2 蟻群算法

1992年意大利學(xué)者Dorigo M首先提出了一種源于蟻群覓食行為的智能仿生蟻群優(yōu)化算法[7]，該算法具有智能搜索、全局優(yōu)化、較強(qiáng)的魯棒性、正反饋、分布式計(jì)算和易與其他算法結(jié)合的特點(diǎn)。筆者通過(guò)蟻群優(yōu)化算法優(yōu)化SVM參數(shù)σ、C的具體操作步驟包括：參數(shù)初始化；通過(guò)蟻群進(jìn)行局部和全局搜索，不斷更新信息素，同時(shí)將每代全局最優(yōu)解保存下來(lái)。

2.2.1參數(shù)初始化

首先，將利用交叉驗(yàn)證法得到的幾組參數(shù)(σ，C)隨機(jī)分配給每只螞蟻，然后對(duì)訓(xùn)練集通過(guò)SVM學(xué)習(xí)得到相應(yīng)的誤差模型：

Δt(i)=α-Error(i)

(9)

用根據(jù)上述誤差模型預(yù)測(cè)得到的誤差值來(lái)確定螞蟻i的位置信息素：

T0(i)=α-Error(i)

(10)

其中，α=2。由式(10)可知：誤差值越小，螞蟻的信息素越大。

2.2.2局部和全局搜索

根據(jù)螞蟻留下來(lái)的信息素的大小確定每只螞蟻下一步的轉(zhuǎn)移概率：

(11)

其中，BestIndex為得到信息素最大的螞蟻。

建立動(dòng)態(tài)揮發(fā)因子。在最初階段信息素?fù)]發(fā)因子相對(duì)較小，隨著不斷增加進(jìn)化次數(shù)，信息素?fù)]發(fā)因子逐漸增大。信息素的揮發(fā)因子定義為：

(12)

其中，k=0.1；Echo為當(dāng)前的進(jìn)化代數(shù)；Echomax為蟻群的最大進(jìn)化代數(shù)。

建立動(dòng)態(tài)轉(zhuǎn)移因子。在每輪迭代過(guò)程中，根據(jù)螞蟻信息素的大小來(lái)確定全局轉(zhuǎn)移因子p0。設(shè)螞蟻數(shù)量為m，計(jì)算e-T0(i)(i=1，2，…，m)，并對(duì)計(jì)算結(jié)果進(jìn)行升序排列，得到序列T1(j)(j=1，2，…，m)。當(dāng)Echo

如果螞蟻的轉(zhuǎn)移概率小于p0，則進(jìn)行局部搜索，否則進(jìn)行全局搜索。在開(kāi)始搜索過(guò)程中，大部分螞蟻進(jìn)行局部搜索，從而保證螞蟻能搜索到更好的解；在后期搜索中，大部分螞蟻進(jìn)行全局搜索，避免陷入局部最優(yōu)，得到全局最優(yōu)解。

更新信息素。根據(jù)蟻群優(yōu)化得到的SVM參數(shù)進(jìn)行信息素更新，更新規(guī)則為：

T0(i)=(1-ρ)T0(i)+Δt(i)

(13)

在每次迭代的過(guò)程中，將信息素最大的螞蟻保存下來(lái)，然后根據(jù)誤差模型計(jì)算誤差值，返回2.2.1小節(jié)進(jìn)行迭代循環(huán)。

如果迭代的次數(shù)滿足開(kāi)始設(shè)置的要求，則搜索完成，從而得到最佳螞蟻，將最佳螞蟻轉(zhuǎn)換成SVM參數(shù)σ、C。

根據(jù)確定的SVM參數(shù)σ、C計(jì)算相應(yīng)的目標(biāo)函數(shù)值，最后進(jìn)行誤差分析(圖1)[8]。

圖1 蟻群算法的SVM參數(shù)優(yōu)化流程

3 仿真實(shí)驗(yàn)

3.1 數(shù)據(jù)源

選取大慶油田某井的測(cè)井?dāng)?shù)據(jù)中有代表性的屬性來(lái)構(gòu)成樣本的維數(shù)。筆者選取具有代表性的某油井在不同深度中的側(cè)向電阻率RT、深側(cè)向電阻率RXO、自然電位SP和自然伽馬GR共4個(gè)參數(shù)進(jìn)行巖性預(yù)測(cè)，輸出為泥巖和砂巖(表1)。

表1 學(xué)習(xí)樣本集

3.2 算法的參數(shù)設(shè)置

蟻群算法中參數(shù)的設(shè)置：螞蟻數(shù)m=25，揮發(fā)因子ρ=0.7，步長(zhǎng)0.2，α=0.5，β=1。SVM參數(shù)C、σ采用二進(jìn)制編碼，C∈[0，500]，σ∈[0.01，100.00]。最大進(jìn)化代數(shù)為100，最優(yōu)解碼誤差為0.02，最終C=10，σ=0.19。

同時(shí)為證明基于改進(jìn)蟻群算法優(yōu)化SVM參數(shù)的優(yōu)越性，采用交叉驗(yàn)證法作為參比模型，其優(yōu)化后的SVM參數(shù)C=1，σ=0.01。

3.3 結(jié)果與分析

預(yù)測(cè)樣本通過(guò)交叉驗(yàn)證法和改進(jìn)蟻群算法優(yōu)化參數(shù)，兩種方法的識(shí)別結(jié)果見(jiàn)表2，識(shí)別準(zhǔn)確率分別為91.666 7%和100%，說(shuō)明采用改進(jìn)蟻群算法優(yōu)化SVM參數(shù)的識(shí)別準(zhǔn)確率高于采用交叉驗(yàn)證法的識(shí)別準(zhǔn)確率，證實(shí)筆者提出的改進(jìn)蟻群算法是分類準(zhǔn)確率較高的參數(shù)優(yōu)化方法。

表2 交叉驗(yàn)證法和改進(jìn)蟻群算法識(shí)別結(jié)果的比較

4 結(jié)束語(yǔ)

SVM參數(shù)的優(yōu)化是當(dāng)前模式識(shí)別研究的一項(xiàng)很有意義的課題，筆者通過(guò)采用改進(jìn)的蟻群算法(即交叉驗(yàn)證法與蟻群算法的有效結(jié)合)對(duì)SVM參數(shù)進(jìn)行優(yōu)化之后，不僅縮短了參數(shù)優(yōu)化的時(shí)間，而且有效地改進(jìn)了其學(xué)習(xí)性能，提高了學(xué)習(xí)精度和識(shí)別準(zhǔn)確率。

[1] Ertekin S,Bottou L,Giles C L.Nonconvex Online Support Vector Machines[J]. IEEE Transactions on Pattern Aanlysis and Machine Intelligence,2010,33(2):368～381.

[2] 莊嚴(yán)，白振林，許云峰.基于蟻群算法的支持向量機(jī)參數(shù)選擇方法研究[J].計(jì)算機(jī)仿真，2011，28(5)：216～219.

[3] 陳桂娟，賈春雨，鄒龍慶，等.基于腐蝕圖像與支持向量機(jī)的CO2腐蝕類型識(shí)別方法研究[J].化工機(jī)械，2014，41(6)：742～745.

[4] 文傳軍，詹永照，陳長(zhǎng)軍.最大間隔最小體積球形支持向量機(jī)[J].控制與決策，2010，25(1)：79～83.

[5] 楊智明，彭宇，彭喜元.基于支持向量機(jī)的不平衡數(shù)據(jù)集分類方法研究[J].儀器儀表學(xué)報(bào)，2009，30(5)：1094～1099.

[6] 王凱，張永祥，姚曉山，等.支持向量機(jī)懲罰參數(shù)的自適應(yīng)調(diào)整方法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(26)：45～47.

[7] 韓虎，黨建武，任恩恩.基于自適應(yīng)小波支持向量機(jī)的圖像去噪研究[C].第七屆全國(guó)信號(hào)與信息處理聯(lián)合會(huì)議暨首屆全國(guó)省(市)級(jí)圖象圖形學(xué)會(huì)聯(lián)合年會(huì)論文集.蘭州：蘭州交通大學(xué)，2008：349～352.

[8] 劉瑜，馬良.基于元胞蟻群算法的臥式內(nèi)壓容器優(yōu)化設(shè)計(jì)[J].化工機(jī)械，2010，37(1)：17～20，89.