胡 瀅

（銅陵學(xué)院 電氣工程學(xué)院，安徽 銅陵 244061）

試論用于特征子集選擇的異步并行微粒群優(yōu)化方法

胡 瀅

（銅陵學(xué)院 電氣工程學(xué)院，安徽 銅陵 244061）

特征子集的選擇是數(shù)據(jù)挖掘與模式分類的重要方法.本文主要從微粒編碼、比較微粒適應(yīng)值、更新微粒引導(dǎo)者、一致混沌變異和計(jì)算步驟五個(gè)方面對(duì)用于特征子集選擇的異步并行微粒群優(yōu)化方法進(jìn)行分析，通過(guò)實(shí)驗(yàn)比對(duì)，可以發(fā)現(xiàn)這種方法具有良好的效果.

特征子集選擇；異步并行方式；微粒群優(yōu)化

最優(yōu)化問(wèn)題指的是在有限或無(wú)限決策中挑選最優(yōu)的決策，而微粒群優(yōu)化（Particle Swarm Optimizer,PSO）算法是一種基于群智能方法的演化計(jì)算方法，是將微粒進(jìn)行初始化隨機(jī)處理，然后利用迭代尋找最優(yōu)解的方法.目前，這種方法已經(jīng)廣泛應(yīng)用到神經(jīng)網(wǎng)絡(luò)訓(xùn)練、預(yù)測(cè)控制及函數(shù)優(yōu)化領(lǐng)域.

1 用于特征子集選擇的異步并行微粒群優(yōu)化方法

1.1 微粒編碼

用于特征子集選擇的異步并行微粒群優(yōu)化首先需要對(duì)微粒進(jìn)行編碼處理.在具體操作中，應(yīng)將每一個(gè)問(wèn)題的特征都當(dāng)作是微粒的一維二進(jìn)制變量，所有特征加在一起的數(shù)量之和就是微粒變量的長(zhǎng)度.也就是說(shuō)在第i位是1的情況下，會(huì)選擇第i個(gè)特征；如果不是，那么這個(gè)特征就會(huì)屏蔽.

1.2 比較微粒適應(yīng)值

為了所選擇的特征子集能夠以少量特征起到良好的分類作用，本文認(rèn)為應(yīng)該從兩方面著手對(duì)其適應(yīng)值進(jìn)行比較和評(píng)價(jià)[1].一是微粒子集包含的特征數(shù)量，二是所確定分類器的準(zhǔn)確度.所有的特征子集中都包含著或多或少的特征，在兩個(gè)特征子集準(zhǔn)確度保持一致的情況下，可以認(rèn)定數(shù)量較少的子集勝出.和最優(yōu)值進(jìn)行比較，如果該特征子集的準(zhǔn)確率很低，可包含的特征數(shù)量不大，那么我們可以認(rèn)定這兩個(gè)特征子集和最優(yōu)的特征子集十分接近，那么就可以增加算法的方式得到最優(yōu)的特征子集，也就是說(shuō)，盡管這種特有子集相對(duì)于最優(yōu)值來(lái)說(shuō)準(zhǔn)確率并不高，可是對(duì)于準(zhǔn)確率較高的特征子集來(lái)說(shuō)，它們所包含的特征數(shù)量得到了顯著的降低.可以利用上述特征完成微粒適應(yīng)值的比較工作.

現(xiàn)假設(shè)η是分類器的準(zhǔn)確率，λ是特征子集中所包含的特征數(shù)量，在給定任意兩個(gè)微粒xi、xj和大于零的常數(shù)ε的情況下，可以得出微粒適應(yīng)值比較的ε支配關(guān)系.

在λ（xi）=λ（xj），同時(shí)滿足η（xi）=η（xj）的情況下，那么我們可以認(rèn)定xi與xj是一種等價(jià)關(guān)系.

在λ（xi）＜λ（xj），同時(shí)滿足η（xi）≥η（xj）-ε的情況下，或在λ（xi）=λ（xj），同時(shí)滿足η（xi）＞η（xj）的情況下，可以認(rèn)定xi對(duì)于x→j起到了支配的作用.也就是說(shuō)，分類器準(zhǔn)確度和常數(shù)的取值應(yīng)該成反比關(guān)系.

1.3 更新微粒引導(dǎo)者

微粒引導(dǎo)者包含個(gè)兩個(gè)方面，即個(gè)體最優(yōu)點(diǎn)和全局最優(yōu)點(diǎn).

1.3.1 個(gè)體最優(yōu)點(diǎn)的更新

