俞穎， 黃風(fēng)華， 阮奇

( 1.陽(yáng)光學(xué)院 空間數(shù)據(jù)挖掘與應(yīng)用福建省高校工程研究中心；2.陽(yáng)光學(xué)院 人工智能學(xué)院； 3.陽(yáng)光學(xué)院 教師發(fā)展中心： 福州 福建 350015 )

0 引言

支持向量機(jī)(support vector machine,SVM)[1]主要用于解決二類分類問(wèn)題，而現(xiàn)實(shí)分類問(wèn)題很多屬于多類范疇，因此若將二類SVM應(yīng)用在多類分類問(wèn)題就需要對(duì)其進(jìn)行參數(shù)優(yōu)化和擴(kuò)展.文獻(xiàn)[2]采用蟻群算法對(duì)SVM進(jìn)行了參數(shù)優(yōu)化，該方法能在較短的時(shí)間內(nèi)尋找到最優(yōu)解，但計(jì)算量相對(duì)較大；文獻(xiàn)[3]針對(duì)SVM優(yōu)化對(duì)象設(shè)計(jì)了一種二進(jìn)制編碼基因串和相應(yīng)的遺傳算子，該方法雖然實(shí)現(xiàn)了SVM參數(shù)的組合優(yōu)化，但需要解決個(gè)體基因的設(shè)計(jì)及編碼問(wèn)題；文獻(xiàn)[4]利用蜂群的分工協(xié)作搜索最優(yōu)蜜源來(lái)實(shí)現(xiàn)了SVM參數(shù)優(yōu)化，該方法雖然可以實(shí)現(xiàn)局部和全局尋優(yōu)，但時(shí)間開(kāi)銷較高；文獻(xiàn)[5]提出了一種利用速度參數(shù)代替人工魚(yú)步長(zhǎng)的人工魚(yú)群加速算法，該方法能夠有效地克服參數(shù)優(yōu)化后期難以逼近最優(yōu)解的問(wèn)題.文獻(xiàn)[6-11]的作者利用改進(jìn)的粒子群優(yōu)化算法(PSO)對(duì)SVM的參數(shù)進(jìn)行了優(yōu)化，其研究結(jié)果均在一定程度上緩解了優(yōu)化過(guò)程中可能出現(xiàn)的早熟和局部最優(yōu)問(wèn)題.

目前，將二類SVM擴(kuò)展到多類分類場(chǎng)合的方法有兩種：一是將原始的多類問(wèn)題分解為多個(gè)二類問(wèn)題，即通過(guò)構(gòu)造多個(gè)二類分類器進(jìn)行數(shù)據(jù)的“多次性”分類[12]；二是直接在目標(biāo)函數(shù)上進(jìn)行修改，將多個(gè)分類面的參數(shù)求解合并到一個(gè)最優(yōu)化問(wèn)題中，然后通過(guò)求解該最優(yōu)化問(wèn)題實(shí)現(xiàn)數(shù)據(jù)的“一次性”多類SVM分類[13].第1種方法使用的算法主要有“一對(duì)一”和“一對(duì)多”，這兩種算法雖然簡(jiǎn)單，但存在無(wú)法確定某些數(shù)據(jù)點(diǎn)的具體類別或者某些數(shù)據(jù)點(diǎn)被劃為多個(gè)類別的現(xiàn)象.第2種方法的優(yōu)點(diǎn)是可利用少量的支持向量獲取較高的分類精度，但其在模型訓(xùn)練過(guò)程中需要求解一個(gè)復(fù)雜的優(yōu)化問(wèn)題.基于上述研究，針對(duì)二類SVM在多類分類場(chǎng)合的應(yīng)用中存在的問(wèn)題，本文通過(guò)引入自適應(yīng)調(diào)節(jié)技術(shù)及協(xié)作式遞歸神經(jīng)網(wǎng)絡(luò)(CRNN),提出一種多類SVM分類方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證該方法的有效性.

1 多類SVM的基本原理

