胡 瀅

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

微粒群優(yōu)化(Particle Swarm Optimization，PSO)是一種受鳥群或魚群覓食行為啟發(fā)產(chǎn)生的全局搜索方法.由于具有參數(shù)少、易于實現(xiàn)，以及不依賴優(yōu)化問題的梯度等優(yōu)點，微粒群優(yōu)化已被用于解決許多實際問題，如電網(wǎng)經(jīng)濟調(diào)度、機器人路徑規(guī)劃，以及車間生產(chǎn)調(diào)度等.但是，目前仍沒有關(guān)于數(shù)據(jù)缺失下的微粒群優(yōu)化特征選擇方法的研究.

1 提出的方法

首先，采用多重插補方法對缺失的數(shù)據(jù)進行插補，得到完整數(shù)據(jù)集；然后，采用k折交叉驗證法計算分類器的精度，并在算法運行后期，對微粒群進行K均值聚類，從中選擇微粒的全局最優(yōu)點，以提高算法的全局搜索能力.

1.1 多重插補

多重插補是一種以模擬為基礎(chǔ)的方法，對每個缺失值產(chǎn)生m個合理的插補值，這樣插補后，得到m組完全數(shù)據(jù)，使用標(biāo)準(zhǔn)的完全數(shù)據(jù)方法分析每組數(shù)據(jù)并融合分析結(jié)果[1].通常，往往假定抽樣機制是可以忽略的，因此，可以考慮簡單隨機抽樣下的多重插補方法.具體過程如下：

1.2 微粒編碼

特征選擇是指從大量特征中選擇出具有較好可分性的特征子集，是離散優(yōu)化問題.因此，需要采用特征選擇的概率對微粒進行編碼，將離散變量的特征選擇問題轉(zhuǎn)化為連續(xù)變量優(yōu)化問題[2].假設(shè)第i個微粒的位置表示為xi=(xi1,xi2,…,xiD)，若xij=1，則第j個特征被選中，否則，該特征沒有被選中.

1.3 適應(yīng)度函數(shù)

在特征選擇過程中，期望所選特征子集的分類精度越高，特征個數(shù)越少.本文借鑒文獻[3]的方法設(shè)置適應(yīng)度函數(shù)：

(1)

其中，A(x)表示以特征子集x反映的特征進行分類的精度，n(x)和β分別表示特征的數(shù)量及其重要程度，由于重點考慮分類精度，因此β可以取0.005.本文采用k折交叉驗證法，計算分類器的精度，對于含有S個數(shù)據(jù)的數(shù)據(jù)集而言，將S個數(shù)據(jù)分成k個不相交的子集，記作{s1,s2,…,sk}.每次從分好的子集里，選擇一個作為驗證集，剩余k-1個作為訓(xùn)練集.首先，由訓(xùn)練集對特征子集形成的分類器進行訓(xùn)練，得到一個分類模型；然后，利用驗證集，驗證分類模型的性能，得到分類精度；最后，計算k次分類精度的平均值，作為該模型的真實分類精度[4].

1.4 全局極值的選擇

由于微粒全局極值選擇直接影響微粒速度的更新，從而影響微粒下一時刻的位置.因此，采用合適的方法選擇微粒的全局極值，是非常重要的.采用傳統(tǒng)方法選擇微粒全局極值，易使算法陷入早熟和局部最優(yōu).因此，在算法運行后期，使用K均值聚類算法，增大搜索范圍，使微粒及時跳出局部最優(yōu)解.方法是：首先，對微粒群進行K均值聚類，產(chǎn)生若干個聚簇；然后，計算各個簇的中心，找到當(dāng)前全局最優(yōu)粒子所在的簇；最后，依次對其余簇進行討論，計算是否包含更優(yōu)的解.具體過程如下：

(2)

式中：α=(-1)λ，用于控制搜索的方向.rand為[0,1]之間均勻分布的隨機數(shù).

1.5 算法步驟

Step1：對缺失數(shù)據(jù)進行插補，得到完整的數(shù)據(jù)集；

Step2：初始化微粒群，設(shè)置每個微粒的個體極值為其本身，儲備集為空，迭代次數(shù)t=0，最大迭代次數(shù)記為Tmax；

Step3：根據(jù)式(1)計算目標(biāo)函數(shù)值；

Step4：更新微粒的全局極值和個體極值；

Step5：算法運行后期(t=0.8Tmax)，按1.4節(jié)方法更新微粒的全局極值；

Step6：調(diào)整微粒的位置；

Step7：判斷算法是否滿足終止條件.如果滿足，輸出優(yōu)化結(jié)果；否則，轉(zhuǎn)Step3.

2 實驗與結(jié)果分析

為驗證本文方法的性能，基于UCI數(shù)據(jù)集，將所提方法與標(biāo)準(zhǔn)微粒群優(yōu)化方法(SPSO)、NSGA-II，及混沌映射二進制微粒群優(yōu)化(CBPSO)進行比較[5]，驗證所提方法的有效性.所有試驗采用的PC機配置為雙核2.66 GHz、2 G RAM，Matlab編程.

