机器学习理论之（9）：特征选择 Feature Selection_pmi算法特征过滤

为什么要进行特征选择

• 通常我们得到的数据集都是包含噪声和很多无用特征的，这些特征不仅不会帮我们达到我们的目的，还可能会干扰我们模型的选择，成为我们模型进行最终选择的 “烟雾弹”
• 所以机器学习界有一句话 “Garbage in Garbage out” 意思就是，特征没选好，给模型喂进去垃圾数据，模型的效果不可能好。
• 因此在进行模型选择和训练之前将数据按照任务进行有效的组织和筛选是非常必要的，这也是特征工程要做的事情。
• 为了解决上述的问题，当我们拿到数据之后会进行如下步骤：
  • 数据预处理：
    • 数据清洗 data cleaning
    • 数据聚合 data aggregation
    • 缺失值填补 dealing with missing values
    • 数据范围调整和数值归一化 scaling or normalization
    • 特征二值化 bianarization
  • 特征选择
• 在本节的内容中，我们着重研究特征选择的方法。

特征选择的主要目标

• 得到更高的模型精度（在某些评价指标下）

其他目标

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

特征选择的方法

• 我们拿到一组数据以及确定了任务之后，我们如何筛选特征呢？一种方法是靠直觉和生活经验，即 intuition 的方法。例如，给你一组全中国青少年的数据，让你建立一个身高预测的模型，那你其实可以很容易想到生活中我们认为的与身高相关的因素，例如：年龄，性别，肤色，体重，…，那么你就可以人为将这些特征筛选出来建立这个任务的模型。
• 但其实绝大多数情况下你不能这么干，因为数据集可能很大，而且很多个特征之间的关系你也并不知道，所以最好的办法是根据某些统计学的知识来进行特征的筛选。

Filtering 过滤法

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

是什么导致了我们对某个特征的评价是 “好” 还是 “坏”呢？

• 一个好的特征应该是和分类结果有相关关系的；也就是说这个特征能够对最终分类的结果其一定程度的作用。
  
• 很显然在这个例子中如果你只看 $a_1$ 的值你就能够得出 $c$ 的值，这种情况下，我们就说 $a_1$ 和 $c$ 的相关性很大。而它也就是一个对于 $c$ 分类任务而言很好的特征

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

Pointwise Mutual Information (PMI) 逐点互信息法

• 我们都知道满足独立性的两个事件 $A,C$ 其概率应该满足如下公式：$$P(A,C)=P(A)P(C)$$ $$P(C|A)=P(C)$$
• 因此我们说：

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

