基于聚类和二元蚂蚁系统的高维数据特征选择算法

周金容 罗 建

1(南充职业技术学院电子信息工程系 四川 南充 637131) 2(西华师范大学计算机学院 四川 南充 637009)

0 引 言

在大数据时代，高维数据已扩展到社交媒体、生物信息学、图像处理和自然语言处理等不同领域[1-2]。计算负担、过拟合和性能不佳是高维数据带来的一些外在表现缺点[3]。在模式识别中，由于存在成千上万的特征，因此从高维数据中选择特征子集仍然是一个挑战[4]，其中过滤掉无关和冗余的特征可以减少过度拟合，节省计算成本并提高分类的准确性。特征选择算法是可以有效地将原始数据缩小到低维空间的算法。特征选择是组合优化问题，在当今许多科学领域中都是重要问题。

特征选择技术已成功应用于各种人工智能领域，包括文本挖掘、图像处理、生物信息学，以及其他领域[5]。目前，研究人员已经开发了许多群体智能启发优化算法用于特征选择。文献[6]提出了一种基于多目标粒子群优化的特征选择方法，该方法根据特征在存档集中的频率对其进行排名，使用这些等级来优化存档集并引导粒子，消除了不相关、多余和嘈杂的特征，降低计算成本。文献[7]提出了一种基于遗传算法和禁忌搜索相结合的特征选择方法，该方法通过定义一个过早收敛索引，以判断遗传算法过程中的收敛情况。当确实发生早收敛时，将执行改进的变异算子，对具有较高适应性值的个体采用禁忌搜索算法。文献[8]提出了一种基于乌鸦搜索的V形二值化包装器，该包装器利用二进制乌鸦搜索算法简化了特征选择模型和减少了分类处理时间。文献[9]为了处理高维低样本数据中的冗余特征和不相关特征，提出了一种基于粒度信息的特征选择算法模型，该模型利用改进的具有特征粒度的二进制遗传算法来选择优化粒子集重要特征。文献[10]设计一种基于粗糙集与人工蜂群算法的动态数据流特征选择算法，使用粗糙集定义数据流增量数据的适应度函数，利用人工蜂群算法从旧特征子集与增量数据提取新的全局特征子集，为了增强人工蜂群算法的鲁棒性，通过降低人工蜂群算法过早收敛几率来满足动态特征选择算法的稳定性需要。文献[11]提出一种基于加权社区检测与增强人工蚁群算法的高维数据特征选择算法，通过设计加权社区检测算法，将特征相似性作为社区划分的模块度，利用人工蚁群算法并行地处理每个特征分类，提取全局最优的特征子集，从而提高了特征选择的时间效率。

为了降低高维数据特征选择的运行时间和提高分类精度，提出一种基于聚类和二元蚂蚁算法相结合的混合滤波器特征选择方法，该方法通过线性二元蚂蚁系统、应用聚类、阻尼突变策略三种组合来改进学习方法，通过在状态空间中进行快速有效的全局和局部搜索来进行特征选择，在短时间内获得最佳特征。

1 二元蚂蚁算法

蚁群优化(Ant Colony Optimization，ACO)[12]算法是由Marco于1992年提出的一种基于概率技术元启发式优化方法，方法的主要目标是根据蚂蚁在整个空间中搜寻食物来源的行为来获得图中最佳路径。在自然世界中，蚁群在觅食过程中，会在其经过的路径上留下一种信息素的化学物质。蚁群个体对信息素具有感知能力，会沿着信息素浓度较高路径行走，从而找出最短路径。但是，由于蚁群优化算法的解空间搜索受到限制，容易导致收敛到局部最优解。为了克服这一问题，Manbari等[13]在2005年引入了一种二元蚂蚁系统(Binary Ant System，BAS)，该系统应用于具有二元解结构的约束优化问题，即搜索空间被表示为一个二进制图，其中每个节点都通过两个边连接到下一个节点，如图1所示。

