基于增強(qiáng)蜂群優(yōu)化算法的特征選擇算法

張霞 龐秀平

摘要：針對(duì)傳統(tǒng)蜂群優(yōu)化（BCO）算法探測(cè)能力強(qiáng)但搜索能力較弱的問(wèn)題，提出一種搜索能力增強(qiáng)的BCO算法，并將其應(yīng)用于數(shù)據(jù)特征選擇問(wèn)題以提高特征選擇的性能。首先，為食物源引入全局權(quán)重的概念，用以評(píng)估各食物源對(duì)種群的重要性，降低蜂群搜索的隨機(jī)性；然后，設(shè)計(jì)了兩步篩選的招募方法提高蜂群搜索能力并保持多樣性；最終，為食物源引入局部權(quán)重的概念，用于評(píng)估某個(gè)食物源與類(lèi)標(biāo)簽的相關(guān)性，從而優(yōu)化解特征選擇問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明，所提方法可以明顯提高BCO的優(yōu)化效果，同時(shí)獲得了較好的特征選擇效果，并且優(yōu)于基于差異的人工蜂群算法（DisABC）和蜂群優(yōu)化特征選擇算法（BCOFS）。

關(guān)鍵詞：特征選擇；蜂群優(yōu)化算法；食物源；類(lèi)標(biāo)簽；全局權(quán)重；招募算法

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A

Abstract：Concerning the problem that the traditional Bee Colony Optimization （BCO） has good exploration but week exploitation performance， an exploitation enhanced BCO algorithm was proposed， and applied to data feature selection problem in order to improve the performance of the feature selection. Firstly， global weight was introduced into the food source， and was used to evaluate the importance of each food source to population， thus the randomness of exploitation was reduced； then， a recruiting method with twostep filtering was designed to improve the exploitation performance and keep diversity； at last， local weight was introduced into the food source to evaluate the correlation between the food source and class labels which were used in the feature selection model. Simulation experimental results show that the proposed method can improve the effect of the BCO and get a good performance in the feature selection problem， and the method outperforms Dissimilarity based Artificial Bee Colony （DisABC） and Feature Selection based on Bee Colony Optimization （BCOFS）.

Key words：feature selection； Bee Colony Optimization （BCO） algorithm； food source； class label； global weight； recruiting algorithm

0 引言

蜂群優(yōu)化（Bee Colony Optimization， BCO）算法[1]是一種較好的人工智能算法，該方法模擬自然中蜂群的行為以求解優(yōu)化問(wèn)題，文獻(xiàn)[1]中將BCO主要分為5個(gè)階段：1）初始化；2）建立解；3）適應(yīng)度評(píng)估；4）忠誠(chéng)度評(píng)估；5）招募蜂選擇。第1）階段為算法參數(shù)設(shè)置初始值，第2）階段通過(guò)幾輪迭代建立解空間，之后3個(gè)階段則根據(jù)不同的應(yīng)用場(chǎng)景作不同的設(shè)計(jì)[2]。BCO的優(yōu)點(diǎn)是在探測(cè)的早期階段可以調(diào)整搜索方向，而其他的群體智能（Swarm Intelligence， SI）算法不具備該特點(diǎn)，例如蟻群優(yōu)化算法（Ant Colony Optimization， ACO）需要蟻群完全遍歷所有路徑最終根據(jù)信息素選擇最優(yōu)路徑。大多SI算法均具有極高的隨機(jī)性，

該特點(diǎn)的好處是提高了算法的探測(cè)能力，但導(dǎo)致了搜索能力的降低[3]。

BCO的每輪迭代均需執(zhí)行上述的3）、4）、5）三個(gè)階段，而為了提高BCO的搜索能力，本文對(duì)4）、5）兩個(gè)階段進(jìn)行了新的設(shè)計(jì)，提高蜂群搜索的方向性，從而提高搜索的性能。

