用于特征選擇的改進二進制蝙蝠算法

李占山， 沈琳睿， 阮 錕， 楊鑫凱,3

(1吉林大學(xué) 軟件學(xué)院， 吉林 長春 130012;2.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 吉林 長春 130012;3.吉林大學(xué) 符號計算與知識工程教育部重點實驗室， 吉林 長春 130012)

0 引 言

現(xiàn)實生活中存在各種各樣的數(shù)據(jù)，如電子交易數(shù)據(jù)、新聞報道數(shù)據(jù)等。這些數(shù)據(jù)通常具有大量的特征，其中許多特征是不相關(guān)的或冗余的。這些不相關(guān)或冗余的特征可能會對機器學(xué)習算法造成負面影響，如增加模型學(xué)習時間、降低模型準確性[1]。特征選擇作為一種常用的數(shù)據(jù)預(yù)處理方法，旨在去除不相關(guān)的、冗余的特征以提高模型的泛化性能，并節(jié)省資源。

根據(jù)子集搜索和評估過程，特征選擇方法可以分為過濾式、包裹式和嵌入式[2]。過濾式方法不依賴于任何學(xué)習算法，而依賴于條件特征和類之間的相關(guān)性。包裹式方法根據(jù)使用分類器的表現(xiàn)，將特征刪除或添加到特征子集中，這個過程會耗費較多資源。通常，包裹式方法比過濾式具有更好的分類性能，得出的特征子集往往更符合分類器的要求。

特征選擇過程中的最優(yōu)特征子集被證明是NP難問題。因此，對于高維數(shù)據(jù)，搜索最優(yōu)特征子集是困難的。對于具有N個特征的數(shù)據(jù)集，其搜索空間隨特征數(shù)呈指數(shù)增長[3]。因此，人們設(shè)計了許多搜索策略來提高特征選擇的效率。由于元啟發(fā)式方法擁有較強的全局搜索能力，在搜索空間中能夠在快速找到接近最優(yōu)的解，許多研究已經(jīng)提出使用元啟發(fā)式方法來解決特征選擇問題[4]。例如，粒子群優(yōu)化算法(PSO)、遺傳算法(GA)、蟻群優(yōu)化算法(ACO)、模擬退化算法(SA)等。

受蝙蝠回聲定位行為的啟發(fā)，Yang X S[5]提出一種新的元啟發(fā)式算法----蝙蝠算法(BA)。該算法具有良好的收斂性和可靠性，Mirjalili S等[6]將BA的搜索策略運用到二進制搜索空間中，提出了二進制蝙蝠算法(BBA)。BBA采用V形傳遞函數(shù)，將蝙蝠個體的速度值映射為位置更新的概率值，從而將連續(xù)搜索空間中的搜索過程映射到二進制搜索空間。同時，BBA保持了BA參數(shù)少、收斂快、魯棒性好的優(yōu)點。

然而，BBA也存在一些問題，在BBA的種群更新過程中，傳遞函數(shù)不能依據(jù)種群的變化情況而調(diào)整。當蝙蝠個體快速移動到當前最優(yōu)解位置后，個體速度趨于0，位置改變的概率趨于0。因此，BBA的二進制轉(zhuǎn)化方案在面臨搜索停滯的局面時，沒有擺脫停滯的能力，不能對當前解空間進一步搜索，并且降低了算法的精度。

為了克服這一問題，文中提出一種改進的二進制蝙蝠算法(ABBA)。利用種群熵評價種群的相似程度，將種群熵計算因子加入傳遞函數(shù)，使傳遞函數(shù)適應(yīng)算法收斂過程，增加在速度為 0 時個體的位置更新概率，使算法具有擺脫停滯的能力。

1 二進制蝙蝠算法(BBA)

二進制蝙蝠算法模擬了蝙蝠狩獵過程，蝙蝠在黑暗中通過回聲定位來搜尋獵物并感知距離，在確定獵物的方向和位置后，通過改變脈沖發(fā)射的頻率和響度進行進一步搜尋。二進制蝙蝠算法利用人工蝙蝠作為搜索代理，每個人工蝙蝠具有位置、速度和頻率。當感知到獵物時就改變其響度與脈沖發(fā)射率，同時向獵物位置靠近。在搜尋獵物的過程中，認為位置最好的蝙蝠總是最靠近獵物的，獵物代表算法所要搜尋的最優(yōu)解。

