李雯婷，韓 迪，葉符明

(1.貴州商學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，貴州 貴陽 550014；2.廣東金融學(xué)院 信用管理學(xué)院，廣東 廣州 510521)

0 引 言

特征選擇是數(shù)據(jù)處理、數(shù)據(jù)挖掘的預(yù)先步驟，主要目標(biāo)是選擇相關(guān)性和信息化程度高的特征子集，消除非相關(guān)冗余特征，提高分類器學(xué)習(xí)效率[1]。目前，特征選擇主要有過濾法和封裝法[2]。過濾法主要利用數(shù)據(jù)關(guān)聯(lián)的統(tǒng)計(jì)手段決定特征關(guān)聯(lián)，方法與學(xué)習(xí)模型無關(guān)。例如信息增益、互信息、主成分分析等。此方法的冗余特征過多、選擇精度差。封裝法將機(jī)器學(xué)習(xí)的思想關(guān)聯(lián)至特征子集的選擇過程中，能夠降低特征子集的維度。而特征選擇的目標(biāo)是同步實(shí)現(xiàn)數(shù)據(jù)集分類的準(zhǔn)確率最高和特征選擇量最小，該問題可視為優(yōu)化問題。

近年來，群智能算法廣泛應(yīng)用于特征選擇問題。如GWO算法[3]、ALO算法[4]、WOA算法[5]、BA算法[6]、SSA算法[7]均在特征選擇領(lǐng)域得到應(yīng)用，并取得了不錯(cuò)的性能表現(xiàn)。蚱蜢(也稱蝗蟲)優(yōu)化算法GOA[8]是近年來提出的一種新型群智能算法，它模擬了蚱蜢在不同成長階段的行為特征，具有較強(qiáng)的全局搜索能力，已廣泛應(yīng)用在調(diào)度優(yōu)化[9]、機(jī)器人尋徑[10]、醫(yī)學(xué)細(xì)胞供應(yīng)預(yù)測[11]等諸多領(lǐng)域。

然而，標(biāo)準(zhǔn)GOA依然存在尋優(yōu)精度差、收斂速度慢的不足。為此，文獻(xiàn)[12]引入正余弦機(jī)制協(xié)調(diào)算法全局搜索和局部開發(fā)，利用變異使算法能夠跳離局部最優(yōu)。文獻(xiàn)[13]提出結(jié)合模擬退火和曲線自適應(yīng)的蝗蟲優(yōu)化算法，對算法全局尋優(yōu)能力和局部最優(yōu)跳離進(jìn)行了優(yōu)化。文獻(xiàn)[14]提出融合變異和均勻分布的蝗蟲優(yōu)化算法，以分段思想作位置更新，使算法更好尋優(yōu)。文獻(xiàn)[15]設(shè)計(jì)對立學(xué)習(xí)蝗蟲優(yōu)化算法，文獻(xiàn)[16]利用混沌系統(tǒng)均衡全局搜索和局部開發(fā)，都實(shí)現(xiàn)了標(biāo)準(zhǔn)GOA算法的性能提升。

鑒于已有工作針對GOA算法在開發(fā)與搜索間的均衡、提升收斂速度及跳離局部最優(yōu)問題上的改進(jìn)仍有片面性，本文具體工作為：設(shè)計(jì)一種融合完全隨機(jī)性的混沌Tent映射實(shí)現(xiàn)種群初始化，豐富種群多樣性和遍歷性；利用學(xué)習(xí)自動(dòng)機(jī)對調(diào)整系數(shù)c更新，均衡全局搜索與局部開發(fā)；引入折射對立學(xué)習(xí)位置更新機(jī)制，避免陷入早熟收斂。將改進(jìn)GOA算法應(yīng)用于特征選擇問題，設(shè)計(jì)新的特征選擇算法LRGOAFS，實(shí)驗(yàn)證明LRGOAFS可以同步降低特征選擇維度和提升數(shù)據(jù)分類準(zhǔn)確率。

1 蚱蜢優(yōu)化算法GOA

蚱蜢優(yōu)化算法GOA是一種較新的自然啟發(fā)式算法，模擬了蚱蜢這類昆蟲的社會(huì)行為。蚱蜢這類害蟲會(huì)影響農(nóng)作物產(chǎn)量，其整個(gè)生命周期由3個(gè)階段組成：蟲卵、幼蟲和成蟲。在幼蟲階段，蚱蜢的運(yùn)動(dòng)特征包括跳躍和柱狀旋轉(zhuǎn)式飛行，步長小，移動(dòng)慢，捕食路徑上的植被；而成蟲階段，蚱蜢則以群體方式大范圍遷移，步長大，且具有突然性。GOA算法則通過幼蟲階段的局部開發(fā)和成蟲階段的全局搜索，促使種群向目標(biāo)移動(dòng)，實(shí)現(xiàn)目標(biāo)搜索。蚱蜢個(gè)體位置的數(shù)學(xué)模型為

