差分進化樽海鞘群特征選擇算法

李占山, 楊鑫凱, 胡 彪, 張 博

(吉林大學 a. 計算機科學與技術學院; b. 符號計算與知識工程教育部重點實驗室; c. 軟件學院, 長春 130012)

0 引 言

特征選擇是從原始特征中選擇一些最有效特征以降低數(shù)據(jù)維度的過程[1], 是機器學習、 數(shù)據(jù)挖掘、 模式識別領域中關鍵的預處理步驟。常見的特征選擇方法依據(jù)選擇策略的不同大致可分為3類： 過濾式(filter)、 嵌入式(embedding)和包裹式(wrapper)[2]。過濾式方法不依賴于任何學習算法, 僅依靠對數(shù)據(jù)的某些特征進行評估, 以評估特征的重要性； 嵌入式方法將特征選擇過程與學習器訓練過程融為一體, 在學習器訓練過程中自動地進行特征選擇[3]； 包裹式方法依賴于預定義的學習算法評估所選特征的量。特征選擇的困難在于搜索空間會隨著特征個數(shù)的增加呈指數(shù)級增長[4], 因此, 設計并改進特征選擇算法成為了特征選擇問題求解的關鍵[5]。

演化計算技術由于具有良好的全局搜索能力， 近年來在特征選擇領域獲得了越來越多的關注[6]。一些基于演化計算的特征選擇包括較經(jīng)典的粒子群特征選擇算法PSO(Particle Swarm Optimization)[7]和較新的二元灰狼特征選擇算法bGWO(binary Grey Wolf Optimization)[8]、鯨魚特征選擇算法WOA(Whale Optimization Algorithm)[9]、 正余弦特征選擇算法SCA(Sine Cosine Algorithm)[10]、 二元蝴蝶特征選擇算法bBOA(binary Butterfly Optimization Approaches)[11]等。

在最新的工作中, Seyedali等[12]提出了一種樽海鞘群優(yōu)化(SSA: Salp Swarm Algorithm)算法。相比于其他算法, SSA算法在解決特征選擇問題上有著較好的表現(xiàn)力[13], 但由于粒子通過遷移方向單調(diào)的平均算子移動, 導致算法搜索能力受限而易陷入局部最優(yōu)； 同時和其他演化算法一樣存在收斂速度較慢的問題, 因此SSA算法仍有較大的提升空間。

筆者提出了一種改進樽海鞘群優(yōu)化算法的特征選擇方法, 將原本種群中跟隨者采取的平均算子更換為搜索能力更強的差分進化策略, 使粒子向前驅(qū)粒子遷移的同時向較優(yōu)的粒子移動, 并引入了根據(jù)適應度大小的進化種群動態(tài)機制用以加強收斂能力, 形成了差分進化樽海鞘群特征選擇算法(DESSA: Differential Evolution Salp Swarm Feature Selection Algorithm)。實驗結(jié)果表明, 筆者提出的方法與對比算法相比具有一定優(yōu)勢和競爭力。

1 相關工作

1.1 SSA算法

與其他演化計算一樣, 在SSA算法中各粒子的位置由二維矩陣各個向量表示, 并假定在搜索空間中存在最優(yōu)位置, 作為整個群體的目標。其中領導者通過

(1)

r1=2e-(4t/T)2

(2)

其中T為最大迭代次數(shù),t為當前迭代次數(shù)。

跟隨者采用

(3)

該算法流程圖如圖1所示。

圖1 SSA算法流程Fig.1 Flowchart of SSA algorithm

1.2 二進制SSA特征選擇算法

在特征選擇問題中, 所有粒子對應的問題解都限于離散{0,1}二值中, 因此在將SSA算法應用于解決特征選擇問題需通過

(4)

2 差分進化樽海鞘群特征選擇算法

針對以上算法的不足提出了相應的改進方案, 給出了差分進化樽海鞘群特征選擇算法。實驗表明, DESSA相較于SSA具有更優(yōu)的性能。

2.1 差分進化算子

