基于黑寡婦算法的特征選擇方法研究

李郅琴，杜建強(qiáng)，聶 斌，熊旺平，徐國良，羅計(jì)根，李冰濤

1.江西中醫(yī)藥大學(xué) 計(jì)算機(jī)學(xué)院，南昌 330004

2.江西中醫(yī)藥大學(xué) 藥學(xué)院，南昌 330004

特征選擇本質(zhì)上是組合優(yōu)化問題，一般在數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)中作為數(shù)據(jù)預(yù)處理過程。通過特征選擇去除無關(guān)特征和冗余特征，可以解決維數(shù)災(zāi)難問題，降低問題的復(fù)雜度，提高學(xué)習(xí)算法的預(yù)測(cè)精度、魯棒性和可解釋性[1]?，F(xiàn)如今，隨著研究問題復(fù)雜度的增加，基于研究問題收集的數(shù)據(jù)集的維度也越來越高。很多特征是無關(guān)或冗余的，它們的存在對(duì)數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等后續(xù)任務(wù)產(chǎn)生消極影響，如降低預(yù)測(cè)精度，增加結(jié)果的復(fù)雜性和不可理解性。因此，在數(shù)據(jù)挖掘之前，使用特征選擇對(duì)數(shù)據(jù)集降維。

黑寡婦算法（black widow optimization algorithm，BWO）[2]是Hayyolalam 等人2020 年提出的一種元啟發(fā)式算法，最初用于解決工程優(yōu)化問題，具有收斂速度快、適應(yīng)度值優(yōu)化等方面的諸多優(yōu)勢(shì)。自黑寡婦算法提出短短不到一年時(shí)間，已有多篇相關(guān)論文發(fā)表，涉及多個(gè)領(lǐng)域；如Houssein 等[3]基于黑寡婦算法提出一種新的多層閾值圖像分割算法，并將該方法與六種知名的元啟發(fā)式算法進(jìn)行比較，灰狼優(yōu)化算法（gray wolf optimization，GWO）、飛蛾火焰優(yōu)化算法（moth flame optimization，MFO）、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）、正弦余弦算法（sine-cosine algorithm，SCA）、耳光群算法（slap swarm algorithm，SSA）、均衡優(yōu)化算法（equilibrium optimization，EO），實(shí)驗(yàn)結(jié)果表明，該方法在適應(yīng)度值和性能指標(biāo)上優(yōu)于其他方法，取得了高效可靠的結(jié)果，被認(rèn)為是最有前途的多級(jí)圖像分割方法；Katooli等[4]和Tightiz等[5]將黑寡婦算法應(yīng)用在自適應(yīng)神經(jīng)模糊推理系統(tǒng)（adaptive neuro-fuzzy inference system，ANFIS）的訓(xùn)練過程中，提高了ANFIS的故障檢測(cè)能力、魯棒性和分類精度；Micev 等[6]提出自適應(yīng)黑寡婦優(yōu)化算法（adaptive black widow optimization algorithm，ABWO）取代提取發(fā)電機(jī)參數(shù)的標(biāo)準(zhǔn)圖解方法，實(shí)驗(yàn)表明該方法的歸一化誤差平方和（normalized sum of squared errors，NSSE）最小，并且在同步發(fā)電機(jī)上驗(yàn)證了優(yōu)化方法的適用性和準(zhǔn)確性；Premkumar 等[7]采用黑寡婦算法對(duì)風(fēng)力機(jī)仿真器的比例-積分（proportionalintegral，PI）控制器進(jìn)行優(yōu)化，通過仿真結(jié)果和硬件結(jié)果的吻合性驗(yàn)證了該方法的有效性。黑寡婦算法是有效果、有潛力的元啟發(fā)式方法，可以預(yù)見它將來會(huì)在更多領(lǐng)域中發(fā)光發(fā)熱，如特征選擇。

本文的目標(biāo)是解決黑寡婦算法不能進(jìn)行特征選擇的問題。本文的貢獻(xiàn)有兩點(diǎn)：第一，提出五種優(yōu)化策略，包括二進(jìn)制策略、“或門”策略、種群限制策略、快速生殖策略以及適應(yīng)度優(yōu)先策略，對(duì)黑寡婦算法進(jìn)行改進(jìn)；第二，將黑寡婦算法推廣到特征選擇問題，提出兩種新的特征選擇方法。前三種優(yōu)化策略解決黑寡婦算法不能進(jìn)行特征選擇的問題，提出黑寡婦特征選擇算法（black widow optimization feature selection algorithm，BWOFS）；綜合五種優(yōu)化策略提升算法性能，提出生殖調(diào)控黑寡婦特征選擇算法（procreation controlled black widow optimization feature selection algorithm，PCBWOFS）。