Xi=Si+Gi+Ai

(1)

式中：Xi為蚱蜢i的位置，Gi為蚱蜢i的重力，Ai為蚱蜢所受風(fēng)力，Si為蚱蜢i與其它種群個(gè)體間的社群作用力，定義為

(2)

式中：dij=|xj-xi| 為蚱蜢i與j間的距離，d′ij=(xj-xi)/dij為個(gè)體i至個(gè)體j間的距離單元矢量。函數(shù)s可視為社群作用力的強(qiáng)度，定義為

s(r)=fe(-r/l)-e-r

(3)

式中：f為吸引力強(qiáng)度，l為吸引力步長。搜索食物過程中，蚱蜢會(huì)根據(jù)社群作用力建立3類區(qū)域：舒適區(qū)、吸引區(qū)和排斥區(qū)。當(dāng)蚱蜢間的距離逐步增大時(shí)(大于10)，函數(shù)s趨近于無法產(chǎn)生社群作用力，即個(gè)體間沒有相互影響的作用力。一般做法是將個(gè)體位置限制于區(qū)間[1,4]。而處于舒適區(qū)個(gè)體的位置不進(jìn)行更新。

Gi定義為

Gi=-ge′g

(4)

其中，g為引力常量，e′g為指向地心的單元矢量。Ai定義為

Ai=ue′w

(5)

其中，u為漂移常量，e′w為風(fēng)向單元矢量。將相關(guān)參數(shù)代入式(1)，有

(6)

其中，N為種群中的蚱蜢數(shù)。

通常情況下，個(gè)體受到重力G和風(fēng)力A的作用較弱，種群個(gè)體僅依據(jù)社群作用力S的影響進(jìn)行位置更新。因此，可將位置更新方式定義為

(7)

(8)

其中，cmax為調(diào)整系數(shù)的最大值，cmin為最小值，l為當(dāng)前迭代數(shù)，L為最大迭代數(shù)。

GOA算法偽代碼如算法1所示。

算法1：標(biāo)準(zhǔn)GOA算法

(1)initialize the value of the parameters such as population sizeN,cmax,cmin,L

(2)generate a random populationX

(3)set the current iterationl=1

(4)whilel

(5) compute the fitness functionf

(7) update the value ofc

(8) fori=1 toNdo

(9) normalize the distance between the solutions inXin the interval [1,4]

(10) updatexi∈X

(11) end for

(12)l=l+1

(13)end while

2 基于學(xué)習(xí)自動(dòng)機(jī)和折射對立學(xué)習(xí)的改進(jìn)蚱蜢優(yōu)化算法LRGOA

2.1 基于混沌映射的種群初始化

初始種群的分布對群智能算法的尋優(yōu)速度和精度有著關(guān)鍵影響。GOA算法通過隨機(jī)方式進(jìn)行個(gè)體的初始化操作，這會(huì)導(dǎo)致種群多樣性缺乏，無法個(gè)體對空間的遍歷性。改進(jìn)算法借助于混沌系統(tǒng)的隨機(jī)性、遍歷性特征，提升種群多樣性。目前，較為常用的混沌映射系統(tǒng)是Logistic和Tent混沌系統(tǒng)，如圖1所示(100次迭代生成的混沌值)?？梢?，Logistic映射比Tent映射遍歷性更差，在[0,0.1]、[0.9,1]兩個(gè)區(qū)間取值率較高(邊緣位置密度高)，中間密度較低，且對初始參數(shù)較為敏感。Tent映射均勻性好于Logistic映射，但Tent映射存在小周期、周期點(diǎn)不確定的不足。綜合考慮，改進(jìn)算法在Tent映射中融入完全隨機(jī)化，添加隨機(jī)變量r/N改變混沌Tent原來的映射方式，具體方式為

(9)

式中：i為種群規(guī)模，j為混沌序號，對應(yīng)個(gè)體空間維度，θ為隨機(jī)數(shù)，μ為混沌參數(shù)，且θ∈[0,1]，μ∈[0,2]。 確定混沌參數(shù)μ并對式(9)取相應(yīng)初始值后，通過式(10)進(jìn)行位置映射

xi,j=oi,min+yi,j×(hi,max-oi,min)

(10)

式中： [oi,min,hi,max] 為位置xi,j的上下限。

圖1 混沌映射

隨機(jī)生成種群無法保證初始個(gè)體均勻遍布完整搜索域，進(jìn)而降低搜索精度。而根據(jù)式(9)，混沌序列的生成值取決于初始值，而初始值所發(fā)生的微小變化也會(huì)導(dǎo)致混沌序列值發(fā)生巨大變化，此時(shí)生成的初始種群將兼具隨機(jī)多樣和遍歷性等特征，這樣可以通過迭代均勻地遍歷到整個(gè)搜索區(qū)域。