差分進化(DE: Differential Evolution)是由Storn等[14]于1997年提出的基于人口的元啟發(fā)式優(yōu)化算法, 因其簡單性、 有效性和魯棒性而受到廣泛關注。在DESSA中, 差分算子主要由突變、 交叉和選擇3個基本部分構(gòu)成。在突變步驟中, 當前t時刻粒子對應的目標向量zi(t)會發(fā)生突變并生成突變載體vi(t)。DESSA通過

vi(t)=zi(t)+F(G-zi-1(t))

(5)

對跟隨者粒子進行突變。其中zi-1(t)為zi(t)的前驅(qū)粒子的位置向量,G為當前種群最優(yōu)粒子的位置向量,F為在[0,f]范圍內(nèi)通過

(6)

遞減的變化系數(shù)。其中f為變化參數(shù)的人為初值。通過式(5)得到的突變載體vi(t)需通過式(4)轉(zhuǎn)化為離散形式向量。

(7)

其中wCR為交叉權(quán)重。

在選擇過程中, 將交叉載體ui(t)與目標向量zi(t)進行評估比較, 具有較高適應度的粒子將勝出并作為更新位置zi(t+1), 表示如下

(8)

其中fitness(z)為用于評價目標函數(shù)。

在DESSA中, 各跟隨者粒子依次通過式(5),式(7),式(8)進行差分算子形式遷移, 直至t=T時結(jié)束。

2.2 進化種群動態(tài)機制

進化種群動態(tài)機制(EPD: Evolutionary Popu-lation Dynamics)是一種通過將最佳解決方案重新定位在最佳解決方案上以消除最差解決方案的過程[15]。它可以剔除找到最優(yōu)粒子可能性較小的一些粒子并根據(jù)一定機制將其替換為環(huán)繞當前種群最優(yōu)粒子的粒子, 從而快速將計算資源集中到搜索找到最優(yōu)粒子可能性較大的區(qū)域。在算法DESSA中, 它被應用到每次迭代的最后。進化種群動態(tài)機制具體分為淘汰和產(chǎn)生新粒子兩個步驟。在淘汰步驟中, 種群會按適應度將較差的后一半粒子淘汰。在產(chǎn)生新粒子步驟中, 種群會先根據(jù)排名選出當前適應度值排名前3的粒子zfirst(t),zsecond(t),zthird(t), 以及一個種群中異于該3個粒子的其他粒子, 之后對每個新生粒子在各維度的位置都以相同概率隨機從上述4個粒子同維度位置中選出一位作為其值, 進而生成新生粒子直至恢復種群固有數(shù)量。在EPD機制中參照多個優(yōu)質(zhì)粒子位置生成的新生粒子在種群中更具有搜索潛力, 同時淘汰種群中較劣粒子提高了種群質(zhì)量, 縮小了搜索空間, 進而加強種群的收斂能力。

2.3 評價指標

在DESSA中, 為了在特征選擇過程中提高分類準確率的同時減少選擇特征數(shù)量, 筆者采用的適應度函數(shù)[16]

fitness(z)=αRCA+(1-β)RDR

(9)

確保DESSA具有一定的降維能力。其中RCA與RDR為分類準確率和維度縮減率,α和β為調(diào)節(jié)參數(shù), 分別代表了分類準確率RCA和維度縮減率RDR的重要性。

2.4 DESSA算法流程

DESSA算法流程如圖2所示。

圖2 DESSA算法流程Fig.2 Flowchart of DESSA algorithm

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

3.1 實驗描述

為了驗證所提出算法的優(yōu)化效果, 筆者使用了8個選自UCI機器學習庫[17]的數(shù)據(jù)集進行對比實驗, 表1描述了各數(shù)據(jù)集的分類數(shù)、 特征數(shù)和樣本數(shù), 表2展示了數(shù)據(jù)集Glass的部分數(shù)據(jù)； 實驗中使用了K折交叉驗證方式, 即將數(shù)據(jù)集切分為K份, 每次取K-1份數(shù)據(jù)用于訓練, 剩余數(shù)據(jù)用于測試, 進行K次的訓練和測試； 實驗結(jié)果在每個數(shù)據(jù)集和算法中獨立運行20次, 最終統(tǒng)計平均值； 在分類器的選擇上,K近鄰(KNN:K-Nearest Neighbor)是一種簡單且非常通用的分類器, 已廣泛用于包裹式特征選擇[18], 實驗選擇該分類器作為基分類器, 并將參數(shù)K設置為最佳參數(shù)5[19]。

