基于鄰域粗糙集和帝王蝶優(yōu)化的特征選擇算法

孫林，趙婧，徐久成，2，王欣雅

（1.河南師范大學(xué) 計算機與信息工程學(xué)院，河南 新鄉(xiāng) 453007；2.教育人工智能與個性化學(xué)習(xí)河南省重點實驗室（河南師范大學(xué)），河南 新鄉(xiāng) 453007）（?通信作者電子郵箱sunlin@htu.edu.cn）

基于鄰域粗糙集和帝王蝶優(yōu)化的特征選擇算法

孫林1，2*，趙婧1，徐久成1，2，王欣雅1

（1.河南師范大學(xué) 計算機與信息工程學(xué)院，河南 新鄉(xiāng) 453007；2.教育人工智能與個性化學(xué)習(xí)河南省重點實驗室（河南師范大學(xué)），河南 新鄉(xiāng) 453007）（?通信作者電子郵箱sunlin@htu.edu.cn）

針對經(jīng)典的帝王蝶優(yōu)化（MBO）算法不能很好地處理連續(xù)型數(shù)據(jù)，以及粗糙集模型對于大規(guī)模、高維復(fù)雜的數(shù)據(jù)處理能力不足等問題，提出了基于鄰域粗糙集（NRS）和MBO的特征選擇算法。首先，將局部擾動和群體劃分策略與MBO算法結(jié)合，并構(gòu)建傳輸機制以形成一種二進制MBO（BMBO）算法；其次，引入突變算子增強算法的探索能力，設(shè)計了基于突變算子的BMBO（BMBOM）算法；然后，基于NRS的鄰域度構(gòu)造適應(yīng)度函數(shù)，并對初始化的特征子集的適應(yīng)度值進行評估并排序；最后，使用BMBOM算法通過不斷迭代搜索出最優(yōu)特征子集，并設(shè)計了一種元啟發(fā)式特征選擇算法。在基準(zhǔn)函數(shù)上評估BMBOM算法的優(yōu)化性能，并在UCI數(shù)據(jù)集上評價所提出的特征選擇算法的分類能力。實驗結(jié)果表明，在5個基準(zhǔn)函數(shù)上，BMBOM算法的最優(yōu)值、最差值、平均值以及標(biāo)準(zhǔn)差明顯優(yōu)于MBO和粒子群優(yōu)化（PSO）算法；在UCI數(shù)據(jù)集上，與基于粗糙集的優(yōu)化特征選擇算法、結(jié)合粗糙集與優(yōu)化算法的特征選擇算法、結(jié)合NRS與優(yōu)化算法的特征選擇算法、基于二進制灰狼優(yōu)化的特征選擇算法相比，所提特征選擇算法在分類精度、所選特征數(shù)和適應(yīng)度值這3個指標(biāo)上表現(xiàn)良好，能夠選擇特征數(shù)少且分類精度高的最優(yōu)特征子集。

帝王蝶優(yōu)化；特征選擇；鄰域粗糙集；鄰域依賴度；二進制

0 引言

特征選擇是數(shù)據(jù)挖掘與機器學(xué)習(xí)領(lǐng)域中一個必不可少的數(shù)據(jù)預(yù)處理步驟［1-2］。特征選擇一般分為啟發(fā)式和窮舉式搜索兩種策略。當(dāng)使用窮舉式搜索對特征數(shù)非常大的數(shù)據(jù)集進行特征選擇時，將所有特征子集列出是不現(xiàn)實的。為避免這一問題，許多研究者轉(zhuǎn)向研究啟發(fā)式搜索策略，如元啟發(fā)式算法。當(dāng)前，已經(jīng)有許多學(xué)者結(jié)合元啟發(fā)式算法解決特征選擇優(yōu)化問題，例如：Hu等［3］提出了一種二進制灰狼算法并應(yīng)用于特征選擇；Tubishat等［4］基于對立學(xué)習(xí)的樽海鞘群算法設(shè)計了一種局部搜索的特征選擇算法。因而，元啟發(fā)式特征選擇是目前流行的數(shù)據(jù)分類策略。

粗糙集理論是特征選擇的一種有效數(shù)學(xué)工具［5-6］。盡管粗糙集模型具有能夠去除不相關(guān)、冗余的特征，并保留原始特征的特性，但也是一種NP-Hard問題，很難找到最優(yōu)解，而這正好被元啟發(fā)式算法彌補。Zaimoglu等［7］提出了基于粗糙集和拔河優(yōu)化算法的特征選擇策略；Huda等［8］構(gòu)建了基于粒子群優(yōu)化和粗糙集的特征選擇算法；Tawhid等［9］提出了基于粗糙集和二進制鯨魚優(yōu)化的特征選擇算法；Wang等［10］運用量子對蝗蟲優(yōu)化算法進行改進，設(shè)計了基于互信息和粗糙集的動態(tài)種群量子二進制蝗蟲優(yōu)化算法；Abd等［11］考慮到還原集中特征的數(shù)量和分類質(zhì)量，將布谷鳥搜索結(jié)合粗糙集理論來構(gòu)建適應(yīng)度函數(shù)，提出了基于粗糙集的布谷鳥搜索算法。但是，上述基于粗糙集的特征選擇算法僅適用于符號型數(shù)據(jù)，若需要處理連續(xù)型數(shù)據(jù)，則必須進行離散化處理，這將不可避免地丟失一些重要信息［12］。為了解決這個問題，研究人員對粗糙集理論進行擴展研究，提出了鄰域粗糙集（Neighborhood Rough Set， NRS）模型、模糊粗糙集、公差近似模型等［13］。鄰域粗糙集不僅可以處理連續(xù)型數(shù)據(jù)，而且也能處理符號型和數(shù)值型的混合數(shù)據(jù)［14］。Zou等［12］通過引入自適應(yīng)函數(shù)來控制人工魚的視覺和步長，結(jié)合魚群算法和鄰域粗糙集理論構(gòu)建特征選擇算法。基于鄰域粗糙集的特征選擇旨在從鄰域決策系統(tǒng)中獲取最優(yōu)/最小的特征子集［15］。截至目前，將鄰域粗糙集與群智能優(yōu)化算法結(jié)合是數(shù)據(jù)挖掘領(lǐng)域中特征選擇的最重要的研究方向之一。