2.2 基于學(xué)習(xí)自動(dòng)機(jī)的調(diào)整系數(shù)c更新

根據(jù)式(7)可知，蚱蜢位置更新時(shí)需要兩次利用調(diào)整系數(shù)c1和c2，其中，c1類似粒子群優(yōu)化PSO的慣性權(quán)重，c1的作用是控制全局搜索與局部開發(fā)間的均衡。c2的作用則是減少個(gè)體間的吸引域、舒適域和排斥域，逐步減小吸引力和排斥力。然而，根據(jù)式(8)可知，調(diào)整系數(shù)是線性遞減的，導(dǎo)致全局搜索與局部開發(fā)切換、不同域內(nèi)的個(gè)體所受吸引力和排斥力都以相同概率進(jìn)行，這并不能滿足最優(yōu)的蚱蜢尋優(yōu)過程，搜索精度會(huì)受到影響。因此，兩個(gè)調(diào)整系數(shù)的更新必須以非線性形式進(jìn)行更新。本文將引入以下的學(xué)習(xí)自動(dòng)機(jī)對調(diào)整系數(shù)進(jìn)行動(dòng)態(tài)更新。

隨機(jī)環(huán)境中，可執(zhí)行的行動(dòng)數(shù)通常是有限的。當(dāng)執(zhí)行輸入行動(dòng)集中的一個(gè)特定行動(dòng)時(shí)，環(huán)境將給出一種反饋(獎(jiǎng)勵(lì)或懲罰)。學(xué)習(xí)自動(dòng)機(jī)的關(guān)鍵目標(biāo)是通過分析過往行動(dòng)及相應(yīng)反饋選擇最優(yōu)行動(dòng)，即：通過調(diào)整每個(gè)行動(dòng)被選中的概率分布，并使概率值最終收斂到最佳行動(dòng)上。學(xué)習(xí)自動(dòng)化中，初始所有行動(dòng)擁有相同概率，隨機(jī)選擇一種行動(dòng)并觀察環(huán)境反饋?；诜答伣Y(jié)果，更新行動(dòng)概率。通過若干次迭代學(xué)習(xí)，LA將選擇獲得環(huán)境獎(jiǎng)勵(lì)的最優(yōu)行動(dòng)集。一個(gè)可變結(jié)構(gòu)的學(xué)習(xí)自動(dòng)機(jī)可定義為六元組 (B,Φ,Ψ,P,G,T)， 其中，B為輸入行動(dòng)集，Φ為內(nèi)在狀態(tài)集，Ψ為環(huán)境反饋集，P為每個(gè)行動(dòng)被選擇的概率矢量，G為概率更新策略，T為學(xué)習(xí)算法。

本文利用線性獎(jiǎng)懲策略作為學(xué)習(xí)算法，兩個(gè)學(xué)習(xí)參數(shù)a、b用于更新學(xué)習(xí)自動(dòng)機(jī)的行動(dòng)選擇概率，其中，a為獎(jiǎng)勵(lì)步長，b為懲罰步長。本文假設(shè)兩個(gè)學(xué)習(xí)參數(shù)a、b相等，以確保每次迭代擁有相同的概率更新。令αi為時(shí)刻t的行動(dòng)選擇，p(t)為行動(dòng)選擇概率分布函數(shù)，β為相應(yīng)環(huán)境反饋。對于β∈{0,1} 的特定環(huán)境反饋，擁有r個(gè)行動(dòng)(B中行動(dòng)數(shù))線性獎(jiǎng)懲策略可定義為式(11)，即β=0的獎(jiǎng)勵(lì)反饋；和式(12)，即β=1的懲罰反饋。

當(dāng)β=0時(shí)

(11)

當(dāng)β=1時(shí)

(12)

其中，i為前一步驟中自動(dòng)機(jī)的狀態(tài)，j為自動(dòng)機(jī)更新后的狀態(tài)。i=j表明保持前一行動(dòng)選擇，i≠j表明需要改變行動(dòng)選擇。

結(jié)合以上分析，本文將利用學(xué)習(xí)自動(dòng)機(jī)對調(diào)整系數(shù)c1和c2進(jìn)行非線性自適應(yīng)更新，具體定義為

c1=c1+k1δ

(13)

c2=c2+k2δ

(14)

