特征选择综述阅读：A survey on feature selection methods

1.介绍

特征：观察过程中的可测量属性。
特征选择（消除变量）有助于理解数据，减少计算要求，降低维度灾难的影响，提高预测器的性能。
特征选择的方法包括：filter（过滤），wrapper（包装），embedded（嵌入）

2.过滤方法（Filter methods）

过滤方法使用变量排序技术作为按顺序选择变量的主要标准。

2.1相关性标准

最简单的标准是皮尔逊相关系数( Pearson correlation coefficient)，但只能用于检测变量和目标之间的线性相关性

2.2 互信息

两个量之间的互信息(MI)是对一个量的认识在多大程度上减少了对另一个量的不确定性的度量。因此一旦选择了计算 MI 的特定方法，那么最简单的特征选择方法之一就是找到每个特征和输出类标签之间的MI，并根据这个值对它们进行排序。但是简单的排序方法忽略了 内部特征(inter-feature) 的MI。

2.2.1 基于条件互信息的二值数据特性排名标准

$$s[n]=\underset{l<k}{\min }\hat{I}\left(Y;X_n\mid X_{v(I)}\right)\mid$$

上面的方程迭代地选择与类最大MI的特征，而不选择与已经选择的特征相似的特征。

2.3 小结

特征排序方法如皮尔逊相关系数，MI 选择的特征仍会存在冗余特征。同时，特征排序中容易忽略本身信息量少，但是和冗余特征合并后含有重要信息的特征。

3.包裹式方法（Wrapper methods）

包装方法将预测器作为黑盒，预测器性能作为目标函数来评估变量子集。

3.1 顺序选择算法

顺序选择算法从一个空集(完整集)开始，添加特征(删除特征)，直到得到最大目标函数。

顺序特征选择算法（SFS）：

1. 从一个空集开始，在第一步增加一个特征，使目标函数的值最大
2. 将剩余的特征单独添加到当前子集，并对新子集进行评估。如果个体特征具有最大的分类精度，那么它将永久地包含在子集中。
3. 重复第二步，直到特征数量达到指定要求

顺序后向选择算法（SBS）： 该算法从完整的变量集开始，每次删除一个特征，该特征的删除使预测器性能下降最小

缺点：没有考虑特征间的依赖

顺序浮动前向选择算法（SFFS）：

• 通过SFS增加特征，SBS删除特征（特征浮动，不是一直增加或减少）
  
  缺点：产生嵌套子集（没有考虑特征间依赖）

自适应顺序浮动前向选择算法（ASFFS）：

• 自适应参数 $r$：指定在包含阶段中添加的特征的数量
• 参数 $o$：在排除阶段移除最大数量的特征以提高性能

理论上ASFFS比SFFS获得的子集冗余更少，但这取决于目标函数和数据分布

Plus-L-Minus-r 搜索算法;

• 每个循环添加 $L$ 个特征删除 $r$ 个特征

3.2 启发式搜索算法

启发式搜索算法通过评估不同的子集来优化目标函数。通过在搜索空间中搜索或通过生成优化问题的解来生成不同的子集。

遗传算法（GA）：
对目标函数的全局极大值给出了最佳次最优子集

1. 随机产生种群。
2. 根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进行下一步。
3. 依据适应度选择父母，适应度高的个体被选中的概率高，适应度低的个体被淘汰。
4. 用父母的染色体按照一定的方法进行交叉，生成子代。
5. 对子代染色体进行变异。

CHCGA：
遗传算法的改良版本

• 从父母和后代中选出最好的N个个体，即较好的后代取代较不适合的父母
• 采用高度分裂的半均匀交叉(HUX)算子对非匹配等位基因的一半进行交叉，其中要交叉的位是随机选择的
• 每个亲代种群成员随机选择，没有替换，并配对进行交配。只有亲代的汉明距离（Hamming distance）的一半超过阈值 $d$，才进行交配
• 如果没有后代产生，并且阈值下降到零，就会引入灾难性的突变来创造一个新的群体

优点：收敛快，搜索速度快

3.3 包裹式方法总结

缺点：

• 寻找特征子集的过程耗费大量计算资源
• 容易过拟合，注意用一个单独的保留测试集可以用来指导搜索的预测准确性

4. 嵌入方法（Embedded methods）

嵌入方法主要通过将特征选择作为训练过程的一部分，以减少包裹式方法对不同子集重新分类所花费的计算时间。

4.1 贪心搜索算法

选择的特征满足以下两点：

• 最大化特征与类输出之间的MI
• 与所选特征子集之间的MI为最小值

$$I(Y,f)-\beta \sum _{s\in S}I(f;s)$$

$Y$ 是输出，$f$ 是当前选择的特征，$s$ 是已经选择的子集 $s$ 中的特征，$b$控制当前特征 $f$ 与子集 $S$ 中的特征之间的MI的重要性。

4.2 最大相关最小冗余算法 mRMR (max-relevancy, min-redundancy)