图1 BAS中的蚂蚁路径图

蚂蚁通过从开始到最后遍历图来生成其解决方案，解以二进制字符串表示：x={x1,x2,…,xn}，xj∈{0,1}。在每次迭代时，一组蚂蚁开始搜索二进制搜索域，并且可以通过从图1上的节点1到节点n+1依次行走的蚂蚁来生成解决方案。在每个节点j上，蚂蚁都会选择两条路径中的一条，以步行到下一个节点j+1。节点xj的信息素值由τjs表示，s∈{0,1}，与选定/取消选定状态相对应。对于选择/取消选择状态，初始信息素分布在所有节点上，表示为τ0。在生成解时，蚂蚁k根据式(1)所述的概率分布选择节点j。

(1)

为了生成解决方案，所有蚂蚁都会为每个节点进行选择。一旦每只蚂蚁完成了巡视，目标函数便会用于评估和比较整个当前迭代过程中生成的所有解决方案。系统保留当前已找到的最佳解决方案作为全局最佳解决方案Sgb，若当前迭代i中的解决方案Sib优于Sgb，则更新最佳解决方案为Sib。在每个迭代周期的末尾执行更新全局信息素的过程。此过程包括两个步骤。在第一步信息素挥发过程中，所有信息素均会根据以下所述挥发规则轻微发散：

τjs(t+1)←(1-ρ)τjs(t)

(2)

式中：ρ表示挥发参数。第二步是将所选节点的信息素增强为Sgb：

τjs(t+1)←τjs(t+1)+ρΔτ(j,s)∈Sgb

(3)

式中：参数Δτ表示增强的信息素量。重复上述循环，直到满足特定的终止条件为止。

目前，在二元蚂蚁系统的基础上，存在多个改进算法。Zhang等[14]为了在不影响解的质量的前提下进一步提高收敛速度，在二元蚂蚁优化算法中加入约束满足条件。Mafarja等[15]为了提高最佳解的质量，在二元蚂蚁系统中引入狮群优化，在全局中寻找最优解。

2 基于聚类和BAS的特征选择

本文提出一种基于BAS和聚类的混合无监督特征选择算法，该算法首先将特征聚类，其次通过将BAS应用到每个集群，在并行过程中对不同集群中的特征进行排序，然后在迭代过程中，通过BAS方法选择每个群集的最佳特征。重复此阶段，直到完成所需的特征子集为止。

2.1 阻尼突变BAS

状态转移规则是概率性的，并且是基于节点信息素值和启发式信息的混合而设计的，定义如下：

(4)

(5)

特征j和先前选择的与特征j具有最大相似性的q个特征之间的平均相似性可表示为：

(6)

式中：Γk包含特征i与子集k中的每个特征之间具有最大相似性的q个节点/特征。

最后，根据式(7)和式(8)，选择(S=1)或不选择(S=0)节点i分别采用贪婪或概率规则来确定。为了避免陷入局部最优和增加搜索空间，使用轮盘赌轮，使得基于阈值θ=0.7进行选择或取消选择过程。

(7)

(8)

式中：γ0为随机值。

为了避免陷入局部最优并克服搜索空间的限制，考虑一种突变策略。蚂蚁的随机运动意味着人工蚂蚁从随机选择的节点开始在映射图上移动；蚂蚁的随机方向，即蚂蚁的顺/逆时针移动方向应随机确定；特定节点处的阻尼突变。采用阻尼变异是为了避免过早收敛。通过变异策略，交换图上的一些节点用于修改节点的顺序，增加搜索空间的状态数。根据这种方法，蚂蚁在初次迭代时被随机放置在图上；然后，变异算子根据变异条件交换图上的特定节点；在随后的迭代中，如果变异已经发生，蚂蚁会移动到新的变异图上。如果当前迭代与前一迭代信息素比率之差小于变异率时，满足变异条件。信息素比率PR是每个节点每次迭代中选定节点上信息素的值。为了比较突变率，这个变量应该被规范化：