其中，δ為較小正常量，k1、k2為決策參數(shù)，即行動(dòng)集 {-1,0,1}。 初始時(shí)，3種行動(dòng)取值概率相等。隨著迭代的進(jìn)行，行動(dòng)選擇概率將根據(jù)線性獎(jiǎng)懲策略進(jìn)行更新，即通過式(9)、式(10)的獎(jiǎng)懲策略更新k1、k2在行動(dòng)上的選擇概率。根據(jù)將選擇環(huán)境反饋β進(jìn)行更新，β=0代表自動(dòng)機(jī)將獲得獎(jiǎng)勵(lì)，β=1代表自動(dòng)機(jī)將獲得懲罰。通過比較個(gè)體適應(yīng)度優(yōu)劣，確定環(huán)境反饋是獎(jiǎng)勵(lì)或懲罰。若新個(gè)體的適應(yīng)度優(yōu)于原始個(gè)體，則自動(dòng)機(jī)獲得獎(jiǎng)勵(lì)，β=0；否則，β=1。通過這種更新方式，算法所選擇的調(diào)整系數(shù)更新將是使得個(gè)體能從環(huán)境中獲得獎(jiǎng)勵(lì)的最優(yōu)行動(dòng)選擇帶來的結(jié)果。

2.3 基于折射對立學(xué)習(xí)的位置更新

對立學(xué)習(xí)是一種豐富候選種群個(gè)體質(zhì)量的有效方式，它綜合利用了當(dāng)前解的對立解的方式對候選種群的分布范圍進(jìn)行了擴(kuò)展，即同時(shí)在當(dāng)前解和對立解的方向進(jìn)行搜索，提高尋得較優(yōu)解的可能性。

定義個(gè)體i的位置為Xi=(xi,1,xi,2,…,xi,d)，xi∈[oi,hi]， 代表d維空間中問題的一個(gè)候選解， [oi,hi] 為個(gè)體i在維度上的搜索范圍。Xi的對立解為X′i=(x′i,1,x′i,2,…,x′i,d)，x′i,j為原解Xi中xi,j的對立數(shù)，i=1,2,…,N，j=1,2,…,d， 且對立數(shù)x′i=oi+hi-xi，xi∈[oi,hi]。 在計(jì)算個(gè)體位置適應(yīng)度的同時(shí)，同步考慮其對立解的適應(yīng)度，將候選解及其對立解同步考慮在種群中，并通過貪婪選擇策略擇優(yōu)保留個(gè)體至下一代種群，即為常規(guī)的對立學(xué)習(xí)機(jī)制。

然而，對立學(xué)習(xí)僅能在種群迭代早期提升算法的尋優(yōu)性能，在迭代晚期，對立解也可能陷入局部最優(yōu)。而折射對立學(xué)習(xí)則在對立學(xué)習(xí)基礎(chǔ)上，應(yīng)用光線的折射原理來擴(kuò)大搜索范圍，增加搜索全局最優(yōu)解的概率。光的折射定理指出：真空中的光線射入另一介質(zhì)時(shí)，入射光線、折射光線及法線處于同一平面。折射角小于入射角，且隨入射角增加而增加，具體原理如圖2所示。

圖2 光線的折射原理

令原始解為x，折射解為x″，入射角為ρ1，折射角為ρ2，入射光線長度為m，折射光線長度為m′， [o,h] 為蚱蜢維度位置的搜索范圍，則

(15)

則光線的折射率φ為

(16)

令z=m/m′， 可得折射對立解為

(17)

若z=φ=1， 則折射對立解退化為對立解。

圖3是當(dāng)前解、對立解及折射對立解的位置可能分布情況?？梢姡舭磳α⒔鈞′方向搜索，候選解將逐步遠(yuǎn)離最優(yōu)解，即使個(gè)體適應(yīng)度得到改善，也可能是局部最優(yōu)。然而，折射對立解的分布區(qū)域明顯與最優(yōu)解距離更近，更利于算法得到全局最解。為了使折射對立解逐步靠近最優(yōu)解的鄰近區(qū)域，可以調(diào)整入射解改變參數(shù)z、φ的取值使更靠近最優(yōu)解的折射對立解x″2或x″3進(jìn)一步接近最優(yōu)解區(qū)域，如：減小入射角ρ1降低折射率φ使折射對立解x″2接近最優(yōu)，或增加折射光線長度m′減小z值使折射對立解x″3接近最優(yōu)。

圖3 當(dāng)前解、對立解及折射對立解的分布

引入折射對立學(xué)習(xí)機(jī)制進(jìn)行個(gè)體位置更新后，通過折射率φ或入射/折射光線長度比z的調(diào)整，有能力使LRGOA算法擴(kuò)展搜索區(qū)域，提高種群多樣性，避免過早陷入局部最優(yōu)。

2.4 LRGOA算法實(shí)現(xiàn)

LRGOA算法步驟如下：

步驟1 對種群規(guī)模N，最大迭代數(shù)L，混沌參數(shù)μ，調(diào)整系數(shù)最大值cmax和最小值cmin、常量δ等參數(shù)進(jìn)行初始化操作；

步驟2 利用修正的混沌Tent映射方法形成初始化種群；

步驟3 計(jì)算種群個(gè)體適應(yīng)度，確定最優(yōu)解；

