2020, Vol. 41
2. 吉林大学 软件学院, 吉林 长春 130012
2. College of Software, Jilin University, Changchun 130012, China
近年来，许多涉及信息的领域中产生了包含众多特征的高维数据，然而并不是所有特征都是重要的.许多特征甚至是不相关或冗余的，这不仅使数据处理过程变得困难，还降低了学习算法的效率，如分类算法等学习算法的性能[1].特征选择旨在利用一种选择策略，消除不相关和冗余的特征，找到最佳特征子集[2].特征选择是一个复杂的问题，对于一个有n个特征的数据集，可能的解决方案的总数是2n-1[3]，其搜索空间十分庞大.因此，用穷举搜索选择一组最优特征的时间复杂度是O(2n)[4]，这在大多数情况下是不切实际的.与传统方法相比，基于演化算法的特征选择方法更适合于解决这种问题.
本文设计了一种基于随机二元蚁群网络的特征选择方法，更换了启发式因子的计算方法，并提出了一种新的信息素更新思路，将整体的信息素量子化，赋予每个信息素生命周期，形成了量子化信息素蚁群优化(quantized pheromone ant colony optimization, QPACO)特征选择算法.
1 相关工作近年来，基于演化计算的特征选择算法受到了广泛研究，基于演化计算的特征选择算法已发表论文超过500篇[1].
1.1 演化计算用于特征选择基于演化计算的特征选择算法的研究近年来取得了较为令人满意的结果.如Rashedi等提出了通过增强传递函数克服停滞问题的IBGSA[5]，IBGSA将二进制向量每个位与一个特征相关联，通过寻找最优二进制向量找到特征选择的最优解；Chuang等在二元粒子群算法BPSO中引入鲶鱼效应，提出了Catfish BPSO[6]，Catfish BPSO将局部最优中的粒子通过鲶鱼效应引导到新的搜索空间，同时使用种群中最差的适应值替换10%的原始粒子，最终避免了局部最优，进一步获得了更好的解；初蓓等提出了改进的森林优化特征选择算法IFSFOA[7]，采用了新的初始化策略和更新机制进一步提高原始算法的性能.
1.2 蚁群优化算法用于特征选择本文主要讨论基于蚁群优化算法的特征选择算法.蚁群优化(ant colony optimization, ACO)算法是Dorigo等提出的一种演化算法[8].蚂蚁之间的通信会产生正反馈行为，引导蚁群收敛到最优解.蚁群路径上分布的信息素模拟了真实蚂蚁所经过的路线上的化学物质[9].
基于蚁群优化算法解决特征选择的主要思想是将问题建模为求解搜索图的最小成本路径问题，创建一个包含节点的搜索空间并设计一个程序来寻找解决方案的路径，蚂蚁的路径表示特征的子集.ACO算法基于信息素和启发式信息计算蚂蚁选择解路径的转移概率.Chen等使用这种类型的ACO算法进行特征选择，提出了ACOFS[10]，ACOFS中使用了F_score标准作为启发式值，但采用了不同的信息素更新策略；Kashef等提出了一种优化的二元蚁群算法ABACO[11]，该算法的不同之处在于每个特征都有两个节点，一个节点用于选择，另一个节点用于取消选择相应的特征，最优特征子集是满足遍历停止条件的最小节点数的蚂蚁遍历图.
与上述特征选择算法相比，本文提出的QPACO算法，采用了新的启发式因子的计算方法，改变了传统的信息素的更新策略，避免了搜索特征时的局部最优，提高了特征选择的精度.
2 QPACO算法 2.1 基于蚁群优化算法的特征选择算法基于蚁群优化算法的特征选择算法首先构造了由n个特征组成的有向图，假设蚂蚁在初始时刻被随机放置在n个特征节点中，并维护一张禁忌列表记录每只蚂蚁已经访问过的节点，每条边的信息素τi, j初始值为0，蚂蚁依据边上的信息素计算在t次迭代时，蚂蚁k从特征i移动到特征j的概率：
|
(1) |
式中：S是蚂蚁k的禁忌列表；α是信息启发因子；β是期望启发式因子，用于分配启发式信息和信息素浓度的权重；ηi, j是启发式信息，通常计算为
|
(2) |
式中, di, j是特征i与特征j之间的欧几里得度量.
当蚂蚁完成一次迭代后，每条路径上的信息素都会进行更新：
|
(3) |
式中：p为权重系数(0 < p < 1)；m为蚂蚁总数；Δτi, jk为蚂蚁k在此次迭代时特征i到特征j之间的信息素增量，其计算如下：
|
(4) |
式中：Q为常数；Lk为蚂蚁k在此次迭代中的路径长度.
基于蚁群优化算法的特征选择算法在特征选择领域上有一定的作用，但仍存在一些不足，因此提出了许多不同版本的改进.
2.2 二元蚁群优化特征选择算法二元蚁群优化(binary ant colony optimization, BACO)特征选择算法是另一种常用的求解算法.该方法仅允许全局最优蚂蚁存放信息素，并采用最大最小策略进行信息素更新，即信息素轨迹被限制在[min，max]区间内，其中min和max是满足min < max的任意正实数.这里，节点表示特征，其中每个节点包含两个子节点：0和1.首先，所有蚂蚁都在比特串的开始节点，然后通过选择不同的子节点爬向终止节点.如果蚂蚁选择第i个特征的子节点为1或0，则代表着该特征被该蚂蚁选择或未选择.假设在迭代中0到1(0→1)之间的子路径的优选概率被计算，计算公式为
|
(5) |
式中：p01是与子路径(0→1)相关联的概率；τ00和τ01是子路径(0→0和0→1)上的信息素.
虽然BACO能够在短时间内找到近似最优解，但是它依旧面临着一些问题，如蚂蚁对特征的看法有限及特征选择的准确率有待提高.在本文提出的算法中，尝试结合传统的ACO和BACO来解决上述问题.
2.3 量子化蚁群优化特征选择算法鉴于现有算法的准确率仍待提高，经过研究，本文提出了量子化信息素蚁群优化特征选择算法QPACO.
2.3.1 路径转移概率计算蚂蚁在特征图中的转移按照概率进行，在QPACO算法中，每一个特征均包含其子节点1或0，则意味着该特征被该蚂蚁选择或未选择.那么在特征i与j之间，显然存在4条路径(0→0, 0→1, 1→0, 1→1).这些路径上的转移概率计算方式如下：
|
(6) |
式中：ix，jy分别表示特征i和j中的子节点；C表示蚂蚁能够访问且尚未被访问到的节点集合；τ表示子节点间的信息素；η表示子节点间的启发式信息；α和β是确定信息素和启发信息值的两个参数.
2.3.2 信息素τ的计算与更新在一般的蚁群和蚁群变种的特征选择算法中，通常人们采用设定一个常量q(0 < q < 1，一般为0.6~0.8)来模拟信息素的消失：
|
(7) |
式中：q为信息素模拟消失常量；τold为原来的信息素值；τnew为更新后的信息素值；Δτ为信息素变化量.
QPACO算法中提出了一种新的信息素挥发方式，即把信息素量子化，看成是一份一份有着时间标记的信息素单元，每一单元信息素都有着属于自己的生命周期，当自己生命周期结束时挥发，其简化公式如下：
|
(8) |
式中，τdead为在该次迭代中生命周期结束的信息素量.
考虑到信息素值的上下限问题，因此在k次迭代时信息素的更新τnew和信息素更新量的记录Δτk计算如下：
|
(9) |
式中：
在参考了众多η的计算方法后，发现基于F_score的改进启发式度量方式更适用于本文的算法.
F_score是用于评价特征识别能力的度量，第i个特征的F_score公式为
|
(10) |
式中：c为类别的数目；xit为类别t(t=1, 2, …, c)中特征i(i=1, 2, …, n)的平均值；xi为所有类别中特征i(i=1, 2, …, n)的平均值；n为特征的数目；Nis为类别s(s=1, 2, …, c)中特征i(i=1, 2, …, n)的样本数；xi, us为类别s(s=1, 2, …, c)中特征i(i=1, 2, …, n)的第u(u=1, 2, …, Nis)次训练样本数；xis为类别s(s=1, 2, …, c)中特征i(i=1, 2, …, n)的平均值.
越大的F_score意味着该特征具有判别力的可能性越大[12]，使用该标准的边的启发信息计算如下：
|
(11) |
式中：ηix, jy代表特征i取值为x时与特征j取值为y时所构成的边上的启发式信息(x和y的取值均为0或1)；n为特征的数目；ξ为常量(通常取值在0~1之间).
2.4 QPACO算法伪代码QPACO算法伪代码见表 1.
|
表 1 QPACO算法伪代码 Table 1 Pseudo code of QPACO algorithm |
本文从UCI数据库中选择了一些典型的数据集对算法进行验证.典型的数据集见表 2.
|
|
表 2 UCI数据集 Table 2 UCI datasets |
为了更好地展现算法的可比性，选择了一些具有代表性的特征选择算法与本文算法进行比较，其中包括Catfish BPSO[6]、改进二元引力搜索(IBGSA)[5]、基于蚁群优化算法的特征选择算法ACOFS[10]和ABACOH[13]、改进的森林优化特征选择算法IFSFOA[7]和二元蝴蝶优化特征选择算法S-bBOA[14]等.
3.2 实验环境、评估指标及实验参数 3.2.1 实验环境实验中使用了python 3.6实现了本文的算法，同时使用了公开的工具包scikit-learn.所有实验均在一台配置为Intel Core i5-4210H(CPU)，8GB内存、1TB硬盘的计算机上完成.
3.2.2 评估指标在本实验中，使用分类精度(Ac)、精确率(Rp)，召回率(Rrecall)和维度缩减率(Rf)来评估所提出的算法性能.
分类精度(Ac)，即正确分类的样本数和测试集的总样本数的百分比，其定义为
|
(12) |
精确率(Rp)和召回率(Rrecall)计算式如下：
|
(13) |
|
(14) |
其中：TPi为第i类下正确分类的测试样本数；FPi为第i类下错误分类的测试样本数；FNi为在其他类别下错误分类的测试样本数.
定义维度缩减率(Rf)如下：
|
(15) |
其中：n是总特征数；p是算法所选择的特征数.
3.2.3 算法参数设置在QPACO算法与其他算法的对比实验中，统一设置了算法的一些参数：所有算法的种群数量和迭代次数为50；在每次实验中，60%的样本随机选择进行训练，剩下40%的样本用于测试；实验结果在每个数据集和算法中独立运行超过20次，最后统计平均值；挥发系数ρ为0.049；每条路径上的最小和最大信息素强度分别设定为0.1和6；每个边缘的初始信息素强度设定为0.1；α和β是决定信息素和启发信息的相对重要性的两个参数，设α=1，β=0.5；在分类器的选择上，使用了K近邻(KNN)分类器作为基分类器，并将参数K设置为1.
3.3 实验结果与分析 3.3.1 实验结果为了确保对比实验的准确性，表 3与表 4中的部分数据采用了文献[13]中的实验结果，表 3是QPACO算法与其对比算法在不同数据集上的分类精度的对比.表 4是QPACO算法与其对比算法在不同数据集上的精确率、召回率及维度缩减率的对比，最后一列为每个算法在所有数据集上的指标和，和越大说明算法总体性能越好.
|
|
表 3 QPACO及其对比算法的平均分类精度对比 Table 3 Comparison of average classification accuracy about QPACO and its comparison algorithms |
|
|
表 4 QPACO及其对比算法的精确率、召回率、维度缩减率对比 Table 4 Comparison of precision, recall and feature-reduction about QPACO and its comparison algorithms |
QPACO算法在时间效率上是基本等同于二元蚁群优化算法的，在算法的改进过程中，计算和记录每次信息素的更新量，以及查找生命周期结束信息素量的时间复杂度都是O(1)，因此时间上的开销差距并不明显，所以本文遵从了相关的基于演化计算的特征选择方法的实验设计模式，并未采用时间效率来衡量算法性能[13-17]，但计算了其他常用的评估指标进行算法间的对比.
对比分类精度，从表 3中不难看出，QPACO算法在Glass，Letter，Shuttle，Spambase，Waveform，Wisconsin这些数据集上均位居第一，在Wine和Yeast上位居第二，只在Vehicle上稍显逊色.因此QPACO算法在分类精度上有了很明显的提升.通过对比表 4中的精确率、召回率以及维度缩减率，发现QPACO算法大多数情况下精确率和召回率都略高于其他算法，且维度缩减率维持在平均水平以上.
4 结论本文提出了基于传统蚁群优化算法和二元蚁群优化算法的量子化信息素蚁群优化(QPACO)特征选择算法.QPACO算法中将信息素量子化，赋予每个信息素单独的生命周期，同时修改了启发式因子的更新方式，增强了算法的搜索能力.经过9个数据集和9个特征选择算法的对比实验，验证了QPACO算法良好的性能.如何在高维数据集中应用QPACO算法进行特征选择问题的求解，将是下一步重点研究的内容.
| [1] |
Xue B, Zhang M, Browne W N, et al. A survey on evolutionary computation approaches to feature selection[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(4): 606-626. DOI:10.1109/TEVC.2015.2504420 |
| [2] |
Zhang Z, Bai L, Liang Y, et al. Joint hypergraph learning and sparse regression for feature selection[J]. Pattern Recognition, 2017, 63: 291-309. DOI:10.1016/j.patcog.2016.06.009 |
| [3] |
Guyon I, Elisseeff A. An introduction to variable and feature selection[J]. Journal of Machine Learning Research, 2003, 3(6): 1157-1182. |
| [4] |
Tan K C, Teoh E J, Yu Q, et al. A hybrid evolutionary algorithm for attribute selection in data mining[J]. Expert Systems with Applications, 2009, 36(4): 8616-8630. DOI:10.1016/j.eswa.2008.10.013 |
| [5] |
Rashedi E, Nezamabadipour H. Feature subset selection using improved binary gravitational search algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2014, 26(3): 1211-1221. |
| [6] |
Chuang L Y, Tsai S W, Yang C H. Improved binary particle swarm optimization using catfish effect for feature selection[J]. Expert Systems with Applications, 2011, 38(10): 12699-12707. DOI:10.1016/j.eswa.2011.04.057 |
| [7] |
初蓓, 李占山, 张梦林, 等. 基于森林优化特征选择算法的改进研究[J]. 软件学报, 2018, 29(9): 2547-2558. (Chu Bei, Li Zhan-shan, Zhang Meng-lin, et al. Research on improvements of feature selection using forest optimization algorithm[J]. Journal of Software, 2018, 29(9): 2547-2558.) |
| [8] |
Dorigo M, Caro G D.Ant colony optimization: a new meta-heuristic[C]//Proceedings of the 1999 Congress on Evolutionary Computation.Washington D C, 1999: 1470-1477. http://www.researchgate.net/publication/3810360_Ant_colony_optimization_a_new_meta-heuristic
|
| [9] |
Dorigo M, Birattari M, Stützle T. Ant colony optimization:artificial ants as a computational intelligence technique[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39. DOI:10.1109/MCI.2006.329691 |
| [10] |
Chen B, Chen L, Chen Y. Efficient ant colony optimization for image feature selection[J]. Signal Processing, 2013, 93(6): 1566-1576. DOI:10.1016/j.sigpro.2012.10.022 |
| [11] |
Kashef S, Nezamabadi-Pour H.A new feature selection algorithm based on binary ant colony optimization[C]//The 5th Conference on Information and Knowledge Technology.Shiraz, Iran, 2013: 50-54.
|
| [12] |
Huang C L. ACO-based hybrid classification system with feature subset selection and model parameters optimization[J]. Neurocomputing, 2009, 73(1/2/3): 438-448. |
| [13] |
Kashef S, Nezamabadi-Pour H. An advanced ACO algorithm for feature subset selection[J]. Neurocomputing, 2015, 147: 271-279. DOI:10.1016/j.neucom.2014.06.067 |
| [14] |
Arora S, Anand P. Binary butterfly optimization approaches for feature selection[J]. Expert Systems with Applications, 2019, 116: 147-160. DOI:10.1016/j.eswa.2018.08.051 |
| [15] |
Mafarja M M, Mirjalili S. Hybrid whale optimization algorithm with simulated annealing for feature selection[J]. Neurocomputing, 2017, 260: 302-312. DOI:10.1016/j.neucom.2017.04.053 |
| [16] |
Emary E, Zawbaa H M, Hassanien A E. Binary grey wolf optimization approaches for feature selection[J]. Neurocomputing, 2016, 172: 371-381. DOI:10.1016/j.neucom.2015.06.083 |
| [17] |
Zhang Y, Song X, Gong D. A return-cost-based binary firefly algorithm for feature selection[J]. Information Sciences, 2017, 418/419: 561-574. DOI:10.1016/j.ins.2017.08.047 |