改进的粒子群算法优化的特征选择方法

李 炜，巢秀琴

1.安徽大学 计算机科学与技术学院，合肥 230601

2.安徽大学 计算智能与信号处理教育部重点实验室，合肥 230601

1 引言

特征选择问题也称特征子集选择问题，是指从已有的M个特征中选择N个特征使系统特定目标最优，从而降低数据维度，提高学习算法性能[1]。近年来，随着数据挖掘、机器学习和计算科学等领域的发展，越来越多高维数据集应用于各个领域的信息系统之中，例如金融分析、商业管理和医疗研究等领域[2]。高维数据集带来的维度灾难使得数据处理的复杂程度急剧增加，因此删减多余或信息量少的特征，选择出最优的特征子集将大大提升后续学习算法的效率[3]。

特征子集选择方法可分为嵌入式（embedded）、过滤式（filter）和封装式（wrapper）三种。嵌入式方法将特征选择过程嵌入到学习模型中，作为训练过程的一个部分，而不是将数据集分为训练集和测试集[4]。过滤式方法中，所有特征按照特定的统计或数学属性进行排序，例如特征对类的可分性或者熵值[1]，最后根据排序选择特征子集[4]。封装式方法则是通过学习算法对候选的特征子集进行评价，并通过多次迭代改变候选特征子集，然后根据分类精度和特征数等评价标准选择最优特征子集[5]。

假设数据集中有n维特征，则全部搜索空间大小为2n，故特征选择问题是一个NP-hard问题[6-7]。因此，穷举搜索最优特征子集将会耗费大量计算和时间成本，不适用于解决大量高维数据集的特征子集选择问题。同时，由于启发式搜索算法的自身优势，一次运行就得到一组解，能够耗费较小时间和计算成本搜索到理想的解集，近年来越来越多基于启发式算法的特征选择方法被提出来，用于解决特征选择问题，并取得很好的效果[8]。例如遗传算法（genetic algorithm，GA）[9]、蚁群算法（ant colony algorithm，ACO）[10]、人工蜂群算法（artificial bee colony algorithm，ABC）和粒子群优化算法（particle swarm optimization algorithm，PSO）[11]等。其中，粒子群优化算法[12]由于其收敛速度快，搜索能力强的优点受到诸多学者关注并提出了大量改进算法。文献[13]提出了基于粗糙集的PSO算法来搜索最优特征子集，并得出结论：基于PSO的特征选择方法比基于GA的方法能更有效地解决特征选择问题。文献[14]提出一种新的变异策略改进PSO算法，通过随机翻转粒子的位置，避免算法陷入局部最优。文献[15]提出基于PSO和粗糙集特征选择技术结合的方法，解决脑-机接口运动图像研究中的特征降维问题，实验结果显示，将该方法选择出来的特征子集应用于提出的多类运动图像分类的领域粗糙集分类器方法中，取得良好效果。文献[16]提出一种基于多目标粒子群优化算法的特征排序方法，将特征频率进行存档并引导粒子进化，在9个基准数据集上进行测试性能，取得了理想效果。文献[17]基于粒子群优化算法和逻辑回归模型，提出将贝叶斯信息准则作为适应度函数，在大量数据集上进行实验，实验结果显示该方法显著提高了分类性能并减少了特征数目。

同时，一些学者还将PSO与不同的分类器结合来解决特征选择问题。文献[18]提出PSO与支持向量机（support vector machine，SVM）结合的特征选择方法，并通过使用Web服务技术的分布式体系结构来减少时间成本。文献[19]提出一种基于改进PSO的过滤-封装特征选择方法来解决图像处理中的特征选择问题。该方法分为两个阶段：在第一个阶段中，采用两种典型的过滤式技术，t检验和多元回归，根据特征识别能力选择图像；第二阶段则通过在PSO算法中动态改变种群规模，并采用SVM作为分类进行特征测试。实验结果表明，该方法能够显著提高分类精度且降低特征维度。文献[20]在解决癌症分类问题时，首先通过快速相关特征选择（fast correlationbased feature selection，FCBC）方法对不相关和冗余特征进行过滤，后期采用PSO对SVM进行优化操作。在9个癌症数据集上的实验结果显示，该文献提出的PA-SVM在处理复杂非线性问题时具有良好的灵活性和适应性。文献[21]提出将GA与PSO相结合的方法用于解决医学诊断中的特征选择问题。首先利用GA来选择特征子集，然后利用PSO对SVM的参数进行优化。由于PSO在搜索合适的连续变量方面表现出优势，最终在UCI数据进行实验，结果显示，该文献中提出的混合方法比单一算法更能够为SVM选择最佳的支持向量机模型参数和更具相关性的特征子集，从而进一步提高了医疗诊断问题的分类性。文献[22]在二进制粒子群优化算法中提出新的初始化策略和更新策略，且该方法使用K近邻（Knearest neighbor，KNN）作为分类器。文献[23]在对离散的共生体搜索算法（symbiotic organisms search，SOS）进行相关改进时，其中一种采用了BPSO（binary particle swarm optimization）与SOS结合的方式，使用KNN作为分类器，通过分类精度和计算时间来评价算法性能，在多个数据集上进行对比实验的结果显示，改进后的算法性能显著提升。

