楊舒云,劉宏志,李海生

(北京工商大學(xué)計(jì)算機(jī)學(xué)院,北京 100048)

1 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái),越來(lái)越多高維數(shù)據(jù)集應(yīng)用于數(shù)據(jù)挖掘中,并伴隨著復(fù)雜噪聲,給機(jī)器學(xué)習(xí)帶來(lái)嚴(yán)峻的維度災(zāi)難問(wèn)題。特征選擇是從原始特征中選擇出最有效特征,以降低數(shù)據(jù)集維度,提高模型性能的過(guò)程,因此近年來(lái)逐漸成為一個(gè)研究熱點(diǎn)。

一般來(lái)說(shuō),特征選擇的算法分為三類:嵌入式(embedded)、過(guò)濾式(filter)和封裝式(wrapper)。在封裝式方法中,使用學(xué)習(xí)算法來(lái)評(píng)估所選的特征子集,窮舉法、順序搜索、全局搜索等方法都可以用來(lái)搜索特征子集。但是在大部分情況下,窮舉法因計(jì)算量太大而無(wú)法應(yīng)用,順序搜索法采用局部搜索可能導(dǎo)致局部最優(yōu),而全局搜索法主要采用隨機(jī)搜索策略來(lái)探索解空間,因此有更大可能搜索到全局最優(yōu)解。近年來(lái),很多元啟發(fā)式方法,如鯨魚(yú)優(yōu)化算法[1]、粒子群優(yōu)化算法[2]等,由于其在全局搜索空間中強(qiáng)大的搜索能力,已經(jīng)在函數(shù)優(yōu)化[3]、參數(shù)優(yōu)化[4]等領(lǐng)域顯示出其有效性。其中,灰狼優(yōu)化算法由于其較強(qiáng)的魯棒性和參數(shù)少等優(yōu)點(diǎn),已經(jīng)被證明了在特征選擇領(lǐng)域的有效性,然而傳統(tǒng)灰狼算法也存在易早熟等問(wèn)題,從而導(dǎo)致次優(yōu)解。

為了提高算法分類精度,一些學(xué)者開(kāi)始對(duì)基本灰狼算法進(jìn)行改進(jìn)。Al-Tashi Q等人[5]提出了一種灰狼算法與粒子群算法結(jié)合的二進(jìn)制版本進(jìn)行特征選擇,經(jīng)對(duì)比實(shí)驗(yàn)表明取得了較高的性能。Attia等人[6]將灰狼優(yōu)化與粗糙集理論結(jié)合,在維度各異的公開(kāi)數(shù)據(jù)集上取得了較好的收斂速度和分類精度。Hu,Jiao等人[7]開(kāi)發(fā)了一種通過(guò)協(xié)方差矩陣自適應(yīng)進(jìn)化策略、征稅飛行機(jī)制和正交學(xué)習(xí)策略增強(qiáng)的 GWO 變體,增強(qiáng)算法的探索性能,在UCI數(shù)據(jù)集上都獲得了優(yōu)越的性能。徐明等[8]提出了基于正弦函數(shù)的非線性過(guò)渡參數(shù)、小孔成像學(xué)習(xí)等多種策略來(lái)提高尋優(yōu)精度,在基準(zhǔn)數(shù)據(jù)集上驗(yàn)證了其有效性。

上述研究從不同角度提高了灰狼算法的尋優(yōu)性能,但勘探與開(kāi)采能力的不平衡問(wèn)題仍然存在,算法求解精度仍有待提高,如Hu,Jiao的GWO變體帶來(lái)了更有效的勘探傾向,但是并未對(duì)算法的開(kāi)采性能進(jìn)行改進(jìn),徐明的非線性參數(shù)過(guò)渡等多種位置更新策略在一定程度上實(shí)現(xiàn)了全局勘探到局部開(kāi)采的良好過(guò)渡,但忽略了種群初始化階段的多樣性。因此繼續(xù)對(duì)其改進(jìn)很有必要,本文提出一種融合蝠鲼旋風(fēng)式螺旋覓食策略的混合灰狼算法(BWSGWO)用于特征選擇,以達(dá)到更高的收斂精度。

2 基本GWO算法