1999年，Bredensteiner等提出了一種多類SVM[13].該多類SVM的基本原理是根據(jù)給出的已知K>2類分類樣本點(diǎn)，構(gòu)造一個(gè)在類之間進(jìn)行有效區(qū)分的決策函數(shù).該方法主要應(yīng)用于2個(gè)以上類別的大數(shù)據(jù)集分類問(wèn)題，其優(yōu)點(diǎn)是可以通過(guò)少量的支持向量獲得很好的分類效果，但需要求解一個(gè)較為復(fù)雜的優(yōu)化問(wèn)題.假設(shè)一個(gè)多類分類問(wèn)題的K類數(shù)據(jù)集為：

(x1,y1),(x2,y2),…,(xN,yN).

(1)

其中樣本點(diǎn)xi∈Rn(i=1,2,…,N)，n為樣本空間初始維度，N為樣本數(shù)量，每個(gè)樣本的種類由yi∈1,2,…,K表示，第i類樣本數(shù)據(jù)集中包涵樣本點(diǎn)的數(shù)量為mi.多類SVM構(gòu)造區(qū)分函數(shù)的目的是盡可能地區(qū)別出每一類與剩余類別，其基本形式為：

fi(x)=ωTφ(x)-γi,i=1,2,…,K.

(2)

(3)

uT=[u12T,u13T,…,u1KT,u21T,u23T,…,uK(K-1)T].

K(x,y)=exp(-g‖x-y‖2).

2 IMPSO優(yōu)化多類SVM參數(shù)

為了有效地克服傳統(tǒng)PSO算法在SVM參數(shù)優(yōu)化過(guò)程中容易出現(xiàn)的早熟收斂及陷入局部最優(yōu)問(wèn)題，本文采用自適應(yīng)慣性權(quán)重結(jié)合自適應(yīng)粒子變異來(lái)動(dòng)態(tài)調(diào)節(jié)粒子的進(jìn)化過(guò)程，以此實(shí)現(xiàn)對(duì)PSO算法的改進(jìn)(該算法記為IMPSO).

假設(shè)在一個(gè)D維空間中，粒子i的位置以Xi=(xi 1,xi 2,xi 3,…,xi D)表示,速度以Vi=(vi 1,vi 2,vi 3,…,vi D)表示.在每一次迭代中，粒子i通過(guò)跟蹤個(gè)體極值pbesti和群體極值gbest來(lái)更新自身的速度和位置.pbesti表示粒子自身找到的最優(yōu)解，可以表示為pbesti=(pi 1,pi 2,pi 3,…,pi D)；gbest表示整個(gè)群體所找到的最優(yōu)解，可以表示為gbest=(g1,g2,g3,…,gD).

在第d(1≤d≤D)維空間中，粒子的速度和位置的更新公式如下：

(4)

(5)

2.1 自適應(yīng)慣性權(quán)重

自適應(yīng)慣性權(quán)重的優(yōu)化公式[14]為：

(6)

其中ωmin和ωmax為慣性權(quán)重的最小值和最大值，f為粒子當(dāng)前的目標(biāo)適應(yīng)度值，favg和fmin分別表示當(dāng)前所有粒子的平均適應(yīng)度值和最小適應(yīng)度值.自適應(yīng)慣性權(quán)重ω能夠隨目標(biāo)適應(yīng)度值的變化而進(jìn)行動(dòng)態(tài)調(diào)整，在優(yōu)化過(guò)程中可避免出現(xiàn)局部極小值，進(jìn)而提高算法的搜索能力[15].

2.2 自適應(yīng)粒子變異

為了實(shí)現(xiàn)動(dòng)態(tài)調(diào)節(jié)每代粒子變異概率，本文在迭代過(guò)程中采用如下種群粒子概率變異方式：

1) ran d: 產(chǎn)生隨機(jī)變異概率

2) 如果ran d>0.5

3)k=ceil(2*ran d)

4) ifk= =1

5)xi k=(20-1)*ran d+1

6) en dif

7) ifk= =2

8)xi k=(xgmax-xgmin)*ran d+xgmin

9) en dif

其中xi k為粒子i第k維的位置，g的區(qū)間為[xgmin,xgmax].

3 基于CRNN的多類SVM分類

