盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

机器学习基础：特征选择_sequential forward selection

作者：盐析白兔 | 2024-03-15 05:27:20

踩

sequential forward selection

1. 需要特征选择的原因

2. 特征选择的方法

2.1 Wrappers 包装法

2.1.1 可实现的Wrapper方法：sequential forward selection（贪心法）

2.1.2 可实现的Wrapper方法：sequential backward selection（消融法）

2.2 Filtering 过滤法

2.2.1 Pointwise Mutual Information（PMI）逐点互信息法

2.2.2 Mutual information（MI）互信息法

2.2.3 卡方检验

3. 特征选择的常见问题

4. 其他特征选择方法

4.1 TFIDF 词频-逆向文件频率选择法

4.2 Embedded 嵌入法

4.3 sklearn 中的特征选择

5. 模型选择的影响

1. 需要特征选择的原因

GIGO: Garbage In, Garbage out

数据集中往往包含一些噪声和无用的特征，这些特征就是垃圾，如果我们放任它们参与训练不加以选择的话，会导致模型输出垃圾的结果。

对数据做一些预处理和清洗的方法有：

数据清洗 data cleaning
数据聚合 data aggregation
缺失值填补 dealing with missing values
数据范围调整和数值归一化 scaling or normalization
特征二值化 bianarization

在对数据进行预处理和清洗之后，我们就可以进行特征选择了。

特征选择的主要目标是：

根据一些评价指标，让模型拥有更好的表现。

特征选择的其他目标是：

通过筛选出的重要特征来获得一些启发和对某些问题另外角度的理解

更少的功能 $\rightarrow$ 更小的模型 $\rightarrow$ 更快的回答；更准确的答案 >> 更快的答案。

2. 特征选择的方法

我们拿到一组数据以及确定了任务之后，我们如何筛选特征呢？一种方法是靠直觉和生活经验，即 $intuition$ 的方法。但绝大多数情况下你不能这么干，因为数据集可能很大，而且很多个特征之间的关系你也并不知道，所以最好的办法是根据某些统计学的知识来进行特征的筛选。

2.1 Wrappers 包装法

包装法采用递归的方式进行

具体方法：

从 $1$ 个特征开始，不断地增加特征的数量然后比较最终的预测结果是否有提升

或者从使用所有特征开始，不断地减少特征的数量直到减少到一个特征，进行观察

例子：对于天气数据选择最好的特征集

包装法的优点：

可以找到符合验证集的最佳特征集合

包装法的缺点：

对于一些特征数量很大的数据集，这几乎是不可实践的，因为假设一共有 $m$ 个特征，那么复杂度是：

$\binom{m}{1}+\binom{m}{2}+...+\binom{m}{m}=m+\frac{m!}{2!(m-2)!}+...+1=2^{m}-1$

完整的包装方法需要多长时间？

假设我们有一个快速的方法（例如 $NB$ ），在一个中等规模的数据集上（ $~50K$ 个实例）。如果每个训练——评估周期需要10秒来完成。对于m个属性：

$\left ( 2^{m}-1 \right )$ 组合 $\rightarrow$ $\approx \frac{2^{m}}{6}$ 分钟， $m=10 \rightarrow \approx 3 h$ ， $m=60 \rightarrow \approx 3.2^{15} h$ 。

所以包装法只对非常小的数据集有用。

2.1.1 可实现的Wrapper方法：sequential forward selection（贪心法）

这是一种使用贪心策略来完成特征筛选的方法，算法流程如下：

在每个单一属性上训练和评估模型。

选出能够导致最好结果的属性 $O$ 。

进行下列操作直到模型收敛：

训练和评估这个单一的最佳属性 $O$ 并且以 $O$ 为基础分别加上剩下的所有单一属性来构成包含两个属性的特征集合 $\left \{ O , T \right \},\left \{ O , H \right \},\left \{ O , W \right \}$ 。
再选出最佳的特征子集，然后以当前筛选出的特征子集为基础，以剩下的单个特征为原料不断地将这个集合不断扩大。

停止条件：表现不再提高（accuracy）

从上面的过程我们可以看到，经过不断迭代，最终到收敛的时候会选择出最佳的前 $n$ 个特征构成特征集合（假设特征空间一共有 $m$ 个特征）。

假设全部 $m$ 个特征都能够参与构成最后使用的特征空间，那么 $wrapper$ 的这过程的时间复杂度可以用如下公式计算：
$m+(m-1)+...+1=\frac{m(m+1)}{2}$

