西瓜书学习笔记-特征选择与稀疏学习

特征选择与稀疏学习

1. 子集搜索与评价

我们将属性称为特征，与学习任务相关的为相关特征，无用的属性为无关特征。从给定特征集合中选择出相关的特征子集的过程称为特征选择。

进行特征选择的主要原因：
减小数据维度
降低学习难度

如何进行特征选择？从以下两点进行考虑：
如何根据评价结果来获取下一个特征子集？
如何评价候选特征子集的好坏？

给定特征集合A = {a1,a2,a3...ad}
我们对每个特征进行评价，假定a2最优，则将{a2}作为第一轮选定集。然后在剩下的d-1个特征中选择，假定构成了{a2，a4}，若优于{a2}，则作为第二轮选定集。以此类推。
这样逐渐增加相关特征的策略为“向前搜索”，类似的，逐渐减少的称为“向后搜索”。

对于子集的评价，我们可以计算属性子集A的信息增益

信息增益越大说明属性子集A有助于分类的信息越多。

常用的特征选择方法可分为三类：过滤式、包裹式、嵌入式。

2 过滤式选择

过滤式方法先对数据集进行特征选择，然后训练学习器。特征选择过程与后续学习器无关。
代表算法为Relief
该方法设计了一个相关统计量来度量特征的重要性。该统计量是一个向量，每个分量对应一个初始特征，特征子集的重要性由特征对应的分量之和来决定。

3 包裹式选择

包裹式特征选择将学习器的性能作为特征子集的评价准则。
显然，包裹式的特征选择结果更好，但是需要多次训练学习器，计算开销更大。
代表算法LVW

4 嵌入式选择

嵌入式选择是将特征选择过程与学习训练过程融合进行的。即在学习的过程中自动的进行特征选择。

5 稀疏表示与字典学习

将数据集考虑为一个矩阵，行为样本，列为特征。
特征选择的问题是特征具有稀疏性，即矩阵中许多列与学习无关。
另外一种稀疏性，D所对应的矩阵有很多0元素。以文档分类为例，我们将行视为一个文档，列为字。以字典为例，有40000+列，但以常用字字典为列，约3500列。显然，给定的文档中，将会有大量的列为0。

后一种稀疏性使得文本数据在大多问题上线性可分，可以很好的学习，同时稀疏矩阵的存储也有很多高效方法可以使用。
所以，我们需要从一般的任务中，学习一种“字典”，将普通稠密样本表达D转为一种适当的稀疏表示。
称为字典学习或稀疏编码。

6 压缩感知

显然y，x，Φ组成的是一个欠定方程，无法进行求解。

虽然s任然是欠定的，11.20没有解决任何问题，但是，若s具有稀疏性，则这个问题会变得可以解决。因为稀疏性使得未知因素的影响大为减小。式中ψ为稀疏基，A的作用类似于字典，将信号转为稀疏表示。

压缩感知关注如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
压缩感知分为感知测量和重构恢复两个阶段，感知测量关注如何对原始信号进行稀疏样本表示，重构恢复关注如何从基于稀疏性从少量观测中恢复原信号。