灰狼優(yōu)化算法(Grey Wolf Optimizer,GWO)模擬狼群嚴(yán)格的社會(huì)等級(jí)制度和狩獵行為[9],狼群中適應(yīng)度最好的三匹灰狼依次記為α、β、δ,剩下的灰狼記為ω。其狩獵過(guò)程包括包圍獵物和攻擊獵物,重復(fù)以上步驟,直到達(dá)到終止條件,則停止迭代,獲得最優(yōu)解。

3 改進(jìn)GWO算法

3.1 Tent混沌策略初始化種群

灰狼算法受種群初始狀態(tài)的影響較大,低質(zhì)量的初始種群在很大程度上影響了算法的收斂速度,導(dǎo)致算法的尋優(yōu)效果較差。基本GWO算法采用隨機(jī)方法初始化種群,沒(méi)有任何先驗(yàn)知識(shí),可能會(huì)導(dǎo)致種群分布不均勻,一些ω狼的位置距離最優(yōu)值過(guò)遠(yuǎn),從而容易陷入局部最優(yōu)解。

混沌系統(tǒng)有隨機(jī)性和遍歷性等特點(diǎn),通過(guò)其產(chǎn)生的灰狼群體具備較好的多樣性。其基本思想是通過(guò)映射關(guān)系產(chǎn)生[0,1]之間的混沌序列,再將其逆映射到灰狼個(gè)體的搜索空間。常見(jiàn)的混沌映射有Logistic映射和Tent映射等,單梁等[10]證明 Tent 映射比 Logistic 映射的分布更均勻,因此,本文采取Tent混沌映射的方法初始化種群,有效避免基本GWO算法中隨機(jī)函數(shù)初始化種群造成的局部最優(yōu)風(fēng)險(xiǎn),其數(shù)學(xué)表達(dá)式如下

(1)

式中,μ為混沌參數(shù),不同μ值Tent映射的范圍不同。μ取0.5時(shí),系統(tǒng)呈現(xiàn)短周期狀態(tài),故不可取,本文經(jīng)多次實(shí)驗(yàn)及文獻(xiàn)分析,取最優(yōu)μ值為為0.7,由圖1(a)(b)可以看出,當(dāng)?shù)欢ù螖?shù)時(shí),混沌參數(shù)為0.7的混沌系統(tǒng)會(huì)產(chǎn)生更加均勻的混沌序列。

圖1 Tent混沌映射變化曲線

3.2 蝠鲼旋風(fēng)式螺旋覓食策略

蝠鲼覓食優(yōu)化(MRFO)[11]是 2020年提出的新型智能仿生群體算法。由于傳統(tǒng)灰狼算法在位置更新時(shí)總是跟隨三匹領(lǐng)導(dǎo)狼,導(dǎo)致局部開(kāi)采能力強(qiáng)、全局勘探能力弱,針對(duì)這個(gè)問(wèn)題,本文受MRFO啟發(fā),通過(guò)蝠鲼覓食會(huì)排成螺旋形捕捉高濃度浮游生物,引入新型旋風(fēng)式螺旋覓食策略進(jìn)行群體協(xié)作,其數(shù)學(xué)模型如下

(2)

式中,β為權(quán)重系數(shù),r為[0,1]中的隨機(jī)數(shù),當(dāng)t/T

圖2 二維空間中的旋風(fēng)覓食行為

如圖所示,灰狼個(gè)體不僅跟隨它前面的個(gè)體,而且只沿著螺旋形路徑向獵物移動(dòng),形成長(zhǎng)長(zhǎng)的覓食鏈,從而大幅提高搜索效果。

本文結(jié)合灰狼算法自身優(yōu)勢(shì),根據(jù)迭代次數(shù)的不同在旋風(fēng)式螺旋覓食與傳統(tǒng)覓食之間轉(zhuǎn)換,以實(shí)現(xiàn)廣泛的適應(yīng)性搜索。對(duì)于傳統(tǒng)覓食行為,結(jié)合個(gè)體對(duì)歷史最優(yōu)解的記憶進(jìn)行改進(jìn),為每一匹狼建立歷史倉(cāng)庫(kù),解決了傳統(tǒng)灰狼算法只盲目跟隨領(lǐng)導(dǎo)狼,忽略個(gè)體與自身經(jīng)驗(yàn)交流的問(wèn)題,其位置更新方程定義為

(3)

(4)