在实际的应用中收敛其实会更早到来，不会用尽所有的 $m$ 个特征，模型可能会很快的选择出一个最优的特征子集并完成收敛。但是也有可能收敛到一个次优甚至糟糕解决方案。

这个过程假设所有的特征之间是相互独立的

2.1.2 可实现的Wrapper方法：sequential backward selection（消融法）

这种方法是和 $forward$ 的筛选方式相对的一种筛选方法， $forward$ 的方法是刚开始使用的特征集合为空 $\left \{ \right \}$ 然后逐个地将最好的特征加入到这个集合中直到模型收敛形成最佳的特征子集

而 $backward$ 的方法的过程刚好相反，它是通过将全部的特征作为开始的集合，然后从这些特征中不断选出最不影响精度结果的特征然后从集合中剔除，最终剩下能满足模型收敛的最佳的特征子集。

算法的流程如下：

将所有的特征都用于模型的训练

删掉某一个特征，然后对模型重新训练和评估

进行如下的操作直至收敛：

从剩下的所有特征中分别单独删除单个的特征，对模型进行重新训练和评估
删除掉那个删掉之后让模型退化程度最小的特征（删除那个最可有可无的特征）

结束条件：性能的下降到某一个阈值 $\epsilon$ 之下

顺序逆向选择的优点：

在开始时删除大部分不相关的属性
当最佳子集很大时，表现最好

顺序逆向选择的缺点：

运行时间：属性越多，周期就越慢
在大型数据集上不可行

2.2 Filtering 过滤法

过滤法的出发点就是要对每个特征进行评估，衡量每个评估有多好，有多不好，然后过滤那些不够好的特征。过滤法和模型的训练是独立的，不需要通过模型的训练来迭代地选择特征，只是采用统计的方法来完成特征的筛选。过滤法分开单独考虑每个特征，因此时间复杂度是线性的。过滤法也是最常用的特征筛选方法。

我们如何评价一个特征是好是坏呢？

一个好的特征应该是和分类结果有相关关系的；也就是说这个特征能够对最终分类的结果起一定程度的作用。

哪个属性是好的， $a_{1}$ 还是 $a_{2}$ ？

$a_{1}$ 可能比较好：

$a_{2}$ 可能不够好：

很显然在这个例子中如果你只看 $a_{1}$ 的值你就能够得出 $c$ 的值，这种情况下，我们就说 $a_{1}$ 和 $c$ 的相关性很大。而它也就是一个对于 $c$ 分类任务而言很好的特征。

为了用数学的形式来衡量这种相关性，我们下面介绍三种常用的方法：

2.2.1 Pointwise Mutual Information（PMI）逐点互信息法

我们都知道满足独立性的两个事件 $A,C$ 其概率应该满足如下公式：

$P(A,C)=P(A)P(C)$ $P(C|A)=P(C)$

当 $\frac{P(A,C)}{P(A)P(C)}> > 1$ 的时候，属性 $A$ 和属性 $C$ 是有正向的相关关系的
当 $\frac{P(A,C)}{P(A)P(C)}\approx 1$ 的时候，属性 $A$ 和属性 $C$ 是相互独立的
当 $\frac{P(A,C)}{P(A)P(C)}< < 1$ 的时候，属性 $A$ 和属性 $C$ 是有负相关关系的

互信息的定义式：

$PMI(A=a,C=c)=log_{2}\frac{P(a,c)}{P(a)P(c)}$

最好的属性（特征）的衡量标准：与类别属性具有最大 $PMI$ 的属性。

例子：

这个实例中，属性 $a_{1}$ 有两种不同的值 $Y,N$ ，类别属性 $c$ 也有两种不同的值 $Y,N$ 。所以我们求算 $a_{1}$ 和 $c$ 之间的 $PMI$ 应该计算4个，即 $PMI(a_{1}=Y,c=Y)$ ， $PMI(a_{1}=Y,c=N)$ ， $PMI(a_{1}=N,c=Y)$ ， $PMI(a_{1}=N,c=N)$ 。

$PMI(a_{1}=Y,c=Y)$ ：

$P(a_{1}=Y)=\frac{2}{4},P(c=Y)=\frac{2}{4},P(a_{1}=Y,c=Y)=\frac{2}{4}$