步驟4 利用學(xué)習(xí)自動(dòng)機(jī)機(jī)制更新調(diào)整系數(shù)c；

步驟5 首先利用式(7)更新所有種群個(gè)體位置，再根據(jù)折射對立學(xué)習(xí)機(jī)制計(jì)算個(gè)體的折射對立解，通過貪婪選擇策略，保留原始解和其折射對立學(xué)習(xí)解中適應(yīng)度較優(yōu)的解至種群中，且種群規(guī)模保持不變；

步驟6 重新計(jì)算種群個(gè)體適應(yīng)度，更新最優(yōu)個(gè)體；

步驟7 迭代尋優(yōu)過程結(jié)束，轉(zhuǎn)到步驟8；否則，重復(fù)步驟4～步驟6；

步驟8 輸出最優(yōu)解。

3 基于LRGOA算法的特征選擇方法LRGOAFS

3.1 特征選擇模型

針對包含若干屬性的數(shù)據(jù)集而言，特征選擇是二值決策優(yōu)化問題，存在的理論解是指數(shù)級的。利用LRGOA算法進(jìn)行特征選擇可以通過群智能算法獨(dú)有的啟發(fā)式搜索機(jī)制極大減小搜索空間和時(shí)間復(fù)雜度。然而，特征選擇解僅為取值0或1，1代表選擇該特征，0代表不選擇該特征。而LRGOA算法是針對連續(xù)優(yōu)化問題的算法，因此，需要將蚱蜢個(gè)體位置改變從連續(xù)變化轉(zhuǎn)化為二值變化。

表1代表一種特征選擇解，可將其視為蚱蜢個(gè)體在搜索空間中的位置矢量。矢量長度代表數(shù)據(jù)集的特征屬性總量，即8個(gè)原始屬性。矢量元素xi,2=xi,3=xi,5=xi,7=1， 代表2、3、5、7被LRGOA算法選擇在最優(yōu)特征子集，矢量元素xi,1=xi,4=xi,6=xi,8=0， 代表特征1、4、6、8未被選擇為最優(yōu)特征。分類器將根據(jù)特征2、3、5、7進(jìn)行數(shù)據(jù)分類。

表1 特征選擇解

利用Sigmoidal函數(shù)(S型)實(shí)現(xiàn)LRGOA算法的二值轉(zhuǎn)換，將連續(xù)蚱蜢優(yōu)化算法轉(zhuǎn)換為二進(jìn)制形式，定義為

(18)

式中：ΔXl表示迭代l時(shí)搜索個(gè)體的步長矢量，函數(shù)T表示特征子集中元素取值為1的概率。

個(gè)體位置將基于概率值T(ΔXl) 進(jìn)行更新，具體為

(19)

其中，rand為隨機(jī)值。

對于封裝法下的特征選擇方法，需要結(jié)合學(xué)習(xí)算法評估所選特征子集優(yōu)劣。本文將采用k最近鄰分類器KNN獲取相應(yīng)解的分類準(zhǔn)確率。分類準(zhǔn)確率越高，表明解的相關(guān)性越好。同時(shí)，由于特征選擇還需要盡可能減少選擇特征量，解中特征數(shù)量越少，也表明解的性能越優(yōu)。因此，需要綜合考慮這兩個(gè)沖突式目標(biāo)設(shè)計(jì)特征選擇算法的適應(yīng)度函數(shù)。本文通過式(20)定義平衡兼顧每個(gè)搜索個(gè)體的特征選擇量(最小化)和分類準(zhǔn)確率(最大化)的適應(yīng)度函數(shù)來評估所選特征子集的質(zhì)量

(20)

式中：ErrRate表示利用所選特征的分類錯(cuò)誤率，即分類器錯(cuò)誤分類在總體分類中的占比，取值0到1之間，|SF|表示特征選擇量，|ALLF|表示原始數(shù)據(jù)集的屬性總量，ξ表示控制參數(shù)，用于控制算法對分類質(zhì)量和特征子集長度的偏好，ξ∈[0,1]。

3.2 特征選擇算法設(shè)計(jì)

算法組成結(jié)構(gòu)如下：首先，對數(shù)據(jù)集進(jìn)行預(yù)處理，將其劃分為測試集和訓(xùn)練集；其次，將數(shù)據(jù)集中的特征分布映射至種群個(gè)體位置的搜索空間中，使特征選擇問題與個(gè)體位置匹配；然后，進(jìn)入LRGOA算法的尋優(yōu)過程，該過程主要通過折射對立學(xué)習(xí)機(jī)制對個(gè)體位置(對應(yīng)特征選擇解)進(jìn)行動(dòng)態(tài)更新，其中的調(diào)整系數(shù)c將以學(xué)習(xí)自動(dòng)機(jī)進(jìn)行更新，從而更好提高搜索精度；通過不斷更新種群最優(yōu)解，最后，在到達(dá)算法終止條件時(shí)，輸出最優(yōu)個(gè)體即特征選擇最優(yōu)解。圖4是基于LRGOA算法的特征選擇過程。