1 相關(guān)工作

為解決特征選擇問題，多年來，研究者們進(jìn)行各種嘗試，提出一系列特征選擇方法?；谔卣鬟x擇和學(xué)習(xí)算法的不同結(jié)合方式，可將特征選擇方法分為過濾式（Filter）、封裝式（Wrapper）、嵌入式（Embedded）以及集成式（Ensemble）四種類型。Filter是最早提出的一類特征選擇方法[8-9]，它和學(xué)習(xí)算法相互獨(dú)立，學(xué)習(xí)算法的效果不影響特征子集的生成，一般基于評(píng)價(jià)準(zhǔn)則對(duì)特征排序來選擇特征，包括對(duì)稱不確定性SU、MIC[10]、mRMR[11]、馬爾科夫毯等準(zhǔn)則。Wrapper 將選用的學(xué)習(xí)算法封裝成黑盒，根據(jù)它在特征子集上的預(yù)測(cè)性能評(píng)價(jià)特征子集，并結(jié)合搜索策略獲取最優(yōu)子集，搜索策略有完全搜索、序列前向搜索（sequential forward selection，SFS）、序列后向搜索（sequential backward selection，SBS）、序列前向浮動(dòng)搜索（sequential forward floating selection，SFFS）、序列后向浮動(dòng)搜索（sequential backward floating selection，SBFS）[12]，以及各種元啟發(fā)式方法，如GA、PSO。一般而言，Wrapper比Filter效果更好，因?yàn)榭紤]了特征子集和學(xué)習(xí)算法的關(guān)系，但Wrapper時(shí)間復(fù)雜度比Filter 高。Embedded 取決于學(xué)習(xí)算法本身的特性，有些學(xué)習(xí)算法天然具有特征選擇的功能，例如決策樹、Lasso等。Ensemble通過引入集成思想，得到比單個(gè)特征選擇方法更好的性能。盡管特征選擇問題取得了一定的進(jìn)展，但也需要根據(jù)不同原理，探索有潛力的特征選擇方法，以解決不同的問題，為相關(guān)研究人員提供更多選擇的可能。

特征選擇使用某種評(píng)價(jià)準(zhǔn)則從原始特征空間中選擇特征子集[13-16]。很明顯，特征選擇問題是一個(gè)NP-hard問題[17]，評(píng)估所有特征子集時(shí)間復(fù)雜度為O( )2n[18]，這只能在低維搜索空間中實(shí)現(xiàn)完全搜索，高維空間中無法實(shí)現(xiàn)，因此高效的搜索策略是有效求解特征選擇問題的關(guān)鍵。啟發(fā)式的搜索策略的時(shí)間復(fù)雜度優(yōu)于完全搜索、有序列前向搜索SFS、序列后向搜索SBS、序列前向浮動(dòng)搜索SFFS、序列后向浮動(dòng)搜索SBFS、雙向搜索等。啟發(fā)式的搜索策略的時(shí)間復(fù)雜度的優(yōu)勢(shì)是以降低學(xué)習(xí)算法的預(yù)測(cè)精度為代價(jià)，近年來，元啟發(fā)式搜索由于其可接受的時(shí)間復(fù)雜度、較好的預(yù)測(cè)精度，在特征選擇領(lǐng)域應(yīng)用廣泛。傳統(tǒng)的元啟發(fā)式搜索方法有遺傳算法、粒子群等，它們?cè)谟糜谔卣鬟x擇時(shí)效果良好，一些較新的元啟發(fā)式特征選擇方法，包括Emary等[19]提出的二元蟻獅優(yōu)化器（binary ant lion optimizer，BALO），Zawbaa等[20]提出的花授粉算法（flower pollination algorithm，F(xiàn)PA），Mafarja 等[21]基于鯨魚優(yōu)化算法（WOA）提出的兩個(gè)二進(jìn)制變體算法，Ghaemi等[22]提出的森林優(yōu)化特征選擇算法（feature selection using forest optimization algorithm，F(xiàn)SFOA）。黑寡婦算法（BWO）[2]是受黑寡婦蜘蛛獨(dú)特的交配行為啟發(fā)而提出的，較于其他元啟發(fā)式方法而言，具有更強(qiáng)大的全局搜索能力，可避免局部最優(yōu)，且收斂速度快。若待求解的優(yōu)化問題具有多個(gè)局部最優(yōu)解，黑寡婦算法會(huì)是好的選擇，但原生的黑寡婦算法并不能直接進(jìn)行特征選擇。

因此，本文針對(duì)黑寡婦算法不能進(jìn)行特征選擇的問題，設(shè)計(jì)五種優(yōu)化策略改進(jìn)黑寡婦算法，提出黑寡婦特征選擇算法（BWOFS）和生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS），兩種新方法都能提高學(xué)習(xí)算法的預(yù)測(cè)精度。

