特征选择查看源代码讨论查看历史

来自 孔夫子旧书网 的图片

特征选择是全国科学技术名词审定委员会审定、公布的科技类名词。

关于汉字的起源，中国古代文献上有种种说法，如“结绳”、“八卦”、“图画”、“书契”等，古书上还普遍记载有黄帝史官仓颉造字的传说。现代学者认为，成系统的文字工具不可能完全由一个人创造出来，仓颉如果确有其人，应该是文字整理者或颁布者。最早刻划符号距今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） 设置阈值一般是给算法的目标值设置一个评价阈值，通过目标与该阈值的比较决定算法停止与否。不过，要设置一个合适的阈值并不容易，需要对算法的性能有十分清晰的了解。否则，设置阈值过高会使得算法陷入死循环，阈值过小则达不到预定的性能指标。