群智能優(yōu)化算法是受生物群體間的智能協(xié)作過程啟發(fā)而設(shè)計的一類算法，具有實現(xiàn)容易、并行性好、連續(xù)和離散區(qū)間問題適應(yīng)性強等優(yōu)點，已經(jīng)成為當(dāng)前各類優(yōu)化問題尤其是組合問題的求解方法［16］。受美國帝王蝶遷徙行為的啟發(fā)，Wang等［17］提出了帝王蝶優(yōu)化（Monarch Butterfly Optimization， MBO）算法。該算法模擬帝王蝶利用兩個算子進行種群更新的行為，具有計算簡單、參數(shù)較少、收斂迅速、易于程序?qū)崿F(xiàn)等優(yōu)點，于是該算法在許多領(lǐng)域得到了廣泛的應(yīng)用，例如：Dorgham等［18］采用MBO算法尋找最優(yōu)閾值，使用質(zhì)量結(jié)構(gòu)相似指數(shù)矩陣評價分割后的圖像精度，提高圖像分割性能。Soltani等［19］開發(fā)了一種基于MBO算法高效的神經(jīng)網(wǎng)絡(luò)模擬系統(tǒng)。截止到目前，利用MBO算法解決特征選擇優(yōu)化問題的應(yīng)用研究較少。孫林等［20］基于柯西變異的差分自適應(yīng)MBO算法，結(jié)合K近鄰分類器提出了特征選擇算法。但是該算法仍存在一些問題：不能處理連續(xù)型數(shù)據(jù)，可搜索位置有限，容易陷入局部最優(yōu)等。

為彌補這些局限性，利用鄰域粗糙集模型既能分析連續(xù)型數(shù)據(jù)，又能處理符號與數(shù)值的混合型數(shù)據(jù)的優(yōu)勢，且二進制算子比連續(xù)算子具有更強的擬合性的特點，提出了基于鄰域粗糙集和帝王蝶優(yōu)化的特征選擇算法。首先，為了使帝王蝶個體在尋找最優(yōu)解時有更強的搜索能力，以避免過早陷入局部最優(yōu)，在MBO算法上加入局部擾動，并結(jié)合群體劃分策略，在到目前為止找到的最優(yōu)解的位置生成了解的二進制形式，構(gòu)造出二進制MBO（Binary MBO， BMBO）算法；且為了進一步增強BMBO算法的搜索能力，引入突變算子增強探測階段，設(shè)計了基于突變算子的BMBO（BMBO based on Mutation operator， BMBOM）算法。然后，使用鄰域粗糙集的鄰域依賴度和所選特征子集的加權(quán)值構(gòu)造新的適應(yīng)度函數(shù)，對選出的特征子集進行評估并排序。最后，結(jié)合新的適應(yīng)度函數(shù)，設(shè)計了基于鄰域粗糙集與BMBOM的特征選擇算法（Feature Selection algorithm based on Neighborhood rough set and BMBOM， FSNB），尋找最優(yōu)特征子集使其在優(yōu)化問題空間中具有更強的搜索能力，有效獲取最優(yōu)/最小特征子集。在6個基準(zhǔn)函數(shù)和14個UCI數(shù)據(jù)集上的實驗結(jié)果表明，本文算法能夠選擇分類精度較高且數(shù)量規(guī)模較小的特征子集。

1 基礎(chǔ)知識

1.1 鄰域粗糙集

1.2 帝王蝶優(yōu)化算法

將帝王蝶優(yōu)化（MBO）算法用于解決全局優(yōu)化問題，性能優(yōu)于其他先進的典型優(yōu)化算法［17］。MBO算法搜索過程由兩種機制主導(dǎo)：遷移算子和調(diào)整算子，具體流程如算法1所示。

算法1 MBO算法。

輸入 初始化所有參數(shù)，適應(yīng)度函數(shù)f（x），群體的規(guī)模N，空間維度D，最大迭代次數(shù)T；

輸出 最優(yōu)帝王蝶個體的位置及相應(yīng)的適應(yīng)度值。

1） While 不滿足最大迭代或停止條件 do

2）計算適應(yīng)度值并排序，找到最優(yōu)帝王蝶位置和其對應(yīng)的適應(yīng)度值；

11） else

14） end if

15） end for

16） end for

21） else

27） end if

28） end if

29） end for

30） end for

31）將新生成的子種群合并為1個整體種群；

33） End while

2 本文特征選擇算法

2.1 改進的MBO算法

一般來說，MBO算法能找到全局最優(yōu)解，但在某些時候，它可能會陷入局部最優(yōu)解。在調(diào)整算子中，每只帝王蝶的步長是由dx和a決定，通過Lévy飛行完全識別搜索過程，但不能根據(jù)實際搜索情況進行調(diào)節(jié)，當(dāng)步長過大時，MBO算法無法獲得最優(yōu)解。為了使步長向著最好的帝王蝶去改變，嘗試擴大步長參數(shù)a的調(diào)節(jié)范圍，進行局部擾動，以幫助MBO算法跳出局部最優(yōu)解。因此將步長參數(shù)a改進為：

其中：Smax表示帝王蝶的最大步長；t表示當(dāng)前迭代次數(shù)；tmax表示最大迭代次數(shù)；m表示步長參數(shù)a的調(diào)整因子，隨著迭代次數(shù)的改變而改變。

接下來，對帝王蝶群體實施群體劃分策略。設(shè)當(dāng)前的帝王蝶群體為N，利用適應(yīng)度函數(shù)計算群體中各個帝王蝶的適應(yīng)度值Fit，并得到N中最佳適應(yīng)度值Fitbest和最差適應(yīng)度值Fitworst。利用分別計算帝王蝶個體i和最優(yōu)個體的適應(yīng)度差值di，best以及和最差個體的適應(yīng)度差值di，worst。若di，best和di，worst滿足，則帝王蝶個體i被劃分到精英子群中，并直接保留到下一次迭代中；否則被劃分到普通子群中，繼續(xù)迭代更新。

依據(jù)上述思路改進MBO算法，獲取分類結(jié)果，然后構(gòu)建傳輸機制獲得二進制表示：

結(jié)合MBO算法和式（11），本文構(gòu)建二進制MBO（BMBO）算法。為了使解決方案朝著目前為止最佳的解決方案演化，可以通過適當(dāng)?shù)耐蛔兟蕦ζ胀ㄗ尤褐械牡弁醯麄€體進行局部搜索來進行突變，從而生成新的解決方案。為了避免過早收斂，可以使用具有適當(dāng)突變率的突變算子來增強算法的多樣性，其中突變率是控制突變算子的關(guān)鍵因素［21］。過高的突變率會增加在搜索空間中搜索更多區(qū)域的概率，從而阻止種群收斂到任何最優(yōu)解；太小的突變率可能導(dǎo)致過早收斂，降低局部最優(yōu)而不是全局最優(yōu)。因而，使用的突變率r3表示為：

