西瓜书 第十一章 特征选择与稀疏学习

上一章我们提到了维度灾难,维度灾难会导致距离计算困难和样本稀疏等问题,缓解维度灾难的两个主要方法,一个就是降维上一章已经介绍过了,这一章主要介绍另一种方法特征选择。

11.1子集搜索与评价

相关特征:对当前学习任务有用的属性。
无关特征:对当前学习任务没用的属性。
冗余特征:其包含的信息可以从其他属性推演出来。如:我们已经有一个属性是正方形的边长和正方形的面积,那么这个时候,面积就是一个冗余特征,它可以通过边长来推演。
特征选择:从给定的特征集合中选择出相关特征子集的过程。
【注:冗余特征不一定会增加学习任务的难度,有可能降低。】

为什么要进行特选择?
减少维度,在样本中一个特征或属性代表一个维度,进行特征选择可以减少维度,从而缓解维度灾难。
降低学习难度,去除一些无关的属性,有利于提高学习效率。

那么我们要怎么进行特征选择呢?要选择出合适的特征子集主要有两个环节,一个是我们如何评价选择了一个一个特征后对于整个特征子集是好是坏,另一个是我们如何在根据上一个属性的评价结果下选择出下一个属性。所以特征选择主要分为两个步骤:子集搜索、子集评价。

子集搜索

①前向搜索:假设特征集合中有d个特征,我们从d个中遍历选择出一个最优的特征,然后将它作为第一轮的选定集,再将d-1个特征与第一轮进行组合选择出最优的,且优于第一轮的选定集,包含两个属性的特征子集,将它作为候选子集,接着第三轮遍历重复,直到最优的(k+1)个属性子集不如上一轮的选定集时则停止将上一轮的选定集作为特征选择的结果。
②后向选择:从整个特征集合开始,每次去掉一个属性,去掉属性后优于去掉属性前,不断遍历,直到去掉后没有优于去掉前的时候则暂停,将去掉前的集合作为特征选择的结果。
③双向选择:每一轮逐渐增加选定相关特征(这些特征在后续轮中确定不会去除),同时减少无关特征。

子集评价

我们要如何评价一个特征子集的好坏呢?我们要明白每一个特征子集实际上都是对数据集进行一种划分,在划分完后我们希望划分在一起的数据集越相似越好,可以参考一下之前的决策树,所以我们可以利用划分后的结果是否合理来对特征子集进行评价,如信息增益:Gain(A)=Ent(D)-\sum_{v=1}^V{\frac{|D^v|}{|D|}}Ent(D^v),其中信息熵定义为Ent(D)=-\sum_{k=1}^{|\gamma|}P_k\log_2P_k信息增益越大,意味着特征子集包含的有助于分类的信息越多。

常见的特征选择

①过滤式选择
②包裹式选择
③嵌入式选择

11.2过滤式选择

过滤式选择先对数据集进行特征选择,再通过选择后的特征来训练学习器。选择过程与训练过程无关。

Relief

思路:设计一个“相关统计量”来度量特征的重要性,每一个分量对应一个特征,由分量的大小来决定特征的重要性,通过设置一个阈值,选择出比阈值大的统计量对应的特征,或者设置要选取的特征数k,取出最大的k个统计量对应的特征。
猜中近邻:x_i的同类样本中寻找最近邻x_{i,nh}
猜错近邻:x_i的异类样本中寻找其最近邻x_{i,nm}
相关统计量对应属性j的分量为:{\delta}^j=\sum_{i}-{diff(x_i^j,x_{i,nh}^j)^2}+diff(x_i^j,x_{i,nm}^j)^2其中x_a^j表示样本x_a在属性j上的取值,diff(x_a^j,x_b^j)取决于属性j类型,若为离散型,则x_a^j=x_b^jdiff(x_a^j,x_b^j)为0,否则为1;若属性j为连续型,则diff(x_a^j,x_b^j)=|x_a^j-x_b^j|.
这个式子的理解:若其值小于0则说明该属性对于区分同类和异类样本有益,反之则无益。

Relief-F

Relief-F是Relief的变形,可以用于处理多分类问题,其原理在上面的式子中加入了不同类样本占总样本的权重,以此来衡量第i类样本与其异类样本间猜错近邻的距离重要性。
{\delta}^j=\sum_{i}-{diff(x_i^j,x_{i,nh}^j)^2}+diff(x_i^j,x_{i,nm}^j)^2其中p_l为第l类样本在数据集D中所占比例。

