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

張霞 龐秀平

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

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

中圖分類號：TP18 文獻標志碼：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)化問題，文獻[1]中將BCO主要分為5個階段：1）初始化；2）建立解；3）適應(yīng)度評估；4）忠誠度評估；5）招募蜂選擇。第1）階段為算法參數(shù)設(shè)置初始值，第2）階段通過幾輪迭代建立解空間，之后3個階段則根據(jù)不同的應(yīng)用場景作不同的設(shè)計[2]。BCO的優(yōu)點是在探測的早期階段可以調(diào)整搜索方向，而其他的群體智能（Swarm Intelligence， SI）算法不具備該特點，例如蟻群優(yōu)化算法（Ant Colony Optimization， ACO）需要蟻群完全遍歷所有路徑最終根據(jù)信息素選擇最優(yōu)路徑。大多SI算法均具有極高的隨機性，

該特點的好處是提高了算法的探測能力，但導致了搜索能力的降低[3]。

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

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

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

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

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

1.1 參數(shù)初始化

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

1.2 建立局部解

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

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

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

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

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

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

1.5 兩步篩選招募算法

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

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

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

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

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

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

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

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

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

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

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

對基于EBCO的特征選擇算法進行測試，使用8個標準的UCI Benchmark數(shù)據(jù)集，如表4所示。首先學習訓練樣本集，然后對測試數(shù)據(jù)集進行分類處理，實驗將數(shù)據(jù)集分為三個子集分別用于訓練、測試與驗證，將一個數(shù)據(jù)集70%分為訓練、20%分為驗證、10%分為測試。

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

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

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

4 結(jié)語

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

參考文獻：

[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]張振海， 李士寧， 李志剛，等. 一類基于信息熵的多標簽特征選擇算法[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]. 計算機學報， 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]代旺， 方昱春， 李楊. 融合過濾和封裝方式的特征選擇算法[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]楊鴻章.基于蟻群算法特征選擇的語音情感識別[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.