基于遗传算法的特征选择方法.pdf

基于遗传算法的特征选择方法

赵云刘惟一
（云南大学信息学院计算机科学系，昆明<&""=%）
>?@1A6：8B12:B@C7A21$D-@

摘要特征提取广泛应用于模式识别、知识发现、机器学习等诸多领域，并受到了越来越多的关注’%(。对于一个给定的
待分类模式，特征提取要求人们从大量的特征中选取一个最优特征子集，以代表被分类的模式。该文对特征提取这一组
合优化及多目标优化问题提出了基于遗传算法的解决方法，把遗传算法作为识别或分类系统的“前端”，找出代表问题空
间的最优特征子集，以大大降低分类系统的搜索空间，从而提高搜索效率。

关键词遗传算法特征提取最优特征子集

文章编号%""!?E++%?（!""#）%&?""&!?"+文献标识码F中图分类号G*+"%

!"#"$%&’()*"$+,%"-"."&+/()0#/)12")"+/&3.1(%/+’4#
5’$(6,)7/,8"/9/
（H9I1.0@920-JK-@I/09.4DA92D9，L/2212M2AN9.7A08，O/2@A2;<&""=%）
3:#+%$&+：4969D0A2;1790-JJ910/.97PQADQA7-I0A@16J-.1;AN920175A71I.-R69@PQADQI618712A@I-.0120.-69A2
1PA:9N1.A908-JD-209207A2D6/:A2;I1009.2.9D-;2A0A-2，52-P69:;9:A7D-N9.8，12:@1DQA29691.2A2;$GQ979I.-R69@7
.9S/A.97969D0A-2-J17/R790-J100.AR/097-.J910/.97（J.-@1@/DQ61.;9.790）0-.9I.979200Q9I1009.270-R9D6177AJA9:$
GQA7I1I9.I.979207121II.-1DQ0-0Q9D-@RA210A-2-I0A@AT10A-212:@/60A?D.A09.A1-I0A@AT10A-2I.-R69@-JJ910/.9
7969D0A-2/7A2;;9290AD16;-.A0Q@7$GQ91II.-1DQ:97D.AR9:Q9.9A2N-6N970Q9/79-J;9290AD16;-.A0Q@7171UJ.-2092:U
0-1D6177AJAD10A-2-..9D-;2A0A-278709@A2-.:9.0-JA2:0Q9R9707/R790-JJ910/.9712:.9:/D90Q92/@R9.-JJ910/.97
/79:0-.9I.979200Q9I.-R69@7I1D97$
;"9<(%=#：V9290ADF6;-.A0Q@7，J910/.97969D0A-2，0Q9R9707/R790-JJ910/.97

%引言且能获得较高的识别率。
随着信息的日益膨胀及复杂性的不断加剧，我们所要解决!$!相关工作
问题的特征空间变得越来越庞大。因此，从大量候选特征中找特征选择策略主要有两类：
出代表问题空间的最优特征子集是十分必要的，这将很大程度（%）第一类是独立于分类性能的特征选择，这种方法通过
上减少分类系统的代价和运行时间。最优特征子集的选择是一一些已知的领域知识或统计信息对特征空间进行裁剪。
个组合优化问题，同时也是一个多目标优化问题，所以选用遗此类方法执行效率高，但无法保证裁剪后的特征空间不丢

传算法解决该问题是一个可行及理想的方法’!(。已证明，该问题失原始特征集包含的所有信息，而且因为是独立于分类性能来
是一个)*问题’+(，因此，寻找一个较好的近似算法具有现实进行选择，所以不能保证获得高的识别率。
意义。（!）第二类方法是在不会显著降低分类系统的性能的条件
文章第%部分为引言，第!部分描述了我们所要解决的问下，从可能的!个特征中依据某个评价标准选出"个特征（!#
题以及相关工作，第+部分讨论了用遗传算法进行特征提取的"）。例如贪心法’#(，,-.-/012345612758’&(，)1.92:.13,/5/21;1’<(
可行性和优势所在，第#部分给出了基于遗传算法解决该问题等等提出的方法。
的关键技术，最后为实验及结论部分。此类方法首先必须为其定义一个适当的评价函数，每个可
能特征都据此计算出权值，然后选择出权值最高的前"个特征
!问题描述和相关工作组成“最优”特征子集。但其由于忽略了特征间的相互关联，因
!$%问题描述此无法真正达到最优。
因为代表问题空间的每一个特征都会增加分类系统的代以上两类方法提到的有关技术存在如下不足：
价和运行时间，为提高搜索效率，首先应对特征空间进行压缩，（%）上述技术包含如下假设：关于数据集的一些信息是事
删去多余、对分类贡献小及对正确分类有影响的特征，找出能先可知的，但实际上这些信息一般很难