另一方面，除了启发式搜索算法，近年越来越多研究者提出图论与社团检测算法结合来解决特征选择问题[24]。首先，将特征集表示为一个无向带权图，图的顶点表示不同的特征，边的权重值则反映出特征之间的相似性，且权值通过一些统计指标来计算，如皮尔森相关系数等[25]。然后使用社团检测算法将图中特征顶点划分为不同的簇，同一个簇中的特征相似性较大，而不同簇中的特征之间相似性则相对较小。

本文组织结构如下：第2章对BPSO算法步骤进行介绍，然后提出本文算法的改进；第3章介绍本文算法框架的具体过程；第4章介绍文中使用的数据集、相关实验参数的设置，并对算法的各个改进模块的有效性进行实验论证，并将改进后的算法与当前代表性优化算法进行对比实验；第5章总结全文。

2 BPSO算法

BPSO算法是Kennedy于1997年在连续性PSO算法基础上提出的，用于解决离散的优化问题[26]。BPSO算法通过模拟鸟类飞行觅食过程，种群中每个粒子相当于解空间中的一个解，粒子具有速度和位置两个属性，位置向量表示该粒子对应的解，速度向量则是为了调整粒子下一次飞行，从而进行位置更新搜索新的解集。粒子飞行过程中根据自己的历史飞行经验和种群中其他粒子的飞行经验调整自身的飞行方向和速度。其中，每个粒子历史飞行过程中的最优位置称为个体最优解pbest，整个种群在历史飞行过程中所经过的最好位置为gbest，称为全局最优解[26]，粒子之间通过pbest、gbest共享信息，从而在进化过程中影响种群的搜索行为。

2.1 种群初始化

2.2 粒子速度与位置更新

任意粒子i(i=1,2,…,N)根据式（1）更新速度向量：

其中，ω表示惯性权重，衡量粒子学习过程中上一代粒子对当代粒子的影响权重；c1、c2表示学习因子；rand1、rand2表示0～1之间的随机数。

其中，rand是0～1之间的随机数。

2.3 种群评价

对于种群中的每一个粒子，用适应度值来评价该粒子对应的解的优劣。任意粒子i(i=1,2,…,N)，计算对应的适应度值为Fitness(i)。

得到种群每一个粒子的适应度值之后，判断粒子在对应个体飞行过程以及种群飞行过程中的优劣。若粒子i适应度值比粒子i历史最优pbesti对应的适应度值更好，则粒子i搜索到当前飞行过程历史中的最优位置，故用粒子i位置向量来更新pbesti向量；否则，pbesti向量保持不变。同理，若粒子i适应度值比种群全局最优gbest对应的适应度值更好，则粒子i搜索到整个种群在当前飞行历史中的最优位置，故用粒子i的位置向量更新gbest向量；否则，gbest向量保持不变。

2.4 算法终止条件

如果满足最大迭代次数，则终止算法并输出最优解gbest对应的特征选择方案。否则，返回2.2节进行下一次迭代操作。

3 算法设计

3.1 改进的种群初始化策略

初始化种群的优劣对BPSO算法后续搜索性能具有很大影响[22]，因此大量研究者在改进BPSO算法解决特征选择问题的时候，也提出了新的种群初始化策略，后续实验结果也证明这些初始化策略能有效提高BPSO算法搜索更优质特征子集。文献[27]提出用非线性单纯形法产生初始种群，通过在14个标准测试函数上进行检测实验，表明该初始化方法在数据维度较低情况下能够明显提高BPSO算法性能。对于高维特征选择问题，文献[28]在PSO算法中提出基于中心旋涡的初始化策略，该策略的目标是降低初始化粒子的特征数目，从而减少每次评价的计算成本。而文献[29]则认为在初始化过程中均匀分布的粒子可以提高PSO算法性能。同时比较了三种不同的初始化策略，即正交矩阵初始化策略、基于混沌技术的初始化策略和反向初始化策略，这三种初始化策略对于不同的特征选择问题有不用的效果。文献[22]则基于传统的初始化方法提出三种新的初始化策略：最大初始化、最小初始化及混合初始化。明显提高了PSO算法性能。

