改进的粒子群算法优化的特征选择方法
李 炜1，巢秀琴2+
【摘 要】特征选择是数据挖掘中数据预处理的一个重要步骤，因此选择出最优的特征子集可有效地降低学习算法的数据维度和计算成本。采用二进制粒子群优化算法（binary particle swarm optimization algorithm，BPSO）来对特征选择过程进行优化。提出基于特征聚类信息进行种群初始化的策略，其中特征的聚类由社团划分算法完成，并根据划分后的信息，在初始化过程中减少信息冗余，提高初始化种群的质量。提出一种基于决策空间相似性的自适应局部搜索策略，其中粒子的相似性指数由粒子在决策空间中的相似性确定。进化过程中，自适应地调整粒子进行局部搜索，避免算法早熟。最后，选择三种代表性的优化算法分别在11个UCI数据集上进行对比实验。实验结果表明，改进后的BPSO算法得到的特征选择结果在降低特征数目方面明显优于其他对比算法，且分类精度也有显著提高。 【期刊名称】计算机科学与探索 【年(卷),期】2019(013)006 【总页数】15
【关键词】二进制粒子群优化算法；特征聚类；交互操作；粒子密度；群智能算法
Received 2018-12-11,Accepted 2019-01-29. CNKI
网
络
出
版
:2019-03-
06,http://kns.cnki.net/KCMS/detail/11.5602.TP.20190304.1707.004.html 李炜,巢秀琴.改进的粒子群算法优化的特征选择方法[J].计算机科学与探
索,2019,13(6):990-1004.
LI W,CHAO X Q.Improved particle swarm optimization method for feature selection[J].Journal of Frontiers of Computer Science and Technology,2019,13(6):990-1004.
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的过滤-封装特征选择方法来解决图像处理中的特征选择问题。该方法分为两个阶段：在第一个阶段中，采用两种典型的过滤式技术，
改进的粒子群算法优化的特征选择方法