其中tmax表示最大迭代次數(shù)。根據(jù)迭代次數(shù)i，參數(shù)r3從0.9線性遞減到0。于是，利用突變率r3代替式（11）中的r2，形成突變算子增強搜索能力，進而設(shè)計BMBOM算法。

2.2 適應(yīng)度函數(shù)

在特征選擇的過程中，讓每個帝王蝶分頭并行地尋找最優(yōu)特征子集，結(jié)合鄰域依賴度與特征子集長度的加權(quán)值，構(gòu)造新的適應(yīng)度函數(shù)，并將其作為啟發(fā)式信息引導(dǎo)算法進行迭代尋優(yōu)。由此，基于鄰域依賴度的適應(yīng)度函數(shù)描述如下。

其中：|B|為所選特征子集的長度；|C|為特征總個數(shù)；表示鄰域依賴度；λ和μ分別表示分類質(zhì)量和子集長度的重要程度，兩個參數(shù)和的設(shè)置參照文獻［3］。

2.3 算法描述

依據(jù)鄰域粗糙集模型和MBO算法原理，用BMBOM算法選出特征子集，通過適應(yīng)度函數(shù)評估特征子集的適應(yīng)度值，排序選出最優(yōu)特征子集，則特征選擇算法的偽代碼如算法2所示。

算法2 基于鄰域粗糙集與BMBOM的特征選擇算法（FSNB）。

輸出 最優(yōu)特征子集。

1） While 不滿足最大迭代或停止條件 do

2） 根據(jù)式（13）計算適應(yīng)度值并排序，找到最優(yōu)的帝王蝶位置和其對應(yīng)的適應(yīng)度值；

11） else

14） end if

15） end for

16） end for

21） else

27） end if

28） end if

29） end for

30） end for

31） 將新生成的子種群合并為1個整體種群；

33） End while

35）計算所有特征在測試集上的分類精度；

36）輸出最佳解決方案的位置（選中的最優(yōu)特征子集）。

下面給出算法2的時間復(fù)雜度分析：假設(shè)帝王蝶群體規(guī)模為N、子群1為N1、子群2為1、最大迭代次數(shù)為T、空間維度為D。由文獻［22］可知，計算正域和鄰域依賴度的時間復(fù)雜度為。FSNB的復(fù)雜度由每次迭代循環(huán)確定，具體分析如下：步驟2）使用鄰域依賴度計算適應(yīng)度函數(shù)，其時間復(fù)雜度為；步驟3）～4）的時間復(fù)雜度都為O（N）；步驟5）～16）的時間復(fù)雜度為O（N1D）；步驟17）～30）的時間復(fù)雜度為；步驟31）～33）的時間復(fù)雜度為O（N）；步驟34）～36）的時間復(fù)雜度為常數(shù)項。因此，F(xiàn)SNB在最壞情況下的總時間復(fù)雜度為O（TN2）。

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

3.1 BMBOM算法性能分析

為驗證BMBOM算法的優(yōu)化性能，選取文獻［20］中典型的6個基準(zhǔn)函數(shù)（如表1所示），與MBO算法［17］、粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法［8］進行測試與比較。表1中，單峰函數(shù)主要測試算法的尋優(yōu)精度；多峰函數(shù)具有多個局部最優(yōu)點檢驗算法的全局搜索性能和避免局部收斂的能力。這些函數(shù)的理論最優(yōu)值為0。為了確保實驗的公平性，依據(jù)文獻［20］，這3種算法在30維上設(shè)置相同的參數(shù)。同時，為防止產(chǎn)生隨機的實驗結(jié)果影響對算法的評估，這3種算法在6個基準(zhǔn)函數(shù)上獨立運行30次。表2給出了3種算法在6個基準(zhǔn)函數(shù)上30維的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差和運行時間的測試結(jié)果。從表2測試結(jié)果可以看出，在上，BMBOM算法的最優(yōu)值、最差值、平均值以及標(biāo)準(zhǔn)差都優(yōu)于MBO算法和PSO算法；尤其在f1和f5上，BMBOM算法的5項指標(biāo)遠領(lǐng)先于其他2種算法；在f6上，PSO算法在標(biāo)準(zhǔn)差上是最優(yōu)的，BMBOM算法在f6的最優(yōu)值、最差值和平均值都是最優(yōu)的。從運行時間上來說，BMBOM算法次于其他2種對比算法，其原因是：BMBOM算法中的局部擾動、群體劃分策略以及突變算子在提高了優(yōu)化性能的同時增加了運行時間。因此，這3種算法在6個基準(zhǔn)函數(shù)30維上的實驗結(jié)果表明，BMBOM算法獲得的優(yōu)化能力和穩(wěn)定性是相對優(yōu)異的。實驗環(huán)境設(shè)置為64位Window 7、Intel Core i5 2.2 GHz CPU、4 GB RAM和Matlab 2016b，且文中所有實驗結(jié)果中的加粗都表示最佳值。

表1 六個基準(zhǔn)函數(shù)信息Tab. 1 Information of six benchmark functions

表2 三種優(yōu)化算法在6個基準(zhǔn)函數(shù)30維上的實驗結(jié)果Tab. 2 Experimental results of three optimization algorithms on 30-dimensions of six benchmark functions

3.2 FSNB性能分析

為驗證FSNB的特征選擇效果，選用14個UCI數(shù)據(jù)集［21］進行測試。表3給出了所選數(shù)據(jù)集的信息。FSNB的種群數(shù)設(shè)置為20，最大迭代次數(shù)設(shè)置為100，依據(jù)文獻［3］，設(shè)置適應(yīng)度函數(shù)中且。實驗采用3類評價指標(biāo)［21］：分類精度、所選特征數(shù)和適應(yīng)度值。為了驗證結(jié)果的最優(yōu)性并確保比較算法的公平性，參照文獻［21］使用K最近鄰分類器（），將每個數(shù)據(jù)集分為訓(xùn)練集占80%和測試集占20%。為了避免算法的隨機性，每種算法獨立運行20次，因而統(tǒng)計測量是20次獨立運行的總體能力和最終結(jié)果。

3.2.1 與基于粗糙集的優(yōu)化特征選擇算法的比較