基于初始化策略对于BPSO算法的重要性及特征选择问题的具体性，本文提出了一种基于特征聚类信息的种群初始化策略，从而得到更理想的初始化种群。

3.1.1 预处理

对数据集标准化处理：实验结果证明特征值的标准化可以提高分类精度，因此在预处理过程中需对数据集作标准化处理，将数据集中每一维特征值缩放到-1到1之间[3]。对于M维特征，n个样本的数据集，任意一维特征i在第j个样本中对应取值为xij，按式（4）得到标准化后的取值xij′:

其中，ximax表示特征i在所有样本中的最大取值，ximin表示特征i在所有样本中的最小取值。

3.1.2 特征邻接图

在图论中，系统中两个元素或多个元素之间的关系可由图来表示[30]。其中，一个图G={V,E,W}的结构由点集V、边集E和每条边的权重W构成[31]。

在特征选择问题中，每个顶点可对应表示一个特征，每条边表示两个特征之间的关系，且每条边的权重取值则对应两个特征之间的关系强度。本文基于特征之间信息的共性，确定特征F1与特征F2之间的相似性。且对于特征F1与特征F2，应用皮尔森相关系数（Pearson's correlation coefficient，PC）来衡量这两个特征之间的相似性，皮尔森相关系数（PC）按照式（5）计算：

其中，SN表示数据集中的样本个数。

根据所有特征之间的皮尔森相关系数，构成特征的PCC矩阵，矩阵中每一个元素PCCij表示特征i与特征j之间的皮尔森相关系数。本文应用中位数切割策略，由PCC矩阵得到特征之间的邻接矩阵（Neighbor）用于后续社团检测进行特征分组。PCC中所有元素的中位数（Med）作为阈值，对于PCC矩阵中任意元素PCCij，若PCCij≥Med，则对应的Neighborij=1；否则，若PCCij＜Med，则Neighborij=0。由此，得到与PCC矩阵大小相同的Neighbor矩阵，且Neighbor矩阵所有元素取值为0或1，取值为0表示在特征邻接图中，对应两个特征顶点之间没有边相连，取值为1则表示对应两个特征顶点之间有边相连。

3.1.3 特征分组

社团结构是网络中的重要模块之一，通过社团检测识别网络中的社团有助于理解网络中的复杂关系[32]。社团检测的目的是将网络中相似性大的顶点聚类为一个社团，从而与其他顶点区分开，同一社团内的顶点具备相似的属性，相似性较大。因此，在特征选择问题中，通过社团检测算法将特征网络按照相似性进行划分，同一个社团中的特征相似性大，不同社团中的特征相似性较小。

其中，Louvain社团检测算法是一种简单高效的社团检测方法，该算法通过最大化模块函数来实现网络中的社团检测[33]。本文应用Louvain社团检测方法对特征网络进行特征聚类，基于PCC矩阵，将特征按照相似性划分为不同的特征聚类{community1,community2,…,communitycNum}，其中，cNum为聚类数目。

3.1.4 种群初始化

数据集维度为D，种群大小为N。种群中每个粒子表示特征选择问题中的一个解，即代表一种特征选择方案。本文采用二进制编码，粒子的每一维取值只能为0或1，取值为0表示对应维度的特征未被选择；相反，取值为1则表示对应维度的特征被选择。因此，每个粒子中所有取值为1的维度代表的特征构成该粒子对应的特征选择方案。每个粒子的具体初始化方式如下：

首先初始化每个粒子对应的特征数目Pi(i=1,2,…,N)，为了控制初始粒子的特征数目，Pi取值不超过总特征数的60%，即|Pi|＜60%×D。Pi个特征分别从各个特征分组中随机选择：如果Pi≤cNum，则随机选择|Pi|个不同的特征分组，并从每个分组中随机选择一个特征。如果Pi＞cNum，则先从所有特征分组中随机选择一个特征放入粒子中，剩余(PicNum)个特征再次从各特征分组中随机选择。

