基于增强蜂群优化算法的特征选择算法

张霞 庞秀平

摘要：针对传统蜂群优化（BCO）算法探测能力强但搜索能力较弱的问题，提出一种搜索能力增强的BCO算法，并将其应用于数据特征选择问题以提高特征选择的性能。首先，为食物源引入全局权重的概念，用以评估各食物源对种群的重要性，降低蜂群搜索的随机性；然后，设计了两步筛选的招募方法提高蜂群搜索能力并保持多样性；最终，为食物源引入局部权重的概念，用于评估某个食物源与类标签的相关性，从而优化解特征选择问题。仿真实验结果表明，所提方法可以明显提高BCO的优化效果，同时获得了较好的特征选择效果，并且优于基于差异的人工蜂群算法（DisABC）和蜂群优化特征选择算法（BCOFS）。

关键词：特征选择；蜂群优化算法；食物源；类标签；全局权重；招募算法

中图分类号：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 引言

蜂群优化（Bee Colony Optimization， BCO）算法[1]是一种较好的人工智能算法，该方法模拟自然中蜂群的行为以求解优化问题，文献[1]中将BCO主要分为5个阶段：1）初始化；2）建立解；3）适应度评估；4）忠诚度评估；5）招募蜂选择。第1）阶段为算法参数设置初始值，第2）阶段通过几轮迭代建立解空间，之后3个阶段则根据不同的应用场景作不同的设计[2]。BCO的优点是在探测的早期阶段可以调整搜索方向，而其他的群体智能（Swarm Intelligence， SI）算法不具备该特点，例如蚁群优化算法（Ant Colony Optimization， ACO）需要蚁群完全遍历所有路径最终根据信息素选择最优路径。大多SI算法均具有极高的随机性，

该特点的好处是提高了算法的探测能力，但导致了搜索能力的降低[3]。

BCO的每轮迭代均需执行上述的3）、4）、5）三个阶段，而为了提高BCO的搜索能力，本文对4）、5）两个阶段进行了新的设计，提高蜂群搜索的方向性，从而提高搜索的性能。

特征选择是模式识别、数据挖掘等领域极为重要的处理阶段，其通过选择原始特征集合中的重要特征构成特征子集以实现数据的降维处理，其性能优劣直接影响之后的挖掘效果[4-5]，特征选择保留的是原始物理特征，因此，可以真正地降低存储需要、测量需求、计算开销等[6]。特征选择对于构建一个简洁、高效的分类系统有重要作用，它不仅可以揭示系统所隐藏的潜在模式和规律，还使分类结果的可视化成为可能[7]。特征选择方法依据其与分类器的关系分为过滤式、封装式与嵌入式三类方法。过滤式方法根据每一个特征对分类贡献的大小，定义其重要度，选择重要的特征构成特征子集；封装式方法依赖于学习过程，将训练样本分成训练子集和测试子集两部分。显然，基于人工智能的特征选择方法属于封装式方法，文献[8-14]均为近期基于人工智能的特征选择算法，虽然获得了较好的效果，但是大多数此类算法并未结合特征选择的特点作深入的设计，从而其性能依然具有提高的空间。

本文不仅设计了新算法将蜂群引向价值较高的食物源，提高BCO的搜索能力，同时为食物源引入局部权重的概念，并评估该局部权重与样本类标签的相关性，将特征选择问题建模为离散优化问题，从而实现BCO食物源不仅考虑了蜂群搜索的性能，同时考虑特征选择的类标签。实验结果表明，本文特征选择算法具有较好的泛化效果，也使得分类器获得了较好的分类精确率。

1 增强的蜂群优化算法

上文指出传统BCO随机地分配雇佣蜂，导致搜索能力不足，为了解决该问题，本文基于文献[1]提出一种改进的BCO算法，简称EBCO算法。图1所示是本文方法的总体简介，本文设计了双权重分配方法以提高食物源搜索的方向性，此外通过权重程序评估蜂群对食物源的忠诚度，然后使用两步筛选机制从未雇佣蜂中选择招募蜂。

1.1 参数初始化

本文方法的初始化参数根据实验结果选择最优参数组合，以期获得最佳的特征选择效率与性能，本文假设蜂群数量为B，迭代次数G，建立解所需的迭代次数为NC。

1.2 建立局部解

建立局部解的过程中，每轮搜索之后，蜂群返回蜂巢评估其适应度与忠诚度，然后将蜂群分为招募蜂与跟随蜂。蜜蜂需要NC次迭代创建一个局部解，该阶段蜂群随机地搜索解空间，图2所示是局部解建立程序的流程。

算法1评估每个预测的类标签对食物源的依赖程度，最终使用式（5）测量每个食物源的局部权重（第7）行）。如果某个食物源对类标签的相关性（贡献度）较高，则认为该食物源价值较高。简言之，如果某个食物源提高了数据的分类精确率，则认为该食物源价值较高。

仅考虑相关性评估可能对蜂群产生误导，因此需要融合适应度值解决该问题。如果适应度值与局部权重的均值较高，则认为该食物源为高质量食物源，因此，需要考虑适应度值适当地调节食物源的局部权重，最终的忠诚度估算方法如式（6）定义：