圖4 LRGOAFS特征選擇算法流程

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)配置

為了驗(yàn)證基于LRGOAFS算法的特征選擇方法的有效性和穩(wěn)定性，選取UCI庫中(https://archive.icu.uci.edu/ml/index.php.)的10個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測試分析，數(shù)據(jù)集描述見表2。實(shí)驗(yàn)環(huán)境為操作系統(tǒng)win 10，CPU為i7 2.2 GHz，內(nèi)存為8 GB。種群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)置為100，混沌參數(shù)μ設(shè)為0.7，調(diào)整系數(shù)最大值cmax為1，最小值cmin為0.000 01、常量δ為0.1，控制參數(shù)ξ為0.99(通常分類準(zhǔn)確率相對特征選擇量具有更大的重要性)。作為群智能算法，LRGOAFS算法下特征選擇過程具有一定隨機(jī)性，在數(shù)據(jù)集上執(zhí)行10次獨(dú)立實(shí)驗(yàn)并取均值結(jié)果以降低偶然因素對算法計(jì)算結(jié)果的影響。實(shí)驗(yàn)實(shí)施中，利用10-折交叉驗(yàn)證(10-folds cross-validation)選擇訓(xùn)練樣本和測試樣本。將每個(gè)數(shù)據(jù)隨機(jī)劃分為10個(gè)部分，9個(gè)部分作為訓(xùn)練集，剩下1個(gè)部分作為測試集。分類器KNN中參數(shù)k=5。圖5是相應(yīng)實(shí)驗(yàn)過程圖解。

表2 數(shù)據(jù)集說明

圖5 實(shí)驗(yàn)過程

選擇基于灰狼優(yōu)化的特征選擇算法BGWOFS[17]、蚱蜢優(yōu)化特征選擇算法BGOAFS[18]和改進(jìn)蚱蜢優(yōu)化特征選擇算法IGOAFS[19]進(jìn)行性能對比。本文基于LRGOA的特征選擇算法命名為LRGOAFS。BGWOFS采用了較新的同為群智能算法的灰狼優(yōu)化算法GWO對特征選擇進(jìn)行求解，BGOAFS則采用標(biāo)準(zhǔn)GOA算法進(jìn)行了特征選擇求解，IGOAFS則在改進(jìn)標(biāo)準(zhǔn)GOA算法尋優(yōu)精度和效率的基礎(chǔ)上再求解特征選擇問題。BGWOFS算法中，收斂因子a的取值范圍為[0,2]。BGOAFS算法參數(shù)與本文相同，IGOAFS算法中l(wèi)imit閾值設(shè)為15，隨機(jī)個(gè)體選取量為種群規(guī)模的三分之一。3種算法的選擇使得后文的對比實(shí)驗(yàn)中同時(shí)兼顧了橫向和縱向的比較。

4.2 評估指標(biāo)

(1)平均分類準(zhǔn)確率AAC

AAC代表得到特征子集后，在特定數(shù)據(jù)集上利用分類器計(jì)算的平均分類準(zhǔn)確率。AAC取值越大，代表分類性能越好。具體定義為

(21)

其中，M為實(shí)驗(yàn)重復(fù)次數(shù)，n為測試數(shù)據(jù)集的屬性總量，Cj為屬性j的正確分類標(biāo)簽，Lj為分類器得到的預(yù)測標(biāo)簽，函數(shù)Mat(x,y) 定義為

(22)

(2)平均特征子集降低比例AFSR

由于原始數(shù)據(jù)集中包含許多非相關(guān)性的冗余特征，若特征子集中特征關(guān)聯(lián)性不大，冗余特征過多，不僅會(huì)降低分類器的學(xué)習(xí)效率，還會(huì)降低數(shù)據(jù)集的分類準(zhǔn)確率。因此，必須有效降低特征子集規(guī)模，最大程度提升特征間的相關(guān)性，在降低特征維度的同時(shí)，實(shí)現(xiàn)分類準(zhǔn)確率的最大提升。

AFSR代表特征選擇算法得到的特征子集規(guī)模降低程度。AFSR取值越小，性能越好。將平均特征子集規(guī)模AFS定義為

(23)

則AFSR為

(24)

其中，M為實(shí)驗(yàn)重復(fù)次數(shù)， |C| 為原始特征子集長度，g*,i為第i次算法運(yùn)行的最優(yōu)特征子集， |*| 為集合*的基數(shù)。

(3)平均適應(yīng)度AF及標(biāo)準(zhǔn)差SD

AF代表最優(yōu)特征子集對應(yīng)的平均適應(yīng)度值，取值越小，算法性能越好。SD則體現(xiàn)特征選擇算法的穩(wěn)定性，取值越小，說明算法穩(wěn)定性越強(qiáng)。具體定義為

(25)

(26)

4.3 實(shí)驗(yàn)結(jié)果

圖6是4種算法在10個(gè)數(shù)據(jù)集上得到的平均分類準(zhǔn)確率及相應(yīng)標(biāo)準(zhǔn)方差值，柱狀圖對應(yīng)左側(cè)縱坐標(biāo)，折線圖對應(yīng)右側(cè)縱坐標(biāo)。本文的LRGOAFS算法在Flare、Hepatitis、Ionoshpere、Wine、Zoo、Vote等6個(gè)數(shù)據(jù)集上得到了最高平均分類準(zhǔn)確率，是4種算法中最好的。同時(shí)，LRGOAFS算法可以在規(guī)模較大的Flare上得到最高分類準(zhǔn)確率，證明算法不僅可以處理中小規(guī)模特征選擇問題，對較大規(guī)模特征選擇也是有效可行的。標(biāo)準(zhǔn)方差對應(yīng)算法穩(wěn)定性，LRGOAFS算法在5個(gè)數(shù)據(jù)集上得到更小的標(biāo)準(zhǔn)方差，說明算法穩(wěn)定性也比較好，在處理不同規(guī)模特征選擇問題上適應(yīng)度較強(qiáng)。另外3種算法雖然在個(gè)別數(shù)據(jù)集上可以得到比LRGOAFS算法更高的平均分類準(zhǔn)確率，但穩(wěn)定性欠佳，求解成功率太低。

圖6 平均分類準(zhǔn)確率

圖7是4種算法在10個(gè)數(shù)據(jù)集上得到的平均適應(yīng)度及相應(yīng)標(biāo)準(zhǔn)方差值，柱狀圖對應(yīng)左側(cè)縱坐標(biāo)，折線圖對應(yīng)右側(cè)縱坐標(biāo)。適應(yīng)度函數(shù)(20)表明分類錯(cuò)誤率越小，特征選擇量越少，算法性能越好，對應(yīng)于適應(yīng)度函數(shù)值越小越好?？梢钥吹剑琇RGOAFS算法在Bands、Ionoshpere、Lung、Wine、Zoo等5個(gè)數(shù)據(jù)集上得到了更小的適應(yīng)度，是4種算法中占比最高的，說明在綜合考慮分類準(zhǔn)確率和特征選擇量方面，算法具有更好的綜合性能。也證實(shí)在LRGOAFS算法中采用針對標(biāo)準(zhǔn)GOA算法的改進(jìn)措施是有效可行的，可以提升算法的尋優(yōu)精度。

圖7 平均適應(yīng)度

圖8 平均特征子集降低比例

圖8是4種算法在10個(gè)數(shù)據(jù)集上得到的特征子集降維比例，比例越大，說明算法選擇的最優(yōu)特征子集規(guī)模越小，數(shù)據(jù)特征降維效果越好。LRGOAFS算法在6個(gè)數(shù)據(jù)集上得到最大降維比例，占比最高。結(jié)合圖6的結(jié)果可知，LRGOAFS算法在Ionoshpere、Wine、Zoo、Vote等4個(gè)數(shù)據(jù)集上同時(shí)實(shí)現(xiàn)了最高的分類準(zhǔn)確率和最小的特征選擇比例，性能最好。另種3種算法并不能保證穩(wěn)定性。

圖9是4種算法在10個(gè)數(shù)據(jù)集上的平均計(jì)算時(shí)間對比結(jié)果。結(jié)果表明，LRGOAFS算法并不能保證在所有數(shù)據(jù)集上擁有最少的計(jì)算時(shí)間，甚至在部分?jǐn)?shù)據(jù)集上計(jì)算時(shí)間花費(fèi)更多(如Lung、Hepatitis數(shù)據(jù)集等)，但結(jié)合前文算法在分類準(zhǔn)確率(圖6)、特征降維(圖8)和適應(yīng)度(圖7)方面的表現(xiàn)，LRGOAFS算法依然實(shí)現(xiàn)了所有算法中的最佳綜合性能，算法在特征降維、提升分類準(zhǔn)確率的同時(shí)，并未犧牲過多計(jì)算效率。

