量子化信息素蚁群优化特征选择算法

李占山， 刘兆赓， 俞 寅， 鄢文浩

(1.吉林大学 计算机科学与技术学院, 吉林 长春 130012； 2.吉林大学 软件学院, 吉林 长春 130012)

近年来，许多涉及信息的领域中产生了包含众多特征的高维数据，然而并不是所有特征都是重要的.许多特征甚至是不相关或冗余的，这不仅使数据处理过程变得困难，还降低了学习算法的效率，如分类算法等学习算法的性能[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)

(4)

式中：Q为常数；Lk为蚂蚁k在此次迭代中的路径长度.

基于蚁群优化算法的特征选择算法在特征选择领域上有一定的作用，但仍存在一些不足，因此提出了许多不同版本的改进.

2.2 二元蚁群优化特征选择算法

二元蚁群优化(binary ant colony optimization, BACO)特征选择算法是另一种常用的求解算法.该方法仅允许全局最优蚂蚁存放信息素，并采用最大最小策略进行信息素更新，即信息素轨迹被限制在[min，max]区间内，其中min和max是满足min

(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

τnew=τold×q+Δτ.

(7)

式中：q为信息素模拟消失常量；τold为原来的信息素值；τnew为更新后的信息素值；Δτ为信息素变化量.

QPACO算法中提出了一种新的信息素挥发方式，即把信息素量子化，看成是一份一份有着时间标记的信息素单元，每一单元信息素都有着属于自己的生命周期，当自己生命周期结束时挥发，其简化公式如下：

τnew=τold-τdead+Δτ.

(8)

式中，τdead为在该次迭代中生命周期结束的信息素量.

考虑到信息素值的上下限问题，因此在k次迭代时信息素的更新τnew和信息素更新量的记录Δτk计算如下：

(9)

2.3.3 启发式信息η的计算

在参考了众多η的计算方法后，发现基于F_score的改进启发式度量方式更适用于本文的算法.

F_score是用于评价特征识别能力的度量，第i个特征的F_score公式为

F_scorei=

(10)

越大的F_score意味着该特征具有判别力的可能性越大[12]，使用该标准的边的启发信息计算如下：

(11)

式中：ηix,jy代表特征i取值为x时与特征j取值为y时所构成的边上的启发式信息(x和y的取值均为0或1)；n为特征的数目；ξ为常量(通常取值在0～1之间).

2.4 QPACO算法伪代码

QPACO算法伪代码见表1.

表1 QPACO算法伪代码

3 实验结果与分析

3.1 实验数据与对比算法

本文从UCI数据库中选择了一些典型的数据集对算法进行验证.典型的数据集见表2.

表2 UCI数据集

为了更好地展现算法的可比性，选择了一些具有代表性的特征选择算法与本文算法进行比较，其中包括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及其对比算法的平均分类精度对比

注：括号中的数字表示在各个数据集上每种算法性能的排名.

3.3.2 实验分析

QPACO算法在时间效率上是基本等同于二元蚁群优化算法的，在算法的改进过程中，计算和记录每次信息素的更新量，以及查找生命周期结束信息素量的时间复杂度都是O(1)，因此时间上的开销差距并不明显，所以本文遵从了相关的基于演化计算的特征选择方法的实验设计模式，并未采用时间效率来衡量算法性能[13-17]，但计算了其他常用的评估指标进行算法间的对比.

对比分类精度，从表3中不难看出，QPACO算法在Glass，Letter，Shuttle，Spambase，Waveform，Wisconsin这些数据集上均位居第一，在Wine和Yeast上位居第二，只在Vehicle上稍显逊色.因此QPACO算法在分类精度上有了很明显的提升.通过对比表4中的精确率、召回率以及维度缩减率，发现QPACO算法大多数情况下精确率和召回率都略高于其他算法，且维度缩减率维持在平均水平以上.

表4 QPACO及其对比算法的精确率、召回率、维度缩减率对比

4 结 论

本文提出了基于传统蚁群优化算法和二元蚁群优化算法的量子化信息素蚁群优化(QPACO)特征选择算法.QPACO算法中将信息素量子化，赋予每个信息素单独的生命周期，同时修改了启发式因子的更新方式，增强了算法的搜索能力.经过9个数据集和9个特征选择算法的对比实验，验证了QPACO算法良好的性能.如何在高维数据集中应用QPACO算法进行特征选择问题的求解，将是下一步重点研究的内容.