2 黑寡婦算法概述

黑寡婦算法（BWO）[2]是受黑寡婦蜘蛛獨(dú)特的交配行為啟發(fā)而提出的，該算法模擬了黑寡婦蜘蛛的生命周期，在51 個(gè)基準(zhǔn)函數(shù)以及3 個(gè)具體工程問題上對(duì)BWO進(jìn)行有效性驗(yàn)證，取得了良好的結(jié)果。

BWO的每一個(gè)解（潛在解決方案）是一只黑寡婦蜘蛛，黑寡婦蜘蛛的長度等于特征的維度。BWO 包括初始化種群、生殖、同類相食、突變、更新種群等5個(gè)階段，除了初始種群階段，其他4個(gè)階段需迭代至滿足結(jié)束條件，返回適應(yīng)度最佳的黑寡婦。

2.1 初始化種群

BWO 算法中，待求解問題的一個(gè)解是一只黑寡婦蜘蛛，可以將黑寡婦蜘蛛視為一個(gè)一維數(shù)組：

其中，Nvar是特征的維度，初始化時(shí)，每個(gè)特征值都是隨機(jī)的浮點(diǎn)數(shù)。每只黑寡婦都有適應(yīng)度，使用某個(gè)適應(yīng)度函數(shù)計(jì)算黑寡婦的適應(yīng)度：

初始化種群時(shí)，需要生成Npop（種群大小）只黑寡婦，得到一個(gè)Npop×Nvar的黑寡婦矩陣。Npop需要預(yù)先定義，常用的有30、50等。

2.2 生殖

生殖階段是全局搜索階段。首先，根據(jù)適應(yīng)度大小對(duì)種群排序，基于生殖率（procreating rate，PP）計(jì)算種群中參與生殖的黑寡婦，然后從中隨機(jī)選擇一對(duì)父母（雌雄黑寡婦）進(jìn)行交配繁殖。在自然界中，每對(duì)黑寡婦都在自己的蜘蛛網(wǎng)上進(jìn)行繁殖，與其他的黑寡婦是分開的，每次大約生成1 000 枚卵[2]，但只有適應(yīng)度較高的小蜘蛛能存活下來。在黑寡婦算法中，每對(duì)父母借助α數(shù)組模擬生殖過程：

其中，W1和W2是父母，child1和child2是后代。這個(gè)過程要重復(fù)Nvar/2 次。

2.3 同類相食

同類相食指的是適應(yīng)度高的蜘蛛吃掉適應(yīng)度低的蜘蛛。黑寡婦蜘蛛的同類相食分為性同類相食、兄弟姐妹同類相食和子食母同類相食三種。性同類相食是指雌黑寡婦會(huì)在交配時(shí)或交配后吃掉雄黑寡婦，可以根據(jù)適應(yīng)度分辨雌雄，適應(yīng)度高的為雌性，適應(yīng)度低的為雄性；兄弟姐妹同類相食發(fā)生在母蛛網(wǎng)上，幼蛛孵化后會(huì)在母蛛網(wǎng)上生活一周左右，期間會(huì)發(fā)生兄弟姐妹同類相食；子食母同類相食是指某些情況下會(huì)發(fā)生小蜘蛛吃掉母蛛的事件。黑寡婦算法中，模擬了性同類相食和兄弟姐妹同類相食，子食母同類相食暫未涉及。通過摧毀父親實(shí)現(xiàn)性同類相食，根據(jù)同類相食率（cannibalism rate，CR）摧毀一部分孩子達(dá)到兄弟姐妹同類相食的目的。使用適應(yīng)度值確定幼蛛的強(qiáng)弱。

2.4 突變

突變階段是局部搜索階段。黑寡婦算法在這一階段根據(jù)突變率（mutation rate，PM）隨機(jī)選擇多個(gè)黑寡婦，每個(gè)黑寡婦隨機(jī)交換數(shù)組中的兩個(gè)特征值。

2.5 更新種群

一次迭代后，將同類相食階段保留下來的黑寡婦以及突變階段得到的黑寡婦作為下一次迭代的初始種群。

2.6 停止條件

可以考慮三種停止條件：（1）提前設(shè)置最大迭代次數(shù)。（2）最佳黑寡婦不再發(fā)生變化。（3）達(dá)到預(yù)設(shè)的精度水平。

黑寡婦算法偽代碼如算法1所示。

算法1 黑寡婦算法（BWO）

3 模型構(gòu)建