前者可以看做是微粒記憶，指的是微粒從最開(kāi)始到現(xiàn)在的迭代次數(shù)得到的最優(yōu)位置.可以通過(guò)實(shí)例進(jìn)行論述，假如pi(t)是微粒xi(t)的個(gè)體最優(yōu)點(diǎn)，而xi(t+1)是第t+1代的新生微粒.那么在pi(t)和xi(t+1)處于等價(jià)關(guān)系的時(shí)候，可以在xi(t+1)與pi(t)之間進(jìn)行隨機(jī)挑選，挑選結(jié)果可作為微粒個(gè)體最優(yōu)點(diǎn)；xi(t+1)ε 對(duì) pi(t)起到支配作用的條件下，可以取x→i(t+1)代替?zhèn)€體最優(yōu)點(diǎn)pi(t+1).如果二者關(guān)系都不是，那么pi(t+1)可以直接取pi(t).

1.3.2 全局最優(yōu)點(diǎn)的判斷

全局最優(yōu)點(diǎn)的判斷指的是在所有微粒群中對(duì)最佳位置完成所有工作，如上文所說(shuō)，采用ε支配關(guān)系的比較方法可以得出個(gè)體最優(yōu)點(diǎn)，個(gè)體最優(yōu)點(diǎn)所在的微粒群就可以認(rèn)定為全局最優(yōu)點(diǎn).

1.4 一致混沌變異

混沌屬于非線性現(xiàn)象，本身有著隨機(jī)性和遍歷性等特點(diǎn)，依照自身的規(guī)律，它可以在一定條件內(nèi)對(duì)所有狀態(tài)作出遍歷，且沒(méi)有重復(fù)，依照這些特性，結(jié)合本文所說(shuō)算法，可以起到增強(qiáng)全局搜索效果的作用[2].

這種通過(guò)結(jié)合而來(lái)的混沌變異算子在國(guó)內(nèi)已經(jīng)有人提出，即利用Zaslavskii映射函數(shù)可以得到混沌變量，然后對(duì)此混沌變量完成混沌空間→決策空間的轉(zhuǎn)化，進(jìn)而能夠?qū)崿F(xiàn)微粒飛行速度的變異.設(shè)速度上下界是Bround，算法終止代數(shù)*//是Tmax,決策變量維數(shù)是n.

為確保Zaslavskii映射可以展現(xiàn)出完全餛飩狀態(tài)，需要進(jìn)行合理的取值，設(shè)r=3，v=400，a=12.6695.可以觀察其混沌狀態(tài)，通過(guò)觀察可以發(fā)現(xiàn)變異算子會(huì)對(duì)微粒飛行速度造成影響，且對(duì)于全局的探索來(lái)說(shuō)，在初始階段效果較好.變異算子的影響效果和迭代次數(shù)之間是呈反比例的關(guān)系.需要額外注意的是，在變異后，如果微粒的速度已經(jīng)在允許范圍之外，那么取值應(yīng)該是速度變量的下界或上界.

1.5 算法步驟

異步并行的方法可以縮短微粒群優(yōu)化的時(shí)間，進(jìn)而達(dá)到提高效率的作用.該一部并行微粒群優(yōu)化算法的步驟可以概括為：循環(huán)分解——消息發(fā)送——算法操作.

可以對(duì)其步驟進(jìn)行簡(jiǎn)單分析，第一，需要在決策空間內(nèi)完成微粒群隨機(jī)初始化的工作；第二，需要利用主處理器把需要評(píng)價(jià)的微粒xj和個(gè)體最優(yōu)點(diǎn)傳送到?jīng)]有處于工作狀態(tài)的附屬處理器；第三，附屬處理器會(huì)進(jìn)行分類器準(zhǔn)確率的確定工作，利用ε的支配關(guān)系，可以完成個(gè)體最優(yōu)點(diǎn)pi的更新工作，進(jìn)而將結(jié)果反饋給主處理器；進(jìn)而由主處理器依據(jù)結(jié)果完成決策評(píng)價(jià)的工作，將全局最優(yōu)點(diǎn)找出，進(jìn)而根據(jù)公式，和一致混沌變異算子對(duì)微粒位置進(jìn)行更新.在具體操作中，需要對(duì)主處理器的優(yōu)化參數(shù)、算法以及微粒速度等條件進(jìn)行設(shè)定，需要對(duì)微粒評(píng)價(jià)的處理完成排序[3]；而對(duì)于附屬處理器，需要結(jié)合微?，F(xiàn)有特點(diǎn)對(duì)SVM分類器進(jìn)行訓(xùn)練，且在準(zhǔn)確率方面，需要結(jié)合10階交叉驗(yàn)證的結(jié)果進(jìn)行分析.