CRNN由若干個(gè)遞歸神經(jīng)網(wǎng)絡(luò)(RNN)組成，其對(duì)解決約束性優(yōu)化問(wèn)題具有明顯的優(yōu)勢(shì)[16-17].為了更高效地對(duì)“一次性”多類SVM分類問(wèn)題進(jìn)行求解，本文將原始多類SVM分類問(wèn)題進(jìn)行分解，并設(shè)計(jì)一個(gè)CRNN用于多類SVM學(xué)習(xí)，以此實(shí)現(xiàn)分類.本文將原始多類SVM分類問(wèn)題分解成2個(gè)子問(wèn)題,即求解支持向量u的二次規(guī)劃問(wèn)題和求解偏差γ的線性規(guī)劃問(wèn)題：

(7)

(8)

本文設(shè)計(jì)的CRNN由2個(gè)RNN自適應(yīng)構(gòu)造而成，其中一個(gè)RNN用于求解二次規(guī)劃問(wèn)題(7),記為RNN(9);另一個(gè)RNN用于求解線性規(guī)劃問(wèn)題(8),記為RNN(10).

(9)

(10)

(11)

4 算法的流程

本文提出的多類SVM分類的算法流程為：

1)準(zhǔn)備原始分類數(shù)據(jù)集Data，將其隨機(jī)劃分為訓(xùn)練集Data1和測(cè)試集Data2，并對(duì)訓(xùn)練集和測(cè)試集行歸一化處理；

2)設(shè)定IMPSO算法的原始參數(shù)，包括迭代次數(shù)、種群規(guī)模、活動(dòng)區(qū)間以及c1、c2、r1和r2等；

3)隨機(jī)產(chǎn)生粒子的位置和速度，設(shè)置慣性權(quán)重的初始值，計(jì)算初始適應(yīng)度值；

4)自適應(yīng)更新粒子的慣性權(quán)重和更新粒子的速度和位置，然后對(duì)粒子進(jìn)行自適應(yīng)變異，并計(jì)算其適應(yīng)度值;

5)更新個(gè)體極值pbesti和群體極值gbest；

6)判斷是否超過(guò)最大迭代次數(shù)，如果是則獲取最優(yōu)多類SVM參數(shù)，轉(zhuǎn)步驟7)；否則轉(zhuǎn)步驟4)，繼續(xù)迭代；

7)利用所設(shè)計(jì)的CRNN對(duì)問(wèn)題求解：利用RNN(9)求解多類SVM的支持向量u，利用RNN(10)求解多類SVM的偏差γ；

8)構(gòu)造決策函數(shù)(3)，通過(guò)計(jì)算函數(shù)(3)的最大值對(duì)待分類數(shù)據(jù)進(jìn)行“一次性”分類；

9)利用分類結(jié)果計(jì)算分類精度和分析分類性能.

5 算法的實(shí)驗(yàn)驗(yàn)證

算法在Matlab R2014a環(huán)境下編程實(shí)現(xiàn).為了驗(yàn)證本文所提出算法的性能，將本文提出分類算法的性能(記為IMPSO_CRNN_SVM)分別與其他3種算法(未進(jìn)行參數(shù)優(yōu)化的原始SVM算法(記為SVM)、基本PSO進(jìn)行SVM參數(shù)優(yōu)化的算法(記為PSO_SVM)、未進(jìn)行PSO參數(shù)優(yōu)化基于CRNN的多類支持向量機(jī)(記為CRNN_SVM))進(jìn)行對(duì)比.

實(shí)驗(yàn)中使用UCI數(shù)據(jù)庫(kù)中的Iris、Wine及abalone 3個(gè)數(shù)據(jù)集對(duì)各算法的分類性能進(jìn)行驗(yàn)證.表1為3種數(shù)據(jù)集的基本信息，表2為4種算法在相同數(shù)據(jù)集上測(cè)試所達(dá)到的分類精度(算法在同一數(shù)據(jù)集上連續(xù)運(yùn)行5次所得出的精度平均值).表3為CRNN_SVM算法和IMPSO_CRNN_SVM算法在Iris及Wine 2種數(shù)據(jù)集上的運(yùn)行時(shí)間效率對(duì)比.這2種算法的迭代次數(shù)為300，種群數(shù)目為30，學(xué)習(xí)因子c1=1.6，c2=1.5.

表1 實(shí)驗(yàn)數(shù)據(jù)集的信息表

表2 不同算法的分類精度

表3 不同算法的運(yùn)行時(shí)間 s