為了驗證算法的有效性，首先將所提的FSNB與5種基于粗糙集的優(yōu)化特征選擇算法進行比較，分別包括：ARRSFA（Attribute Reduction based on Rough Sets and the discrete Firefly Algorithm）［23］、PSORSFS（Feature Selection algorithm based on Rough Sets and Particle Swarm Optimization）［24］、FSARSR（Rough Set Reducts with Fish Swarm Algorithm）［25］、QCSIA_FS（Cooperative Swarm Intelligence Algorithm based on Quantum-inspired and rough sets for Feature Selection）［26］、DQBGOA_MR（Dynamic population Quantum Binary Grasshopper Optimization Algorithm based on Mutual information and Rough set）［10］。這些算法使用對應(yīng)文獻中的最佳實驗參數(shù)，對比的實驗數(shù)據(jù)與結(jié)果選自文獻［10］。表4給出了FSNB與其他5種特征選擇算法在10個UCI數(shù)據(jù)集上的分類精度的實驗結(jié)果。從表4可以看出，在Vote數(shù)據(jù)集上，F(xiàn)SNB比最優(yōu)的FSARSR略差1.3個百分點；在其他9個數(shù)據(jù)集上，F(xiàn)SNB的分類精度都是最優(yōu)的，尤其是在Wine數(shù)據(jù)集上，F(xiàn)SNB的分類精度比其他5種算法遠高出23.3～29.9個百分點。同時，F(xiàn)SNB在分類精度平均值上是最優(yōu)的，提升了11.6～14.0個百分點。由此可以說明，F(xiàn)SNB能夠獲得最優(yōu)的分類精度。

表5給出了FSNB與其他5種特征選擇算法所選擇的特征數(shù)的實驗結(jié)果。在Spect、Tic-tac-toe和Vote這3個數(shù)據(jù)集上，F(xiàn)SNB比其他5種算法具有顯著優(yōu)勢。在Lungcancer數(shù)據(jù)集上，F(xiàn)SNB獲取的特征數(shù)略遜于DQBGOA_MR，但是結(jié)合表4的分類精度綜合分析可知，F(xiàn)SNB的分類性能遠優(yōu)于DQBGOA_MR。同樣的，在其余6個數(shù)據(jù)集上，盡管FSNB所選的特征數(shù)不如其他5種算法，但是它們之間的差值較小，同時FSNB獲得了具有明顯優(yōu)勢的分類精度。綜合考慮表4～5的實驗結(jié)果可知，F(xiàn)SNB的分類能力優(yōu)于其他5種算法。

表3 14個UCI數(shù)據(jù)集信息Tab. 3 Information of fourteen UCI datasets

表4 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的分類精度實驗結(jié)果 單位： %Tab. 4 Experimental results of FSNB and five optimized feature selection algorithms based on rough sets on classification accuracy unit： %

表5 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的所選特征數(shù)實驗結(jié)果Tab. 5 Experimental results of FSNB and five optimized feature selection algorithms based on rough set on number of selected features

接下來，為了進一步評估FSNB的分類性能，選用當(dāng)前流行的8種優(yōu)化算法：IRRA（Improved Runner-Root Algorithm）［27］、GA（Genetic Algorithm）［28］、PSO（Particle Swarm Optimization）［29］、ABC（Artificial Bee Colony）［30］、FA（Firefly Algorithm）［31］、SSO（Social Spider Optimization）［32］、CS（Cuckoo Search）［33］和HS（Harmony Search algorithm）［34］，與粗糙集 （Rough Set）模型結(jié)合，構(gòu)造8種特征選擇算法進行對比，分別簡寫為IRRARS、GARS、PSORS、ABCRS、FARS、SSORS、CSRS和HSRS。上述8種優(yōu)化算法使用對應(yīng)文獻中的最佳實驗參數(shù)，對比的實驗數(shù)據(jù)與結(jié)果選自文獻［27］。表6給出了FSNB與上述8種特征選擇算法在7個UCI數(shù)據(jù)集上的分類精度的實驗結(jié)果。從表6的比較結(jié)果可知，在Breastcancer數(shù)據(jù)集上，F(xiàn)SNB的分類精度比IRRARS略低了2.3個百分點，但是優(yōu)于GARS、PSORS、FARS、SSORS和CSRS這5種算法；在Lungcancer數(shù)據(jù)集上，F(xiàn)SNB的分類精度比其他8種算法高出了13.2～29.2個百分點；在Heart、Ionosphere、Waveform和Zoo這4個數(shù)據(jù)集上，F(xiàn)SNB也明顯優(yōu)于其他8種算法，同時也獲得了相對最好的分類精度；而在Congress數(shù)據(jù)集上，F(xiàn)SNB的分類精度并沒有其他8種算法好，但是在選擇的特征數(shù)上來講，F(xiàn)SNB占據(jù)了絕對的優(yōu)勢。盡管FSNB在Breastcancer和Congress數(shù)據(jù)集上的分類精度不是最優(yōu)的，但相較于其余8種算法，F(xiàn)SNB還是具有較好的優(yōu)勢。同時，F(xiàn)SNB在分類精度平均值上是最高的，提升了3.9～13.2個百分點。表7中給出了FSNB和其他8種算法所選特征數(shù)。與這8種結(jié)合粗糙集的元啟發(fā)式特征選擇算法相比，F(xiàn)SNB在7個數(shù)據(jù)集上表現(xiàn)出了優(yōu)越的性能，所選特征數(shù)遠少于其他8種算法。詳細來說，在Waveform數(shù)據(jù)集上，GARS所選特征數(shù)是FSNB的606倍；在Breastcancer和Congress這2個數(shù)據(jù)集上，F(xiàn)SNB雖然沒有獲得最高分類精度，但是選擇的特征數(shù)取得了最小值，尤其是IRRARS和SSORS這2個算法選擇的特征數(shù)分別是FSNB的57倍和30倍，表明FSNB的分類性能是最優(yōu)的。

總的來說，從表4～7的實驗結(jié)果可以看出，與粗糙集和優(yōu)化算法結(jié)合的特征選擇算法相比，F(xiàn)SNB在選擇較少的特征的同時能夠保持良好的分類精度。這表明FSNB選出的特征子集具有較少的數(shù)量和較高的分類精度，驗證了FSNB的有效性。

表6 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法的分類精度實驗結(jié)果 單位： %Tab. 6 Experimental results of FSNB and eight feature selection algorithms combining rough set and optimization algorithm on classification accuracy unit： %

表7 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法所選特征數(shù)實驗結(jié)果Tab. 7 Experimental results of FSNB and eight feature selection algorithms combining rough set and optimization algorithm on number of selected features

3.2.2 與基于鄰域粗糙集的優(yōu)化特征選擇算法的比較

首先將鄰域粗糙集與文獻［17］的MBO算法相結(jié)合，構(gòu)建新的特征選擇算法FSNM（Feature Selection algorithm based on NRS and MBO），在選定的14個UCI數(shù)據(jù)集上，比較FSNM和FSNB的性能，驗證BMBOM算法的優(yōu)化性能。表8給出了3類指標(biāo)的實驗結(jié)果。