設(shè)迭代次數(shù)為t，學(xué)習(xí)因子是c1和c2，慣性全值為w，在[0,1]之間的隨機(jī)數(shù)是r1和r2.其調(diào)整位置的公式為：

而利用二進(jìn)制微粒群優(yōu)化算法，微粒xi中的分量xij取值在[0,1]之間，那么對(duì)其更新微粒位置可以利用邏輯函數(shù)轉(zhuǎn)化的方法，其轉(zhuǎn)化公式為：

2 實(shí)驗(yàn)及性能分析

2.1 實(shí)驗(yàn)流程

對(duì)于優(yōu)化性能進(jìn)行分析，需要利用學(xué)習(xí)數(shù)據(jù)庫(kù)，測(cè)試問(wèn)題包含了Class、Vowel等數(shù)據(jù)集.具體信息可見(jiàn)表1.

表1 測(cè)試問(wèn)題數(shù)據(jù)集

如表1所示數(shù)據(jù)，可以采用SFS（前向選擇）算法、BPSO算法和HGA（混雜遺傳）算法等五種算法對(duì)數(shù)據(jù)問(wèn)題優(yōu)化20次，可以得出結(jié)果，進(jìn)而完成比較.

2.2 性能分析

以Class為例，其結(jié)果如表2所示.

表2 多種算法結(jié)果示例表

通過(guò)分析結(jié)果，可以發(fā)現(xiàn)BPSO的平均準(zhǔn)確率要低于AP-PSO與MDPSO，且SFS平均準(zhǔn)確率要低于HGA，如果測(cè)試問(wèn)題較少，如Class與Vowel，呢么SFS與HGA效果可以達(dá)標(biāo)，而特征數(shù)目較多的時(shí)候，AP-PSO的性能更好.

對(duì)于AP-PSO算法并行性能進(jìn)行分析，可以利用Satellite的數(shù)據(jù)集，利用三個(gè)方法進(jìn)行性能測(cè)度.一是效率Ep等于加速比Sp和處理器數(shù)量p的比值；二是加速比Sp等于串行算法最劣條件下運(yùn)行時(shí)間Ts與并行算法最劣條件下運(yùn)行時(shí)間Tp的比值；三是并行算法中擴(kuò)展性的一個(gè)指示器

據(jù)此進(jìn)行計(jì)算分析，可以得出結(jié)果，即同步并行方式與異步并行方式的計(jì)算速度都和處理器數(shù)目成正比，二者相比，異步并行方式速度增加的幅度更大；依據(jù)不同數(shù)目下的處理器進(jìn)行比較，可以發(fā)現(xiàn)無(wú)論數(shù)目為多少，異步并行方式的速度都更快；在多個(gè)處理器之中，存在一個(gè)性能劣質(zhì)的處理器時(shí)，異步并行方式所受影響更小.因?yàn)檫@種性能優(yōu)勢(shì)，這種方法可以在多個(gè)領(lǐng)域存在強(qiáng)大的發(fā)展空間，如物流車輛路徑問(wèn)題的解決等.

3 結(jié)論

綜上所述，通過(guò)對(duì)分類器的準(zhǔn)確度的設(shè)定，對(duì)混沌變異算子的結(jié)合等步驟可以實(shí)現(xiàn)特征子集選擇的異步并行微粒群優(yōu)化方法，利用實(shí)驗(yàn)進(jìn)行分析，可以發(fā)現(xiàn)一致混沌變異算子能夠?qū)ξ⒘Ｗ儺惙秶c變異概率起到調(diào)節(jié)的作用，且異步并行優(yōu)化方法和同步并行方法比較上具有更高的效率，利用這種方法可以讓計(jì)算效率和計(jì)算準(zhǔn)確率得到提高.

〔1〕馬立新,王繼銀,欒健,黃陽(yáng)龍.三目標(biāo)自適應(yīng)變異微粒群算法的無(wú)功優(yōu)化[J].電子科技,2016（04）:41-44.

〔2〕張勇,夏長(zhǎng)紅,鞏敦衛(wèi),榮淼.基于多種群協(xié)同微粒群優(yōu)化的流數(shù)據(jù)聚類算法[J].控制與決策,2016(10).

〔3〕鞏敦衛(wèi),胡瀅,張勇.知識(shí)引導(dǎo)微粒群優(yōu)化特征選擇方法[J].模式識(shí)別與人工智能,2014（01）:1-10.

TP301

A

1673-260X（2017）10-0026-02

2017-07-10