在BBA中，搜索代理在迭代過程中的頻率與速度更新遵循

Fi=Fmin+(Fmax-Fmin)β,

(1)

vi(t+1)=vi(t)+(xi(t)-Gbest)Fi,

(2)

式中：Fi----個體i的頻率;

β----[0,1]之間的隨機數(shù);

vi(t)----個體i在第t次迭代中的速度;

xi(t)----個體i在第t次迭代中的位置;

Gbest----當前最優(yōu)個體的位置。

在二進制搜索空間中，改變位置需要通過位置向量中幾個位的反轉(zhuǎn)來實現(xiàn)。BBA中使用V形傳遞函數(shù)將搜索代理的速度向量按位轉(zhuǎn)換成位置向量中每一位反轉(zhuǎn)的概率，位置更新公式為：

(3)

(4)

式中：xi(t)----第t次迭代中個體i的位置向量在第k維的值;

rand----[0,1]之間的隨機數(shù)。

V形傳遞函數(shù)圖像如圖 1所示。

圖1 V形傳遞函數(shù)圖像

在個體速度接近0的時候，傳遞函數(shù)值也趨近于0，結(jié)合式(2)可知，在個體與獵物相近時，其位置改變的概率較小。

BBA的隨機游走過程是通過與當前全局最優(yōu)個體的位置向量交叉實現(xiàn)的。這個過程解釋為：用Gbest位置向量中的一些維度與當前個體位置向量中的一些維度做交換。

在人工蝙蝠搜尋到更優(yōu)的解決方案后，改變響度和脈沖頻率。其更新公式為：

Ai(t+1)=αAi(t),

(5)

ri(t+1)=ri(0)[1-exp(-γt)],

(6)

式中：α,γ----[0,1]之間的參數(shù)。

式(5)和(6)表明,隨著迭代次數(shù)的增加，響度將趨近于0，脈沖發(fā)射率將趨近于ri(0)。其中α相當于退火因子。

BBA算法的偽代碼如下：

算法1 二進制蝙蝠算法:

1: 設(shè)置最大迭代次數(shù)tmax, 頻率的上界和下界Fmax和Fmin, 響度和脈沖發(fā)射頻率的遞減因子α和γ, 脈沖發(fā)射率的最終值r(0);

2: 隨機初始化蝙蝠種群的位置X_i (i=1,2,…,n), 速度Vi=0, 頻率Fi, 脈沖發(fā)射率ri和響度Ai

3: while t

4: for i=1;i

5: 用式(1)與式(2)更新當前個體i的頻率和速度

6: 用式(3)和式(4)更新當前個體i的位置

7: if (rand>ri) then

8: 在最佳解決方案中隨機選擇一個解決方案(Gbest)

9: 用Gbest改變位置向量的一些維度

10: end if

11: 利用隨機飛行生成新解

12: if rand

13: 接受新的解決方案

14: 用式(5)和式(6)更新響度Ai和脈沖發(fā)射率ri

15: end if

16: end for

17: 給當前種群個體排序并選擇出Gbest

18:end while

在BBA的收斂過程中，種群中個體逐漸靠近，當個體之間變得相近時，算法的收斂趨于成熟，此時個體進行位置更新的概率較低，出現(xiàn)停滯的現(xiàn)象，在陷入局部最優(yōu)時沒有跳出停滯的能力。針對這個問題，文中提出了改進的二進制蝙蝠算法。

2 改進的二進制蝙蝠算法

對二進制蝙蝠算法的改進分為兩部分：

1)利用種群熵對傳遞函數(shù)進行改進，使得算法在趨于停滯時具有跳出當前局面的可能；

2)對基于種群熵的傳遞函數(shù)進行改進，加快算法收斂。

兩個改進點相互補充，共同作用，提高算法的精度。

2.1 運用種群熵對傳遞函數(shù)的改進