3.1.5pbest与gbest初始化

对于种群中的每一个粒子i(i=1,2,…,N),初始pbesti就是粒子i本身，而初始gbest则记录为种群中第一个粒子。

3.2 粒子速度与位置更新

本文算法中，粒子速度更新与BPSO算法一致，即每个粒子的速度与位置按照2.2节介绍的更新方式进行操作。

3.3 交互操作

众所周知，BPSO算法的收敛性很强，但后期搜索容易陷入局部最优，即粒子之间相似性增大，算法搜索性能受到极大限制。因此本文根据种群进化过程中粒子在决策空间中的相似性来对粒子进行自适应的交互操作：粒子在种群中相似性大，则相应粒子进行交互的概率大；反之，粒子进行交互的概率小。进行交互操作的目的是从决策空间的角度，增加种群中粒子的多样性，从而避免算法陷入到局部最优状态，提高搜索性能。交互操作过程如下：

3.3.1 定义粒子相似

本文定义了基于粒子在决策空间中的相似性指标衡量粒子在种群中的相似性，对于粒子i(i=1,2,…,N)，判断其与种群中其他粒子j(i=1,2,…,N|j≠i)的相似性规则如下：

其中，Fi、Fj分别表示粒子i与粒子j对应的特征子集。因此，S1表示Fi、Fj共有的特征结合，S2表示仅在Fi中存在且不在Fj中存在的特征集合。

本文实验中，若|S1|≥0.6且|S2|≤0.4，则判定粒子j是粒子i的相似粒子，由此统计出种群中所有粒子i的相似粒子集合simi。

同时，定义指标Coni来衡量种群其他粒子j(j=1,2,…,N且j≠i)中特征与粒子i中特征的重合程度，Coni按照式（6）计算：

Coni的值越大，表明粒子j与粒子i的公共特征数目占粒子i中特征数目的比例越大，则粒子j对于粒子i的包含程度越高。由于粒子群优化算法进化后期，粒子之间相似性增大，则粒子之间的包含程度也随之增大。因此，本文实验中将通过选择种群中与当前粒子包含程度最小的粒子来进行交互操作，从而增大种群的多样性，避免算法过早收敛。

3.3.2 计算相似性指数

对粒子i(i=1,2,…,N)，相似性指数按式（7）计算：

3.3.3 交互操作

进行交互操作之前，首先按照式（8）计算粒子i的交互概率Interratei：

由式（8）可知，随着粒子在决策空间中的相似性增大，粒子的交互概率也随之增大，从而进一步增大后期对相似性较大的粒子的扰动力度，降低种群中粒子的相似性，避免种群搜索陷入局部最优。

对任意粒子i(i=1,2,…,N)，用随机函数产生随机数randi，若randi≤Localratei，则需对粒子i进行交互操作。交互操作规则如下：

（1）根据指标Coni对应的最小值，找出粒子i的交互粒子j。

（2）将粒子i与粒子j中元素“1”所对应的特征序号分别提取出来，构成临时交互父代个体Pti与Ptic，如果Pti与Ptic维度不相同，则在维度小的临时父代中随机补充0元素直到两个父代个体维度相同为止。

（3）随机产生交互位置，从交互位置开始进行判断：首先判断Ptic对应位置的特征是否存在于Pti中，如果该特征不在Pti中存在，则继续产生随机数rand，若rand≤Localratei，则交换Pti与Ptic中对应位置的特征，完成该位置的交互操作。除此之外所有情况下，临时父代个体Pti与Ptic均不进行交互操作，直到Pti的最后一维判断结束。

（4）对Pti进行交互操作之后，得到新的粒子Pti′，最终需将其转化为二进制编码形式。转化过程如下：首先将粒子i的每一个维度初始取值均设置为“0”。然后在粒子i中，将所有Pti′的非零元素对应的位置取值重置为“1”，得到新的粒子i′。

对种群粒子之间进行交互操作之后，需进一步对种群中的粒子进行自我调整操作，避免粒子内部的特征高度集中于单个或极少特征聚类中，造成特征之间的信息冗余。粒子的自我调整过程如下：

（1）统计每个粒子中的特征所在的特征聚类信息：Gi={g1,g2,…,ginum}，其中，ginum表示粒子i中出现的聚类数目。

图1为粒子i的交互操作过程实例。

3.4 种群评价

Fig.1 Interaction process of particlei图1 粒子i的交互操作过程