由表2可以看出，PSO_SVM算法和IMPSO_CRNN_SVM算法的分類精度總體上高于SVM算法和CRNN_SVM算法，其中本文提出算法的分類精度相對(duì)最高.由表3可以看出，本文提出的算法在優(yōu)化SVM參數(shù)時(shí)需要的時(shí)間相對(duì)略長(zhǎng)，但分類器的訓(xùn)練時(shí)間低于CRNN_SVM算法.CRNN_SVM算法的訓(xùn)練時(shí)間相對(duì)較長(zhǎng)的原因是其參數(shù)(經(jīng)驗(yàn)值)的設(shè)置需要經(jīng)過(guò)多次試驗(yàn)才能獲取.

6 算法應(yīng)用

圖1 原始遙感影像圖

為了進(jìn)一步驗(yàn)證本文算法的有效性和實(shí)用性，將IMPSO_CRNN_SVM算法應(yīng)用于遙感影像分類.驗(yàn)證選取的是1幅多光譜遙感影像圖，圖中包涵水域、林地、草地和裸地4個(gè)類別的數(shù)據(jù)(圖1).該影像圖共有6個(gè)波段，數(shù)據(jù)集的基準(zhǔn)是wgs-84，影像的空間分辨率是30 m.

首先對(duì)遙感影像圖進(jìn)行目視解譯，并在實(shí)驗(yàn)區(qū)中提取4個(gè)類別的樣本點(diǎn)數(shù)據(jù).每類數(shù)據(jù)量為300個(gè)，共計(jì)1 200個(gè).然后將每類數(shù)據(jù)的樣本點(diǎn)隨機(jī)劃分為訓(xùn)練集(50個(gè)樣本點(diǎn))和測(cè)試集(250個(gè)樣本點(diǎn))，并對(duì)其進(jìn)行歸一化處理.最后利用IMPSO_CRNN_SVM算法進(jìn)行分類處理.通過(guò)IMPSO優(yōu)化之后的SVM參數(shù)取值為：bestc=74.590 5，bestg=0.010 0.由CRNN構(gòu)造決策數(shù)據(jù)得到的分類實(shí)驗(yàn)結(jié)果為：訓(xùn)練集正確率為100%，測(cè)試集正確率為97.7%.由此可以看出，本文提出的IMPSO_CRNN_SVM算法具有良好的分類效果.

利用本文提出的IMPSO_CRNN_ SVM算法、CRNN_SVM算法、PSO_SVM算法及SVM算法對(duì)實(shí)驗(yàn)區(qū)遙感影像進(jìn)行分類識(shí)別，結(jié)果如圖2—圖5所示.

圖2 基于IMPSO_CRNN_SVM算法的影像分類

圖4 基于PSO_SVM算法的影像分類

圖3 基于CRNN_SVM算法的影像分類

圖5 基于SVM算法的影像分類

由圖2—圖5可以看出，IMPSO_CRNN_SVM算法在邊界處理方面整體優(yōu)于其他3種算法.其中：SVM算法對(duì)裸地的識(shí)別精度低于CRNN_SVM和PSO_SVM算法，但SVM算法對(duì)林地的識(shí)別精度優(yōu)于CRNN_SVM和PSO_SVM算法；IMPSO_CRNN_SVM算法對(duì)林地的識(shí)別精度較高，但對(duì)裸地的識(shí)別精度相對(duì)較低.

7 結(jié)論

研究表明，本文提出的IMPSO_CRNN_SVM算法的分類精度優(yōu)于未進(jìn)行參數(shù)優(yōu)化的SVM算法、基于傳統(tǒng)PSO的SVM算法及未進(jìn)行參數(shù)優(yōu)化的基于CRNN的多類SVM分類方法，且可有效地避免粒子群優(yōu)化算法在優(yōu)化多類SVM參數(shù)過(guò)程中容易陷入局部最優(yōu)以及“多次性”SVM分類可能存在的不可分區(qū)域的問(wèn)題，因此IMPSO_CRNN_SVM算法具有很好的實(shí)用價(jià)值.在今后的研究中，我們將利用分布式并行處理技術(shù)進(jìn)一步降低算法的計(jì)算代價(jià)，提高算法的訓(xùn)練效率.