特征選擇是模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域極為重要的處理階段，其通過(guò)選擇原始特征集合中的重要特征構(gòu)成特征子集以實(shí)現(xiàn)數(shù)據(jù)的降維處理，其性能優(yōu)劣直接影響之后的挖掘效果[4-5]，特征選擇保留的是原始物理特征，因此，可以真正地降低存儲(chǔ)需要、測(cè)量需求、計(jì)算開(kāi)銷(xiāo)等[6]。特征選擇對(duì)于構(gòu)建一個(gè)簡(jiǎn)潔、高效的分類(lèi)系統(tǒng)有重要作用，它不僅可以揭示系統(tǒng)所隱藏的潛在模式和規(guī)律，還使分類(lèi)結(jié)果的可視化成為可能[7]。特征選擇方法依據(jù)其與分類(lèi)器的關(guān)系分為過(guò)濾式、封裝式與嵌入式三類(lèi)方法。過(guò)濾式方法根據(jù)每一個(gè)特征對(duì)分類(lèi)貢獻(xiàn)的大小，定義其重要度，選擇重要的特征構(gòu)成特征子集；封裝式方法依賴(lài)于學(xué)習(xí)過(guò)程，將訓(xùn)練樣本分成訓(xùn)練子集和測(cè)試子集兩部分。顯然，基于人工智能的特征選擇方法屬于封裝式方法，文獻(xiàn)[8-14]均為近期基于人工智能的特征選擇算法，雖然獲得了較好的效果，但是大多數(shù)此類(lèi)算法并未結(jié)合特征選擇的特點(diǎn)作深入的設(shè)計(jì)，從而其性能依然具有提高的空間。

本文不僅設(shè)計(jì)了新算法將蜂群引向價(jià)值較高的食物源，提高BCO的搜索能力，同時(shí)為食物源引入局部權(quán)重的概念，并評(píng)估該局部權(quán)重與樣本類(lèi)標(biāo)簽的相關(guān)性，將特征選擇問(wèn)題建模為離散優(yōu)化問(wèn)題，從而實(shí)現(xiàn)BCO食物源不僅考慮了蜂群搜索的性能，同時(shí)考慮特征選擇的類(lèi)標(biāo)簽。實(shí)驗(yàn)結(jié)果表明，本文特征選擇算法具有較好的泛化效果，也使得分類(lèi)器獲得了較好的分類(lèi)精確率。

1 增強(qiáng)的蜂群優(yōu)化算法

上文指出傳統(tǒng)BCO隨機(jī)地分配雇傭蜂，導(dǎo)致搜索能力不足，為了解決該問(wèn)題，本文基于文獻(xiàn)[1]提出一種改進(jìn)的BCO算法，簡(jiǎn)稱(chēng)EBCO算法。圖1所示是本文方法的總體簡(jiǎn)介，本文設(shè)計(jì)了雙權(quán)重分配方法以提高食物源搜索的方向性，此外通過(guò)權(quán)重程序評(píng)估蜂群對(duì)食物源的忠誠(chéng)度，然后使用兩步篩選機(jī)制從未雇傭蜂中選擇招募蜂。

1.1 參數(shù)初始化

本文方法的初始化參數(shù)根據(jù)實(shí)驗(yàn)結(jié)果選擇最優(yōu)參數(shù)組合，以期獲得最佳的特征選擇效率與性能，本文假設(shè)蜂群數(shù)量為B，迭代次數(shù)G，建立解所需的迭代次數(shù)為NC。

1.2 建立局部解

建立局部解的過(guò)程中，每輪搜索之后，蜂群返回蜂巢評(píng)估其適應(yīng)度與忠誠(chéng)度，然后將蜂群分為招募蜂與跟隨蜂。蜜蜂需要NC次迭代創(chuàng)建一個(gè)局部解，該階段蜂群隨機(jī)地搜索解空間，圖2所示是局部解建立程序的流程。

算法1評(píng)估每個(gè)預(yù)測(cè)的類(lèi)標(biāo)簽對(duì)食物源的依賴(lài)程度，最終使用式（5）測(cè)量每個(gè)食物源的局部權(quán)重（第7）行）。如果某個(gè)食物源對(duì)類(lèi)標(biāo)簽的相關(guān)性（貢獻(xiàn)度）較高，則認(rèn)為該食物源價(jià)值較高。簡(jiǎn)言之，如果某個(gè)食物源提高了數(shù)據(jù)的分類(lèi)精確率，則認(rèn)為該食物源價(jià)值較高。