BBA中利用V形傳遞函數(shù)將個體速度映射為位置改變的概率。當個體在當前最優(yōu)解的附近時，個體的速度趨于0，根據(jù)V形傳遞函數(shù)，其位置改變的概率很小，容易陷入停滯的局面。此時，考慮將V形函數(shù)在0及其附近的函數(shù)值增大。而在個體未處于當前最優(yōu)解附近時，盡量小地增加函數(shù)值。因此對函數(shù)值增加的量需要適應(yīng)函數(shù)自變量的變化，在個體速度趨于0時，增加量越大;在個體速度值遠離0時，增加量越小。根據(jù)二進制蝙蝠算法的搜索策略中式(2)，個體與當前最優(yōu)個體位置越靠近，種群間個體的一致程度越高，這個增加量應(yīng)當越大;反之，個體間差別越大，這個增加量應(yīng)當越小。

文中運用種群熵來反映演化過程中個體之間的多樣性和一致性。種群熵是路景等[7]提出的一種反映種群多樣性的量。要達到增加量能夠根據(jù)種群變化進行相應(yīng)調(diào)整的目的，要求種群熵可以反映當前的種群多樣性程度，或者反映將來種群多樣性程度的變化趨勢。

定義：計算出當前第t代種群的平均適應(yīng)度值favg，取當前種群中所有fi

定義第t代種群的熵為

其中，

根據(jù)定義可知，當種群中個體各不相同，即m=N時，種群熵取最大值Emax=logN；當種群中個體均相同，即m=1時，種群熵取最小值Emin=0。

種群熵反映了種群中不同類型個體的分布情況。種群中個體分類越多，分布越均勻，種群熵越大。通過種群熵與種群最大熵的比較，可以衡量出當前種群的多樣性程度。令

顯然，b∈[0,1]且b越大，種群中不同個體數(shù)目越多，即種群的多樣性越大;反之，種群的多樣性越小。

在種群逐漸趨于同一化的過程中，種群熵逐漸減小，而增加量需要增大。故新的傳遞函數(shù)公式為

b----種群熵定義中的種群較優(yōu)個體多樣性量化值。

新的傳遞函數(shù)圖像如圖2所示。

圖2 種群熵改進的傳遞函數(shù)

通過比較新傳遞函數(shù)圖像和原V形傳遞函數(shù)圖像可以看出，新傳遞函數(shù)可以適應(yīng)種群的變化情況，相應(yīng)地調(diào)整位置改變的概率。當b減小時，增加量越大;b增大時，增加量越小。那么，當個體到達當前最優(yōu)個體位置附近時，即使速度值為0，個體仍將獲得一定的概率來改變位置，這樣種群便具有跳出停滯的能力。

2.2 輔助改進

基于種群熵改進的傳遞函數(shù)是種群在趨于一致過程中具有一定阻力，在收斂趨于成熟的過程中不斷有個體改變自身位置，向異于當前最優(yōu)的方向改變，雖然增加了種群多樣性，但在算法演化不足的情況下，會在一定程度上影響算法的收斂速度以及算法精度。因此，文中提出對基于種群熵傳遞函數(shù)改進的輔助改進點。

根據(jù)BBA的改進策略，蝙蝠個體只有在找到優(yōu)于當前最優(yōu)解的位置后才會改變響度與脈沖發(fā)射率。其中響度更新中的α類似于退火因子，響度變化會影響算法的收斂速度。因此，我們考慮改變響度與脈沖發(fā)射率更新的條件。

文中提出的改進的二進制蝙蝠算法(ABBA)的偽代碼如下：

算法2 改進的二進制蝙蝠算法:

1:設(shè)置最大迭代次數(shù)tmax, 頻率的上界和下界Fmax和Fmin, 響度和脈沖發(fā)射頻率的遞減因子α和γ, 脈沖發(fā)射率的最終值r(0);

2:隨機初始化蝙蝠種群的位置Xi(i=1,2,…,n), 速度Vi=0, 頻率Fi, 脈沖發(fā)射率ri和響度Ai

3:while t

4: for i=1;i

5: 用式(1)與式(2)更新當前個體i的頻率和速度