$PMI(a_{1}=Y,c=Y)=log_{2}\frac{\frac{1}{2}}{\frac{1}{2}\cdot \frac{1}{2}}=log_{2}2=1$

$PMI(a_{2}=Y,c=Y)$ ：

$P(a_{2}=Y)=\frac{2}{4},P(c=Y)=\frac{2}{4},P(a_{2}=Y,c=Y)=\frac{1}{4}$

$PMI(a_{2}=Y,c=Y)=log_{2}\frac{\frac{1}{4}}{\frac{1}{2}\cdot \frac{1}{2}}=log_{2}1=0$

结论：对于 $a_{1}$ ， $a_{2}$ 来说， $a_{1}$ 的 $Y$ 和 $c$ 的 $Y$ 的相关性更大

特征好坏的判断标准：

与有吸引力的类别有很好的相关性：知道 $a$ 让我们更有信心地预测 $c$
与有吸引力的类别反向相关：知道 $\bar{a}$ 让我们更有信心地预测 $c$
与没有吸引力的类别有很好的相关性或相反的相关性：知道 $a$ 让我们更有信心地预测 $\bar{c}$ ，通常没有那么好，但仍然有用。

2.2.2 Mutual information（MI）互信息法

具体表达式：

考虑 $a$ ， $\bar{a}$ ， $c$ ， $\bar{c}$ 之间的 $PMI$ 的综合结果，即：

$MI(A,C)=P(a,c)log_{2}\frac{P(a,c)}{P(a)P(c)}+P(\bar{a},c)log_{2}\frac{P(\bar{a},c)}{P(\bar{a})P(c)}+P(a,\bar{c})log_{2}\frac{P(a,\bar{c})}{P(a)P(\bar{c})}+P(\bar{a},\bar{c})log_{2}\frac{P(\bar{a},\bar{c})}{P(\bar{a})P(\bar{c})}$

也可以表示为：

$MI(A,C)=\sum _{i\in \left \{ a,\bar{a} \right \}}\sum _{i\in \left \{ c,\bar{c} \right \}}P(i,j)log_{2}\frac{P(i,j)}{P(i)P(j)}$

$0log_{2}0=0$

例子：

用一张表来帮助我们计算互信息：

其中 $\sigma \left ( \cdot \right )$ 代表当前格子中的数量， $M$ 是总数。所以我们表示某个格子的概率，可以写成：
$P\left ( \cdot \right )= \frac{\sigma \left ( \cdot \right )}{M}$

现在将那张图转换成表格，可以写成

对于 $a_{1}$ 和 $c$ 的互信息计算过程可以如下表示：

$P\left ( a_{1} \right )=\frac{2}{4},P(c)=\frac{2}{4},P(\bar{a_{1}})=\frac{2}{4},P(\bar{c})=\frac{2}{4}$

$P(a_{1},c)=\frac{2}{4},P(\bar{a_{1}},c)=0,P(a_{1},\bar{c})=0,P(\bar{a_{1}},\bar{c})=\frac{2}{4}$

$MI(A,C)=P(a,c)log_{2}\frac{P(a,c)}{P(a)P(c)}+P(\bar{a},c)log_{2}\frac{P(\bar{a},c)}{P(\bar{a})P(c)}+P(a,\bar{c})log_{2}\frac{P(a,\bar{c})}{P(a)P(\bar{c})}+P(\bar{a},\bar{c})log_{2}\frac{P(\bar{a},\bar{c})}{P(\bar{a})P(\bar{c})}$

$=\frac{1}{2}log_{2}\frac{\frac{1}{2}}{\frac{1}{2}\cdot \frac{1}{2}}+0log_{2}\frac{0}{\frac{1}{2}\cdot \frac{1}{2}}+0log_{2}\frac{0}{\frac{1}{2}\cdot \frac{1}{2}}+\frac{1}{2}log_{2}\frac{\frac{1}{2}}{\frac{1}{2}\cdot \frac{1}{2}}=\frac{1}{2}\cdot 1+0+0+\frac{1}{2}\cdot 1=1$

$P\left ( a_{2} \right )=\frac{2}{4},P(c)=\frac{2}{4},P(\bar{a_{2}})=\frac{2}{4},P(\bar{c})=\frac{2}{4}$

$P(a_{2},c)=\frac{1}{4},P(\bar{a_{2}},c)=\frac{1}{4},P(a_{2},\bar{c})=\frac{1}{4},P(\bar{a_{2}},\bar{c})=\frac{1}{4}$

