胡 瀅

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

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

1 提出的方法

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

1.1 多重插補

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

1.2 微粒編碼

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

1.3 適應度函數

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

(1)

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

1.4 全局極值的選擇

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

(2)

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

1.5 算法步驟

Step1：對缺失數據進行插補，得到完整的數據集；

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

Step3：根據式(1)計算目標函數值；

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

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

Step6：調整微粒的位置；

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

2 實驗與結果分析

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

2.1 測試數據及參數設置

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

表1 UCI數據集相關信息

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

2.2 實驗結果

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

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

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

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

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

3 結語

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

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

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

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

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

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

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

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