僅考慮相關(guān)性評(píng)估可能對(duì)蜂群產(chǎn)生誤導(dǎo)，因此需要融合適應(yīng)度值解決該問(wèn)題。如果適應(yīng)度值與局部權(quán)重的均值較高，則認(rèn)為該食物源為高質(zhì)量食物源，因此，需要考慮適應(yīng)度值適當(dāng)?shù)卣{(diào)節(jié)食物源的局部權(quán)重，最終的忠誠(chéng)度估算方法如式（6）定義：

獲得忠誠(chéng)度之后，則可通過(guò)多種方法劃分雇傭蜂與非雇傭蜂，本文選擇忠誠(chéng)度較高的作為雇傭蜂。

1.4 適應(yīng)度與性能評(píng)估

本文EBCO應(yīng)用于特征選擇問(wèn)題，因此適應(yīng)度函數(shù)設(shè)為分類(lèi)準(zhǔn)確率[15]。

1.5 兩步篩選招募算法

傳統(tǒng)BCO基于輪盤(pán)賭方法分配招募蜂[16]，由此會(huì)引起兩個(gè)情況：

1）大量的未雇傭蜂跟隨少量的雇傭蜂，而大量的雇傭蜂仍然沒(méi)有跟隨者。

2）每個(gè)雇傭蜂被一個(gè)以上的未雇傭蜂更隨。

對(duì)于第1）種情況，其種群多樣性較低，較多蜜蜂的解相似而導(dǎo)致早熟收斂，并且降低了蜂群的搜索能力。為了解決該問(wèn)題，本文提出一種兩步篩選分配算法：

第一步 如果某個(gè)雇傭蜂與跟隨蜂搜索的食物源相近，則該跟隨蜂傾向于跟隨該雇傭蜂，該數(shù)學(xué)模型如下：

圖4、5中每個(gè)行對(duì)應(yīng)一個(gè)蜜蜂，第1列是蜜蜂的標(biāo)識(shí)符； 第2～6列的每列對(duì)應(yīng)一個(gè)食物源，其中1與0分別表示該食物源是否被選擇； 第7列表示該蜜蜂是否被招募（C表示分配（Committed），U表示未分配（Uncommitted））；最后一列是蜜蜂的適應(yīng)度值。

本文兩步分配方法的主要優(yōu)點(diǎn)是有助于提高算法的搜索能力：本方法使跟隨蜂跟隨相似的領(lǐng)蜂加強(qiáng)蜂群的搜索能力，同時(shí)并保持多樣性。圖5所示是兩步篩選分配流程：第一步：基于未雇傭蜂與雇傭蜂的相似性進(jìn)行招募；第二步：根據(jù)適應(yīng)度值從相似蜂群中篩選招募蜂。

為了使用EBCO算法優(yōu)化特征選擇問(wèn)題，需將特征選擇問(wèn)題建模為離散優(yōu)化問(wèn)題。因此使用二值格式（1與0）表示某個(gè)特征是否被選擇，數(shù)據(jù)集的特征數(shù)量應(yīng)該與解長(zhǎng)度相等。例如一個(gè)解為1111100000，表示選擇前五個(gè)特征。

EBCO_FS初始化之后，每個(gè)蜜蜂獨(dú)立地向前移動(dòng)，移動(dòng)距離為NC，即每個(gè)蜜蜂決定是否選擇前NC個(gè)特征。算法2是創(chuàng)建局部解的程序，特征總數(shù)量設(shè)為F，x表示前幾個(gè)剩余特征，將每個(gè)蜜蜂的開(kāi)始位置設(shè)為第一個(gè)特征（第1）、2）行）。然后進(jìn)行NC長(zhǎng)度的局部解創(chuàng)建步驟（第4）～9）行）。在一些情況下，剩余特征的數(shù)量可能低于預(yù)設(shè)的NC值（第12）行），因此蜜蜂將x作為其N(xiāo)C值。

從表3可以看出，EBCO的性能易受解空間大小與蜂群數(shù)量的影響，主要原因是在評(píng)估忠誠(chéng)度與兩步篩選招募方法中使用了較多的種群信息。實(shí)驗(yàn)結(jié)果可看出，蜂群數(shù)量越大，因?yàn)镋BCO可從多個(gè)方式來(lái)評(píng)估忠誠(chéng)度，可篩選出較好的跟隨蜂，因此優(yōu)化性能越好。同時(shí)EBCO與標(biāo)準(zhǔn)BCO以及其他兩種改進(jìn)BCO方法相比，EBCO具有一定的優(yōu)勢(shì)，可見(jiàn)本方法對(duì)BCO進(jìn)行了有效的增強(qiáng)。