11.3包裹式选择

包裹式特征选择:直接将学习器的性能作为评价特征子集的标准,即为学习器选择使其性能最优的特征子集。

LVW

思路:通过随机选择一个特征子集,进行学习器训练,使用交叉验证法得到训练后学习器的误差,接着随机产生特征子集进行训练,获得误差,若误差小于上一个学习器的误差,将用当前的特征子集保留下来,若大于则保留上一个特征子集,接着迭代直到一定的次数。

LVW算法描述.PNG

11.4嵌入式选择与L_1正则化

嵌入式特征选择是将特征选择过程与学习器训练过程融为一体。两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。

给定数据集,以线性回归为例,以平方误差为损失函数:\min_w{\sum}^m_{i=1}(y_i-w^Tx_i)^2.
但是当特征数大于样本数时,容易陷入过拟合,所以通过引入正则化来缓解过拟合。

引入L_2正则化项,称为“岭回归”。\min_w{\sum^m_{i=1}(y_i-w^Tx_i)^2+{\lambda}||w||^2_2}.
通过引入L_2正则化项,可以显著的降低过拟合的风险。
引入L_1正则化项,称为“LASSO”。\min_w{\sum^m_{i=1}(y_i-w^Tx_i)^2+{\lambda}||w||_1}.
L_1范数和L_2范数都能有助于降低过拟合风险,但是L_1范数比L_2范数更容易获得稀疏解,即它求得的w会有更少的非零分量。
所以同时使用L_1范数和L_2范数可以避免过拟合和实现降维。\min_w{\sum^m_{i=1}(y_i-w^Tx_i)^2+{\lambda_1}||w||_1}+{\lambda_2}||w||_2^2.

11.5稀疏表示与字典学习

稀疏性的两种理解
①矩阵中有许多列与当前任务无关,去除这些列,特征可以获得稀疏性。
②矩阵中有许多0元素,但是这些0元素并不是整行或者整列存在。
稀疏表示:用较小的基本信号的线性组合来表达大部分或者全部的原始信号,即选择一个矩阵A和一个字典矩阵B,使得A*B尽可能的还原x,且A尽可能稀疏,A就是x的稀疏表示。

1.PNG

字典学习

为普通稠密表示的样本找到合适的字典,将样本转化为合适的稀疏表示形式,从而学习任务得以简单化,模型复杂度得以降低,通常称为“字典学习”,以称为“稀疏编码”。
数据字典最简单的形式是:\min_{a_i}||x_i-Ba_i||^2_2+\lambda||a_i||_1.
其中x_i为第i个样本,B为数据字典,a_ix_i的稀疏表示。
补:上式求解的方法是先固定B来求得各个样本的稀疏表示,然后固定a_i来对B进行逐列求解,重新对上面两步进行迭代,最终求得B和a_i

11.6压缩感知

根据奈奎斯特采样定理,令采样频率达到模拟信号最高频率的两倍,则采样后的数字信号就保留了模拟信号的全部信息。
而压缩采样为数据的压缩与恢复提供了另一种思路,只要信号是稀疏的且采用了随机亚采用机制(不相关性),则可以在远低于采样定理要求的采样点重建恢复。

压缩感知分为:感知测量和重构恢复两个阶段。
①感知测量:关注如何对原始数据进行处理以获得稀疏样本表示。
②重构恢复:关注是如何基于稀疏性从少量观测中恢复原始信号。

假定对长度为m的离散信号x进行采样:y={\Phi}x其中\Phi对信号x的测量矩阵,它确定以什么频率进行采样以及如何将采样样本组成采样后的信号。
而往往x都不是稀疏的,所以我们需要在某种稀疏基上进行稀疏表示。令x={\Psi}s,\Psi为稀疏基矩阵,s为稀疏系数。所以方程为:y={\Phi}{\Psi}s=AS,在已知y、\Psi、\Phi下求解s。

压缩感知过程.png

目前,压缩感知的重构算法主要分为两类:
(1)贪婪法:它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近,此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。
(2)凸优化算法:它是把0范数放宽到1范数通过线性规划求解的,此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。

参考文档:
嵌入式选择
稀疏表示
压缩感知

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容