$MI(A,C)=P(a,c)log_{2}\frac{P(a,c)}{P(a)P(c)}+P(\bar{a},c)log_{2}\frac{P(\bar{a},c)}{P(\bar{a})P(c)}+P(a,\bar{c})log_{2}\frac{P(a,\bar{c})}{P(a)P(\bar{c})}+P(\bar{a},\bar{c})log_{2}\frac{P(\bar{a},\bar{c})}{P(\bar{a})P(\bar{c})}$

$=\frac{1}{4}log_{2}\frac{\frac{1}{4}}{\frac{1}{2}\cdot \frac{1}{2}}+\frac{1}{4}log_{2}\frac{\frac{1}{4}}{\frac{1}{2}\cdot \frac{1}{2}}+\frac{1}{4}log_{2}\frac{\frac{1}{4}}{\frac{1}{2}\cdot \frac{1}{2}}+\frac{1}{4}log_{2}\frac{\frac{1}{4}}{\frac{1}{2}\cdot \frac{1}{2}}=\frac{1}{4}\cdot 4\cdot 0=0$

从上面的计算结果我们可以得出结论： $a_{1}$ 和 $c$ 的相关性更大，因此 $a_{1}$ 特征比 $a_{2}$ 特征要好。

2.2.3 $\chi ^{2}$ 卡方检验

卡方检验的运作原理是：

通过统计学的方式来衡量两个属性之间的相关程度。

卡方检验在对两个属性进行计算的时候进行的假设是：

假设两个属性是独立的。

使用卡方检验我们同样需要使用一张表：

如果 $a$ ， $c$ 相互独立的话，则有： $P(a,c)=P(a)P(c)$

依然使用 $\sigma (\cdot )$ 表示某个格子中的数值，进而我们可以得到如下推导：

$P(a,c)=P(a)P(c)$ $\frac{\sigma (a,c)}{M}=\frac{\sigma (a)}{M}\cdot \frac{\sigma (c)}{M}$

$\sigma (a,c)=\frac{\sigma (a)\sigma (c)}{M}$ $E(W)=\frac{(W+Y)(W+X)}{W+X+Y+Z}$

$E(W)$ 是我们按照假设的期望值，即在两个属性独立的情况下应该得到的数值。而实际上我们会根据计算得到一个 $O(W)$ ，它代表了实际的观察值。

如果 $O(W)>>E(W)$

代表 $a$ 和 $c$ 伴随出现的程度比随机状态更加紧密——是一种可预测的状态（predictive）

如果 $O(W)<<E(W)$

代表 $a$ 和 $c$ 伴随出现的程度不如随机情况——是一种可预测的状态（predictive）

如果 $O(W)\approx E(W)$

代表 $a$ 和 $c$ 之间的关系几乎是随机的——是一种不可预测的状态（not predictive）

根据 $O(W),E(W)$ 我们可以计算卡方 $\chi ^{2}$ 的值，根据下列公式：

$\chi ^{2}=\frac{(O(W)-E(W))^{2}}{E(W)}+\frac{(O(X)-E(X))^{2}}{E(X)}+\frac{(O(Y)-E(Y))^{2}}{E(Y)}+\frac{(O(Z)-E(Z))^{2}}{E(Z)}$

$\chi ^{2}=\sum _{i\in \left \{ a,\bar{a} \right \}}\sum _{j\in \left \{ c,\bar{c} \right \}}\frac{(O_{i,j}-E_{i,j})^{2}}{E_{i,j}}$

得到的 $\chi ^{2}$ 值越大，代表两个属性 $a,c$ 之间的依赖性越大；也就越不支持原假设（两个属性相互独立）。

通过 $a_{1},a_{2}$ 分别和 $c$ 进行 $\chi ^{2}$ 计算的结果：

$a_{1}$ 的 $\chi ^{2}$

$\chi ^{2}=\frac{(O_{a,c}-E_{a,c})^{2}}{E_{a,c}}+\frac{(O_{\bar{a},c}-E_{\bar{a},c})^{2}}{E_{\bar{a},c}}+\frac{(O_{a,\bar{c}}-E_{a,\bar{c}})^{2}}{E_{a,\bar{c}}}+\frac{(O_{\bar{a},\bar{c}}-E_{\bar{a},\bar{c}})^{2}}{E_{\bar{a},\bar{c}}}$