机器学习第十六章特征选择

资料来源参考：

清华大学出版社周志华《机器学习》第十一章

子集搜索与评价

在机器学习中我们将用于描述任务数据的属性称之为特征（feature），对当前学习任务有用的属性则称之为相关特征（relevant feature），没用的则称之为无关特征（irrelevant feature）。从给定的特征集合中选择出相关特征子集的过程则称为特征选择（feature selection）

特征选择作为一个重要的数据预处理（data preprocessing）过程在机器学习中应用到。

意义

特征选择对于机器学习具有两个很重要的意义，第一个是用于对属性过多的维数灾难问题进行降维；第二个意义就在于，去除不相关的特征从而降低学习任务的难度，

冗余特征

无关特征特指与当前学习任务无关的特征，而这还有一类比较特殊的特征称之为冗余特征（redundant feature），这类特征并非与学习任务无关，而是它们所包含的信息可以由其它特征推算出来。例如已知一个方形的长与宽，那么他的面积就是一个冗余特征，因为这是可以算出来的。

作用

冗余特征在很多时候都不起作用，去除它们可以降低学习负担。但有时候冗余特征又可以降低学习任务的难度，例如如果我们要估算一个长方体的体积，那么在知道底面积的情况下显然比仅有底面长和宽更容易；换句话说，若某个冗余特征恰好对应完成了学习任务所需的“中间概念”，则该冗余特征是有益的。

不过为了简化讨论，我们暂且假设数据中不包含冗余特性，并假定初始的特征集合包含了所有的重要信息。

选择的方法

要从一个初始的特征集合中筛选出包含所有信息的特征子集，我们有两个环节：

第一个环节是子集搜索（subset search），先搜索出一个可能适合的候选者子集
第二个环节是子集评价（subset evaluation），评价出候选子集，再基于候选子集的好坏产生下一个候选子集…直至无法找到更好的子集

子集搜索

前向搜索

假定我们有初始特征集 $$\{a_1,...,a_d\}$ $，我们将每一个特征看作是一个特征子集，然后对这 $$d$ $个候选单特征子集作出评价，假设发现 $$\{a_2\}$ $最优，我们就将 $$\{a_2\}$ $作为第一轮的选定集；

接着我们在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假设在这 $$d-1$ $个候选两特征子集中 $$\{a_2,a_4\}$ $最优，且优于 $$\{a_2\}$ $，我们就可以将它作为第二轮的候选子集…以此类推，直到最优候选第 $$k+1$ $轮子集不如上一轮的选定集

这样的搜索方式我们就称之为前向（forward）搜索。

后向搜索

若我们从完整子集开始，每次去掉一个无关特征，我们就称之为**后向（backward）搜索

双向搜索

将前与后结合，每一轮逐渐增加选定相关特征（这些特征将不会在后续轮中被去除），同时减少无关特征，这便是双向（bidirectional）特征

这三种搜索方式都是贪心的，因为仅考虑了本轮特征选定集的最优，例如第一轮中 $$\{a_1\}$ $最优，但有可能第二轮中 $$\{a_2,a_3\}$ $却比所有的 $$\{a_i\}$ $更优，但事实上，若不使用穷举法，这样的情况是在所难免的。

子集评价

现在我们来讨论子集评价问题。

给定数据集D，假定D中样本所占的比例为$$$p_i(i=1,2,…,

) $$，为了便于讨论，我们假定这些样本均为离散型。对属性子集A，假定其根据其数值将D分成了V个子集$ ${D^1,D^2,…,D^V}$$$，每个子集中的样本在A上取值相同，于是我们可计算属性子集A的信息增益。

$Gain(A)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$

其中 $$Ent(D)$ $就是我们在决策树一章中介绍过的信息熵：

$Ent(D)=-\sum^{|Y|}_{k=2}p_klog_2p_k$

（假设每个属性有 $$v$ $个可能取值，则有$$$V=v^{v^{

}} $$（例如子集A中包含两个属性，每个属性$ $2 $$种取值，那么$ $V=2^2=4$$$表示会将数据集D划分为4个子集用于计算信息增益），这可能会是一个很大的值，因此我们实践中通常是从子集搜索中前一轮子集自己的评价值出发来进行计算。）

信息增益 $$Gain(A)$ $越大意味着特征子集A包含的有助于分类的信息越多，由此我们可以用基于训练数据集D计算得到的信息增益来作为评价的标准。

（既然信息增益可以，那基尼系数想必也是可以的）

更一般的，这其实就是用特征子集A对数据集D做一个划分，每个划分区域对应着A上的一个取值，通过估算这个取值与真实划分的差异来对A进行评价。也正因此，所有可以判断这种差异的方法都可以拿来作为特征子集的评价，信息增益就是其中一种。

常见的特征选择方法分为以下三类：

过滤式（filter）
包裹式（wrapper）
嵌入式（embedding）

过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，换言之特征选择过程与后续学习器是不相干的。这种做法就像是先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型。

Relief