圖9 算法的平均計(jì)算時(shí)間

本文在第4節(jié)的實(shí)驗(yàn)配置階段為LRGOAFS算法選用的分類器為KNN，這一部分進(jìn)一步引用支持向量機(jī)SVM作為分類器對LRGOAFS算法的性能進(jìn)行對比分析。KNN找到訓(xùn)練集中離預(yù)測樣本點(diǎn)距離最近的k個(gè)值即可，在訓(xùn)練集和測試集規(guī)模很大時(shí)，預(yù)測效率很可觀。且其參數(shù)只有一個(gè)k值，調(diào)參比較簡單。SVM具有相對復(fù)雜的訓(xùn)練過程，訓(xùn)練完后再對測試集進(jìn)行分類，兩步獨(dú)立進(jìn)行。同時(shí)SVM參數(shù)更多，訓(xùn)練時(shí)間復(fù)雜性會(huì)略高。兩種分類器各有優(yōu)劣。將利用兩種分類器的特征選擇算法分別命名為LRGOAFS-KNN和LRGOAFS-SVM。測試了兩種算法在平均分類準(zhǔn)確率和平均特征子集降低比例上的實(shí)驗(yàn)結(jié)果，如圖10所示。圖中，柱狀圖對應(yīng)左縱軸的平均分類準(zhǔn)確率結(jié)果，折線圖對應(yīng)右縱軸的平均特征子集降低比例結(jié)果。由結(jié)果可知，LRGOAFS-KNN算法在6個(gè)數(shù)據(jù)集上的平均分類準(zhǔn)確率是占優(yōu)于LRGOAFS-SVM算法的，有一個(gè)數(shù)據(jù)集在這項(xiàng)指標(biāo)上幾乎接近。此外，LRGOAFS-KNN算法在7個(gè)數(shù)據(jù)集上的平均特征子集降低比例是占優(yōu)于LRGOAFS-SVM算法的，LRGOAFS-SVM算法則有3個(gè)數(shù)據(jù)集。同時(shí)，結(jié)合兩種指標(biāo)的結(jié)果可知，LRGOAFS-KNN算法總共在6個(gè)數(shù)據(jù)集上同步實(shí)現(xiàn)了更高的分類準(zhǔn)確率和更高的平均特征子集降低比例，說明在近選10組數(shù)據(jù)集的測試上，LRGOAFS-KNN算法的性能略優(yōu)于LRGOAFS-SVM算法。