3.2 基于EBCO特征選擇算法的性能

對(duì)基于EBCO的特征選擇算法進(jìn)行測(cè)試，使用8個(gè)標(biāo)準(zhǔn)的UCI Benchmark數(shù)據(jù)集，如表4所示。首先學(xué)習(xí)訓(xùn)練樣本集，然后對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分類(lèi)處理，實(shí)驗(yàn)將數(shù)據(jù)集分為三個(gè)子集分別用于訓(xùn)練、測(cè)試與驗(yàn)證，將一個(gè)數(shù)據(jù)集70%分為訓(xùn)練、20%分為驗(yàn)證、10%分為測(cè)試。

EBCO_FS算法EBCO部分參數(shù)與3.1節(jié)一致，因?yàn)?00次迭代之后實(shí)驗(yàn)結(jié)果僅具有極小的提高，所以每組獨(dú)立實(shí)驗(yàn)的迭代次數(shù)設(shè)為100，根據(jù)上文實(shí)驗(yàn)結(jié)果，將種群大小設(shè)為5000。基于訓(xùn)練集的對(duì)比實(shí)驗(yàn)?zāi)繕?biāo)是測(cè)試算法創(chuàng)建模型的效果，訓(xùn)練之后，使用測(cè)試數(shù)據(jù)集測(cè)試本算法的性能。在訓(xùn)練實(shí)驗(yàn)中，對(duì)訓(xùn)練集與驗(yàn)證集進(jìn)行各特征選擇算法，并且保存每輪的最優(yōu)解。在測(cè)試實(shí)驗(yàn)中，利用訓(xùn)練實(shí)驗(yàn)的每輪最優(yōu)解，對(duì)測(cè)試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，每輪迭代取其迭代最優(yōu)值，結(jié)果從100個(gè)最優(yōu)值中（迭代次數(shù)）取均值。

其中TS與TC分別是樣本總數(shù)量與正確分類(lèi)樣本的數(shù)量。

實(shí)驗(yàn)中，將EBCO_FS與基于差異的人工蜂群算法（Dissimilarity based Artificial Bee Colony， DisABC）[9]和蜂群優(yōu)化特征選擇算法（Feature Selection based on Bee Colony Optimization， BCOFS）[13]進(jìn)行比較，表5所示是特征選擇的實(shí)驗(yàn)結(jié)果，訓(xùn)練集實(shí)驗(yàn)的結(jié)果顯示，對(duì)于大多數(shù)數(shù)據(jù)集，EBCO_FS算法均優(yōu)于BCOFS與DisABC算法；而對(duì)于測(cè)試集的實(shí)驗(yàn)結(jié)果顯示了本方法具有絕對(duì)的優(yōu)勢(shì)。可見(jiàn)本文的兩步篩選招募方法與雙權(quán)重食物源分配方法提高了BCO的搜索能力，同時(shí)保持了BCO較好的樣本多樣性，并且獲得了較好的特征選擇效果。

4 結(jié)語(yǔ)

本文設(shè)計(jì)了新算法將蜂群引向價(jià)值較高的食物源，提高BCO的搜索能力，同時(shí)為食物源引入局部權(quán)重的概念，并評(píng)估該局部權(quán)重與樣本類(lèi)標(biāo)簽的相關(guān)性，將特征選擇問(wèn)題建模為離散優(yōu)化問(wèn)題，從而使得BCO食物源不僅考慮了蜂群搜索的性能，同時(shí)考慮特征選擇的類(lèi)標(biāo)簽。實(shí)驗(yàn)結(jié)果證明本文的兩步篩選招募方法與雙權(quán)重食物源分配方法提高了BCO的搜索能力，同時(shí)保持了BCO較好的樣本多樣性，并且獲得了較好的特征選擇效果。

參考文獻(xiàn)：

[1]TEODOROVIC D， LUCIC P， MARKOVIC G， et al. Bee colony optimization： principles and applications[C]// Proceedings of the 8th Seminar on Neural Network Applications in Electrical Engineering. Piscataway， NJ： IEEE， 2006：151-156.