從表8可以看出，在14個UCI數(shù)據(jù)集上，F(xiàn)SNB獲得了最優(yōu)的分類精度和最少的特征數(shù)。詳細來說，在Wine數(shù)據(jù)集上為最高分類精度97.53%；在Zoo、Waveform和Breastcancer這3個數(shù)據(jù)集上次之，分別為97.14%、96.89%和95.67%。在Congress和Heart這2個數(shù)據(jù)集上，F(xiàn)SNB的適應(yīng)度值略低于FSNM，但是在分類精度和特征數(shù)上都優(yōu)于FSNM。此外，在Waveform數(shù)據(jù)集上，F(xiàn)SNB選擇的特征數(shù)最少，即為6.30。

同時，從表8可以看出，在Breastercancer、Hepatitis、Ionosphere等12個數(shù)據(jù)集上，F(xiàn)SNB獲得了最優(yōu)的適應(yīng)度值，同時，在適應(yīng)度值上，F(xiàn)SNB的平均值也是最優(yōu)的。從運行時間上看出，在Breastcancer、Hepatitis、Ionosphere、Lungcancer、Lymphography、Waveform和Zoo這7個數(shù)據(jù)集上，F(xiàn)SNB優(yōu)于FSNM，尤其是在Lymphography數(shù)據(jù)集上，F(xiàn)SNB的運行時間不到FSNM的6%；在Congress、Heart、Sonar和Wine這4個數(shù)據(jù)集上，F(xiàn)SNB與FSNM的運行時間是一樣的；在Spect、Tic-tac-toe和Vote這3個數(shù)據(jù)集上，F(xiàn)SNB的運行時間次于FSNM；在平均值上，F(xiàn)SNB仍然優(yōu)于FSNM。

從表8的4個評價指標(biāo)總體結(jié)果來說，F(xiàn)SNB的分類結(jié)果優(yōu)于FSNM。也就是說，BMBOM算法具有較好的優(yōu)化分類性能。

接下來，為了驗證FSNB的分類性能，選用當(dāng)前流行的8種優(yōu)化算法：IRRA［27］、GA［28］、PSO［29］、ABC［30］、FA［31］、SSO［32］、CS［33］和HS［34］，與鄰域粗糙集模型結(jié)合構(gòu)造8種特征選擇算法進行對比，分別簡寫為IRRANRS、GANRS、PSONRS、ABCNRS、FANRS、SSONRS、CSNRS和HSNRS。對比的實驗數(shù)據(jù)選自文獻［27］。表9給出了FSNB與其他8種算法在分類精度上的實驗比較結(jié)果。表10描述了FSNB與其他8種算法所選特征數(shù)的對比結(jié)果。

表8 FSNB與FSNM在分類精度、適應(yīng)度值和所選特征數(shù)上的實驗結(jié)果Tab. 8 Experimental results of FSNM and FSNB on classification accuracy， fitness value and number of selected features

表9 FSNB與8種結(jié)合鄰域粗糙集與優(yōu)化算法的特征選擇算法的分類精度實驗結(jié)果 單位： %Tab. 9 Experimental results of FSNB and eight feature selection algorithms combining NRS and optimization algorithms on classification accuracy unit： %

表10 FSNB與8種結(jié)合鄰域粗糙集與優(yōu)化算法的特征選擇算法所選特征數(shù)實驗結(jié)果Tab. 10 Experimental results of FSNB and eight feature selection algorithms combining NRS and optimization algorithms on number of selected features

從表9可以看出，對于Heart、Ionosphere、Lungcancer、Waveform和Zoo這5個數(shù)據(jù)集，F(xiàn)SNB的性能最優(yōu)。FSNB在除了Congress以外的6個數(shù)據(jù)集上都優(yōu)于GANRS、FANRS和CSNRS這3個算法。值得一提的是，在Lungcancer數(shù)據(jù)集上，F(xiàn)SNB的分類精度明顯優(yōu)于其他8種算法。此外，在Zoo數(shù)據(jù)集上，F(xiàn)SNB的分類精度高達97.14%；而在Congress數(shù)據(jù)集上，F(xiàn)SNB的分類精度略低于其他8種算法，這可能是FSNB在迭代的過程中丟失了一些重要的特征，導(dǎo)致分類精度降低。

根據(jù)表10可知，在7個數(shù)據(jù)集上，F(xiàn)SNB選擇的特征數(shù)依舊是最少的。尤其在Waveform數(shù)據(jù)集上，GANRS的特征數(shù)是FSNB的588倍。在Breastcancer和Congress這2個數(shù)據(jù)集上，F(xiàn)SNB雖然沒有獲得最高的分類精度，但是選擇的特征數(shù)是最少的，并且IRRANRS和PSONRS這2個算法選擇的特征數(shù)分別是FSNB的54倍和41倍。

總的來說，在Heart、Ionosphere、Lungcancer、Waveform和Zoo這5個數(shù)據(jù)集上，F(xiàn)SNB的分類精度是穩(wěn)定的，而GANRS、ABCNRS、FANRS、CSNRS和HSNRS這5種算法的分類性能是不穩(wěn)定的。同時，F(xiàn)SNB在分類精度和特征數(shù)上總的平均值都是最優(yōu)的，即在分類精度平均值上提升了1.1～10.5個百分點，在所選特征數(shù)的平均值上比其他算法少了347～678。因此，F(xiàn)SNB能夠有效消除冗余特征并顯著提高算法的分類精度，優(yōu)于其他8種算法，也就是說FSNB在解決特征選擇問題上具有明顯的優(yōu)勢。

3.2.3 與基于二進制灰狼優(yōu)化的特征選擇算法的比較

為了更好地展示FSNB的有效性，從文獻［3］中選擇6種基于二進制灰狼優(yōu)化（Binary Grey Wolf Optimizer）的特征選擇算法，具體包括：BGWO、ABGWO、ABGWO-V1、ABGWO-V2、ABGWO-V3和ABGWO-V4，與本文提出的FSNB進行實驗比較。上述6種算法使用文獻［3］中對應(yīng)的最佳實驗參數(shù)，對比的實驗數(shù)據(jù)與結(jié)果也選自文獻［3］。表11給出了FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法的分類精度比較結(jié)果。

從表11可以看出，在Congress數(shù)據(jù)集上，F(xiàn)SNB的分類精度略低于最優(yōu)的ABGWO。但是，在其余8個數(shù)據(jù)集上，F(xiàn)SNB獲得最優(yōu)的分類精度，尤其是在Zoo數(shù)據(jù)集上的分類精度最高，即為97.14%；在Lymphography數(shù)據(jù)集上，F(xiàn)SNB的分類精度明顯比其他6種算法高出44.1～45.4個百分點。同時，F(xiàn)SNB在分類精度的平均值上是最優(yōu)的，即提升了13.5～14.3個百分點。