式中,w為慣性權(quán)重,X1、X2、X3、X4分別為灰狼個(gè)體向著α、β、δ及自身歷史最優(yōu)解前進(jìn)的步長(zhǎng)和方向,A和C為系數(shù)向量。

3.3 自適應(yīng)精英反向?qū)W習(xí)策略

(5)

式中,k可以取不同的實(shí)數(shù),當(dāng)k=1時(shí)稱其為廣義反向?qū)W習(xí),lbj和ubj分別為第j維搜索空間的邊界。雖然反向?qū)W習(xí)有大于一般的概率優(yōu)更逼近最優(yōu)解,但是并不能保證一定優(yōu)于原解,因此,在反向?qū)W習(xí)后采用貪心策略選擇其中的更優(yōu)解進(jìn)入下一次的迭代,其數(shù)學(xué)模型如下

(6)

同時(shí),為適應(yīng)種群復(fù)雜的非線性變化,加入變異因子Mp進(jìn)行選擇性反向?qū)W習(xí),即隨著迭代次數(shù)的增加,變異概率非線性遞減,前期變異概率大,更有利于全局勘探,后期變異概率小,有利于局部開(kāi)采迅速收斂,其數(shù)學(xué)模型如下:

(7)

式中,Mpmax為最大變異概率,Mpmin為最小變異概率。

4 BWSGWO特征選擇算法組成

4.1 二進(jìn)制離散編碼

特征選擇問(wèn)題本質(zhì)上是要找到一個(gè)合適的0/1串,0表示特征不被選擇,1表示特征被選擇,如圖3所示為一個(gè)包含十個(gè)特征數(shù)據(jù)集的可能解決方案。

圖3 解決方案表示

基本GWO算法在提出之初主要是為了解決解決連續(xù)優(yōu)化問(wèn)題,為了能讓其解決離散空間問(wèn)題,引入二進(jìn)制思想來(lái)重新設(shè)計(jì)算法,使用轉(zhuǎn)換函數(shù)來(lái)實(shí)現(xiàn)連續(xù)搜索空間到二進(jìn)制空間的轉(zhuǎn)換。但是代表性的S型轉(zhuǎn)換函數(shù)sigmoid變化敏感,易于飽和,影響特征選擇的精度,而tanh[13]函數(shù)克服了這一缺點(diǎn)。綜上,本文采用V型函數(shù)tanh進(jìn)行二進(jìn)制轉(zhuǎn)換,其數(shù)學(xué)模型如下

xsi=|tanh(x)|

(8)

(9)

4.2 適應(yīng)度函數(shù)設(shè)計(jì)

特征選擇問(wèn)題被認(rèn)為是一個(gè)多目標(biāo)問(wèn)題,因?yàn)樗仨殞?shí)現(xiàn)以下兩點(diǎn):最大化給定分類器的分類精度,最大限度地減少所選特征的數(shù)量。基于上述,本文將用于評(píng)估解決方案的適應(yīng)度函數(shù)設(shè)計(jì)為實(shí)現(xiàn)兩個(gè)目標(biāo)之間的平衡,即

(10)

式中,error表示分類錯(cuò)誤率,用KNN采用十折交叉驗(yàn)證法計(jì)算,F代表所選特征子集長(zhǎng)度,dim代表原始數(shù)據(jù)集中所有特征,α和β是對(duì)應(yīng)于分類精度和所選特征子集長(zhǎng)度的權(quán)重參數(shù),α∈[0,1]且β=1-α,本文算法意在保證較高精度的前提下減少特征數(shù)目,因此將α和β分別設(shè)置為 0.99 與 0.01[13]。

4.3 算法流程

綜上所述,本文提出了融合蝠鲼旋風(fēng)式覓食策略的灰狼特征選擇算法,其執(zhí)行步驟如下:

Step1:設(shè)置相關(guān)參數(shù),種群規(guī)模N,最大迭代次數(shù)Tmax,搜索維度為d,搜索范圍[lb,ub];

Step2:根據(jù)3.1節(jié)描述的Tent混沌策略初始化灰狼種群,并計(jì)算其適應(yīng)度值,保存適應(yīng)度最好的前三匹狼記為α、β、δ;

