基于自适应模拟退火遗传算法的特征选择方法.pdf

万方数据

基于自适应模拟退火遗传算法的特征选择方法Method张昊，陶然，李志勇，杜华SimulatedAlgorithm0引言问题，已被证明是非确定性多项式(NP)完全问题，摘要：特征选择是机器学习及模式识别领域的重要问题之一。针对高维数据对象，特征选择不仅可以在保证数据完整性的情况下减少特征维数，还能够提高分类精度。文中提出了一种基于自适应模拟退火遗传算法的特征选择方法，该方法将模拟退火算法嵌入到自适应遗传算法的循环体中，利用模拟退火算法具有较强的局部搜索能力，并且能够使搜索过程避免陷入局部最优解的特点，解决了基本遗传算法收敛速度慢，时间复杂度高的缺点。实验结果表明，在保证分类正确率的前提下，该方法有效提高了特征选择效率。关键词：人工智能；特征选择；自适应遗传算法；模拟退火算法；搜索能力中图分类号：TGl56文献标志码：A文章编号：1000—1093(2009)01．0081．05AFeatureSelectionBasedAdaptiveAnnealingGeneticpattern特征选择的任务是从一组N个特征中按一定的选择标准选择出一组由，z(挖<N)个特征组成的特征子集。这个子集具有比特征全集更好的或和特征全集一样的分类功能，这实际是一个组合优化的没有多项式算法。所以最优特征子集的选择很重要。特征选择算法从模型上可分为Filter模型和Wrapper模型。一般来说Filter模型的效率高，效果差；Wrapper模型的效率低，效果好。为了解决这两种模型所存在的问题，文献[1]中提出了结合Filter第30卷第1期9年1月兵工学报Zhi—yong，DUHuaimportantmachineimprovedsimulatedalgorithmembedssire—optimalsolvetimecom—experimentmethodcorrectselection．selectiofi；adaptivealgorithm；simulatedARM^^IENTARIIJan．(北京理工大学信息科学技术学院，北京100081)onZHANGHao，TAORan，LI(SchoolInformationTechnology。BeijingTechnology，Beijing100081，China)Abstract：Featureselectionisofproblemsinlearningandrecognitionareas．Forhighdemensiandata，featuredimensionbedecreasedundertheconditionensuringdataintegrityclassificationbyfeatureselection．Abasedadaptiveannealinggeneticwasproposed，whichulatedcirclethatsimulat—edhasstrongabilitylocalsearchmakessearchingavoidsinkingintosolution，toshortcomingsslowspeedplexity．TheresultsshowimproveefficiencyKeywords：artificialintelligence；featurealgorithm；search收稿日期：2008—01—25基金项且：国防基础科研项目(C1120060497．06．02)作者简介：张吴(1981一)，男，博士研究生。E．mail：[e-mail]；陶然(1964一)，男。教授，博士生导师。E-mail；[e-mail]20ACTAVoI．30NO．12009ScienceInstituteoneaccuracyprocessconvergenceguaranteeratecanuses
万方数据

厶；一，。。降低，故，一一，avg可作为考察遗传算法学报是否收敛的尺度。Pf和P。是随着^。一厶。变化P。=1／(，一一^vg)，兵工1基于自适应模拟退火遗传算法的特征选择性能解个体遭到破坏，那么群体就可能拥有收敛到模型和Wrapper模型的Hybrid模型，虽然该模型在性能上有一定的提高，但是效果并不理想。特征选择算法从特征子集生成方式上又可分为搜索性和非搜索性算法。搜索性算法最为常见，其通过利用评价准则对所得到的特征子集进行评估，从而得到最优特征子集。在搜索策略方面，针对大数据集，JainK等人[2】提出了诸如正向搜索、反向搜索、顺序搜索等启发式搜索策略。KudoM等人[3]提出了比启发式搜索更有优势的随机搜索策略，如遗传算法。在大规模数据集上的特征选择，这些搜索策略的计算资源耗用大，收敛速度慢，时间复杂度