Relief（Relevant Features）是一种著名的过滤式特征选择方法，该方法通过一个相关统计量来度量特征的重要性。其原理如下：

统计量本身是一个向量，其每个分量分别对应于一个初始特征，通过子集中每个特征所对应的相关统计量分量之和来决定特征子集的重要性。最终，我们需要确定一个阈值 $$\tau$ $，然后选择比该阈值大的相关统计量分量所对应的特征即可；或指定k个欲选取的特征个数，然后选满k个特征即可。

Relief计算相关统计量的方法如下：

给定训练集 $$\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$ $,对每个样本 $$x_i$ $Relief会先在 $$x_i$ $的同类样本中寻找其最近邻 $$x_{i,nh}$ $，称为猜中近邻（near-hit），再从 $$x_i$ $的异类样本中寻找其最近邻 $$x_{i,nm}$ $，称为猜错近邻（near-miss），然后，相关统计量对应于属性 $$j$ $的分量就为：

其中 $$x^j_a$ $表示样本 $$x_a$ $在属性 $$j$ $上的取值，而 $$diff(x^j_a,x^j_b)$ $在属性 $$j$ $为离散型时，当 $$x_a^j=x_b^j$ $时为0，否则为1；属性 $$j$ $为连续型时$$$diff(x_a^j,x_b^j)=

x_a^j-x_b^j

$$，注意$ $x_a^j,x_b^j $$此时都已经规范化到$ $[0,1]$$$区间。

从上式可以看出，若 $$x_i$ $与其猜中近邻在属性 $$j$ $上的距离小于与其猜错近邻的距离，那么属性 $$j$ $对区分同类与异类样本就是有益的。

实际上我们可以让Relief只在数据集的采样上而不必在整个数据集上估计相关统计量。这么一来，Relief的时间开销随采样次数以及原始特征数线性增长，因此，这是一个运行效率很高的过滤式特征选择算法。

但是，Relief是为二分类问题设计的，它的扩展变体Relief-F 能够处理多分类问题，假设数据集D中的样本来自$$$

$$个类别，那么对示例$ $x_i $$，如果它属于第$ $k $$类，则Relief-F先在第$ $k $$类样本中寻找$ $x_i $$的最近邻并将其设为猜中近邻，然后再在第$ $k $$类之外的每一个类中找一个$ $x_i $$的最近邻设为猜错近邻，这里的猜错近邻符号表示为$ $x_{i,l,nm}(l=1,2,…,

;l ≠k)$$$，由此，我们得到相关统计量关于属性j的分量为：

其中 $$p_l$ $表示第 $$l$ $类样本在数据集D中所占的比例。

包裹式选择

包裹式选择与过滤式选择不同，它将最终学习器的性能作为特征子集的评价标准，换言之，包裹式选择的目的就是为给定学习器“量身定做”一个最有利于其性能的特征子集。

一般而言，包裹式选择比过滤式选择更好，原因显而易见，因为它针对的是对最终学习器的优化，但是，由于在特征选择过程中需要多次训练学习其，因此包裹式选择的计算开销通常要比过滤式选择大得多（几乎每一次我们都可以发现，效果好的方法与机制往往开销都会比效果不好的大）

LVW

现在我们来介绍一个典型的包裹式特征选择方法，LVW（Las Vegas Wrapper），它在拉斯维加斯方法（Las Vegas method）的框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则。

拉斯维加斯方法的算法描述如图所示：

算法第8行 CrossValidation 意思是在数据集D上通过交叉验证来估算学习器 $$L$ $ 的的误差，这个误差是在使用特征子集 $$A'$ $时得到的。然后我们可以看到，如果它比当前特征子集 $$A$ $上的误差“还小”或者“相当并且包含的特征数更少”，那么我们就采用这个特征子集 $$A'$ $并让其参与下一轮特征选择。

由于我们采用了随机搜索特征子集的策略，因此算法设置了体制条件控制参数T以免长时间得不到一个特征子集。但是，若运行时间过短，T设置的过小，有很有可能得不到解，而理论上来说，若时间无限长LVW是可以给出一个可行解的。

嵌入式选择与 $$L_1$ $正则化

过滤式和包裹式选择都将特征选择过程与学习器训练过程区分开来，而与此不同的是，嵌入式选择则将特征选择过程与学习器训练过程融为一体。

我们曾经提到过正则化，但只是简单地分析了正则化的作用，在这里，我们先来进一步剖析正则化的原理与内容。

正则化与 $$L_0,L_1,L_2$ $范数

假设数据集为 $$D=\{(x_1,y_1),...(x_m,y_m)\},x∈R^d,y∈R$ $，我们考虑最简单的线性回归模型，并以平方损失函数作为loss函数，则优化问题为：

为了防止过拟合，我们引入 $$L_2$ $范数的正则化项

正则化参数 $$\lambda >0$ $。

这个式子又被称为岭回归（ridge regression）或者权值衰减（weight decay），常用来降低过拟合的风险。其中 $$L_2$ $范数的意思就是向量中所有元素的平方和的平方根。