Step3:據(jù)3.2節(jié)描述的策略,由當(dāng)前迭代次數(shù)與總迭代次數(shù)的比值,當(dāng)t≤ 0.7T時(shí),采用蝠鲼旋風(fēng)式螺旋覓食策略進(jìn)行灰狼位置更新,當(dāng)t> 0.7T時(shí),將灰狼等級(jí)捕獵制度與個(gè)體最優(yōu)解記憶策略結(jié)合,進(jìn)行圍捕中的位置更新,以實(shí)現(xiàn)勘探到開(kāi)采的良好過(guò)渡;

Step4:采用自適應(yīng)精英反向?qū)W習(xí)策略,以一定的概率對(duì)當(dāng)前最優(yōu)解求其反向解,并進(jìn)行兩兩評(píng)估,貪婪地選擇較優(yōu)解作為下一代個(gè)體精英個(gè)體;

Step5:重復(fù)上述步驟,若達(dá)到終止條件,則停止迭代,并輸出結(jié)果。

5 仿真分析

5.1 仿真參數(shù)介紹

本文的仿真中,為保證仿真結(jié)果的公平性,各算法基本參數(shù)的選擇相同,種群規(guī)模 N 為 10,最大迭代次數(shù) Tmax為 100,取自參考文獻(xiàn)中的經(jīng)驗(yàn)值[14],其它對(duì)比算法的參數(shù)設(shè)置也與相應(yīng)的參考文獻(xiàn)保持一致。由于元啟發(fā)式算法的特征選擇具有一定的隨機(jī)性,為避免偶然誤差對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生影響,所有算法獨(dú)立運(yùn)行10次取平均值。

5.2 實(shí)驗(yàn)數(shù)據(jù)集介紹

本文從機(jī)器學(xué)習(xí)資料庫(kù)UCI中收集的8個(gè)規(guī)模各異、特征數(shù)目不同的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集進(jìn)行特征選擇,來(lái)驗(yàn)證所提算法的有效性。數(shù)據(jù)集的詳細(xì)信息如表1所示。

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

5.3 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證本文所提策略的有效性,本文將所提算法與經(jīng)典離散粒子群算法、灰狼優(yōu)化算法、鯨魚(yú)優(yōu)化算法作為對(duì)比,在表1的數(shù)據(jù)集上進(jìn)行進(jìn)行10次獨(dú)立重復(fù)實(shí)驗(yàn),比較算法的平均性能指標(biāo)。

5.3.1 分類精度與所選特征數(shù)對(duì)比

表2從運(yùn)行結(jié)果的平均分類精度及平均所選特征數(shù)對(duì)算法進(jìn)行了對(duì)比。其中,加粗字體為所有算法中的最高平均分類精度和最小平均特征數(shù)。分析BWSGWO的實(shí)驗(yàn)結(jié)果可知,在所有的數(shù)據(jù)集中,BWSGWO都展示出了最高的分類精確。同時(shí),在大部分?jǐn)?shù)據(jù)集中,BWSGWO都展示出了較低的特征數(shù),除了在ionosphere、Sonar、WaveformEW數(shù)據(jù)集中,本文所提算法雖然在特征選擇數(shù)目上不是最佳,但與最優(yōu)特征數(shù)差距不大,同時(shí)精度得到了非常顯著的提升。

表2 測(cè)試數(shù)據(jù)集準(zhǔn)確率對(duì)比

5.3.2 適應(yīng)度對(duì)比

表3為四種算法的適應(yīng)度函數(shù)值對(duì)比,其中Avg＿fit、Best＿fit分別為算法在不同數(shù)據(jù)集上的平均適應(yīng)度和最佳適應(yīng)度。由表4可知,除WaveformEW、Lymphography、Exactly數(shù)據(jù)集外都取得了最優(yōu)的最佳適應(yīng)度,盡管在在WaveformEW、Lymphography、Exactly數(shù)據(jù)集中表現(xiàn)不是最優(yōu),但是其上限接近最佳。此外,本文所提算法在8個(gè)數(shù)據(jù)集上都取得了最優(yōu)的平均適應(yīng)度,這在一定程度上表明了所提算法的穩(wěn)定性。

表3 測(cè)試數(shù)據(jù)集適應(yīng)度對(duì)比

5.3.3 收斂性分析