8: if (rand>ri)

then

9: 在最佳解決方案中隨機選擇一個解決方案(Gbest)

10: 用Gbest改變位置向量的一些維度

11: end if

12: 利用隨機飛行生成新解

14: 接受新的解決方案

15: 用式(5)和式(6)更新響度Ai和脈沖發(fā)射率ri

16: end if

17: end for

18: 給當前種群個體排序并選擇出Gbest

19:end while

其中，改進部分用下劃線標出。

3 實驗及其結(jié)果分析

3.1 實驗設(shè)計

為了評估提出算法的性能，將ABBA與7個最近提出的特征選擇算法進行了對比實驗，所用的對比算法均來自已發(fā)表的文獻，具體信息見表1。

表1 最新特征選擇算法的信息

將ABBA與BBA中的公共參數(shù)都設(shè)為相同的值，所有實驗均采用包裹式方法較常用的KNN分類器，在來自UCI機器學(xué)習數(shù)據(jù)庫的22個數(shù)據(jù)集上進行，見表2。

表2 數(shù)據(jù)集的特征數(shù)和實例數(shù)

續(xù)表2

ABBA是通過Python3.7和開放的工具包scikit-learn實現(xiàn)的，實驗均在配置為Intel(R) Core(TM) i7-8550U CPU @1.80 Ghz 2.00 GHz的電腦上進行，實驗結(jié)果均為采用五折交叉驗證方法的25次獨立實驗的平均結(jié)果。

3.2 評價準則

文中將分類準確率(ACC)和降維率(DR)作為算法性能的評價指標，公式為：

(8)

(9)

式中：NCC----正確分類的樣本數(shù)量;

NAS----總樣本數(shù)量;

NSF----選擇特征的數(shù)量;

NAF----所有特征的數(shù)量。

文中還采用適應(yīng)度函數(shù)來評價所選特征子集，適應(yīng)度函數(shù)的計算依賴于KNN分類器。

fitness(x)=α*×ACC+β*×DR，

(10)

式中：α*，β*----參數(shù)。

文中將分類準確率作為主要優(yōu)化目標，取α*=0.99，β*=0.01，使算法在提高分類準確率的同時盡量減小特征子集的長度。

在實驗結(jié)果分析的過程中，采用標準差統(tǒng)計量來反映多次實驗結(jié)果的變化情況，對于M次獨立實驗，統(tǒng)計標準差的計算方法為

(11)

式中：g*i----在第i次運行中的最佳解決方案;

Mean----執(zhí)行M次得到的平均解決方案。

3.3 實驗結(jié)果及分析

實驗數(shù)據(jù)包括ABBA與ABBA_1的對比，以及ABBA與MBAFS，HBBEPSO，PSO(4-2)，MBO，BEPO_V4，SBOA這6個近期提出的特征選擇算法的對比。這些特征選擇算法是被廣泛接受且表現(xiàn)良好的。其中ABBA_1在BBA中只應(yīng)用了基于種群熵改進的傳遞函數(shù)，未加輔助改進。

實驗結(jié)果包括所有算法的分類準確率數(shù)據(jù)表、維度縮減率數(shù)據(jù)表、統(tǒng)計標準差數(shù)據(jù)表和適應(yīng)度收斂圖像。

提出算法與對比算法的分類準確率見表 3。

表3 提出算法與對比算法的分類準確率

續(xù)表3

ABBA_1的分類準確率在18個數(shù)據(jù)集上優(yōu)于BBA，其分類準確率的提高范圍在0.08%～4.20%,在Leukemia，Breastcancer，PenglungEW， Tic-tac-toe這4個數(shù)據(jù)集上低于BBA，因為基于種群熵改進的傳遞函數(shù)在一定程度上增加了種群多樣性，在算法后續(xù)演化不足的情況下，影響算法的收斂。因此，我們加入了輔助改進點?？梢钥吹皆谠黾虞o助改進點之后，ABBA的分類精度相比ABBA_1進一步提高，ABBA在全部22個數(shù)據(jù)集上均優(yōu)于BBA，其提高范圍在0.312 5%～9.005%。加入輔助改進點后的ABBA相比ABBA_1在分類精度上提高0.216 5%～4.800 0%，在ABBA_1低于BBA的4個數(shù)據(jù)集上，加入輔助改進點后分類準確率均有提高。因此，輔助改進點的添加加速算法收斂，改善了因為種群多樣性增加對算法收斂效果產(chǎn)生的影響。