表1 數(shù)據(jù)集詳細信息

表2 數(shù)據(jù)集Glass部分數(shù)據(jù)

為對比算法的性能, 筆者在實驗中比較DESSA與SSA的同時加入了一些具有代表性的特征選擇算法： PSO[7]、 bGWO[8]、 WOA[9]、 SCA[10]、 bBOA[11]； 為保證對比實驗的公平性, DESSA除了變化參數(shù)初值f與交叉權(quán)重RCR, 參數(shù)設置與SSA完全相同, 實驗中所有算法的具體參數(shù)在表3中給出； 在筆者的實驗中, 用python 3.6實現(xiàn)算法, 同時使用了公開的工具包scikit-feature和scikit-learn。所有實驗均在一臺配置為Intel i7-7700HQ、 8 GByte內(nèi)存、 500 GByte硬盤的電腦上完成。

表3 算法參數(shù)詳細信息

3.2 評價指標

下面使用分類準確率CA(Classification Accuracy,RCA)和維度縮減率 DR(Dimensionality Reduction,RDR)作為算法最基本的評價指標[20], 其具體定義如下

(10)

(11)

其中NCC為正確分類的實例數(shù),NAS為數(shù)據(jù)集實例總數(shù),NSF為被選擇的特征數(shù),NAF為數(shù)據(jù)集的特征總數(shù)。為測試實驗中算法的穩(wěn)定程度, 筆者使用標準差評價算法魯棒性的指標, 具體定義[11]如下

(12)

其中Vfitness(G*i)為第i次運行得到的最佳適應度值,VMean為運行得到多個最優(yōu)解的平均適應度, 定義如下

(13)

3.3 實驗結(jié)果對比分析

對比分類準確率, 從表3可見, DESSA相較于SSA有較大的提升, 且在除Spambase數(shù)據(jù)集外的所有數(shù)據(jù)集上的平均分類準確率均達到了最高。因此在分類準確率上有了明顯的提升。

對比維度縮減率, 從表4可見, DESSA在所有數(shù)據(jù)集上相較于SSA都有一定提升, 且在Heart、 Vehicle、 Wine和Yeast數(shù)據(jù)集上達到了最高, 在其他數(shù)據(jù)集上也有較優(yōu)表現(xiàn)。

表4 DESSA及其對比算法的分類準確率CA實驗對比Tab.4 The results of the proposed DESSA and its comparison algorithms on classification accuracy (%)

對比標準差, 從表5中可見, DESSA在所有數(shù)據(jù)集上相較于SSA都表現(xiàn)更加穩(wěn)定, 且在Glass、 Lymphography、 Spambase、 Wisconsin和Yeast數(shù)據(jù)集上達到了最小, 在其他數(shù)據(jù)集上也有較優(yōu)表現(xiàn)。由此可見DESSA具有較好的魯棒性。

表5 DESSA及其對比算法的維度縮減率DR實驗對比Tab.5 The results of the proposed DESSA and its comparison algorithms on dimension reduction (%)

表6 DESSA及其對比算法的標準差實驗對比

4 結(jié) 語

筆者針對SSA在解決特征選擇問題時的不足之處提出了差分進化樽海鞘群算法DESSA。DESSA結(jié)合差分算子增強了算法的搜索能力, 同時引入EPD機制加快算法的收斂速度。最后, 通過8個數(shù)據(jù)集與具有代表性的6個特征選擇算法, 與DESSA一起進行了對比實驗, 驗證了DESSA優(yōu)異的性能。如何進一步增強算法的降維能力, 以及針對解決在高維數(shù)據(jù)集上的特征選擇問題的優(yōu)化, 將是下一步重點研究的內(nèi)容。