圖4所示為8個(gè)數(shù)據(jù)集上BPSO、BGWO、BWOA、BWSGWO的適應(yīng)度曲線對(duì)比結(jié)果。從圖4中的收斂趨勢(shì)可以看出,隨著算法迭代次數(shù)的增加,各個(gè)算法在不同數(shù)據(jù)集上的適應(yīng)度值均在降低,但相較于BPSO、BGWO、BWOA,本文提出的BWSGWO算法在總迭代次數(shù)相同的情況下,總能搜索到更優(yōu)的解。圖4(c)(e)分別為四種算法在Sonar和HeartEW數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,表明BWSGWO算法在上述兩個(gè)數(shù)據(jù)集上的收斂速度均大幅優(yōu)于其它算法且搜索到的解都優(yōu)于其它算法。圖4(f)為四種算法在Lymphography數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,表明BWSGWO算法在1次迭代后就搜索到了比其它算法更優(yōu)的解,且前8次的迭代中收斂速度都優(yōu)于其它算法,雖然在8-33次的迭代中暫時(shí)陷入局部最優(yōu),但是依然始終優(yōu)于其它算法,且33次迭代之后迅速收斂得到全局最優(yōu)解。圖4(a)(d)(h)分別為四種算法在KrVsKpEW、WaveformEW、Exactly數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,雖然在前期的迭代中表現(xiàn)并不是最優(yōu),但中后期快速收斂,搜索到的解均遠(yuǎn)由于其它算法。

圖4 改進(jìn)算法在8個(gè)數(shù)據(jù)集上的適應(yīng)度曲線

綜上可知,本文所提BWSGWO算法總能搜索到比其它算法都更優(yōu)的解,體現(xiàn)出 BWSGWO算法具有更好的尋優(yōu)性能。

因此,綜合分類準(zhǔn)確率、特征選擇數(shù)量、魯棒性、搜索性能和收斂性能方面對(duì)比四種算法,本文所提BWSGWO特征選擇算法的總體性能優(yōu)于其它四種算法。

5.4 時(shí)間復(fù)雜度分析

雖然特征選擇算法需要取得較高的準(zhǔn)確率,但是也需要較低的時(shí)間復(fù)雜度。在種群規(guī)模為N,優(yōu)化維度為D,最大迭代次數(shù)為Tmax的情況下,基本GWO時(shí)間復(fù)雜度主要為種群初始化部分和灰狼位置更新部分,其時(shí)間復(fù)雜度為O(NDTmax)。

同理,改進(jìn)灰狼的基本流程與基本GWO一樣,此外,引入混沌策略O(shè)(ND),蝠鲼旋風(fēng)式螺旋覓食策略與粒子群策略的新型捕獵行為O(NDTmax),自適應(yīng)精英反向?qū)W習(xí)策略O(shè)(DTmax),因此總的時(shí)間復(fù)雜度與基本GWO算法相比沒(méi)有增加,依然為O(NDTmax),都取決于種群規(guī)模、優(yōu)化問(wèn)題維度與最大迭代次數(shù),因此可判定改進(jìn)算法并未造成時(shí)間復(fù)雜度的增加,但是其性能卻得到了顯著的提升,證明了本文所提算法的有效性。

6 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)灰狼算法易陷入局部最優(yōu)、尋優(yōu)性能差的問(wèn)題,提出了融合蝠鲼旋風(fēng)式覓食策略的灰狼特征選擇算法。創(chuàng)新性地引入蝠鲼旋風(fēng)式螺旋覓食策略及時(shí)調(diào)整灰狼最佳位置,并為種群建立歷史倉(cāng)庫(kù),有效降低了傳統(tǒng)灰狼算法中只跟隨領(lǐng)導(dǎo)狼群進(jìn)行捕獵的盲目性,大幅協(xié)調(diào)了灰狼種群的勘探和開(kāi)采性能。此外,引入Tent混沌映射提高種群多樣性,自適應(yīng)精英反向?qū)W習(xí)策略提升抗局部極值能力。相較于其它經(jīng)典元啟法式算法,具有尋優(yōu)策略良,算法不易早熟等優(yōu)勢(shì)。在8個(gè)規(guī)模各異、特征數(shù)目不同的UCI標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行仿真,仿真結(jié)果表明,與經(jīng)典算法BPSO、BGWO、BWOA對(duì)比,本文提算法能在最大程度提高分類精度的同時(shí),保證較低的特征選擇數(shù),算法性能大大提升。在后續(xù)的研究中,主要考慮尋找更高效的特征表示方式,并進(jìn)一步拓展該算法的應(yīng)用領(lǐng)域。