种群更新之后，需对更新后的种群进行评价。由于特征选择的最终目标是在减少特征数目的同时，保留有效特征，从而保证后续学习算法的学习性能不受影响。因此在各种特征选择算法中，应用不同的分类器来评价特征子集的质量，如：支持向量机（SVM）[29]、K近邻分类器（KNN）[34]等。

本文实验中，在对数据集进行标准化操作之后，将其划分为训练集和测试集：70%数据样本作为训练集，30%数据样本作为测试集。训练过程中，通过使用5-NN分类器并采用十折交叉验证（10-fold cross validation method）[35]计算种群中的每一个粒子所代表的特征子集选择方案的分类错误率和特征数目，并计算粒子的适应度值对粒子进行评论。算法最后，在测试集上对粒子进行测试得到算法的最终结果。分类错误率按式（9）计算：

其中，FP表示负样本被预测错误的个数，FN表示正样本被预测错误的个数，TP表示正样本被预测正确的个数，TN表示负样本被正确预测的个数。

本文采用分类错误率与特征数目的加权和作为适应度函数，用于评价种群中的每一个粒子的优劣。对于粒子i(i=1,2,…,N)，按照式（10）计算其适应度函数值：

其中，ErrorRate(i)表示粒子i的分类错误率，FeatureNum(i)表示粒子i对应的特征数目。

得到种群中每一个粒子适应度函数值之后，对pbest与gbest进行更新，对于任意粒子i(i=1,2,…,N)，更新策略如下：

（1）若Fitness(pbesti)＜Fitness(i)，则不更新对应的pbesti；若Fitness(pbesti)＞Fitness(i)，则用粒子i更新对应的pbesti；若Fitness(pbesti)=Fitness(i)，则比较pbesti与粒子i的特征数目，将特征数少的作为pbesti。

（2）若Fitness(gbest)＜Fitness(i)，则不更新gbest；若Fitness(gbest)＞Fitness(i)，则用粒子i更新gbest；若Fitness(gbest)=Fitness(i)，则比较gbest与粒子i的特征数目，将特征数少的作为gbest。

3.5 更新种群

交互操作和自我调整操作结束后得到新的种群构成新一代种群，并按照3.3节评价种群更新pbest和gbest。

图2为本文算法流程图。

Fig.2 Flow chart of BPSOBCI图2BPSOBCI算法流程图

4 实验

为证明本文改进策略的有效性和改进后算法的优越性，设置两组对比实验。第一组对比实验分别验证本文提出的基于特征聚类信息的初始化策略的有效性及基于粒子在决策空间中密度的交互操作的有效性。第二组对比实验则将本文改进后的特征选择算法与三个具有代表性的特征选择算法进行对比，验证本文算法的优越性。

4.1 实验参数设置

本文所有对比实验均在内存10.0 GB的PC机上运行，运行环境为Matlab R2016b。所有算法均使用五近邻算法（5-NN）作为分类器评价种群中粒子所代表的特征选择方案的优劣，且种群大小设置为40，学习因子c1=c2=2，惯性权重ω=0.9，粒子最大速度vmax=4，最小速度vmin=-4。

表1所示为本文实验采用的11个UCI数据集信息，其中包括二分类及多分类数据集，特征数目最少为13，最多为309。

Table1 Information of datasets表1 数据集信息

4.2 阈值φ取值实验

由于阈值φ的作用是判断粒子内部特征是否过于集中于相关特征聚类中的标准，且不必要的冗余特征将对分类性能产生不良影响。若阈值φ取值过大，则粒子进行自我调整的力度也将增大，过大的扰动操作会直接影响搜索稳定性。相反，若阈值φ取值过小，则粒子进行自我调整的力度相应减小，过小的扰动操作，将无法发挥调整作用。因此，阈值φ的选择应当兼顾稳定性和扰动合理性，本文在进行后续实验之前，首先对阈值φ的取值进行了相关实验，进一步对阈值进行选择。

实验分别在11个数据集上进行10次独立运行实验，每次运行最大迭代次数为100。所有取值性能均由最终平均特征数及平均分类错误率作为各个取值的性能评价标准。表2所示为阈值φ分别取0.1、0.2、0.3、0.4、0.5、0.6及0.7时的实验结果，其中，加粗字体表示各个数据集上进行实验所得到的最小平均错误率及最小特征数。