圖10 KNN與SVM分類器間的比較

為了測試算法跳出局部最優(yōu)的能力，利用一個(gè)多峰值基準(zhǔn)函數(shù)Griewank進(jìn)行尋優(yōu)測試，函數(shù)表示如式(27)所示，函數(shù)的搜索區(qū)間為[-600,600]，函數(shù)的理論極值為0。Griewank函數(shù)在整個(gè)搜索區(qū)間內(nèi)存在多個(gè)極值點(diǎn)，因此可以測試算法是否具有跳離局部最優(yōu)解的能力。依然選取前文灰狼優(yōu)化算法BGWO[17]、蚱蜢優(yōu)化算法BGOA[18]和改進(jìn)蚱蜢優(yōu)化算法IGOA[19]進(jìn)行性能對比。結(jié)果如圖11所示。首先，從尋優(yōu)精度上看，在400次迭代過程中，LRGOA算法明顯比另外3個(gè)算法可以得到更接近于理論極值點(diǎn)的解，說明其尋優(yōu)精度更高。同時(shí)，曲線趨勢上看，LRGOA算法具有明顯的下墜趨勢，而另外3種算法走勢更平緩，說明尋優(yōu)精度已經(jīng)無法進(jìn)一步提高。尤其在100次迭代至150次迭代中，LRGOA算法在某處停留后，有一個(gè)加快下墜的趨勢，此處趨勢可解釋為：LRGOA在得到某局部最優(yōu)解后，仍然可以跳離局部極值，進(jìn)一步擴(kuò)展到其他搜索空間得到更優(yōu)解

(27)

圖11 算法的尋優(yōu)曲線

5 結(jié)束語

為了降維數(shù)據(jù)特征維度，提高數(shù)據(jù)分類準(zhǔn)確率，提出了一種基于改進(jìn)蚱蜢優(yōu)化算法的特征選擇算法。首先，利用融合完全隨機(jī)性的混沌映射機(jī)制優(yōu)化了蚱蜢初始種群，利用學(xué)習(xí)自動(dòng)機(jī)對蚱蜢位置更新的調(diào)整系數(shù)進(jìn)行改進(jìn)，均衡全局搜索與局部開發(fā)；引入折射對立學(xué)習(xí)擴(kuò)展搜索區(qū)域，避免算法過早陷入局部最優(yōu)解，實(shí)現(xiàn)了改進(jìn)蚱蜢優(yōu)化算法。然后，將改進(jìn)蚱蜢優(yōu)化算法應(yīng)用于數(shù)據(jù)集的特征選擇求解，通過10種數(shù)據(jù)集測試驗(yàn)證該算法不僅降低特征維度，還可以提高數(shù)據(jù)分類準(zhǔn)確率，且具有更好的穩(wěn)定性。后續(xù)研究中，如何實(shí)現(xiàn)針對更高特征維度的特征選擇以及如何實(shí)現(xiàn)蚱蜢優(yōu)化算法的進(jìn)一步優(yōu)化是下一步的主要研究內(nèi)容。