表12給出了FSNB與其他6種算法所選特征數(shù)比較結(jié)果。從表12可以看出，F(xiàn)SNB表現(xiàn)最優(yōu)，其次是ABGWO-V2和ABGWO-V3這2種算法。在Congress、Sonar、Spect、Tic-tac-toe、Waveform和Zoo這6個數(shù)據(jù)集上，F(xiàn)SNB選取的特征數(shù)為最小值。在Breastcancer和Ionosphere這2個數(shù)據(jù)集上，雖然FSNB的特征數(shù)都不如ABGWO-V2算法，但FSNB的分類精度值分別比ABGWO-V2算法高出15.4個百分點和8.1個百分點；而在Lymphography數(shù)據(jù)集上，F(xiàn)SNB的特征數(shù)少于ABGWO-V3算法，但FSNB的分類精度是7種算法中最高的。總體來說，綜合考慮分類精度和所選特征數(shù)這2個評價指標(biāo)，F(xiàn)SNB明顯優(yōu)于這6種基于二進制灰狼優(yōu)化的特征選擇算法。

表11 FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法的分類精度實驗結(jié)果 單位： %Tab. 11 Experimental results of FSNB and six feature selection algorithms based on binary grey wolf optimizer on classification accuracy unit： %

表12 FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法所選特征數(shù)實驗結(jié)果Tab. 12 Experimental results of FSNB and six feature selection algorithms based on binary grey wolf optimizer on number of selected features

3.3 統(tǒng)計分析

使用Friedman和Bonferroni-Dunn測試［35］來分析所有實驗結(jié)果的統(tǒng)計意義，計算式為：

其中：k是算法數(shù)量；N是數(shù)據(jù)集數(shù)量；Ri是k個算法在N個數(shù)據(jù)集上的平均排名。依據(jù)測試結(jié)果可知，如果平均距離水平超出臨界距離，則算法性能有顯著差異。臨界距離定義為：

其中：qα是測試的關(guān)鍵列表值；α表示顯著水平。

依據(jù)表5、7、9、11的分類精度實驗結(jié)果，分別對所有比較的算法進行Friedman檢驗，驗證所有算法在分類性能上是否存在顯著性差異，表13～16分別給出了在KNN分類器下的排序結(jié)果和2個評價指標(biāo)（和）的值。

為了直觀地顯示FSNB與其他對比算法的相對性能，圖1給出了比較的算法在分類精度下的值，其中每個算法的平均排序沿數(shù)軸繪制。軸上的最小值位于左側(cè)，因此，左側(cè)排序的算法更好。表13給出了FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的平均排序和值，其中，的零假設(shè)被拒絕。如圖1所示，在顯著性水平下，，，其中且，由此可知，F(xiàn)SNB明顯優(yōu)于其他5種算法。表14給出了FSNB與8種結(jié)合粗糙集與優(yōu)化的特征選擇算法的平均排序和值，其中的臨界值為，時拒絕零假設(shè)。圖2顯示了在顯著性水平下，，，其中且，由此可以看出，IRRARS結(jié)果最優(yōu)，F(xiàn)SNB次之，但是FSNB優(yōu)于其他7種算法。表15給出了FSNB與8種結(jié)合鄰域粗糙集與優(yōu)化的特征選擇算法的平均排序和值，其中的臨界值為1.802，時的零假設(shè)將被拒絕。如圖3所示，在顯著性水平下，，其中且。因而可知，IRRANRS最優(yōu)，F(xiàn)SNB次之，但是FSNB優(yōu)于其他7種算法。表16給出了FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法的平均排序以及值，其中的臨界值為1.901，時的零假設(shè)被拒絕。圖4顯示了在時，，其中且。因此，F(xiàn)SNB的Bonferron-Dunn檢驗優(yōu)于其他6種算法。

總的來說，通過上述統(tǒng)計結(jié)果的分析可知，F(xiàn)SNB的性能優(yōu)于其他比較算法，并在所有數(shù)據(jù)集上實現(xiàn)了良好的泛化性能。

表13 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的統(tǒng)計檢驗Tab. 13 Statistical test of FSNB and five optimized feature selection algorithms based on rough set

表14 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法的統(tǒng)計檢驗Tab. 14 Statistical test of FSNB and eight feature selection algorithms combining rough set and optimization algorithms

表15 FSNB與8種結(jié)合鄰域粗糙集與優(yōu)化算法的特征選擇算法的統(tǒng)計檢驗Tab. 15 Statistical test of FSNB and eight feature selection algorithms combining NRS and optimization algorithms

表16 FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法的統(tǒng)計檢驗Tab. 16 Statistical test of FSNB and six feature selection algorithms based on binary grey wolf optimizer

圖1 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的Bonferroni-Dunn檢驗結(jié)果Fig. 1 Bonferroni-Dunn test results of FSNB and five optimized feature selection algorithms based on rough set

圖2 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法的Bonferroni-Dunn檢驗結(jié)果Fig. 2 Bonferroni-Dunn test results of FSNB and eight feature selection algorithms based on rough set and optimization algorithms

圖3 FSNB與8種結(jié)合鄰域粗糙集與優(yōu)化算法的特征選擇算法的Bonferroni-Dunn檢驗結(jié)果Fig. 3 Bonferroni-Dunn test results of FSNB and eight feature selection algorithms based on NRS and optimization algorithms

圖4 FSNB與6種基于二進制灰狼優(yōu)化的特征選擇算法的Bonferroni-Dunn檢驗結(jié)果Fig. 4 Bonferroni-Dunn test results of FSNB and six feature selection algorithms based on binary grey wolf optimizer

4 結(jié)語

本文利用MBO算法的計算簡單、所需計算參數(shù)較少、收斂迅速等優(yōu)點，提出了一種基于鄰域粗糙集與改進的MBO的特征選擇算法。首先，針對獲取的數(shù)據(jù)構(gòu)建鄰域決策系統(tǒng)，設(shè)計了BMBOM算法；然后，基于鄰域粗糙集構(gòu)造適應(yīng)度函數(shù)，評估初始化的特征子集的適應(yīng)度值并排序；最后，使用BMBOM算法搜索最優(yōu)特征子集，設(shè)計了一種元啟發(fā)式的特征選擇算法。在6個基準(zhǔn)函數(shù)和14個UCI數(shù)據(jù)集上的實驗結(jié)果表明，所提算法是有效的。究其原因是在MBO算法上加入了局部擾動和群體劃分策略，促使MBO算法能夠最大化地搜索特征空間達到最優(yōu)，加入突變算子使改進的MBO算法的多樣性增強，進而更容易收斂到最優(yōu)/接近最優(yōu)解。將鄰域粗糙集模型與改進的MBO算法相結(jié)合，使該特征選擇算法更快地找到最小特征子集，特別是在處理高維數(shù)據(jù)時效果更加明顯。但是，在算法運行時效上，本文所提算法的改善效果不夠顯著，在下一步研究工作中需繼續(xù)改進。