由表2的实验结果显示，φ取值为0.5时，在所有数据集上都得到了最小的平均分类错误率。其中，在特征数较多的几个数据集上，φ取0.5时取得的结果优势尤其明显。具体对其中3个数据集进行分析，LVST数据集有309个特征，φ取值为0.5时，平均分类错误率为0.088 5，比φ取值0.6时，错误率降低2.5%的同时，平均特征数减少了5.1。与φ取0.1的情况相比，平均特征数虽然只减少了0.4，但平均分类错误率却降低了17.6%。在Musk1数据集上，φ取值0.5时，平均错误率为0.108 2，比φ取值0.4时得到的0.113 8降低了4.92%，平均特征数也减少了0.5。φ取值0.6时，虽然平均特征数只相差0.3，但平均分类错误率同时降低了12.17%。Hillvalley数据集上，φ取值0.5时，得到平均分类错误率为0.414 9，比φ取值0.2时得到的0.416 7降低了0.43%，平均特征数减少了1.8。除了在Ionosphere数据集上，φ取值0.5未得到最小的平均特征数之外，在其他所有数据集上，均可以得到最小的平均特征数。

基于不同的特征规模，特征聚类后，采用阈值φ来衡量每种特征选择方案中特征的聚集程度，从而灵活地对粒子进行相应调整。实验结果证明，综合分类错误率和特征数两个指标上的表现，φ取0.5均得到了最好的结果。也说明了在特征规模不定的情况下，φ取0.5能够更有效地平衡特征选择过程中的稳定性及该策略的有效性，从而提高算法的整体性能。因此，在后续相关实验中，阈值φ的取值均设为0.5。

4.3 策略验证实验结果分析

为验证本文提出的初始化策略及交互操作能够有效提高粒子群优化算法的性能，本文在第一组实验中，除了BPSO之外，将基于特征聚类信息的初始化策略及基于粒子决策空间密度的交互操作分别加入粒子群算法中，得到基于聚类信息的BPSO（binary particle swarm optimization based on cluster，BPSOBC）、基于交互策略的BPSO（binary particle swarm optimization based on interaction，BPSOBI）及基于聚类信息和交互的BPSO（binary particle swarm optimization based on cluster and interaction，BPSOBCI）。4个算法分别在上述11个数据集上进行实验，算法最大迭代次数为200，根据算法适应度值的变化趋势来评价算法的收敛和搜索性能，从而验证本文提出的两个策略的有效性。

图3所示为BPSO、BPSOBC、BPSOBI和BPSOBCI分别在11个数据集上进行对比实验的结果。其中，X轴坐标表示迭代次数，Y轴坐标表示适应度函数值。从图3中折线图趋势可以看出，随着算法迭代次数的增加，适应度值均在降低，但相较于BPSO，BPSOBC和BPSOBI在搜索次数相同的情况下，搜索到适应度值更小的粒子。而BPSOBCI则能够在11个数据集上搜索到比其他3种算法更优质的粒子。这充分验证了本文所提出的两个改进策略的有效性。

对策略效果进行具体分析，如图3结果显示，在BPSO基础上加入基于特征聚类信息的初始化策略之后，在11个数据集上，BPSOBC均可以在初始情况下，降低种群的适应度值。其中，对于Hillvalley数据集，BPSO得到初始种群gbest对应的适应度值为0.459 1，而BPSOBC的初始值为0.363 3。在数据集Musk1上，BPSO得到初始种群gbest对应的适应度值为0.233 0，而BPSOBC得到的值为0.185 1。对于LVST数据集，BPSO得到初始种群gbest对应的适应度值为0.216 5，BPSOBC得到的值则为0.172 2。在这3个数据集上，BPSOBC得到初始适应度值明显降低。Hillvalley数据集的特征数为100，Musk1数据集的特征数为166，LVST数据集的特征数为309，特征数目较多时，社团检测算法能够更加灵敏地将特征划分为多个特征聚类，从而对特征进行更精确的区分。也正是由于这个原因，Wine数据集特征数目只有13，特征数目过少，社团划分算法对特征进行聚类的效果不明显，在控制特征数目的基础上，再采用聚类结果对特征进行选择，会导致特征中有效信息的损失。因此BPSOBC在特征规模较小时，适应度值没有高维特征集中同样显著的优势。但从总体上说，只有Wine是BPSOBC在11个数据集上唯一没有得到明显优质初始种群的数据集，因此本文提出的基于特征聚类信息的初始化策略虽然有损失有效信息的可能性，但总体表现稳定。迭代200次之后，BPSOBC在11个数据集上得到的解的适应度值均比BPSO更小，这显示BPSOBC得到优质的初始化种群之后，经过进化算法能够搜索到更理想的结果。综合11个数据集的实验结果，充分验证了本文提出的基于特征聚类信息的初始化策略能够减少冗余特征的同时提高分类性能，明显提升BPSO的性能。