為將黑寡婦算法推廣到特征選擇問題以及提升算法性能，提出二進(jìn)制策略、“或門”策略、種群限制策略、快速生殖策略以及適應(yīng)度優(yōu)先策略對(duì)黑寡婦算法進(jìn)行改進(jìn)?；谶@些優(yōu)化策略，提出兩種新的特征選擇方法：黑寡婦特征選擇算法（BWOFS）和生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。

3.1 優(yōu)化策略

3.1.1 二進(jìn)制策略

傳統(tǒng)的黑寡婦算法的目標(biāo)是在連續(xù)搜索空間中尋找最優(yōu)解，但特征選擇是在離散的二進(jìn)制空間中搜索最優(yōu)解。所謂二進(jìn)制策略是指引入二進(jìn)制編碼，隨機(jī)使用“0”或“1”初始化黑寡婦的每個(gè)特征，“0”表示特征被選擇，“1”代表特征未被選擇，因此，特征選擇問題中每只黑寡婦都是一個(gè)特征子集：

其中，Nvar是特征維度，每個(gè)特征值都是0或1。圖1是特征選擇問題中黑寡婦的一個(gè)示例。

圖1 特征選擇問題中的黑寡婦Fig.1 Black widows in feature selection problems

3.1.2 “或門”策略

特征選擇時(shí)，參與計(jì)算的黑寡婦和α是0，1 數(shù)組，因此生殖方式有所變化，新的生殖方式稱為“或門”策略：

其中，W1和W2是父母，child1和child2是后代，×代表對(duì)應(yīng)位置相乘，||代表對(duì)應(yīng)位置做或運(yùn)算，例如[0，1，1，0]||[1，1，0，0]=[1，1，1，0]，這個(gè)過程要重復(fù)Nvar/2 次。算法的生殖過程是在搜索空間進(jìn)行全局搜索。

3.1.3 種群限制策略

種群限制策略根據(jù)適應(yīng)度對(duì)同類相食階段保留下來的黑寡婦進(jìn)行排序，將超過Npop（種群大小）的適應(yīng)度低的黑寡婦刪除。首先，黑寡婦算法種群過快增長以致算法較難收斂；其次，幼蛛孵化后會(huì)在母蛛網(wǎng)上生活一周左右，期間會(huì)發(fā)生兄弟姐妹同類相食，之后會(huì)被風(fēng)帶到其他的地方開始生活，許多幼蛛由于資源爭(zhēng)奪、氣候、天敵等原因并不能平安長大；此外，有許多進(jìn)化算法都有種群限制的過程，如森林優(yōu)化算法（forest optimization algorithm，F(xiàn)OA）[23-24]。因此，設(shè)計(jì)種群限制策略，讓黑寡婦種群數(shù)量保持在一個(gè)較為穩(wěn)定的范圍內(nèi)。種群限制策略可以防止黑寡婦種群的無限擴(kuò)展，減小算法的時(shí)間復(fù)雜度，加快算法的收斂速度。

3.1.4 快速生殖策略

每次迭代時(shí)，生殖階段控制一對(duì)蜘蛛只參與一次生殖，這便是快速生殖策略。算法1步驟5～11是實(shí)現(xiàn)生殖和同類相食的功能，容易發(fā)現(xiàn)步驟6會(huì)選擇到重復(fù)的父母進(jìn)行生殖。首先，這將導(dǎo)致重復(fù)的母親保留在種群當(dāng)中，這些適應(yīng)度較高且相同的蜘蛛將被選中參與下一次繁殖，不利于全局搜索時(shí)產(chǎn)生多樣化的孩子。其次，不符合自然界黑寡婦的繁殖規(guī)律，一對(duì)雌雄黑寡婦在單獨(dú)的網(wǎng)上進(jìn)行生殖，因?yàn)榈谝粋€(gè)進(jìn)入網(wǎng)絡(luò)的雄性通過網(wǎng)絡(luò)縮減降低了雌性網(wǎng)絡(luò)對(duì)競(jìng)爭(zhēng)對(duì)手的吸引力[25]。最后，父親（雄黑寡婦）在繁殖時(shí)或繁殖后會(huì)被母親（雌黑寡婦）吃掉，母親也可能被孩子吃掉，所以父親只能參與一次生殖，母親也一般參與一次生殖（如果母親沒有被吃掉，那么在下一次迭代時(shí)能再次生殖）?？焖偕巢呗圆粌H能解決以上問題，還意味著算法每次迭代時(shí)從nr對(duì)黑寡婦生殖產(chǎn)生nr×Nvar個(gè)孩子，變成nr/2 對(duì)黑寡婦進(jìn)行生殖產(chǎn)生nr/2×Nvar個(gè)孩子，大大縮短了時(shí)間消耗，因此稱為快速生殖策略。

