基于禁忌搜索算法的特征选择研究

摘要

随着计算机应用范围的不断扩大和Internet的全球普及，在各种应用系统中积累了越来越多的数据，这就很容易造成了“数据爆炸”问题，它已经悄悄来到我们的身边，甚至更严重的“数据雪崩”也正向我们走来，这就需要制定好对策，避免被数据活埋，并从大量的数据中挑选出重要的数据为我们所用。近年来，数据挖掘引起了信息产业界的极大关注，经过长期的研究发现，要高效对数据进行挖掘，首先必须对数据进行预处理，而在数据预处理过程中我们通常就会用到特征选择方法。
　　 近些年来各种智能优化方法接连出现，其中就包括禁忌搜索算法，研究者们发现当把智能优化算法运用于特征选择时，往往会得到令人满意的效果。随后基于禁忌搜索算法的特征选择被提出，但是研究者对它研究得还不是很充分，更注重其应用方面的研究，对于如何改进这个算法本身的性能研究得比较少。本文主要是研究如何进一步改善该方法，从而来扩大它的应用范围。
　　 本人在充分研究禁忌搜索算法的基础上对这个算法进行了三点改进：
　　 (1)众所周知，禁忌搜索算法对初始解的依赖性非常强，质量好的初始解可以帮助算法更快地完成搜索任务，在这里本人混合了遗传算法的相关思想来生成高质量的初始解，在此基础上再用禁忌搜索算法寻得最优特征解。
　　 (2)由于目标函数对禁忌搜索算法的搜索过程的影响很大，设置合适的目标函数就显得非常关键，在这里本人把Muhammad Atif Tahir提出的函数用到了此算法中，这个函数同时考虑了分类准确率和特征维数两个要素，这样做不仅能改善最后得到的特征解的质量，还能压缩特征维数，这也就减少了分类器分类所耗费的时间。
　　 (3)最后本人把贺一等提出的自适应搜索策略中的一些思想运用到了具体算法实践中来，首先把候选解集中分为一半的集中性搜索元素K和一半的多样搜索元素K＇，根据当前得到的解的优劣性相应地调整K的大小，K=K-1或K=K+1。这样我们就可以适应性地平衡集中性搜索和多样性搜索。
　　 本文是通过最后设计的KNN分类器的分类准确率和分类时间来判断改进后的算法是否具有更好的效果，只要能提高该算法的性能我们就可以接受。