11.1 子集搜索与评价

        对一个学习任务来说，给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用.我们将属性称为"特征" (feature) ，对当前学习任务有用的属性称为"相关特征" (relevant feature) 、没什么用的属性称为"无关特征" (irrelevant feature). 从给远的特征集合中选择出相关特征于集的过程，称为"特征选择" (feature selection)。

为什么要进行特征选择:

• 减轻维数灾难问题（与降维的原因相同）
• 去除不相关特征往往会降低学习任务的难度

        我们不能直接用排列组合进行遍历所有可能子集，这样会遭遇组合爆炸。所以我们选择产生一个“候选子集”，评价它的好坏，然后根据评价结果产生下一个候选特征子集，再进行评价，持续进行直到无法找到一个更好的子集为止。 

如何根据评价结果获取下一个候选特征子集?

• 前向搜索：初始将每个特征当做一个候选特征子集，然后从当前所有的候选子集中选择出最佳的特征子集；接着在上一轮选出的特征子集中添加一个新的特征，同样地选出最佳特征子集；最后直至选不出比上一轮更好的特征子集。
• 后向搜索：从完整的特征集合开始，每次尝试去掉一个无关特征。
• 双向搜索：前向后向结合，每一轮逐渐增加选定相关特征，同时减少无关特征（前面增加的特征不会被去除）。
• 优点：思路简单，速度快，不用全部情况都遍历一遍。
• 缺点：使用贪心算法，不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，结果不一定是最好的。

如何评价候选特征子集的好坏?

\(\mathrm{Gain}(A)=\mathrm{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\)

        信息熵定义为：

\(\mathrm{Ent}(D)=-\sum_{i=1}^{|\mathcal{Y}|}p_k\log_2p_k\)

        信息增益Gain(A)越大，特征子集A包含的有助于分类的信息越多。对每个候选特征子集，可基于训练数据集D来计算其信息增益，以此作为评价准则。信息熵也是同理，只要能判断两个划分差异的机制都能用于特征子集评价。

        将特征子集搜索机制和子集评价机制相结合，即可得到特征选择方法。 

11.2 过滤式选择（Relief） 

        过滤式方法是一种将特征选择与学习器训练相分离的特征选择技术，即首先将相关特征挑选出来，再使用选择出的数据子集来训练学习器。Relief是其中著名的代表性算法，它使用一个“相关统计量”来度量特征的重要性，该统计量是一个向量，其中每个分量代表着相应特征的重要性，因此我们最终可以根据这个统计量各个分量的大小来选择出合适的特征子集。 

        Relief算法的关键是如何确定相关统计量。对于数据集中的每个样例xi，Relief首先找出与xi同类别的最近邻与不同类别的最近邻，分别称为猜中近邻（near-hit）与猜错近邻（near-miss），接着便可以分别计算出相关统计量中的每个分量。对于j分量：

\(\delta^j=\sum_i-\mathrm{diff}(x_i^j,x_{i,\mathrm{nh}}^j)^2+\mathrm{diff}(x_i^j,x_{i,\mathrm{nm}}^j)^2\)

        直观上理解：对于猜中近邻，两者j属性的距离越小越好，对于猜错近邻，j属性距离越大越好。更一般地，若xi为离散属性，diff取海明距离，即相同取0，不同取1；若xi为连续属性，则diff为曼哈顿距离，即取差的绝对值。分别计算每个分量，最终取平均便得到了整个相关统计量。

        标准的Relief算法只用于二分类问题，后续产生的拓展变体Relief-F则解决了多分类问题。对于j分量，新的计算公式如下： 

\(\delta^{j}=\sum_{i}-\mathrm{diff}(x_{i}^{j},x_{i,\mathrm{nh}}^{j})^{2}+\sum_{l\neq k}\left(p_{l}\times\mathrm{diff}(x_{i}^{j},x_{i,l,\mathrm{nm}}^{j})^{2}\right)\)

        其中\(p_l\)表示第\(l\)类样本在数据集中所占的比例，易知两者的不同之处在于：标准Relief 只有一个猜错近邻，而Relief-F有多个猜错近邻。 

11.3 包裹式选择（LVW） 

        与过滤式选择不同的是，包裹式选择将后续的学习器也考虑进来作为特征选择的评价准则。因此包裹式选择可以看作是为某种学习器量身定做的特征选择方法，由于在每一轮迭代中，包裹式选择都需要训练学习器，因此在获得较好性能的同时也产生了较大的开销。

        拉斯维加斯方法和蒙特卡罗方法是两个以著名赌城名字命名的随机化方法．两者的主要区别是：若有时间限制，则拉斯维加斯方法或者给出满足要求的解，或者不给出解，而蒙特卡罗方法一定会给出解，虽然给出的解未必满足要求；若无时间限制，则两者都能给出满足要求的解。

        LVW（Las Vegas Wrapper），它在拉斯维加斯框架下使用随机策略来进行特征子集的搜索，并以最终分类器的误差为特征子集评价准则。

1. 初始化：
   1. \(E\)：算法误差，初始化为无穷大
   2. \(d\)：特征子集的特征（属性）个数，初始化为特征集的特征个数
   3. \(A^*\)：特征子集，初始化为特征集
   4. \(t\)：连续没有优化效果的特征子集数，初始化为0
2. 循环部分：
   1. 随机产生一个特征子集\(A'\)，用\(A'\)的特征个数更新\(d\)
   2. 使用交叉验证法计算学习器\(\mathfrak{L}\)在\(A'\)下的误差
   3. \(\left.\left\{\begin{array}{l}\text{更新}t,E,d,A^*;\text{ 较目前最好的算法误差}E\text{小或者精度无提升但特征数变少}\\t=t+1, else\end{array}\right.\right.\)
3. 重复循环部分，直到满足停止条件控制参数，输出当前最好的特征子集\(A^*\)