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

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

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

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

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

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

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

0 引言

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 鄰域粗糙集

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

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

算法1 MBO算法。

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

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

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

2）計(jì)算適應(yīng)度值并排序，找到最優(yōu)帝王蝶位置和其對(duì)應(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個(gè)整體種群；

33） End while

2 本文特征選擇算法

2.1 改進(jìn)的MBO算法

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

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

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

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

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

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

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

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

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

2.3 算法描述

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

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

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

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

2） 根據(jù)式（13）計(jì)算適應(yīng)度值并排序，找到最優(yōu)的帝王蝶位置和其對(duì)應(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個(gè)整體種群；

33） End while

35）計(jì)算所有特征在測(cè)試集上的分類精度；

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

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

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

3.1 BMBOM算法性能分析

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

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

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

3.2 FSNB性能分析

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

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

為了驗(yàn)證算法的有效性，首先將所提的FSNB與5種基于粗糙集的優(yōu)化特征選擇算法進(jìn)行比較，分別包括：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］。這些算法使用對(duì)應(yīng)文獻(xiàn)中的最佳實(shí)驗(yàn)參數(shù)，對(duì)比的實(shí)驗(yàn)數(shù)據(jù)與結(jié)果選自文獻(xiàn)［10］。表4給出了FSNB與其他5種特征選擇算法在10個(gè)UCI數(shù)據(jù)集上的分類精度的實(shí)驗(yàn)結(jié)果。從表4可以看出，在Vote數(shù)據(jù)集上，F(xiàn)SNB比最優(yōu)的FSARSR略差1.3個(gè)百分點(diǎn)；在其他9個(gè)數(shù)據(jù)集上，F(xiàn)SNB的分類精度都是最優(yōu)的，尤其是在Wine數(shù)據(jù)集上，F(xiàn)SNB的分類精度比其他5種算法遠(yuǎn)高出23.3～29.9個(gè)百分點(diǎn)。同時(shí)，F(xiàn)SNB在分類精度平均值上是最優(yōu)的，提升了11.6～14.0個(gè)百分點(diǎn)。由此可以說(shuō)明，F(xiàn)SNB能夠獲得最優(yōu)的分類精度。

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

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

表4 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的分類精度實(shí)驗(yàn)結(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ù)實(shí)驗(yàn)結(jié)果Tab. 5 Experimental results of FSNB and five optimized feature selection algorithms based on rough set on number of selected features

接下來(lái)，為了進(jìn)一步評(píng)估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種特征選擇算法進(jìn)行對(duì)比，分別簡(jiǎn)寫為IRRARS、GARS、PSORS、ABCRS、FARS、SSORS、CSRS和HSRS。上述8種優(yōu)化算法使用對(duì)應(yīng)文獻(xiàn)中的最佳實(shí)驗(yàn)參數(shù)，對(duì)比的實(shí)驗(yàn)數(shù)據(jù)與結(jié)果選自文獻(xiàn)［27］。表6給出了FSNB與上述8種特征選擇算法在7個(gè)UCI數(shù)據(jù)集上的分類精度的實(shí)驗(yàn)結(jié)果。從表6的比較結(jié)果可知，在Breastcancer數(shù)據(jù)集上，F(xiàn)SNB的分類精度比IRRARS略低了2.3個(gè)百分點(diǎn)，但是優(yōu)于GARS、PSORS、FARS、SSORS和CSRS這5種算法；在Lungcancer數(shù)據(jù)集上，F(xiàn)SNB的分類精度比其他8種算法高出了13.2～29.2個(gè)百分點(diǎn)；在Heart、Ionosphere、Waveform和Zoo這4個(gè)數(shù)據(jù)集上，F(xiàn)SNB也明顯優(yōu)于其他8種算法，同時(shí)也獲得了相對(duì)最好的分類精度；而在Congress數(shù)據(jù)集上，F(xiàn)SNB的分類精度并沒(méi)有其他8種算法好，但是在選擇的特征數(shù)上來(lái)講，F(xiàn)SNB占據(jù)了絕對(duì)的優(yōu)勢(shì)。盡管FSNB在Breastcancer和Congress數(shù)據(jù)集上的分類精度不是最優(yōu)的，但相較于其余8種算法，F(xiàn)SNB還是具有較好的優(yōu)勢(shì)。同時(shí)，F(xiàn)SNB在分類精度平均值上是最高的，提升了3.9～13.2個(gè)百分點(diǎn)。表7中給出了FSNB和其他8種算法所選特征數(shù)。與這8種結(jié)合粗糙集的元啟發(fā)式特征選擇算法相比，F(xiàn)SNB在7個(gè)數(shù)據(jù)集上表現(xiàn)出了優(yōu)越的性能，所選特征數(shù)遠(yuǎn)少于其他8種算法。詳細(xì)來(lái)說(shuō)，在Waveform數(shù)據(jù)集上，GARS所選特征數(shù)是FSNB的606倍；在Breastcancer和Congress這2個(gè)數(shù)據(jù)集上，F(xiàn)SNB雖然沒(méi)有獲得最高分類精度，但是選擇的特征數(shù)取得了最小值，尤其是IRRARS和SSORS這2個(gè)算法選擇的特征數(shù)分別是FSNB的57倍和30倍，表明FSNB的分類性能是最優(yōu)的。

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

表6 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法的分類精度實(shí)驗(yàn)結(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ù)實(shí)驗(yàn)結(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)化特征選擇算法的比較

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

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

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

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

接下來(lái)，為了驗(yàn)證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種特征選擇算法進(jìn)行對(duì)比，分別簡(jiǎn)寫為IRRANRS、GANRS、PSONRS、ABCNRS、FANRS、SSONRS、CSNRS和HSNRS。對(duì)比的實(shí)驗(yàn)數(shù)據(jù)選自文獻(xiàn)［27］。表9給出了FSNB與其他8種算法在分類精度上的實(shí)驗(yàn)比較結(jié)果。表10描述了FSNB與其他8種算法所選特征數(shù)的對(duì)比結(jié)果。

表8 FSNB與FSNM在分類精度、適應(yīng)度值和所選特征數(shù)上的實(shí)驗(yàn)結(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)化算法的特征選擇算法的分類精度實(shí)驗(yàn)結(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ù)實(shí)驗(yàn)結(jié)果Tab. 10 Experimental results of FSNB and eight feature selection algorithms combining NRS and optimization algorithms on number of selected features

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

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

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

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

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

從表11可以看出，在Congress數(shù)據(jù)集上，F(xiàn)SNB的分類精度略低于最優(yōu)的ABGWO。但是，在其余8個(gè)數(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個(gè)百分點(diǎn)。同時(shí)，F(xiàn)SNB在分類精度的平均值上是最優(yōu)的，即提升了13.5～14.3個(gè)百分點(diǎn)。

表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個(gè)數(shù)據(jù)集上，F(xiàn)SNB選取的特征數(shù)為最小值。在Breastcancer和Ionosphere這2個(gè)數(shù)據(jù)集上，雖然FSNB的特征數(shù)都不如ABGWO-V2算法，但FSNB的分類精度值分別比ABGWO-V2算法高出15.4個(gè)百分點(diǎn)和8.1個(gè)百分點(diǎn)；而在Lymphography數(shù)據(jù)集上，F(xiàn)SNB的特征數(shù)少于ABGWO-V3算法，但FSNB的分類精度是7種算法中最高的?？傮w來(lái)說(shuō)，綜合考慮分類精度和所選特征數(shù)這2個(gè)評(píng)價(jià)指標(biāo)，F(xiàn)SNB明顯優(yōu)于這6種基于二進(jìn)制灰狼優(yōu)化的特征選擇算法。

表11 FSNB與6種基于二進(jìn)制灰狼優(yōu)化的特征選擇算法的分類精度實(shí)驗(yàn)結(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種基于二進(jìn)制灰狼優(yōu)化的特征選擇算法所選特征數(shù)實(shí)驗(yàn)結(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)計(jì)分析

使用Friedman和Bonferroni-Dunn測(cè)試［35］來(lái)分析所有實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)意義，計(jì)算式為：

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

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

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

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

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

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

表14 FSNB與8種結(jié)合粗糙集與優(yōu)化算法的特征選擇算法的統(tǒng)計(jì)檢驗(yàn)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)計(jì)檢驗(yàn)Tab. 15 Statistical test of FSNB and eight feature selection algorithms combining NRS and optimization algorithms

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

圖1 FSNB與5種基于粗糙集的優(yōu)化特征選擇算法的Bonferroni-Dunn檢驗(yàn)結(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檢驗(yàn)結(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檢驗(yàn)結(jié)果Fig. 3 Bonferroni-Dunn test results of FSNB and eight feature selection algorithms based on NRS and optimization algorithms

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

4 結(jié)語(yǔ)

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

[1] 吳信東，董丙冰，堵新政，等.數(shù)據(jù)治理技術(shù)［J］.軟件學(xué)報(bào)，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ù)測(cè)［J］.電力系統(tǒng)保護(hù)與控制，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檢驗(yàn)和鄰域粗糙集的特征選擇方法［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(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] 劉琨，封碩.加強(qiáng)局部搜索能力的人工蜂群算法［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(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] 薛占熬，龐文莉，姚守倩，等.基于前景理論的直覺(jué)模糊三支決策模型［J］.河南師范大學(xué)學(xué)報(bào)（自然科學(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] 彭鵬，倪志偉，朱旭輝，等.基于改進(jìn)二元螢火蟲群優(yōu)化算法和鄰域粗糙集的屬性約簡(jiǎn)方法［J］.模式識(shí)別與人工智能，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] 孫林，趙婧，徐久成，等.基于改進(jìn)帝王蝶優(yōu)化算法的特征選擇方法［J］.模式識(shí)別與人工智能，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é)報(bào)（自然科學(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] 徐小琴，王博，趙紅生，等.基于布谷鳥搜索和模擬退火算法的兩電壓等級(jí)配網(wǎng)重構(gòu)方法［J］.電力系統(tǒng)保護(hù)與控制，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。

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

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