论文部分内容阅读
特征选择是一个从原始数据集中选择出最优特征子集的过程,它是通过降低数据集维度来提高学习算法性能的重要手段,也是机器学习过程中关键的数据预处理步骤。在保证一定分类精度的前提下,使用特征选择方法删除数据集中不相关和冗余的特征,解决了数据集中特征数量庞大、特征之间相互作用复杂的问题,从而降低后续机器学习任务中的难度,使分类器的工作既快又准确。元启发式算法是指一类通用型的启发式算法。在时间和成本有限的条件下,元启发式算法有助于在有限的时间内从巨大的解空间中找到近似最优解。学者们试图将元启发式算法应用到求解复杂的特征选择问题,其中受大自然启发的元启发式算法在各个领域证明了他们的潜力,可以为不同的优化问题提供解决方案。但是,至今没有特定的算法能给出所有优化问题的最佳解决方案。基于自然现象、物种智慧及觅食行为,学者们提出了许多基于不同理论和技术的算法,例如以遗传算法为代表的传统进化算法、蚁群优化、粒子群优化、布谷鸟搜索算法、萤火虫算法等。同样受到自然灵感启发的乌鸦搜索算法(Crow search algorithm,简称Cr SA)是一种新型的元启发式算法,它是由Askarzadeh在2016年提出。该算法的主要思想是:乌鸦作为一种群居鸟类,它具有导航的能力,存储和寻找食物的智慧,以及避免自己的食物被其他同伴偷取的聪明大脑。通过对Cr SA的分析,我们发现可以利用Cr SA解决离散空间搜索问题,特别是求解特征选择问题。由此,我们提出基于乌鸦搜索算法的特征选择算法(Feature selection using crow search algorithm,简称FSCr SA)。为了验证FSCr SA的有效性,我们将FSCr SA用在三种分类器上指导学习过程,分别为SVM,J48和KNN分类器,并且在多个数据集上进行实验。通过与传统的机器学习特征选择算法和基于进化计算的特征选择算法比较,FSCr SA能够在数据集中选择辨识度较强的特征,不仅大幅度降低了特征子集的规模,而且提高了分类准确率。通过对FSCr SA的分析,我们发现算法在初始化以及搜索阶段具有局限性,导致维度缩减能力不高,由此我们对FSCr SA进行改进,提出了Improved Feature Selection UsingCrow Search Algorithm(简称:IFSCr SA)。我们使用反向学习搜索策略设置乌鸦在离散空间的初始位置,利用反向学习的优点,使算法的初始值不是完全随机,我们选择较优的初始值作为初始位置从而提高寻优速度;采用Lévy飞行方法平衡全局搜索与局部搜索,通过Lévy飞行步长的调节,使算法在前期不过早陷入局部最优,在后期又能快速收敛于全局最优;我们同时提出使用贪婪策略的更新机制,从而进一步加快算法的收敛速度。通过实验结果可以证明,相比于FSCr SA,IFSCr SA在不降低分类准确率的条件下,维度缩减能力更强。