$$I\left(x_j;C\right)-\frac{1}{m-1}\sum _{x_1\in S_{m-1}}I\left(x_j;x_l\right)$$

$x_i$ 是子集 $S$ 中的第 $m$ 个特征，$C$ 为目标分类，而集合 $S_{m-1}$ 是迄今为止选择的具有 $m-1$ 个特征的子集。

该算法即令 $I\left(x_j;C\right)$ “相关性”最大，$\frac{1}{m-1}{\sum }_{x_1\in S_{m-1}}I\left(x_j;x_l\right)$ “冗余”最小

4.3 使用权重分类

对特征排序以移除特征

$$w_j=\frac{{\mu }_j(+)-{\mu }_j(-)}{{\sigma }_j(+)+{\sigma }_j(-)}$$

其中 ${\mu }_j(+)$ 和 ${\mu }_j(-)$ 分别表示类别 $+$ 和 $-$，${\sigma }_j$ 表示对应类别的方差，其中 j = { 1 , 2 , . . . , D } j = \{1,2,...,D\} j={1,2,...,D}

特征选择方式：

$$D(x)=w(x-\mu )$$

$w$ 是特征的排序 (rank) 或者权重 ，$D(x)$ 是决策，$\mu$ 是数据的均值。因此，特征的权重可以作为分类器的权重，权重的改变可以看作特征的移除。

SVM-RFE (SVM Recursive Feature Elimination)： 使用权重作为排名，并利用目标函数的变化进行搜索的SVM分类器，执行递归式特征消除。该算法主要用于二元分类算法。该算法要注意范式的选择：$l_2$范式用于SVM最小化问题。

4.4 神经网络

训练多层感知器网络，并使用从训练网络中计算的显著性度量来计算特征权值。

方法如下：

• 网络剪枝（Network Pruning）：对节点上的小幅度特征施加惩罚，并排除与这些输入特征连接的节点。常用于优化网络结构。
• 损失函数（cost function）：用于随机变量消除的损失函数
• 丢弃的特征使用多任务学习提高预测器性能
• 懒惰特征选择（Lazy Feature Selection）(LFS)：利用特征空间的稀疏性作为文本分类问题的特征选择方法

5. 其他特征选择方法

无监督学习：聚类
半监督学习：同时使用标记的数据（样本数量较少）和未标记的数据（大量可用）来修改仅由标记的数据得到的假设
集成特征选择：一个单一的特征选择算法在从自举法得到的不同数据样本子集上运行，结果被汇总以获得最终的特征集

6. 特征选择算法的稳定性

不稳定：算法对训练数据中的任何扰动产生不同的子集

提高特征算法稳定性：

• 使用各种度量
• 利用多种特征选择算法对组合后的特征进行排序和评分，结合多个分类器得到一个鲁棒子集以提高分类精度
• 对输入特征进行划分(根据其特征提取过程)，得到不同的分类器并进行组合

7. 分类器

7.1 支持向量机（SVM）

支持向量机是一种边际分类器，它使两个类中的数据样本之间的边际值最大，通过绘制最佳的超平面边界来分离数据。

决策函数：

$$D(x)=w\varphi (x)+b$$

其中 $\varphi (x)$ 将输入数据映射到M维空间的核函数

超平面到模式 $x$ 的距离：

$$\frac{D(x)}{\Vert w\Vert }$$

线性决策函数参数：

w = ∑ k a k y k x k b = ( y k − w ∗ x k )

$$\begin{array}{l} w=\sum_{k} a_{k} y_{k} x_{k} \\ b=\left(y_{k}-w * x_{k}\right) \end{array}$$ w=∑k​ak​yk​xk​b=(yk​−w∗xk​)​

其中向量 $w$ 是训练模式的线性组合，$a_k$ 是支持向量，$b$ 是支持向量的平均

目标方程：

$$J=\left(\frac{1}{2}\right)\Vert w{\Vert }^2$$

7.2 径向基函数网络（Radial Basis Function Network）

一种前馈神经网络：

隐藏层由径向对称高斯核组成：

$${\varphi }_j=e^{-\frac{{\Vert x-x_j\Vert }^2}{{\sigma }^2}},j=1...M$$

$M$为核函数的个数，$x_j$ 为核心（kernel centroid），

将核通过权重 $W_j$ 连接得到输出：

$$Y=\sum _{j=1}^M{W}_j{\varphi }_j$$

训练过程中权重的计算：

$$W={\varphi }^{-1}\cdot Y$$

其中矩阵 $\varphi$ 的元素 ${\varphi }_{ij}$ 给出第 $i$ 个样本的 ${\varphi }_j$ 值。核函数的质心可以用聚类算法寻找。

7.3 验证方法

交叉验证：

• 2重交叉验证（2-fold cross-validation）
• k重交叉验证（K-fold cross-validation）
• 留一交叉验证（Leave-one out cross-validation）(LOOCV)