分析BPSOBI的实验结果，图3实验曲线显示，BPSOBI在大部分数据集上进行200次迭代后得到的适应度值比BPSO要小。本文提出交互操作的目的在于通过粒子在决策空间中的密度对密度过大的粒子进行交互操作，避免种群陷入局部最优，从而增强种群的搜索性能。在图3实验图中，BPSOBI在11个数据集上均能够在很少的迭代次数下搜索到比当前适应度值更小的粒子，体现出BPSOBI较强的全局搜索能力及收敛性。在Hillvalley数据集上，BPSOBI的初始gbest对应的适应度值为0.425 2，迭代20次后，搜索到的gbest适应度值为0.396 5，迭代30次后，搜索到的gbest适应度值进一步降低为0.386 9的粒子，迭代40次后，再一次搜索到比当前适应度更小的粒子，说明算法具备良好的收敛性能。迭代100次后，BPSO、BPSOBC和BPSOBI实验曲线不再变动，算法搜索陷入局部最优状态，而BPSOBI在第150次迭代时仍搜索到适应度值为0.367 6的粒子，最终得到的gbest适应度值也比BPSO小，表现出BPSOBI具备较强的全局搜索能力。同样的，在Spectf数据集上，BPSOBI的搜索性能则得到更好的验证，初始gbest对应的适应度值为0.266 0，迭代30次后，gbest适应度值迅速下降到0.218 4。而算法迭代30次后，BPSO的gbest适应度值由初始的0.201 4降低到0.187 2，适应度值的降低幅度远小于BPSOBI，表现出BPSOBI的优秀收敛性能。且后续搜索中，BPSO和BPSOBC实验结果曲线变动幅度很小，BPSO在迭代到80次时才搜索到适应度值为0.183 9的粒子，BPSOBC在第70次迭代时才搜索到适应度值为0.161 9的粒子，两个算法在此之后均未搜索到适应度值更小的粒子，而BPSOBI则在第50次迭代时搜索到适应度值为0.213 6的粒子，迭代到第80次时搜索到适应度值为0.203 9的粒子，且在迭代到100次和130次时仍能够继续搜索到适应度值为0.200 6和0.171 1的粒子。此外，在LVST数据集、Libras数据集、Lung cancer数据集和Wine数据集上，BPSOBI在算法初期搜索中，将初始gbest的适应度值迅速降低到很小的水平，体现了本文提出的交互策略能有效提升算法的收敛性能。且由后期的搜索曲线分析，也充分验证了本文提出的交互策略能够在算法陷入局部最优状态之后，仍然保证算法具备有效的全局搜索能力，继续搜索到比当前更优秀的特征子集。

Fig.3 Experimental results on 11 datasets of two strategies图3 两种策略在11个数据集上的验证实验结果

分别验证本文提出的两种策略的有效性之后，由图3中BPSOBCI的实验曲线分析，在11个数据集上，BPSOBCI无论是在初始适应度值上，还是搜索性能上都比BPSO更优越，且在11个数据集上，BPSOBCI最后搜索到的适应度值均比BPSO搜索到的适应度值小。在Hillvalley数据集上，BPSO最终搜索到的gbest适应度值为0.387 2，而BPSOBCI最终搜索到的gbest适应度值为0.345 1，降低了10.87%。在Libras数据集上，BPSO搜索到的粒子最小适应度值为0.289 8，而BPSOBCI搜索到的粒子最小适应度值为0.240 6，降低了16.98%。在Parkinsons数据集上，BPSO搜索到的最小适应度值为0.253 7，同时，BPSOBCI搜索到最小适应度值为0.065 4，降低了74.22%。另一方面，BPSOBCI在大部分数据集上能够搜索到比BPSOBC和BPSOBI适应度值更小的粒子。因此验证了本文提出的两种改进策略组合能够极大提升BPSO算法的稳定性和搜索性能。

4.4 算法效果对比实验结果分析

在4.3节中分别验证了本文提出的两种策略的有效性，4.4节中进一步将本文算法与人工蜂群算法（ABC）、PSO(4-2)和PSO-2stage进行对比实验。其中，BPSOBCI、ABC和PSO(4-2)在11个数据集上分别运行20次进行测试，算法迭代200代。PSO-2stage则按论文运行40次，每次运行迭代100代。所有算法均以运行过程中的最终平均特征数及平均分类错误率作为算法性能的衡量指标。

