摘要

特征选择是模式识别和数据挖掘中的一种重要的数据处理方法。由于没有考虑FS问题本身的特点，大多数粒子群优化（PSO）算法采用的传统粒子更新机制和群体初始化策略限制了他们在处理高维FS问题上的性能。针对这一问题，提出了一种基于互信息的基本粒子群算法（BBPSO）的特征选择算法。首先，一处了一种有效的基于标签关联的群初始化策略，充分利用特征和类标签之间的相关性来加速群的收敛。然后，为了提高算法的开发性能，提出了两种基于特征相关性冗余的局部搜索算子，即补充算子和删除算子。此外，设计了一种自适应翻转变异算子来帮助粒子跳出局部最优解。将该算法应用于基于K近邻分类器（KNN）的典型数据集，并与11种最新算法进行了比较。实验结果表明，该算法能够获得性能较好的特征子集，是一种具有较强竞争力的FS算法。

1 介绍

作为一种数据处理方法，FS算法根据给定的准则从原始特征集中选择最优子集。通过去除不相关的或可重复的特征，FS可以减小特征的大小，缩短学习时间，提高分类器的性能。

现有的特征选择算法（FSAs）可以大致分为三类：过滤器、包装器和嵌入式。过滤器和包装器之间的主要区别在于在评估特征子集时是否使用了分类算法。过滤器选择特征子集作为预处理步骤，不需要任何分类算法。一般来说，它的计算成本低于包装器和嵌入式。所以它能快速处理高维数据。然而，由于缺乏后续学习算法，其性能往往不如包装器和嵌入式系统。包装器利用一个学习算法或分类器作为一个黑盒子得分特征子集。该方法比传统的滤波方法效率高，但由于需要一个分类器来评价特征子集的分类性能，因此计算量较大。包装方法需要强大的搜索策略来寻找最优的特征子集。

作为包装器和过滤器的有效组合，嵌入式的方法相比具有良好的收敛性，并且通过结合过滤器和包装器的优点，可以生成具有较高分类精度的特征子集。通常，混合方法由以下两个阶段组成：过滤阶段和包装阶段。过滤阶段的目的是通过根据许多标准对特征进行排序来生成缩减的特征子集。然后，通过局部或全局搜索策略，使用每阶段包裹从缩减的特征子集中寻找最优特征。

进化算法以全局搜索能力而闻名，近年来在求解FS问题上受到了广泛的关注。到目前为止，遗传算法、人工蜂群、差分进化和萤火虫算法已经应用于FS。粒子群优化算法最早由Kennedy和Eberhart于1995年提出。由于它具有概念简单、收敛速度快的优点，人们提出了许多基于粒子群优化的包装函数算法。为了进一步提高分类的可能性，最近一些研究人员尝试将过滤器集成到PSO的搜索过程中。然而，这些方法仍然存在以下缺点：

1. 首先，大多数算法采用随机初始化策略生成初始群。Gutierrez等人指出，PSO中的初始化策略对于不同的高维优化问题表现不同。因此，根据粒子群算法的特点设计一种有效的初始化策略，可以提高粒子群算法的性能，降低对初始粒子群的敏感性。
2. 其次，在这些方法中使用的过滤策略大多只考虑特征与类标签之间的关系，忽略了特征之间的冗余。因此，一些冗余特征通常以高概率选择在最终子集中。
3. 此外，其中大多数要求决策者调整控制参数，包括惯性权重、加速度系数和速度钳制，以获得可设计的特征子集。而且，如何为这些控制参数设置合适的值需要决策者的先验知识。

1.1 目标和贡献

本文的主要目的是结合滤波器和包装器的优点，提出一种新的有效的特征选择方法。与现有的大多数混合策略不同，本文将过滤器作为一种有效的局部搜索算子集成到基于粒子群优化的包装方法中，以提高粒子群优化算法的可拓展性。具体地说，在粒子群算法的迭代过程中，通过补充和删除两种受过滤器启发的局部搜索算子不断改进群体生成的精英粒子。在该混合算法中，具有全局搜索能力的粒子群优化算法专注于寻找潜在的最优区域，而受滤波器启发的局部搜索算子则专注于深入挖掘这些区域以加速收敛。