基于改進(jìn)粒子群優(yōu)化算法和CRNN的多類SVM分類

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

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

0 引言

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

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

1 多類SVM的基本原理

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

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

(1)

其中樣本點xi∈Rn(i=1,2,…,N)，n為樣本空間初始維度，N為樣本數(shù)量，每個樣本的種類由yi∈1,2,…,K表示，第i類樣本數(shù)據(jù)集中包涵樣本點的數(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)化過程中容易出現(xiàn)的早熟收斂及陷入局部最優(yōu)問題，本文采用自適應(yīng)慣性權(quán)重結(jié)合自適應(yīng)粒子變異來動態(tài)調(diào)節(jié)粒子的進(jìn)化過程，以此實現(xiàn)對PSO算法的改進(jìn)(該算法記為IMPSO).

假設(shè)在一個D維空間中，粒子i的位置以Xi=(xi 1,xi 2,xi 3,…,xi D)表示,速度以Vi=(vi 1,vi 2,vi 3,…,vi D)表示.在每一次迭代中，粒子i通過跟蹤個體極值pbesti和群體極值gbest來更新自身的速度和位置.pbesti表示粒子自身找到的最優(yōu)解，可以表示為pbesti=(pi 1,pi 2,pi 3,…,pi D)；gbest表示整個群體所找到的最優(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)行動態(tài)調(diào)整，在優(yōu)化過程中可避免出現(xiàn)局部極小值，進(jìn)而提高算法的搜索能力[15].

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

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

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

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

(7)

(8)

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

(9)

(10)

(11)

4 算法的流程

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

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

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

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

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

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

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

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

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

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

5 算法的實驗驗證

算法在Matlab R2014a環(huán)境下編程實現(xià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的多類支持向量機(記為CRNN_SVM))進(jìn)行對比.

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

表1 實驗數(shù)據(jù)集的信息表

表2 不同算法的分類精度

表3 不同算法的運行時間 s

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

6 算法應(yīng)用

圖1 原始遙感影像圖

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

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

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

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

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

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

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

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

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ù)過程中容易陷入局部最優(yōu)以及“多次性”SVM分類可能存在的不可分區(qū)域的問題，因此IMPSO_CRNN_SVM算法具有很好的實用價值.在今后的研究中，我們將利用分布式并行處理技術(shù)進(jìn)一步降低算法的計算代價，提高算法的訓(xùn)練效率.