2.1 測試數(shù)據(jù)及參數(shù)設(shè)置

選擇4個UCI數(shù)據(jù)集進行分析，分別是Class、Letter、WDBC及Sonar，隨機刪除其中的一部分?jǐn)?shù)據(jù).相關(guān)信息如表1所示.

表1 UCI數(shù)據(jù)集相關(guān)信息

算法參數(shù)設(shè)置如下：最大迭代次數(shù)Tmax=100，微粒群規(guī)模N=100，c1=c2=2，由于慣性權(quán)重w用來平衡微粒群的探索和開發(fā)能力，因此，按照文獻[6]給出線性時變調(diào)節(jié)方法取值，其中，wmax=0.995，wmin=0.5，比較算法參數(shù)依據(jù)相應(yīng)文獻進行設(shè)置.

2.2 實驗結(jié)果

針對完整數(shù)據(jù)集和缺失數(shù)據(jù)集兩種情況，將本文方法與其他3種方法進行比較，分別計算它們的分類精度和降維后特征子集的個數(shù)，結(jié)果如表2所示.

表2 四種方法的分類精度比較

由表2可知，對于缺失數(shù)據(jù)集，4種方法所得分類精度均小于完整數(shù)據(jù)集.原因是采用多重插補方法得到的替代值仍是估計值.由此，訓(xùn)練集構(gòu)建的分類器也是一個近似分類器，分類精度要小于實際分類器的分類精度[7].對于Class、Letter及Sonar數(shù)據(jù)集，本文方法獲得的分類精度均較高，且得到的特征子集的個數(shù)也是最少的，而對于WDBC數(shù)據(jù)集，盡管CBPSO方法獲得的分類精度要優(yōu)于本文方法，但本文方法能夠獲得最少的特征子集個數(shù).綜上結(jié)果可知，針對缺失數(shù)據(jù)下的特征選擇，所提方法比其它3種方法具有更好的特征選擇效果.

圖1針對完整數(shù)據(jù)集和缺失數(shù)據(jù)集，給出了本文方法對上述4種數(shù)據(jù)集的進化優(yōu)化結(jié)果.從圖中可以看出，缺失數(shù)據(jù)下的分類精度均小于完整數(shù)據(jù)集的分類精度，且隨著進化代數(shù)的增加，分類精度越來越高，當(dāng)達到100代后，分類精度基本保持不變.由此可知，本文方法均能以較快的尋優(yōu)速度獲得較高的分類精度.

圖1 本文方法對上述4種數(shù)據(jù)集在完整數(shù)據(jù)和缺失數(shù)據(jù)上的分類精度進化曲線

3 結(jié)語

本文針對數(shù)據(jù)缺失這一普遍現(xiàn)象，提出了一種改進的微粒群優(yōu)化特征選擇方法.首先，采用多重插補方法對缺失的數(shù)據(jù)進行插補，得到完整數(shù)據(jù)集；然后，用k折交叉驗證法計算分類器的精度，比較微粒解的優(yōu)劣；同時為防止微粒群陷入局部最優(yōu)，在算法運行后期，進行K均值聚類，使微粒群跳出局部最優(yōu)點；最后，通過測試4個典型UCI數(shù)據(jù)集，對完整數(shù)據(jù)集與隨機刪除部分?jǐn)?shù)據(jù)后的缺失數(shù)據(jù)集的特征選擇結(jié)果進行比較.結(jié)果表明，本文方法在處理數(shù)據(jù)缺失的特征選擇問題上具有一定的優(yōu)勢，是一種有效的特征選擇方法.

[1] 周勇,何創(chuàng)新.基于獨立特征選擇與相關(guān)向量機的變載荷軸承故障診斷[J].振動與沖擊,2012,31(3)：157-161.

[2] 鞏敦衛(wèi),胡瀅,張勇.知識引導(dǎo)微粒群優(yōu)化特征選擇方法[J].模式識別與人工智能，2014,27(1)：1-10.

[3] 宋相法,張延鋒,鄭逢斌.基于L2,1基范數(shù)稀疏特征選擇和超法向量的深度圖像序列行為識別[J].計算機科學(xué),2017,44(2)：306-308,323.

[4] 曾現(xiàn)峰.基于雙層微粒群優(yōu)化的機器人全局路徑規(guī)劃[J].計算機工程與應(yīng)用，2013,49(19)：238-241.

[5] 鄧桂秀,江修波,蔡金錠.基于混沌二進制粒子群算法的配電網(wǎng)重構(gòu)研究[J].電力科學(xué)與工程，2013,29(9)：34-37.

[6] 王麗,王曉凱.一種非線性改變慣性權(quán)重的粒子群算法[J].計算機工程與應(yīng)用,2007,43(4)：47-49.

[7] 徐海波,仲梁維,龔文露.車間生產(chǎn)調(diào)度優(yōu)化中改進微粒群算法的引用[J].機械工程與自動化,2015,6(3)：76-80.