3.1.5 適應(yīng)度優(yōu)先策略

適應(yīng)度優(yōu)先策略的思想是當(dāng)孩子具有更好的適應(yīng)度時(shí)，對(duì)應(yīng)的母親將會(huì)被取代。采用適應(yīng)度優(yōu)先策略能夠避免耗費(fèi)計(jì)算資源搜索低適應(yīng)度的空間。該策略類似黑寡婦的子食母同類相食過程，自然界中，母親在生殖后有幾率被孩子吃掉。

3.2 黑寡婦特征選擇算法

本文首次嘗試將黑寡婦算法調(diào)整推廣到用于特征選擇的離散搜索空間問題，綜合二進(jìn)制策略、“或門”策略和種群限制策略，提出黑寡婦特征選擇算法（BWOFS）。

假設(shè)原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目標(biāo)特征Y=(y1,y2,…,yM)T，初始種群Npop，生殖率PP，同類相食率CR，突變率PM，BWOFS 模型具體構(gòu)建流程如下：

步驟1 二進(jìn)制策略初始化黑寡婦種群：二進(jìn)制策略初始化黑寡婦蜘蛛，生成含有Npop只蜘蛛的黑寡婦種群pop，每只黑寡婦都是一個(gè)特征子集，為每只黑寡婦計(jì)算適應(yīng)度，若是分類任務(wù)，適應(yīng)度函數(shù)可以選擇KNN、決策樹、SVM 等，適應(yīng)度值可以是分類準(zhǔn)確率等；對(duì)于回歸任務(wù)，適應(yīng)度函數(shù)可選PLS、Lasso 等回歸方法，適應(yīng)度值可以是RMSE、R2等。經(jīng)過初始化種群階段，生成Npop（種群大?。┲缓诠褘D，得到一個(gè)Npop×Nvar的黑寡婦矩陣。Npop需預(yù)先定義，可選30、50等。

步驟2“或門”策略生殖：首先根據(jù)適應(yīng)度大小對(duì)種群排序，基于生殖率PP計(jì)算種群中參與生殖的黑寡婦，然后從中隨機(jī)選擇一對(duì)父母（雌雄黑寡婦），使用“或門”策略進(jìn)行交配繁殖生成Nvar個(gè)孩子并計(jì)算適應(yīng)度。

步驟3 同類相食：首先摧毀步驟2 中的父親，然后根據(jù)適應(yīng)度值對(duì)步驟2中的Nvar個(gè)孩子排序，基于同類相食率CR，摧毀適應(yīng)度低的孩子，剩下的黑寡婦保存到種群pop2中。

步驟4 種群限制策略：種群pop2根據(jù)適應(yīng)度排序，執(zhí)行種群限制策略將超過Npop（種群大?。┑倪m應(yīng)度低的黑寡婦刪除。

步驟5 突變：每個(gè)隨機(jī)被選擇進(jìn)行突變的黑寡婦隨機(jī)交換0，1 數(shù)組中的兩個(gè)特征值，使用突變率PM 確定需要突變的黑寡婦的數(shù)量；

步驟6 更新種群：種群pop 更新為步驟4 保留下來的黑寡婦以及步驟5得到的黑寡婦。

步驟7 返回最優(yōu)特征子集：循環(huán)步驟2～步驟6直到停止條件，返回種群pop 中適應(yīng)度最好的最佳黑寡婦，得到最優(yōu)特征子集Xbest。

該算法最終輸出的最優(yōu)特征子集是適應(yīng)度最高的黑寡婦，黑寡婦特征選擇算法（BWOFS）的偽代碼如算法2所示。

算法2 黑寡婦特征選擇算法（BWOFS）

3.3 生殖調(diào)控的黑寡婦特征選擇算法

綜合二進(jìn)制策略、“或門”策略、種群限制策略、快速生殖策略以及適應(yīng)度優(yōu)先策略，提出生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。

假設(shè)原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目標(biāo)特征Y=(y1,y2,…,yM)T，初始種群Npop，生殖率PP，同類相食率CR，突變率PM，PCBWOFS 模型具體構(gòu)建流程如下：

步驟1 二進(jìn)制策略初始化黑寡婦種群：使用二進(jìn)制策略初始化黑寡婦，產(chǎn)生含有Npop只黑寡婦種群pop，每只黑寡婦都是一個(gè)特征子集，為每只黑寡婦計(jì)算適應(yīng)度。

步驟2 快速生殖策略和“或門”策略進(jìn)行生殖：首先根據(jù)適應(yīng)度大小對(duì)種群排序，基于生殖率PP 計(jì)算種群中參與生殖的黑寡婦，然后執(zhí)行快速生殖策略不重復(fù)的隨機(jī)選擇一對(duì)父母，使用“或門”策略和快速生殖策略進(jìn)行交配繁殖生成Nvar個(gè)孩子，并計(jì)算適應(yīng)度。