• 互信息的定义式：
  $$PMI(A=a,C=c)=lo{g}_2\frac{P(a,c)}{P(a)(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)$ 举例：
  
  同样的方式，我们可以求算相同条件下 $a_2$ 属性和 $c$ 的逐点互信息：
  

• 从上面的例子我们可以得出结论：对于 $a_1,a_2$ 来说， $a_1$ 的 $Y$ 和 $c$ 的 $Y$ 的相关性更大；通俗的理解可以是，张三笑，王五一定笑，李四笑，王五不一定会笑。在“笑”这个事件上，张三对王五的影响更大。

好的特征的判断标准

• 与某类别属性有正向的关联：知道特征 $a$ 可以对判断 $c$ 的类别更加有信心
• 与某类别属性有反向的关联：知道特征 $\bar{a}$(not $a$) 可以对判断 $c$ 的类别更有信心

Mutual information (MI) 互信息法

• 考虑 $a,\bar{a},c,\bar{c}$ 之间的 PMI 的综合结果，即：
• 也可以表示成：
  

Note: $0lo{g}_{2}0=0$

• 如果我们还是使用这个例子来计算互信息 MI
  
• 我们可以用一张表来帮助我们计算互信息
  
• 其中 $\sigma (\cdot )$ 代表当前格子中的数量，$M$ 是总数
• 所以我们表示某个格子的概率，可以写成 $$P(\cdot )=\frac{\sigma (\cdot )}{M}$$
• 现在将那张图转换成表格，可以写成
  

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

根据互信息的公式：

用同样的方法我们可以得到 $a_2$ 特征和 $c$ 的互信息：

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

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

• 卡方检验的运作原理是：通过统计学的方式来衡量两个属性之间的相关程度
• 卡方检验在对两个属性进行计算的时候进行的假设是：假设两个属性是独立的。
• 使用卡方检验我们同样需要使用一张表：
  

如果 $a,c$ 相互独立的话，则有：$$P(a,c)=P(a)P(c)$$
依然使用 $\sigma (\cdot )$ 表示某个格子中的数值，进而我们可以得到如下推导:

• $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$ 值越大，代表两个属性 $a,c$ 之间的依赖性越大；也就越不支持原假设（两个属性相互独立）

• 接下来通过 $a_1,a_2$ 分别和 $c$ 进行 ${\chi }^2$ 计算的结果

• $O_{a,c}=\sigma (a,c)=2,E_{a,c}=\frac{(W+Y)(W+X)}{W+X+Y+Z}=\frac{(2\cdot 2)}{4}=1$
  
  
  
  用红色框里面的来计算 $E(\cdot )$ 用蓝框中的部分来计算 $O(\cdot )$

Wrapper 包装法

• 包装法通常采用递归的方式进行
• 从 $1$ 个特征开始，不断地增加特征的数量然后比较最终的预测结果是否有提升
• 或者从使用所有特征开始，不断地减少特征的数量直到减少到一个特征，进行观察
  

Advantages

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

Disadvantages

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

可实现的 Wrapper 方法

sequential forward selection

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

1. 拿出每一个单独的特征进行训练和测试
2. 选出能够导致最好结果的属性 $O$
3. 进行下列操作直到模型收敛：

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

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

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

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

• 在实际的应用中收敛其实会更早到来，不会用尽所有的 $m$ 个特征，模型可能会很快的选择出一个最优的特征子集并完成收敛

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

sequential backward selection

• 这种方法是和 forward 的筛选方式相对的一种筛选方法，forward 的方法是刚开始使用的特征集合为空 { } \{\} {} 然后逐个地将最好的特征加入到这个集合中直到模型收敛形成最佳的特征子集
• 而 backward 的方法的过程刚好相反，它是通过将全部的特征作为开始的集合，然后从这些特征中不断选出最不影响精度结果的特征然后从集合中剔除，最终剩下能满足模型收敛的最佳的特征子集。
• 算法的流程如下：

1. 将所有的特征都用于模型的训练
2. 删掉某一个特征，然后对模型重新训练和评估
3. 进行如下的操作直至收敛：

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

4. 结束条件：性能的下降到某一个阈值 $ϵ$ 之下

特征选择的常见问题

特征类型

类别、标签 (Nominal) 形式的特征

• 对于一些类别形式（Nominal）的特征，例如天气的属性有三个不同的值：晴天、阴天、雨天： O u t l o o k = { s u n n y , o v e r c a s t , r a i n y } Outlook = \{sunny, overcast, rainy\} Outlook={sunny,overcast,rainy}，这种用名词的形式表示的特征

处理方式1：
使用独热编码；

处理方式2：

• 这种处理方式我也没弄懂是什么意思，后面弄懂了再补

连续 (Continuous) 形式的特征

• 通常采用高斯分布来估计概率
• 根据中心极限定理，当数量很多的时候随机变量大多复合高斯分布
• 对于较小的数据集或者是特殊情况（疾病类型的特征）也可以采用二项分布或者多项式分布

多分类问题

• 多分类问题解决起来的难度通常是远大于二分类问题
• PMI, MI, ${\chi }^2$ 都是根据每一个类别（per-class）来进行分别求算的
• 需要根据每个不同的 class 选取不同的特征来训练分类器来获得最好的预测结果
• 下面的例子是通过 推文 来确定一个人所处的位置

其他特征选择方法

TFIDF

• 名为：词频-逆向文件频率 选择法
• TF 指的是词频：term frequency
• IDF 指的是逆向文件频率：inverse document frequency
• 如果某个词或短语在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
  
  
• 在这个公式中可以看到 $f_{d,t}$ 是某个词 $t$ 在文件 $d$ 中出现的频率，$N$ 代表了系统中一共存在的文件数量；$f_t$ 代表了一共有多少个文件里面包含了 $t$ 这个词
• 因此 $\frac{N}{f_t}$ 越大代表在这个文件系统中越少的文件包含了这个词 $t$，而 $f_{d,t}$ 越大代表了当前文件中这个词的出现频次越高。
• 综上所述，如果 $w_{d,t}$ 越大，就代表这个词 $t$ 可以帮助文件 $d$ 在整个文件系统中被区分出来。

Embedded 嵌入法

• 通过决策树或者带有正则化的回归模型来筛选有用的特征
• 例如：通过 sklearn 里面决策树有关的属性 feature_importance_ 可以得到每个特征的重要程度，根据这些特征重要程度的排名，可以筛选出最重要的特征子集
• 使用嵌入法和使用 filter 方法不同，我们就很难去界定一个有效的临界值（filter 中使用卡方检验可以用 0.05 或者 0.01这种值来衡量相关性）。这种情况下，如何指定一个阈值来帮助我们筛选特征也是需要考虑的问题
• 另外，嵌入法引入了算法来挑选特征，并且每次挑选都会使用全部特征；而且由于使用算法来挑选特征，所以挑选的算法的运算速度会直接影响到嵌入法挑选特征的速度，比如选择 KNN 和 决策树 的嵌入法性能上会差别很大

sklearn 中的特征选择

模型选择的影响

• 对于 KNN 模型来说，特征选择是必要的；因为 KNN 需要对每个特征上进行距离求算
• 朴素贝叶斯和决策树对于特征选择的依赖较轻
• SVM 可以在没有特征选择的情况下进行的很好