特征选择算法

1.特征选择的定义

特征选择技术是从高维数 据中获取有效信息的重要手段，是机器学习领域的重要技术，也是主要的降维技术（Dimensionality Reduction） 。特征选择可用于为分类任务选择最相关的特 征，同时消除不相关和冗余的特征。特征选择可以找到原始特征空间中重要属性 的集合，而后再构建模型。特征选择能够去除不相关的特征，获得可以产生优秀 预测模型性能的特征子集 。特征选择属于机器学习中预处理的步骤，可以保留特征属性的物理含义。特征选择技术可以缩短构建模型的时间，减少存储空间并 提升分类模型性能。

2.特征选择的框架

特征选择框架由子集生成，子集评估，结束准则以及结果验证四部分组成。

子集生成是指基于指定的搜索方法，在特征搜索空间中选择特征子集，被选 中的特征子集将进入下一步，即子集评估。

       特征子集生成策略是特征选择过程的关键组成部分，它决定了如何生成不同的 特征子集．特征子集生成的过程受到 3 因素的影响：搜索起点、搜索空间和所搜方法;

通常有四种搜索起点方法可供选择 [66]：1) 正向搜索；2) 反向搜索；3) 双向搜索； 4) 随机搜索．这些方法可以根据需求选取，每种方法都有不同的特点和适用场景．具体描述如下：

1）序列前向搜索（Sequential Forward Generation），特征子集X从空集开始，依照评估标准，依次选择一个特征x加入集合X直到满足预先设定好的特征子集中的数目或无法继续选择下一最优特征为止。

2）序列后向搜索（Sequential Backward Generation），特征子集X从全集开始，根 据一个评价标准每次从中剔除掉一个特征x，使得剔除后评价函数达到最优，迭代操作直到满足预设的特征子集中特征数目或无法继续移除下一特征为止。

3）双向搜索（Bidirectional Generation）结合序列前向和序列后向搜索，两方相同时开始，直到达到预设的特征子集中特征数目或无法选择下一特征位置。

 4）随机搜索（Random Generation）搜索起点随机，增加和删除特征也同时具有随机性。

3. 特征选择算法的类型

特征选择算法主要分为以下四种类型。

3.1 过滤式（Filter）

 将特征选择过程独立于分类模型，仅仅依靠数据本 身的特点，采用指定评价函数来对特征的重要性进行排序。一般选取重要性最高 的前几个特征作为最优特征子集，其中选取特征的个数为指定的数字，或者是通 过搜索评价算法来确定特征子集。过滤式的特征选择过程如下图所示。过滤式 特征选择算法的时间复杂度低，但是由于后续分类算法不参与选取特征子集的过 程，因此不能保障所选特征在分类模型中具有良好的性能。该算法适合对高维数 据进行初步地有监督特征选择，从而大幅地缩短其他后续特征选择算法对特征进 一步筛选所需的时间。

常用的过滤式特征选择算法有Relief算法、mRMR算法和t检验法等。t检 验是一种常用的基于数学统计的过滤式特征选择算法，常用在高维数据集中。其 中t检验特征选择算法的原理是该方法可以找到正负样本之间平均差异性最显著 的特征。

3.2 封装式（Wrapper）

特征选择的过程中与指定的分类器相结合，每次 迭代通过计算模型的预测结果来评估特征子集的性能，并寻找最佳的特征集合。 封装式的特征选择过程如下图所示。封装式特征选择算法的搜索机制主要有顺序搜索以及启发搜索。在处理高维数据时，如果采用大量迭代的方式进行特征选 择，从中选取具有最佳分类性能的特征子集，作为最终选择特征，那么所需时间 巨大。因为需要不断训练模型，并且如果在子集评价过程中过于追求特征集合的 高分类性能指标，那么容易出现模型的过拟合。所以封装法的一个重要任务是在 追求模型性能与运行时间上达到一个平衡。常见的基于封装式的特征选择算法包括采用顺序搜索的方式，如序列前向选择和前向浮动搜索等，以及采用随机搜索 方式的基于元启发式特征选择算法，如二元灰狼算法，二元生物地理优化算法和 二元人工蜂群优化算法等。

3.3 嵌入式（Embedded）

       结合了特征选择过程和分类学习模型，能够 在训练模型的同时根据所评价的特征的重要性选取特征集合，并得到分类模型的 性能指标。

决策树是一个典型的嵌入式特征选择算法，该算法在训练决策树的同时对特 征进行分割。Lasso算法是一种经典的基于正则化模型的嵌入式特征选择算法， 其主要原理是在引入惩罚因子的最小二乘上得到最小平方损失，并得到很多系数 为0的特征，当回归系数为0的时候，代表这个变量与分类任务的相关性不强，从而可以删除大量无关特征。

3.4 整合式（Ensemble）

特征选择算法结合了多个特征选择算法，可以兼 顾学习模型性能和计算效率。该方法可以通过发扬一个算法的优点来弥补另一个 算法不足。最流行的整合式特征选择算法主要分为两个步骤。第一部分采用过滤 式特征选择算法，在特征子集空间中去除那些含有信息量少的特征集合。第二步 采用封装式方法对特征集合进行再次筛选。整合式算法可以在合理时间内得到高 性能的解，在提升分类模型性能的同时降低对计算资源的消耗。