ML——特征选择和稀疏学习

子集搜索与评价

特征选择

特征选择的原因：1）属性过多易造成维数灾难，仅选择重要特征构建模型则能减轻该问题；2）去除不相关特征能降低学习任务的难度。

冗余特征：所包含的信息能从其他特征中推演出来。eg已知立方体底面长和宽，则底面积是冗余特征，但作为学习任务“中间概念”时能加速运算，例如计算立方体体积，知道底面积能加速运算。

欲从初始特征集合中选取一个包含所有重要信息的特征子集，一般包含两个环节：子集搜索与子集评价。

1.子集搜索一般分为前向搜索、后向搜索和双向搜索。

前向搜索：给定特征集合，将每个特征看做一个候选子集，对这d个候选单特征子集进行评价，假定最优，将作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这d-1候选子集中最优，且优于，将做为本轮的选定集，假定在低k+1轮时，最优的候选（k+1）特征子集不如上一轮的选定集，停止。

后向搜索：类似前向搜索，但从完整的特征集合开始，每次尝试去掉一个无关特征，逐渐减少特征的过程。

双向搜索：将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续轮中将确定不会被去除）、同时减少无关特征。

显然上述策略都是贪心的，因为仅考虑了使本轮选定集最优。

2.子集评价

特征子集A实际上确定了对数据集D的一个划分，这个划分与真实划分的差异越小，说明A越好。可通过信息熵判断这个差异。

给定数据集D,假定D中第i类样本所占的比例为。对于属性子集A，假定根据其取值将D分成了V个子集，每个子集的样本在A上取值相同，于是我们可计算属性子集A的信息增益：信息增益越大，则特征子集包含的有助于分类的信息越多。

特征选择方法

过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择与训练学习器过程无关。

Relief是一种著名的过滤式特征选择方法，它设计了一个“相关统计量”来度量特征重要性。对每个示例，relief先在其同类样本中找最近邻（猜中近邻），再从其异类样本中找最近邻（猜错近邻），则相关统计量对应属性j的分量为：

二分类Relief算法

最后对基于不同样本的估计结果进行平均，得到各属性的相关统计量分量，分量值越大，对应属性的分类能力越强。多分类Relief相较二分类有多个猜错近邻，计算公式为：

多分类Relief算法

Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量，是一种高效的过滤式特征选择方法。

包裹式选择

包裹式选择的目的是为给定学习器选择最有利于其性能、“量身定做”的特征子集。代表算法LVW是在拉斯维加斯方法框架下使用随机策略进行子集搜索，并以最终分类器的误差为特征子集评价准则。

LVW算法描述

嵌入式选择与L1正则化

嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，在学习器训练过程中自动进行特征选择。例如对线性回归模型的优化目标函数添加L1正则项：

LASSO:               

L1正则化有助于防止过拟合，常见的L2正则化也可实现这一目的：

岭回归：              

L1范数会趋向产生少量的特征（稀疏解），其求得的w会有更少的非零分量；L2会选择更多的特征，这些特征的权值都会接近于0。因此L1范数在特征选择上就十分有用，而L2范数则具备较强的控制过拟合能力。可以从下面两个方面来理解：

（1）下降速度：L1范数按照绝对值函数来下降，L2范数按照二次函数来下降。因此在0附近，L1范数的下降速度大于L2范数，故L1范数能很快地下降到0，而L2范数在0附近的下降速度非常慢，因此较大可能收敛在0的附近。

2）空间限制：L1范数与L2范数都试图在最小化损失函数的同时，让权值W也尽可能地小。假定x仅有两个属性，于是无论岭回归还是LASSO接触的w都只有两个分量，即w1,w2，我们将其作为两个坐标轴，然后在图中绘制出两个式子的第一项的”等值线”。

L1范数比L2范数更易得到稀疏解

稀疏表示与字典学习

将数据集D看成一个矩阵，每行对应于一个样本，每列对应一个特征，考虑特征具有稀疏性，则通过特征选择去除这些列，就得到了一个稀疏矩阵；数据的另一种稀疏性是指D中存在很多0元素，且并不是以整行整列的形式存在。

当样本具有这样的稀疏表达形式时，对学习任务有不少好处，例如使大多数问题线性可分，且不会造成存储上的巨大负担。

字典学习（稀疏编码）：为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表达形式从而使学习任务得以简化，模型复杂度得以降低。

字典学习的形式

采用变量交替优化的策略求解上式：1）确定映射字典的词汇量 k，并初始化字典 B，d＊k，其中 d 为样本属性数；2）固定住字典 B，求得样本集 X 通过字典映射后的稀疏表示 ；3）固定住  来更新字典 B；4）反复第2）、3）步，最终可得合适的字典 B 和样本 X 的稀疏表示 。

压缩感知

不同于特征选择和稀疏表示，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。能通过压缩感知技术恢复欠采样信号的前提之一是信号有稀疏表示。压缩感知一般分为“感知测量”和“重构恢复”两个阶段。感知测量关注如何对原始信号进行处理以获得稀疏样本表示，eg傅里叶变换、小波变换、字典学习、稀疏编码等；重构恢复关注如何基于稀疏性从少量观测中恢复原信号。

https://blog.csdn.net/u011826404/article/details/72860607