表3所示为BPSOBCI与3个对比算法在11个数据集上的实验结果。其中，加粗字体表示所有算法里最小的平均分类错误率和最小平均特征数目。表3所示的结果显示，在11个数据集上，BPSOBCI得到的平均特征数比ABC、PSO(4-2)和PSO-2stage都要小，且除了Wine数据集，BPSOBCI在其他所有数据集上最终的平均分类错误率均要小于另外3个对比算法。实验结果充分验证了本文算法的优越性。

具体分析各个数据集的实验结果，LVST数据集特征数目为309，样本数目为126。在该数据集上的实验结果显示，BPSOBCI最终的平均分类错误率为0.098 8，相比PSO-2stage，BPSOBCI的分类错误率降低了约8%。平均特征数为121.1，PSO-2stage最终的平均特征数为153.025，平均特征数目减少了31.925。

Musk1数据集特征数目为166，样本数为476，BPSOBCI分类错误率至少降低约0.000 1，同时平均特征数目至少降低了22.3。Libras数据集，特征数目为90，样本数为360，BPSOBCI分类错误率降低约0.47%，平均特征数却比ABC、PSO(4-2)和PSO-2stage分别减少了10.95、18.75和13.675。而且Libras数据集分类数目为15，本文算法与其他3个对比算法相比，依然取得了最高的分类精度和最少的特征数目。在这3个具有代表性的数据集上，实验结果直接验证了本文算法在消除冗余特征方面有很强的优越性，且在其他数据集上均能取得较好的分类精度，同时大大减少冗余特征数目。然而在Wine数据集上，本文算法的分类精度比PSO-2stage降低了0.006，但与此同时，平均特征数目降低了约58.74%。相较于ABC，虽然平均特征数目只减少了0.05，但平均分类错误率同时降低了约30.8%，算法整体的稳定性也由此可以验证。

另一方面，从表3的对比实验结果中可以看出：同等条件下运行20次之后，本文算法在绝大部分数据集上，无论是分类错误率的标准差还是平均特征数的标准差相较于对比的3个算法要小很多。首先，所有数据集上得到的平均错误率的标准差均接近于0，足以显示算法在随机运行的情况下的稳定性。对于Musk1数据集，BPSOBCI分类错误率的标准差为0.018 3，比PSO-2stage的0.019 3降低了5.18%，平均特征数的标准差也减少了0.494 9。Sonar数据集上，BPSOBCI多次运行后，在平均分类错误率上的标准差为0.013 2，相较于PSO(4-2)得到的0.015 7，降低了15.92%。同时，平均特征数上的标准差为2.560 3，比ABC取得的3.278 3减少了0.718。Spectf数据集上，BPSOBCI分类错误率的标准差为0.020 7，比PSO-2stage的0.037 1降低了21.59%。平均特征数的标准差也减少了1.430 2。在平均分类错误率和平均特征数两个指标上取得优势的基础上，BPSOBCI上同时得到了最小的标准差，证明BPSOBCI在每次运行时，都能够稳定地搜索到最好的特征子集，有效地反映了BPSOBCI的稳定性。

Table3 Comparison between BPSOBCI and contrast algorithms on 11 datasets表3 BPSOBCI与对比算法在11个数据集上的对比实验结果

综上所述，对多个特征规模及样本数量各不相同的数据集的实验结果进行分析，分析结果显示，本文算法能够稳定地在兼顾提升分类精度的同时大大减少冗余特征的数目。在样本数目少，训练不足的情况下仍然可以取得稳定的实验结果。同时，在特征数目多的数据集上本文算法能够极大减少特征数目且保证分类精度稳定，优势十分明显。多分类和二分类数据集上也都可以取得良好的实验效果。

5 结束语

由于粒子群算法容易陷入局部最优状态，本文针对这一缺陷，根据粒子在决策空间中的密度，对粒子进行判断后进行交互操作，及时调整粒子，保持种群的多样性，避免算法过早收敛。同时，在算法中，结合特征聚类信息，改进PSO的初始化策略，提高了初始种群的质量。在11个数据集上的结果显示，与其他3个相关算法相比，本文算法在保证特征分类精度的同时，能够大大减少特征选择方案中的冗余特征，算法性能得到明显提升。