[2]NIKOLIC M， TEODOROVIC D. Empirical study of the Bee Colony Optimization （BCO） algorithm[J]. Expert Systems with Applications， 2013， 40（11）：4609-4620.

[3]KANG F， LI J， MA Z. Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions[J]. Information Sciences， 2011， 181（16）：3508-3531.

[4]張振海， 李士寧， 李志剛，等. 一類(lèi)基于信息熵的多標(biāo)簽特征選擇算法[J]. 計(jì)算機(jī)研究與發(fā)展， 2013， 50（6）：1177-1184.（ZHANG Z H， LI S N， LI Z G， et al. Multilabel feature selection algorithm based on information entropy[J]. Journal of Computer Research and Development， 2013， 50（6）： 1177-1184.）

[5]謝娟英， 謝維信. 基于特征子集區(qū)分度與支持向量機(jī)的特征選擇算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2014， 37（8）：1704-1718.（XIE J Y， XIE W X. Several feature selection algorithms based on the discernibility of a feature subset and support vector machines[J]. Chinese Journal of Computers， 2014， 37（8）：1704-1718.）

[6]BOLNCANEDO V， SNCHEZMAROO N， ALONSOBETANZOS A. A review of feature selection methods on synthetic data[J]. Knowledge & Information Systems， 2013， 34（3）：483-519.

[7]代旺， 方昱春， 李楊. 融合過(guò)濾和封裝方式的特征選擇算法[J]. 計(jì)算機(jī)工程， 2012， 38（24）：166-170.（DAI W， FANG Y C， LI Yang. Feature selection algorithm fused with filtering and packaging mode[J]. Computer Engineering， 2012， 38（24）： 166-170.）

[8]DZIWINSKI P， LUKASZ BARTCZUK， STARCZEWSKI J T. Fully controllable ant colony system for text data clustering[C]// Proceedings of the 2012 International Symposia on Swarm and Evolutionary Computation. Berlin： Springer， 2012：199-205.

[9]KASHAN M H， NAHAVANDI N， KASHAN A H. DisABC： a new artificial bee colony algorithm for binary optimization[J]. Applied Soft Computing， 2012， 12（1）：342-352.

[10]ASAD A H， AZAR A T， HASSAANIEN A E O. A comparative study on feature selection for retinal vessel segmentation using ant colony system[C]// Proceedings of the 2nd International Symposium on Intelligent Informatics. Berlin： Springer， 2014， 235：1-11.

[11]楊鴻章.基于蟻群算法特征選擇的語(yǔ)音情感識(shí)別[J]. 計(jì)算機(jī)仿真， 2013， 30（4）：377-381.（YANG H Z. Feature selection of speech emotional recognition based on ant colony optimization algorithm[J]. Computer Simulation， 2013， 30（4）：377-381.）

[12]PALANISAMY S， KANMANI S. Artificial bee colony approach for optimizing feature selection[J]. International Journal of Computer Science Issues， 2012， 9（3）：432-438.

[13]FORSATI R， MOAYEDIKIA A， SHAMSFARD M， et al. A novel approach for feature selection based on the bee colony optimization[J]. International Journal of Computer Applications， 2012， 43（8）：13-16.

[14]RAKSHIT P， BHATTACHARYYA S， KONAR A， et al. Artificial bee colony based feature selection for motor imagery EEG data[C]// Proceedings of Seventh International Conference on BioInspired Computing： Theories and Applications. Berlin： Springer， 2013：127-138.

[15]FORSATI R， MOAYEDIKIA A， JENSEN R， et al. Enriched ant colony optimization and its application in feature selection[J]. Neurocomputing， 2014， 142（1）：354-371.

[16]TEODOROVIC D， LUCIC P， MARKOVIC G， et al. Bee colony optimization： principles and applications[C]// Proceedings of the 8th Seminar on Neural Network Applications in Electrical Engineering. Piscataway， NJ： IEEE， 2006：151-156.

[17]ALZAQEBAH M， ABDULLAH S. Hybrid bee colony optimization for examination timetabling problems[J]. Computers & Operations Research， 2015， 54（54）：142-154.

[18]LU P， ZHOU J， ZHANG H， et al. Chaotic differential bee colony optimization algorithm for dynamic economic dispatch problem with valvepoint effects[J]. International Journal of Electrical Power & Energy Systems， 2014， 62（11）：130-143.