特征选择查看源代码讨论查看历史
![]() |
特征选择是全国科学技术名词审定委员会审定、公布的科技类名词。
关于汉字的起源[1],中国古代文献上有种种说法,如“结绳”、“八卦”、“图画”、“书契”等,古书上还普遍记载有黄帝史官仓颉造字的传说。现代学者认为,成系统的文字工具不可能完全由一个人创造出来,仓颉[2]如果确有其人,应该是文字整理者或颁布者。最早刻划符号距今8000多年。
名词解释
特征选择( Feature Selection )也称特征子集选择( Feature Subset Selection , FSS ),或属性选择( Attribute Selection )。是指从已有的M个特征(Feature)中选择N个特征使得系统的特定指标最优化,是从原始特征中选择出一些最有效特征以降低数据集维度的过程,是提高学习算法性能的一个重要手段,也是模式识别中关键的数据预处理步骤。对于一个学习算法来说,好的学习样本是训练模型的关键。
此外,需要区分特征选择与特征提取。特征提取 ( Feature extraction )是指利用已有的特征计算出一个抽象程度更高的特征集,也指计算得到某个特征的算法。
特征选择过程一般包括产生过程,评价函数,停止准则,验证过程,这4个部分。
四要素
一般而言,特征选择可以看作一个搜索寻优问题。对大小为n 的特征集合, 搜索空间由2n-1 种可能的状态构成。Davies 等证明最小特征子集的搜索是一个NP 问题,即除了穷举式搜索,不能保证找到最优解。但实际应用中,当特征数目较多的时候, 穷举式搜索因为计算量太大而无法应用,因此人们致力于用启发式搜索算法寻找次优解。一般特征选择算法必须确定以下4 个要素:1)搜索起点和方向;2)搜索策略;3)特征评估函数;4)停止准则。
搜索起点和方向
搜索起点是算法开始搜索的状态点,搜索方向是指评价的特征子集产生的次序。搜索的起点和搜索方向是相关的,它们共同决定搜索策略。一般的,根据不同的搜索起点和方向,有以下4 种情况:
1)前向搜索搜索起点是空集S,依据某种评价标准,随着搜索的进行,从未被包含在S 里的特征集中选择最佳的特征不断加入S。
2)后向搜索搜索起点是全集S,依据某种评价标准不断从S 中剔除最不重要的特征,直到达到某种停止标准。
3)双向搜索双向搜索同时从前后两个方向开始搜索。一般搜索到特征子集空间的中部时,需要评价的子集将会急剧增加。当使用单向搜索时,如果搜索要通过子集空间的中部就会消耗掉大量的搜索时间,所以双向搜索是比较常用的搜索方法。
4)随机搜索随机搜索从任意的起点开始,对特征的增加和删除也有一定的随机性。
搜索策略
假设原始特征集中有n 个特征(也称输入变量),那么存在2n-1 个可能的非空特征子集。搜索策略就是为了从包含
2n-1 个候选解的搜索空间中寻找最优特征子集而采取的搜索方法。搜索策略可大致分为以下3 类:
1)穷举式搜索它可以搜索到每个特征子集。缺点是它会带来巨大的计算开销,尤其当特征数较大时,计算时间很长。分支定界法(Branch and Bound, BB)通过剪枝处理缩短搜索时间。
2)序列搜索它避免了简单的穷举式搜索,在搜索过程中依据某种次序不断向当前特征子集中添加或剔除特征,从而获得优化特征子集。比较典型的序列搜索算法如:前向后向搜索、浮动搜索、双向搜索、序列向前和序列向后算法等。序列搜索算法较容易实现,计算复杂度相对较小,但容易陷入局部最优。
3)随机搜索由随机产生的某个候选特征子集开始,依照一定的启发式信息和规则逐步逼近全局最优解。例如:遗传算法(Genetic Algorithm, GA)、模拟退火算法(SimulatedAnnealing, SA)、粒子群算法(Particl Swarm Optimization,PSO)和免疫算法(Immune Algorithm, IA)等。
特征评估函数
评价标准在特征选择过程中扮演着重要的角色,它是特征选择的依据。评价标准可以分为两种:一种是用于单独地衡量每个特征的预测能力的评价标准;另一种是用于评价某个特征子集整体预测性能的评价标准。
在Filte方法中,一般不依赖具体的学习算法来评价特征子集,而是借鉴统计学、信息论等多门学科的思想,根据数据集的内在特性来评价每个特征的预测能力,从而找出排序较优的若干个特征组成特征子集。通常,此类方法认为最优特征子集是由若干个预测能力较强的特征组成的。相反,在Wrapper 方法中,用后续的学习算法嵌入到特征选择过程中,通过测试特征子集在此算法上的预测性能来决定它的优劣,而极少关注特征子集中每个特征的预测性能如何。因此,第二种评价标准并不要求最优特征子集中的每个特征都是优秀的。
停止准则
停止标准决定什么时候停止搜索, 即结束算法的执行。它与评价准则或搜索算法的选择以及具体应用需求均有关联。常见的停止准则一般有:
1)执行时间即事先规定了算法执行的时间,当到达所制定的时间就强制终止算法运行,并输出结果。
2)评价次数即制定算法需要运算多少次,通常用于规定随机搜索的次数, 尤其当算法运行的结果不稳定的情况下,通过若干次的运行结果找出其中稳定的因素。
3) 设置阈值一般是给算法的目标值设置一个评价阈值,通过目标与该阈值的比较决定算法停止与否。不过,要设置一个合适的阈值并不容易,需要对算法的性能有十分清晰的了解。否则,设置阈值过高会使得算法陷入死循环,阈值过小则达不到预定的性能指标。
参考文献
- ↑ 中国“汉字”从何而来?每个汉字,都是仓颉造出来的吗?,搜狐,2022-10-01
- ↑ 造字的仓颉,为何叫“仓颉”?甲骨文揭开了颠覆性的一幕,搜狐,2022-09-12