步驟3 適應(yīng)度優(yōu)先策略的同類相食：首先摧毀步驟2中的父親，然后根據(jù)適應(yīng)度值對(duì)步驟2中的Nvar個(gè)孩子排序，基于同類相食率CR，摧毀適應(yīng)度低的孩子，根據(jù)適應(yīng)度優(yōu)先策略若孩子出現(xiàn)比母親更好的適應(yīng)度，摧毀步驟2中的母親，其余的黑寡婦保存到種群pop2中。

步驟4 種群限制策略：種群pop2根據(jù)適應(yīng)度排序，執(zhí)行種群限制策略，將超過Npop（種群大?。┑倪m應(yīng)度低的黑寡婦刪除。

步驟5 突變：每個(gè)隨機(jī)被選擇進(jìn)行突變的黑寡婦隨機(jī)交換0，1 數(shù)組中的兩個(gè)特征值，使用突變率PM 確定需要突變的黑寡婦的數(shù)量。

步驟6 更新種群：種群pop 更新為步驟4 保留下來的黑寡婦以及步驟5得到的黑寡婦。

步驟7 返回最優(yōu)特征子集：循環(huán)步驟2～步驟6直到停止條件，返回種群pop 中適應(yīng)度最好的最佳黑寡婦，得到最優(yōu)特征子集Xbest。

PCBWOFS算法的偽代碼如算法3所示。

算法3 生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）

PCBWOFS 可以看作是BWOFS 的改進(jìn)算法。PCBWOFS 在BWOFS 的基礎(chǔ)上，增加快速生殖策略和適應(yīng)度優(yōu)先策略。對(duì)比算法2 步驟7～13（BWOFS 偽代碼）和算法3 步驟7～16（PCBWOFS 偽代碼）發(fā)現(xiàn)兩個(gè)算法的不同之處，每次迭代時(shí)，BWOFS 有nr對(duì)黑寡婦進(jìn)行生殖，可以產(chǎn)生nr×Nvar個(gè)孩子，而PCBWOFS 只有nr/2 對(duì)黑寡婦進(jìn)行生殖，產(chǎn)生nr/2×Nvar個(gè)孩子。因此，BWOFS 較PCBWOFS 的明顯優(yōu)勢(shì)在于每次迭代時(shí)全局搜索的特征子集的可能性更多，找到最優(yōu)特征子集的可能性大；PCBWOFS 較BWOFS 的優(yōu)勢(shì)是每次迭代的計(jì)算量小，而且適應(yīng)度優(yōu)先策略能降低算法在低適應(yīng)度空間計(jì)算資源的消耗。

4 實(shí)驗(yàn)結(jié)果與討論

4.1 數(shù)據(jù)說明

本文將分別在分類、回歸任務(wù)中驗(yàn)證提出的BWOFS和PCBWOFS。分類任務(wù)的10個(gè)數(shù)據(jù)集來自于UCI，分別是紅酒數(shù)據(jù)集（wine），Ultrasonic Flowmeter Diagnostics數(shù)據(jù)集（有4 個(gè)數(shù)據(jù)集，分別簡(jiǎn)稱為UltrasonicA、UltrasonicB、UltrasonicC和UltrasonicD），SCADI，Breast Cancer Coimbra（簡(jiǎn)稱為BCCoimbra），Breast Cancer Wisconsin（Diagnostic）（簡(jiǎn)稱為BCWisconsin），Connectionist Bench（Sonar，Mines vs. Rocks）（簡(jiǎn)稱為Bench），以及Diabetic Retinopathy Debrecen（簡(jiǎn)稱為Diabetic）。由于獲取的原始數(shù)據(jù)有些存在缺失值，需要通過數(shù)據(jù)預(yù)處理得到有效樣本。經(jīng)數(shù)據(jù)預(yù)處理，各分類數(shù)據(jù)集的信息描述見表1。

表1 分類數(shù)據(jù)集的信息描述Table 1 Information description of classification datasets

回歸任務(wù)的7 個(gè)實(shí)驗(yàn)數(shù)據(jù)集分別來自于UCI 數(shù)據(jù)集上的Residential Building Data Set（簡(jiǎn)稱為RBuild）、Student Performance Data Set（有數(shù)學(xué)成績和葡萄牙語成績，分別簡(jiǎn)稱為SPMath和SPPortuguese）、Communities and Crime Data Set（簡(jiǎn)稱為CCrime）、Superconductivity Data Set（簡(jiǎn)稱為SConduct）、Blog Feedback Data Set的訓(xùn)練集（簡(jiǎn)稱為BlogTr），以及Kaggle競(jìng)賽數(shù)據(jù)集House Prices Advanced Regression Techniques（簡(jiǎn)稱為House）、Restaurant Revenue Prediction（簡(jiǎn)稱為Restaurant）。同樣地，對(duì)上述數(shù)據(jù)集進(jìn)行預(yù)處理得到有效樣本。經(jīng)數(shù)據(jù)預(yù)處理，各回歸數(shù)據(jù)集的信息描述見表2。