[1] 吳信東，董丙冰，堵新政，等.數(shù)據(jù)治理技術(shù)［J］.軟件學(xué)報，2019，30（9）：2830-2856.（WU X D， DONG B B， DU X Z， et al. Data governance technology ［J］. Journal of Software， 2019， 30（9）： 2830-2856.）

[2] 鄧威，郭釔秀，李勇，等.基于特征選擇和Stacking集成學(xué)習(xí)的配電網(wǎng)網(wǎng)損預(yù)測［J］.電力系統(tǒng)保護與控制，2020，48（15）：108-115.（DENG W， GUO Y X， LI Y， et al. Power losses prediction based on feature selection and Stacking integrated learning ［J］. Power System Protection and Control， 2020， 48（15）： 108-115.）

[3] HU P， PAN J S， CHU S C. Improved binary grey wolf optimizer and its application for feature selection ［J］. Knowledge-Based Systems， 2020，195： Article No.105746.

[4] TUBISHAT M， IDRIS N， SHUIB L， et al. Improved salp swarm algorithm based on opposition based learning and novel local search algorithm for feature selection ［J］. Expert Systems with Applications， 2020， 145： Article No.113122.

[5] 劉艷，程璐，孫林.基于K-S檢驗和鄰域粗糙集的特征選擇方法［J］.河南師范大學(xué)學(xué)報（自然科學(xué)版），2019，47（2）：21-28.（LIU Y， CHENG L， SUN L. Feature selection method based on K-S test and neighborhood rough sets ［J］. Journal of Henan Normal University （Natural Science Edition）， 2019， 47（2）： 21-28.）

[6] 劉琨，封碩.加強局部搜索能力的人工蜂群算法［J］.河南師范大學(xué)學(xué)報（自然科學(xué)版），2021，49（2）：15-24.（LIU K， FENG S. An improved artificial bee colony algorithm for enhancing local search ability ［J］. Journal of Henan Normal University （Natural Science Edition）， 2021， 49（2）： 15-24.）

[7] ZAIMOGLU E A， CELEBI N， YURTAY N. Binary-coded tug of war optimization algorithm for attribute reduction based on rough set ［J］. Journal of Multiple-Valued Logic and Soft Computing， 2020， 35（1/2）： 93-111.

[8] HUDA R K， BANKA H. Efficient feature selection and classification algorithm based on PSO and rough sets ［J］. Neural Computing and Applications， 2019， 31（8）： 4287-4303.

[9] TAWHID M A， IBRAHIM A M. Feature selection based on rough set approach， wrapper approach， and binary whale optimization algorithm ［J］. International Journal of Machine Learning and Cybernetics， 2020， 11（3）： 573-602.

[10] WANG D， CHEN H M， LI T R， et al. A novel quantum grasshopper optimization algorithm for feature selection ［J］. International Journal of Approximate Reasoning， 2020， 127： 33-53.

[11] ABD EL AZIZ M， HASSANIEN A E. Modified cuckoo search algorithm with rough sets for feature selection ［J］. Neural Computing and Applications， 2018， 29（4）： 925-934.

[12] ZOU L， LI H X， JIANG W， et al. An improved fish swarm algorithm for neighborhood rough set reduction and its application ［J］. IEEE Access，2019， 7： 90277-90288.

[13] 薛占熬，龐文莉，姚守倩，等.基于前景理論的直覺模糊三支決策模型［J］.河南師范大學(xué)學(xué)報（自然科學(xué)版），2020，48（5）：31-36，79.（XUE Z A， PANG W L， YAO S Q， et al. The prospect theory based intuitionistic fuzzy three-way decisions model ［J］. Journal of Henan Normal University （Natural Science Edition）， 2020， 48（5）： 31-36， 79.）

[14] HU Q H， YU D R， LIU J F， et al. Neighborhood rough set based heterogeneous feature subset selection ［J］. Information Sciences， 2018， 178（18）： 3577-3594.

[15] 彭鵬，倪志偉，朱旭輝，等.基于改進二元螢火蟲群優(yōu)化算法和鄰域粗糙集的屬性約簡方法［J］.模式識別與人工智能，2020，33（2）：95-105.（PENG P， NI Z W， ZHU X H， et al. Attribute reduction method based on improved binary glowworm swarm optimization algorithm and neighborhood rough set ［J］. Pattern Recognition and Artificial Intelligence， 2020， 33（2）： 95-105.）

[16] SUN L， CHEN S S， XU J C， et al. Improved monarch butterfly optimization algorithm based on opposition-based learning and random local perturbation ［J］. Complexity， 2019， 2019： Article No.4182148.

[17] WANG G G， DEB S， CUI Z H. Monarch butterfly optimization ［J］. Neural Computing and Applications， 2019， 31（7）： 1995-2014.

[18] DORGHAM O M， ALWESHAH M， RYALAT M H， et al. Monarch butterfly optimization algorithm for computed tomography image segmentation ［J］. Multimedia Tools and Applications， 2021， 80（20）： 30057-30090.

[19] SOLTANI P， HADAVANDI E. A monarch butterfly optimization- based neural network simulator for prediction of siro-spun yarn tenacity ［J］. Soft Computing， 2019， 23（20）： 10521-10535.

[20] 孫林，趙婧，徐久成，等.基于改進帝王蝶優(yōu)化算法的特征選擇方法［J］.模式識別與人工智能，2020，33（11）：981-994.（SUN L， ZHAO J， XU J C， et al. Feature selection method based on improved monarch butterfly optimization algorithm ［J］. Pattern Recognition and Artificial Intelligence， 2020， 33（11）： 981-994.）

[21] MAFARJA M， ALJARAH I， FARIS H， et al. Binary grasshopper optimisation algorithm approaches for feature selection problems ［J］. Expert Systems with Applications， 2019， 117： 267-286.

[22] SUN L， WANG L Y， DING W P， et al. Feature selection using fuzzy neighborhood entropy-based uncertainty measures for fuzzy neighborhood multigranulation rough sets ［J］. IEEE Transactions on Fuzzy Systems， 2021， 29（1）： 19-33.

[23] LONG N C， MEESAD P， UNGER H. Attribute reduction based on rough sets and the discrete firefly algorithm ［M］// BOONKRONG S， UNGER H， MEESAD P. Recent Advances in Information and Communication Technology，AISC 265. Cham： Springer， 2014： 13-22.