获得忠诚度之后，则可通过多种方法划分雇佣蜂与非雇佣蜂，本文选择忠诚度较高的作为雇佣蜂。

1.4 适应度与性能评估

本文EBCO应用于特征选择问题，因此适应度函数设为分类准确率[15]。

1.5 两步筛选招募算法

传统BCO基于轮盘赌方法分配招募蜂[16]，由此会引起两个情况：

1）大量的未雇佣蜂跟随少量的雇佣蜂，而大量的雇佣蜂仍然没有跟随者。

2）每个雇佣蜂被一个以上的未雇佣蜂更随。

对于第1）种情况，其种群多样性较低，较多蜜蜂的解相似而导致早熟收敛，并且降低了蜂群的搜索能力。为了解决该问题，本文提出一种两步筛选分配算法：

第一步 如果某个雇佣蜂与跟随蜂搜索的食物源相近，则该跟随蜂倾向于跟随该雇佣蜂，该数学模型如下：

图4、5中每个行对应一个蜜蜂，第1列是蜜蜂的标识符； 第2～6列的每列对应一个食物源，其中1与0分别表示该食物源是否被选择； 第7列表示该蜜蜂是否被招募（C表示分配（Committed），U表示未分配（Uncommitted））；最后一列是蜜蜂的适应度值。

本文两步分配方法的主要优点是有助于提高算法的搜索能力：本方法使跟随蜂跟随相似的领蜂加强蜂群的搜索能力，同时并保持多样性。图5所示是两步筛选分配流程：第一步：基于未雇佣蜂与雇佣蜂的相似性进行招募；第二步：根据适应度值从相似蜂群中筛选招募蜂。

为了使用EBCO算法优化特征选择问题，需将特征选择问题建模为离散优化问题。因此使用二值格式（1与0）表示某个特征是否被选择，数据集的特征数量应该与解长度相等。例如一个解为1111100000，表示选择前五个特征。

EBCO_FS初始化之后，每个蜜蜂独立地向前移动，移动距离为NC，即每个蜜蜂决定是否选择前NC个特征。算法2是创建局部解的程序，特征总数量设为F，x表示前几个剩余特征，将每个蜜蜂的开始位置设为第一个特征（第1）、2）行）。然后进行NC长度的局部解创建步骤（第4）～9）行）。在一些情况下，剩余特征的数量可能低于预设的NC值（第12）行），因此蜜蜂将x作为其NC值。

从表3可以看出，EBCO的性能易受解空间大小与蜂群数量的影响，主要原因是在评估忠诚度与两步筛选招募方法中使用了较多的种群信息。实验结果可看出，蜂群数量越大，因为EBCO可从多个方式来评估忠诚度，可筛选出较好的跟随蜂，因此优化性能越好。同时EBCO与标准BCO以及其他两种改进BCO方法相比，EBCO具有一定的优势，可见本方法对BCO进行了有效的增强。

3.2 基于EBCO特征选择算法的性能

对基于EBCO的特征选择算法进行测试，使用8个标准的UCI Benchmark数据集，如表4所示。首先学习训练样本集，然后对测试数据集进行分类处理，实验将数据集分为三个子集分别用于训练、测试与验证，将一个数据集70%分为训练、20%分为验证、10%分为测试。

EBCO_FS算法EBCO部分参数与3.1节一致，因为100次迭代之后实验结果仅具有极小的提高，所以每组独立实验的迭代次数设为100，根据上文实验结果，将种群大小设为5000。基于训练集的对比实验目标是测试算法创建模型的效果，训练之后，使用测试数据集测试本算法的性能。在训练实验中，对训练集与验证集进行各特征选择算法，并且保存每轮的最优解。在测试实验中，利用训练实验的每轮最优解，对测试数据集进行实验，每轮迭代取其迭代最优值，结果从100个最优值中（迭代次数）取均值。

其中TS与TC分别是样本总数量与正确分类样本的数量。

实验中，将EBCO_FS与基于差异的人工蜂群算法（Dissimilarity based Artificial Bee Colony， DisABC）[9]和蜂群优化特征选择算法（Feature Selection based on Bee Colony Optimization， BCOFS）[13]进行比较，表5所示是特征选择的实验结果，训练集实验的结果显示，对于大多数数据集，EBCO_FS算法均优于BCOFS与DisABC算法；而对于测试集的实验结果显示了本方法具有绝对的优势。可见本文的两步筛选招募方法与双权重食物源分配方法提高了BCO的搜索能力，同时保持了BCO较好的样本多样性，并且获得了较好的特征选择效果。

4 结语

本文设计了新算法将蜂群引向价值较高的食物源，提高BCO的搜索能力，同时为食物源引入局部权重的概念，并评估该局部权重与样本类标签的相关性，将特征选择问题建模为离散优化问题，从而使得BCO食物源不仅考虑了蜂群搜索的性能，同时考虑特征选择的类标签。实验结果证明本文的两步筛选招募方法与双权重食物源分配方法提高了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]. 计算机研究与发展， 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]谢娟英， 谢维信. 基于特征子集区分度与支持向量机的特征选择算法[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.