(9)

突变率是决定突变的一个参数。突变率在迭代初始是最大值，在迭代过程中变异率会随之降低。原因是该算法在学习初期具有较高的探索能力，然后通过降低变异率，使算法的局部搜索能力和收敛性逐渐提高。通过该技术的应用，在搜索空间中实现了勘探与开发的平衡。选择节点时频率较低的节点会被选择频率最高的节点所代替。在蚁群算法的每次迭代中，图上随机放置一个蚂蚁。然后，随机选择蚂蚁的顺时针或逆时针运动。每只蚂蚁根据运动方向不断地遍历圆图，直到返回初始位置。同时，蚂蚁根据概率状态转移规则选择或取消选择特征。状态转移规则寻求选择具有最高项方差值且与式(4)描述的先前选择的特征的相似性最低的特征。蚂蚁选择/取消选择特定节点的次数被定义为特征状态计数器。然后，在每次迭代结束时，通过特征状态计数器和根据信息素的更新规则更新每个节点的信息素值。在满足停止准则后，选择信息素值最高的特征。

信息素更新规则适用于更新所有边缘上的信息素。 每个蚂蚁完成遍历后，使用式(10)更新信息素值。

(10)

2.2 特征选择算法

2.2.1特征聚类

基于要素之间的相似度将其分为几个聚类。应用Louvain社区检测算法[11]将图划分为小分区，在社区中通过最大化模块化功能来检测社区。这是一种实现算法的简单、高效且简便的方法，该算法应用于节点的相似度图，可检测非常大的图中的社区。

2.2.2并行特征选择

在每个聚类中分别执行阻尼突变BAS，即将特征放置在阻尼突变BAS的搜索空间中表示，蚂蚁开始搜索并注入信息素。特征聚类和图形如图3所示。

图3 在特征聚类中执行阻尼突变BAS

由于聚类是完全分离的，因此每个聚类由一批蚂蚁并行滚动。与其他基于聚类的特征选择方法相比，由于进行并行处理使得该阶段的时间复杂度显著降低。在对聚类进行处理后，基于阻尼突变BAS方法，信息素被蚂蚁注入后，根据聚类中的信息素值对每个聚类中的特征进行排序。因此，每个聚类中的显著特征位于列表的前段。

2.2.3顺序特征选择

在每次迭代中，从每个聚类中提取前K个剩余特征，将阻尼突变BAS应用于这些特征，并选择K0个最佳特征。然后，将所选特征从所属聚类中删除，并更新聚类用于重新选择K个要素。该循环一直持续到所需的特征子集完成为止。在这个过程中重复了nf/K0次，但此图的处理时间远远少于包含所有特征的初始图的处理时间。图4给出了本文方法在K0=3时的示意图。

图4 本文方法示意图

算法1中显示了本文方法的伪代码。在第1行和第2行中，完成了并行特征选择，包括特征聚类，并且在每个聚类中应用了阻尼突变BAS。在并行特征选择中，基于每个聚类信息素值排序的特征将被返回。在第4-第9行中，完成了顺序特征选择。在第4行中，重复循环，直到完成所需的特征子集为止。在第5行中，从每个聚类中选择前K个特征。第6行则是选择所有聚类中K个最佳特征。由于必须从各个聚类中选择出最好的特征，因此聚类的信息素值必须具有可比性，因此对聚类的信息素值进行如下归一化处理：

(11)

算法1基于聚类和阻尼突变BAS的特征选择算法

输入：所选特征数量nf，聚类数量nc，具有p个模式的n维数据集Dp×n。

输出：降维的数据集Dp×nm。

1. 将特征进行聚类；

2. 在每个聚类上执行阻尼突变BAS算法，并从中返回排序后的特征List_features；

3.K=nf/nc；K=K0