表2 回歸數(shù)據(jù)集的信息描述Table 2 Information description of regression datasets

4.2 參數(shù)設(shè)置

實(shí)驗(yàn)中涉及到的3 個(gè)最優(yōu)化算法FSFOA、BWOFS和PCBWOFS 的參數(shù)如表3 所示，為了確保實(shí)驗(yàn)的公平性，本文提出的兩個(gè)算法BWOFS 和PCBWOFS 的參數(shù)設(shè)置保持一致。

表3 FSFOA、BWOFS、PCBWOFS的參數(shù)設(shè)置Table 3 Parameters setting of FSFOA，BWOFS and PCBWOFS

4.3 實(shí)驗(yàn)結(jié)果對(duì)比分析

在驗(yàn)證BWOFS、PCBWOFS 的同時(shí)，加入了全集、近似馬爾科夫毯（AMB）、序列前向搜索（SFS）、序列前向浮動(dòng)搜索（SFFS）、森林優(yōu)化特征選擇算法（FSFOA）的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。分類任務(wù)使用KNN(k=3)作為適應(yīng)度函數(shù)，分類準(zhǔn)確率（CA）當(dāng)作適應(yīng)度值，實(shí)驗(yàn)結(jié)果見表4。回歸任務(wù)的適應(yīng)度函數(shù)為PLS，均方根誤差（RMSE）作為適應(yīng)度值，實(shí)驗(yàn)結(jié)果由表5 給出。表4 和表5中加粗顯示的結(jié)果顯示該數(shù)據(jù)集的最佳CA/RMSE或最好的維度縮減率（DR）。本文實(shí)驗(yàn)的硬件配置為Intel?CoreTMi5-3470 CPU@3.20 GHz，8.00 GB 內(nèi)存，使用Python語言編寫算法，IDE為PyCharm 2017.3.2。

由表4、表5 可知，相較其他對(duì)比方法（全集、AMB、SFS、SFFS、FSFOA），BWOFS 和PCBWOFS 各有優(yōu)勢(shì)。BWOFS 的優(yōu)勢(shì)在于全局搜索時(shí)產(chǎn)生的孩子數(shù)量比PCBWOFS 多，尋找最優(yōu)特征子集有優(yōu)勢(shì)，雖然可能在低適應(yīng)度空間耗費(fèi)計(jì)算資源，但還是有比PCBWOFS表現(xiàn)更好的情況出現(xiàn)，如表4 的UltrasonicC 和表5 的SPPortuguese-y3；PCBWOFS 全局搜索時(shí)孩子數(shù)量少但更多地避免了低適應(yīng)度空間計(jì)算資源的浪費(fèi)，表現(xiàn)出較好的結(jié)果，如PCBWOFS 在表4 的UltrasonicD、BCWisconsin、Bench、Diabetic 和表5 的CCrime 中的指標(biāo)（CA/RMSE）都是對(duì)比結(jié)果中唯一最好的。其他對(duì)比方法尤其是FSFOA 也展現(xiàn)了較好的結(jié)果，但本文方法BWOFS和PCBWOFS仍有優(yōu)勢(shì)，如RBuild-y1和RBuildy2 中，BWOFS 和PCBWOFS 選擇的特征子集的RMSE值都低于FSFOA，且PCBWOFS、BWOFS分別在RBuildy1、RBuild-y2中的3個(gè)最優(yōu)化特征選擇方法中展現(xiàn)了最好的RMSE值。

表4 分類數(shù)據(jù)集實(shí)驗(yàn)結(jié)果（10-fold）Table 4 Experimental results of classification datasets（10-fold）

表5 回歸數(shù)據(jù)集實(shí)驗(yàn)結(jié)果（10-fold）Table 5 Experimental results of regression datasets（10-fold）

綜上，兩個(gè)新方法BWOFS、PCBWOFS展現(xiàn)了其搜索優(yōu)勢(shì)，提高了模型精度，降低了特征維度，提高了分類準(zhǔn)確率或減少了均方根誤差。PCBWOFS因生殖調(diào)控，特征子集展現(xiàn)了比BWOFS 更好的分類準(zhǔn)確率以及與BWOFS 相當(dāng)?shù)腞MSE 值?？傮w來看，PCBWOFS 表現(xiàn)更好一些。