文中提出算法與對比算法的降維率見表4。

表4 提出算法與對比算法的降維率

續(xù)表4

結(jié)合ABBA與6個最新特征選擇算法的分類準確率數(shù)據(jù)來看，ABBA在17個數(shù)據(jù)集上優(yōu)于所有的對比算法，在未取得最優(yōu)的5個數(shù)據(jù)集中，spectew，BreastEW，glass這3個數(shù)據(jù)集上ABBA的分類準確率只低于6個對比算法中的一個。因此，在分類準確率方面，ABBA取得了較好的效果，在對比算法中很有競爭力。

在降維率方面，ABBA相比BBA有所下降，因為在設(shè)計特征子集的評價標準時，分類準確率的占比為0.99，而降維率的占比為0.01 。因此分類準確率是算法主要的優(yōu)化目標，在分類準確率提高的同時降維率降低，是因為算法更趨向于選擇對分類準確率貢獻更高的特征子集，而不是更短的特征子集。ABBA的降維率在6個最新特征選擇算法中不具有明顯優(yōu)勢，但是在大多數(shù)數(shù)據(jù)集上，ABBA處于所有算法的平均水平上，并且在21個數(shù)據(jù)集上，ABBA的降維率并非所有算法中的最低值。

提出算法與對比算法的適應(yīng)度標準差見表5。

表5 提出算法與對比算法的適應(yīng)度標準差

相比于BBA的穩(wěn)定性，ABBA在22個數(shù)據(jù)集上都有提升，其中在Exactly和vehicle兩個數(shù)據(jù)集上提升最為顯著，幾乎在所有的數(shù)據(jù)集上ABBA的統(tǒng)計量標準差相比于BBA都提高了一個數(shù)量級。因此，ABBA的穩(wěn)定性優(yōu)于BBA。結(jié)合6個最新特征選擇算法的統(tǒng)計量標準差數(shù)據(jù)來看，ABBA在7個數(shù)據(jù)集上取得最小值，只在ionosphere，glass，PenglungEW， Sonar這4個數(shù)據(jù)集上相比最小值相差一個數(shù)量級，其余未取得最小值的數(shù)據(jù)集上，ABBA均與最小值相差不大。

綜上所述，ABBA在分類精度上取得了明顯的提高，改善了BBA種群多樣性下降快，易陷入局部最優(yōu)的問題，賦予算法跳出停滯的能力。并且兩個改進相互輔助，共同提高了算法的分類準確率。在最新的6個特征選擇算法中，ABBA在分類準確率、魯棒性、收斂特性方面具有明顯優(yōu)勢。因此，ABBA是一種分類精度高、魯棒性好的特征選擇算法。

4 結(jié) 語

提出改進的二進制蝙蝠算法(ABBA)運用基于種群熵的傳遞函數(shù)改進，以及一個輔助改進點緩解了算法易早熟，陷入局部最優(yōu)的問題?；诜N群熵的傳遞函數(shù)可以適應(yīng)算法收斂過程，在一定程度上增加種群多樣性，并賦予算法克服停滯的能力。針對新的傳遞函數(shù)可能影響算法收斂這一問題，增加了輔助改進，改變了響度和脈沖發(fā)射率更新的條件，加速算法收斂。實驗表明，輔助改進與新傳遞函數(shù)良好結(jié)合，可以共同提高算法的分類精度和魯棒性，并且保證算法擁有較好的收斂性能。在與最新的特征選擇算法的對比中，ABBA在主要優(yōu)化目標上具有明顯優(yōu)勢，是一種有競爭力的特征選擇算法。

下一步研究計劃中考慮使用其他方法代替輔助改進，在不改變原有搜索機制下增加算法的演化能力，加快算法收斂，與傳遞函數(shù)相互輔助，進一步提高算法的分類準確率與降維率。