4. while 特征子集未完成

5. 从每个聚类中选择前K个特征；

6. 从所有基于信息素的聚类中移除选择的K个特征，并更新；

7. 对第5-6行中选择的特征执行阻尼突变BAS；

8. 选择K0个最佳特征，添加值特征子集中，并将其从List_features中删除；

9. End while；

10. 返回最终特征子集。

在第7行，将从聚类获得的前段特征放置在小的二元圆形图上，然后将阻尼突变BAS方法应用于特征上。从这些前段特征中选择具有最大信息素值的K0个特征，并将其添加到第8行中选定特征的最终列表中。这些K0特征从特征列表中删除，然后更新列表，重复循环，直到完成所需的特征子集为止。

最佳的聚类数是根据式(12)获得的。

(12)

式中：nf是目标特征数量；μ是所有要素之间相似度的平均标准偏差。

3 实验与结果分析

为了评价本文算法的性能，本文方法在相同条件下与基于遗传算法和禁忌搜索混合的特征选择(GATS)[7]、基于乌鸦搜索算法二值化特征选择(BCSA)[8]、基于动态相关性和联合互信息最大化的特征选择(DRJMIM)[14]等现有的特征选择方法相比。本文仿真实验是在具有2.7 GHz频率和6 GB RAM的Intel Core i5 CPU系统的PC上执行的。使用C#.Net编程语言实现了所有算法，在实验中使用的分类器为支持向量机SVM，其他参数如表1所示。

表1 本文方法的参数设置

3.1 数据集和评估标准

本文使用了来自UCI大学存储库的一些知名的真实世界数据集，数据集名称为Wine、Ionosphere、Hepatitis、SpamBase、Arrhythmia、Madelon、Colon和Leukemia[1]。这些数据集已用于许多机器学习研究中，包括特征选择并涵盖了小、中和大特征维范围。表2给出了这些数据集的特征总结。

采用准确率(Precision)、召回率(Recall)、综合评价指标(F1-Measure)三个性能评价指标进行评估本文方法的性能。

准确率P表示被分类正确的样品中实际为正确的比例，计算式表示为：

(13)

式中：TP表示为将正类预测为正类数；FP表示为将负类预测为正类数。

召回率R是覆盖面的度量，度量有多个正类被分为正类：

(14)

式中：FN表示将负类预测为负类数。综合评价指标F1值是准确率P和召回率R加权调和平均：

(15)

3.2 结果分析

图5-图7显示了在UCI数据集上，本文方法与其他特征选择方法在准确率、召回率、F1三个指标的测试结果比较。可以看出，相对其他方法，本文方法具有很好的性能，在三个测试指标中均获得良好的结果。

图5 不同特征选择方法的准确率结果对比

图6 不同特征选择方法的召回率结果对比

图7 不同特征选择方法的F1指数结果对比

表3给出了本文算法与其他对比算法在数据集上的测试结果。可以看到，本文方法的平均执行时间比其他方法缩短约49～56倍。本文方法的主要优势在于其性能与完全图方法相同，而计算复杂度非常低，大大减少了高维数据集的运行时间。

表3 不同特征选择方法的执行时间 单位：ms

4 结 语

本文提出一种基于混合滤波器的特征选择算法，用于降低计算成本、简化学习模型、提高分类器性能。该算法由线性二进制蚂蚁系统、聚类、阻尼突变策略组成。二元蚂蚁系统可以克服搜索空间的挑战，聚类在一定程度上减轻处理高维数据集的问题，通过引入突变使搜索空间更加随机化。本文方法中，将特征聚类并顺序放置在圆形图中后，应用阻尼突变BAS算法，然后在迭代过程中选择一些最佳特征，直到完成所需的特征子集为止。模型在聚类之间和聚类内部应用了全局和局部搜索功能。实验结果表明，本文方法显著减少了计算时间，并且比其他特征选择方法具有更好的效果。