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

胡 瀅

（銅陵學院 電氣工程學院，安徽 銅陵 244061）

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

胡 瀅

（銅陵學院 電氣工程學院，安徽 銅陵 244061）

特征子集的選擇是數據挖掘與模式分類的重要方法.本文主要從微粒編碼、比較微粒適應值、更新微粒引導者、一致混沌變異和計算步驟五個方面對用于特征子集選擇的異步并行微粒群優化方法進行分析，通過實驗比對，可以發現這種方法具有良好的效果.

特征子集選擇；異步并行方式；微粒群優化

最優化問題指的是在有限或無限決策中挑選最優的決策，而微粒群優化（Particle Swarm Optimizer,PSO）算法是一種基于群智能方法的演化計算方法，是將微粒進行初始化隨機處理，然后利用迭代尋找最優解的方法.目前，這種方法已經廣泛應用到神經網絡訓練、預測控制及函數優化領域.

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

1.1 微粒編碼

用于特征子集選擇的異步并行微粒群優化首先需要對微粒進行編碼處理.在具體操作中，應將每一個問題的特征都當作是微粒的一維二進制變量，所有特征加在一起的數量之和就是微粒變量的長度.也就是說在第i位是1的情況下，會選擇第i個特征；如果不是，那么這個特征就會屏蔽.

1.2 比較微粒適應值

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

現假設η是分類器的準確率，λ是特征子集中所包含的特征數量，在給定任意兩個微粒xi、xj和大于零的常數ε的情況下，可以得出微粒適應值比較的ε支配關系.

在λ（xi）=λ（xj），同時滿足η（xi）=η（xj）的情況下，那么我們可以認定xi與xj是一種等價關系.

在λ（xi）＜λ（xj），同時滿足η（xi）≥η（xj）-ε的情況下，或在λ（xi）=λ（xj），同時滿足η（xi）＞η（xj）的情況下，可以認定xi對于x→j起到了支配的作用.也就是說，分類器準確度和常數的取值應該成反比關系.

1.3 更新微粒引導者

微粒引導者包含個兩個方面，即個體最優點和全局最優點.

1.3.1 個體最優點的更新

前者可以看做是微粒記憶，指的是微粒從最開始到現在的迭代次數得到的最優位置.可以通過實例進行論述，假如pi(t)是微粒xi(t)的個體最優點，而xi(t+1)是第t+1代的新生微粒.那么在pi(t)和xi(t+1)處于等價關系的時候，可以在xi(t+1)與pi(t)之間進行隨機挑選，挑選結果可作為微粒個體最優點；xi(t+1)ε 對 pi(t)起到支配作用的條件下，可以取x→i(t+1)代替個體最優點pi(t+1).如果二者關系都不是，那么pi(t+1)可以直接取pi(t).

1.3.2 全局最優點的判斷

全局最優點的判斷指的是在所有微粒群中對最佳位置完成所有工作，如上文所說，采用ε支配關系的比較方法可以得出個體最優點，個體最優點所在的微粒群就可以認定為全局最優點.

1.4 一致混沌變異

混沌屬于非線性現象，本身有著隨機性和遍歷性等特點，依照自身的規律，它可以在一定條件內對所有狀態作出遍歷，且沒有重復，依照這些特性，結合本文所說算法，可以起到增強全局搜索效果的作用[2].

這種通過結合而來的混沌變異算子在國內已經有人提出，即利用Zaslavskii映射函數可以得到混沌變量，然后對此混沌變量完成混沌空間→決策空間的轉化，進而能夠實現微粒飛行速度的變異.設速度上下界是Bround，算法終止代數*//是Tmax,決策變量維數是n.

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

1.5 算法步驟

異步并行的方法可以縮短微粒群優化的時間，進而達到提高效率的作用.該一部并行微粒群優化算法的步驟可以概括為：循環分解——消息發送——算法操作.

可以對其步驟進行簡單分析，第一，需要在決策空間內完成微粒群隨機初始化的工作；第二，需要利用主處理器把需要評價的微粒xj和個體最優點傳送到沒有處于工作狀態的附屬處理器；第三，附屬處理器會進行分類器準確率的確定工作，利用ε的支配關系，可以完成個體最優點pi的更新工作，進而將結果反饋給主處理器；進而由主處理器依據結果完成決策評價的工作，將全局最優點找出，進而根據公式，和一致混沌變異算子對微粒位置進行更新.在具體操作中，需要對主處理器的優化參數、算法以及微粒速度等條件進行設定，需要對微粒評價的處理完成排序[3]；而對于附屬處理器，需要結合微粒現有特點對SVM分類器進行訓練，且在準確率方面，需要結合10階交叉驗證的結果進行分析.

設迭代次數為t，學習因子是c1和c2，慣性全值為w，在[0,1]之間的隨機數是r1和r2.其調整位置的公式為：

而利用二進制微粒群優化算法，微粒xi中的分量xij取值在[0,1]之間，那么對其更新微粒位置可以利用邏輯函數轉化的方法，其轉化公式為：

2 實驗及性能分析

2.1 實驗流程

對于優化性能進行分析，需要利用學習數據庫，測試問題包含了Class、Vowel等數據集.具體信息可見表1.

表1 測試問題數據集

如表1所示數據，可以采用SFS（前向選擇）算法、BPSO算法和HGA（混雜遺傳）算法等五種算法對數據問題優化20次，可以得出結果，進而完成比較.

2.2 性能分析

以Class為例，其結果如表2所示.

表2 多種算法結果示例表

通過分析結果，可以發現BPSO的平均準確率要低于AP-PSO與MDPSO，且SFS平均準確率要低于HGA，如果測試問題較少，如Class與Vowel，呢么SFS與HGA效果可以達標，而特征數目較多的時候，AP-PSO的性能更好.

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

據此進行計算分析，可以得出結果，即同步并行方式與異步并行方式的計算速度都和處理器數目成正比，二者相比，異步并行方式速度增加的幅度更大；依據不同數目下的處理器進行比較，可以發現無論數目為多少，異步并行方式的速度都更快；在多個處理器之中，存在一個性能劣質的處理器時，異步并行方式所受影響更小.因為這種性能優勢，這種方法可以在多個領域存在強大的發展空間，如物流車輛路徑問題的解決等.

3 結論

綜上所述，通過對分類器的準確度的設定，對混沌變異算子的結合等步驟可以實現特征子集選擇的異步并行微粒群優化方法，利用實驗進行分析，可以發現一致混沌變異算子能夠對微粒變異范圍與變異概率起到調節的作用，且異步并行優化方法和同步并行方法比較上具有更高的效率，利用這種方法可以讓計算效率和計算準確率得到提高.

〔1〕馬立新,王繼銀,欒健,黃陽龍.三目標自適應變異微粒群算法的無功優化[J].電子科技,2016（04）:41-44.

〔2〕張勇,夏長紅,鞏敦衛,榮淼.基于多種群協同微粒群優化的流數據聚類算法[J].控制與決策,2016(10).

〔3〕鞏敦衛,胡瀅,張勇.知識引導微粒群優化特征選擇方法[J].模式識別與人工智能,2014（01）:1-10.

TP301

A

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

2017-07-10