不仅如此，我们还可以将正则化项中的 $$L_2$ $范数替换为 $$L_1$ $范数（ $$L_1$ $范数表示向量中各个元素的绝对值的和）：

该式又被称为LASSO（Least Absolute Shrinkage and Selection Operator）（直译为“最小绝对收缩选择算子”） $$L_1$ $范数的正则化项同样有降低过拟合风险的好处，但更关键的是，它可以有效“稀疏”得到的解，换言之，它可以让 $$w$ $中有更少的非零分量。

事实上 $$L_0$ $范数也有这个“稀疏”效果（ $$L_0$ $范数为向量中非0元素的个数），并且更加自然（放在式子中显而易见就是要减少非0元素），但由于 $$L_0$ $范数不连续，难以优化求解，所以还是常用 $$L_1$ $范数。

西瓜书中介绍了这样一个例子来辅助理解 $$L_1$ $的稀疏功能：

首先假设 $$x$ $仅具有两个属性，这样子 $$w$ $就只有两个分量 $$w_1,w_2$ $，将这两个分量作为两个坐标轴然后建立平面直角坐标系，然后，再在图上作出 $$w_1,w_2$ $在平方误差项上取值相同的点的连线，这条线称为该项的“等值线”，然后，再分别绘制出 $$L_1$ $范数和 $$L_2$ $范数的“等值线”，效果如下图：

（至于为什么这么画，可以很容易看出来， $$L_2$ $范数项的表达式为$$$\sqrt{w_1^2+w_2^2}=

_2 $$，所以是个圆，同理$ $L_1 $$范数表达式$ $

w_1

w_2

_1 $$，平方误差项表达式$ $(y-x_1w_1-x_2w_2)^2=d (这里我们把y,x_1,x_2,d都看为可变的常数)$$$）

而上面我们所说的式子(11.7)与(11.6)的优化问题的解又要在平方误差项与正则化项之间折中，因此这便体现在图中正则化项与平方误差项相交（因为两个项中的 $$w_1,w_2$ $取值一定是相同的），这个时候我们就可以发现， $$L_1$ $正则化项与平方误差项的交点经常会出现在坐标轴上，由此 $$w_1$ $或 $$w_2$ $就总是容易取到0，因而会更容易得到“稀疏”解。

而又因为 $$w$ $向量中取 $$0$ $的部分会使得对应的属性无法在最终模型中体现，换言之就是这部分属性被消解掉了。因此，这就得到了仅采用一部分初始特征的模型。

求解 $$L_1$ $正则化问题

求解这个问题我们可以采用近端梯度下降（Proximal Gradient Descent,PGD）

我们先令 $$\nabla$ $表示微分算子，对优化目标

若 $$f(x)$ $可导，且 $$\nabla f$ $满足 $$L-Lipschitz$ $条件，即存在常数 $$L > 0$ $使得

利普西茨条件，意思就是对区间D中的任意两个不同的 $$x_1,x_2$ $（在图中表示为 $$x,x'$ $）满足上述公式则必有 $$f(x)$ $在区间D上一致连续。

由此我们可以在 $$x_k$ $附近将 $$f(x)$ $通过二阶泰勒展开式近似为

const表示与 $$x$ $无关的常数， $$<.,.>$ $表示内积。

（如果对这个式子的推导有疑问，可以假设 $$x$ $只有一个分量，然后进行推导： $\hat{f}(x)=f(x_k)+f'(x_k)(x-x_k)+\frac{f''(x_k)}{2!}(x-x_k)^2\\ 设f''(x_k)为常数L（因为x_k是一个常数）\\ =const+f'(x_k)x+\frac{L}{2}(x^2-2xx_k)\\ =\frac{L}{2}(x-(x_k-\frac{1}{L}f'(x_k)))^2+const$ ）

式子（11.10）的最小值在下面这个式子中的 $$x_{k+1}$ $获得

（因为显而易见的，求 $$arg min_x a(x-b)^2+c$ $ 就是使 $$x=b$ $）

由此得知，若通过梯度下降法对 $$f(x)$ $进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数 $$\hat{f}(x)$ $，推广式子到（11.8），则每一步迭代的公式为

这时便在每一步对 $$f(x)$ $进行梯度下降迭代的同时考虑 $$L_1$ $范数最小化。

对于式子（11.2）我们可以先计算 $$z=x_k-\frac{1}{L}\nabla f(x_k)$ $，然后求解

令 $$x^i$ $表示 $$x$ $的第 $$i$ $个分量，将式子按分量展开可以看出 $$x^ix^j(i≠j)$ $这样的项是不存在的，换言之，我们可以断言 $$x$ $的分量互不影响，于是式子（11.13）有闭式解

其中 $$x^i_{k+1}$ $与 $$z^i$ $就是 $$x_{k+1},z$ $的第 $$i$ $个分量。因此，我们可以通过PGD使LASSO和其它基于 $$L_1$ $范数最小化的方法得以快速求解。

ZyBlog

机器学习第十六章特征选择

子集搜索与评价

意义