[24] WANG X Y， YANG J， TENG X L， et al. Feature selection based on rough sets and particle swarm optimization ［J］. Pattern Recognition Letters， 2007， 28（4）： 459-471.

[25] CHEN Y M， ZHU Q X， XU H R. Finding rough set reducts with fish swarm algorithm ［J］. Knowledge-Based Systems， 2015， 81： 22-29.

[26] ZOUACHE D， BEN ABDELAZIZ F. A cooperative swarm intelligence algorithm based on quantum-inspired and rough sets for feature selection ［J］. Computers and Industrial Engineering， 2018， 115： 26-36.

[27] IBRAHIM R A， ABD ELAZIZ M， OLIVA D， et al. An improved runner-root algorithm for solving feature selection problems based on rough sets and neighborhood rough sets ［J］. Applied Soft Computing， 2020，97（Pt B）： Article No.105517.

[28] JING S Y. A hybrid genetic algorithm for feature subset selection in rough set theory ［J］. Soft Computing， 2014， 18（7）： 1373-1382.

[29] ZHANG Y， GONG D W， HU Y， et al. Feature selection algorithm based on bare bones particle swarm optimization ［J］. Neurocomputing， 2015， 148： 150-157.

[30] SUGUNA N， THANUSHKODI K G. An independent rough set approach hybrid with artificial bee colony algorithm for dimensionality reduction ［J］. American Journal of Applied Sciences， 2011， 8（3）： 261- 266.

[31] 汪春峰，褚新月.基于精英鄰居引導(dǎo)的螢火蟲算法［J］.河南師范大學(xué)學(xué)報（自然科學(xué)版），2019，47（6）：15-21.（WAND C F， CHU X Y. A firefly algorithm based on elite neighborhood guide ［J］. Journal of Henan Normal University （Natural Science Edition）， 2019， 47（6）： 15-21.）

[32] ABD EL AZIZ M， HASSANIEN A E. An improved social spider optimization algorithm based on rough sets for solving minimum number attribute reduction problem ［J］. Neural Computing and Applications， 2018， 30（8）： 2441-2452.

[33] 徐小琴，王博，趙紅生，等.基于布谷鳥搜索和模擬退火算法的兩電壓等級配網(wǎng)重構(gòu)方法［J］.電力系統(tǒng)保護與控制，2020，48（11）：84-91.（XU X Q， WANG B， ZHAO H S， et al. Reconfiguration of two-voltage distribution network based on cuckoo search and simulated annealing algorithm ［J］. Power System Protection and Control， 2020， 48（15）： 108-115.）

[34] INBARANI H H， BAGYAMATHI M， AZAR A T. A novel hybrid feature selection method based on rough set and improved harmony search ［J］. Neural Computing and Applications， 2015， 26（8）： 1859-1880.

[35] SUN L， WANG L Y， DING W P， et al. Neighborhood multi- granulation rough sets-based attribute reduction using Lebesgue and entropy measures in incomplete neighborhood decision systems ［J］. Knowledge-Based Systems， 2020， 192： Article No.105373.

Feature selection algorithm based on neighborhood rough set and monarch butterfly optimization

SUN Lin1，2*， ZHAO Jing1， XU Jiucheng1，2， WANG Xinya1

（1.College of Computer and Information Engineering，Henan Normal University，Xinxiang Henan453007，China；2.Key Laboratory of Artificial Intelligence and Personalized Learning in Education of Henan Province（Henan Normal University），Xinxiang Henan453007，China）

The classical Monarch Butterfly Optimization （MBO） algorithm cannot handle continuous data well， and the rough set model cannot sufficiently process large-scale，high-dimensional and complex data. To address these problems， a new feature selection algorithm based on Neighborhood Rough Set （NRS） and MBO was proposed. Firstly， local disturbance， group division strategy and MBO algorithm were combined， and a transmission mechanism was constructed to form a Binary MBO （BMBO） algorithm. Secondly， the mutation operator was introduced to enhance the exploration ability of this algorithm， and a BMBO based on Mutation operator （BMBOM） algorithm was proposed. Then， a fitness function was developed based on the neighborhood dependence degree in NRS， and the fitness values of the initialized feature subsets were evaluated and sorted. Finally， the BMBOM algorithm was used to search the optimal feature subset through continuous iterations， and a meta-heuristic feature selection algorithm was designed. The optimization performance of the BMBOM algorithm was evaluated on benchmark functions， and the classification performance of the proposed feature selection algorithm was evaluated on UCI datasets. Experimental results show that， the proposed BMBOM algorithm is significantly better than MBO and Particle Swarm Optimization （PSO） algorithms in terms of the optimal value， worst value， average value and standard deviation on five benchmark functions. Compared with the optimized feature selection algorithms based on rough set， the feature selection algorithms combining rough set and optimization algorithms， the feature selection algorithms combining NRS and optimization algorithms，the feature selection algorithms based on binary grey wolf optimization， the proposed feature selection algorithm performs well in the three indicators of classification accuracy， the number of selected features and fitness value on UCI datasets，and can select the optimal feature subset with few features and high classification accuracy.

Monarch Butterfly Optimization (MBO); feature selection; Neighborhood Rough Set (NRS); neighborhood dependence degree; binary

TP181

A

1001-9081（2022）05-1355-12

10.11772/j.issn.1001-9081.2021030497

2021?04?02；

2021?09?15；

2021?09?22。

國家自然科學(xué)基金資助項目（62076089，61772176，61976082）；河南省科技攻關(guān)項目（212102210136）。

孫林（1979—），男，河南南陽人，副教授，博士，CCF會員，主要研究方向：粒計算、數(shù)據(jù)挖掘、機器學(xué)習(xí)、生物信息學(xué)； 趙婧（1996—），女，河南洛陽人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、機器學(xué)習(xí)； 徐久成（1963—），男，河南洛陽人，教授，博士生導(dǎo)師，博士，CCF高級會員，主要研究方向：粒計算、數(shù)據(jù)挖掘、機器學(xué)習(xí)； 王欣雅（1997—），女，河南平頂山人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、機器學(xué)習(xí)。

This work is partially supported by National Natural Science Foundation of China （62076089， 61772176，61976082）， Key Scientific and Technological Project of Henan Province （212102210136）.

SUN Lin， born in 1979， Ph. D.， associate professor. His research interests include granular computing， data mining， machine learning， bioinformatics.

ZHAO Jing， born in 1996， M. S. candidate. Her research interests include data mining， machine learning.

XU Jiucheng， born in 1963， Ph. D.， professor. His research interests include granular computing， data mining， machine learning.

WANG Xinya， born in 1997， M. S. candidate. Her research interests include data mining， machine learning.