另外，對(duì)比維度縮減率，從表4、表5可以看出：BWOFS和PCBWOFS沒有展現(xiàn)過多的優(yōu)勢(shì)，原因在于它們的搜索方向是更高的CA 或更低的RMSE，所以維度縮減率優(yōu)勢(shì)不大。這可以是新的研究方向，在盡可能降低特征維度的情況下尋找最優(yōu)特征子集，尤其是分類問題中，如UltrasonicB和SCADI數(shù)據(jù)集上都出現(xiàn)了相同的分類準(zhǔn)確率卻不同維度縮減率的情況，因此這個(gè)研究方向具有可行性。

4.4 模型迭代過程

本節(jié)探討最優(yōu)化特征選擇算法的迭代過程，將本文提出的兩個(gè)方法BWOFS、PCBWOFS 與FSFOA 在分類和回歸任務(wù)中進(jìn)行比較。

由圖2 不難發(fā)現(xiàn)，與FSFOA 相比，新方法BWOFS和PCBWOFS 可以在更少的迭代次數(shù)下找到最優(yōu)特征子集，圖3 上這一優(yōu)勢(shì)更加明顯。原因在于BWOFS 和PCBWOFS強(qiáng)大的全局搜索能力，每次迭代搜索的解更多；然而FSFOA的局部播種和全局播種策略相對(duì)簡(jiǎn)單，需要更多的迭代次數(shù)尋找最優(yōu)特征子集。此外，從圖2、圖3可以發(fā)現(xiàn)BWOFS和PCBWOFS有相似的收斂次數(shù)和最優(yōu)適應(yīng)度，證明PCBWOFS 對(duì)BWOFS 的改進(jìn)是可接受的。

圖2 分類數(shù)據(jù)集上三種最優(yōu)化特征選擇算法的迭代過程Fig.2 Iterative process of three optimal feature selection algorithms on classification datasets

圖3 回歸數(shù)據(jù)集上三種最優(yōu)化特征選擇算法的迭代過程Fig.3 Iterative process of three optimal feature selection algorithms on regression datasets

4.5 BWOFS和PCBWOFS的時(shí)間比較

對(duì)比本文提出的兩個(gè)特征選擇算法BWOFS 和PCBWOFS 的時(shí)間效率，表6、表7 分別是它們?cè)诜诸?、回歸數(shù)據(jù)集上的時(shí)間比較。相較BWOFS，PCBWOFS時(shí)間消耗小，幾乎只有BWOFS 的一半。因?yàn)锽WOFS每次迭代產(chǎn)生nr×Nvar個(gè)孩子，而PCBWOFS 由于快速生殖策略每次迭代只產(chǎn)生nr/2×Nvar個(gè)孩子，所以計(jì)算量小，時(shí)間消耗少。

表6 BWOFS和PCBWOFS在分類任務(wù)的時(shí)間比較Table 6 Comparison of time between BWOFS and PCBWOFS in classification tasks s

表7 BWOFS和PCBWOFS在回歸任務(wù)的時(shí)間比較Table 7 Comparison of time between BWOFS and PCBWOFS in regression tasks s

5 結(jié)束語

本文提出五種優(yōu)化策略：二進(jìn)制策略、“或門”策略、種群限制策略、快速生殖策略以及適應(yīng)度優(yōu)先策略。使用前三種優(yōu)化策略解決黑寡婦算法不能特征選擇的問題，提出黑寡婦特征選擇算法（BWOFS）；綜合五種優(yōu)化策略提升算法性能，提出生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。實(shí)驗(yàn)證明，將黑寡婦算法推廣到特征選擇問題是明智的，相較其他對(duì)比方法，BWOFS 和PCBWOFS可以找到預(yù)測(cè)精度更高的特征子集，有能力提供有競(jìng)爭(zhēng)力和有前景的結(jié)果。特別地，若只對(duì)比兩個(gè)新算法，發(fā)現(xiàn)PCBWOFS比BWOFS計(jì)算量小，時(shí)間消耗也少，但搜索最優(yōu)特征子集的能力并未下降甚至有所提升。在接下來的研究中，將嘗試使用本文提出的兩個(gè)特征選擇算法解決多目標(biāo)任務(wù)特征選擇問題，在提高預(yù)測(cè)性能的基礎(chǔ)上盡可能減少特征數(shù)量，也即在預(yù)測(cè)性能和特征數(shù)量之間取得平衡。此外，還將嘗試構(gòu)建框架，讓本不適合高維數(shù)據(jù)的黑寡婦特征選擇算法在高維數(shù)據(jù)上發(fā)揮它的優(yōu)勢(shì)。