目录

前言

什么是特征选择？

为什么要特征选择？

特征子集的搜索机制/评价机制

过滤式（filter）

包裹式（wrapper）

嵌入式（embeding)

总结

---

前言

        笔者学习到周志华的《机器学习》11章特征选择与稀疏学习部分，发现很感兴趣，所以顺势整理出一篇文章，主要梳理特征选择的部分，分享给有同样学习兴趣的同志。当然，如果出现错误也欢迎交流~

什么是特征选择？

        在判断一个人是否得了流感时，我们普通人往往看是否发烧、是否咳嗽，但是准确率往往不高，而专业的医生只需要看一份报告就知道具体的是否患病、以及什么类型的流感。换句话说，对于一个特定的任务，有些特征很关键，而有一些特征不那么重要。我们把比较重要的、可以推进任务完成的特征成为“相关特征”(relevant feature)，而从给定的特征集合中选取特征子集的过程就是特征选择。

为什么要特征选择？

        那么问题来了，我们为什么非得选出一部分特征出来呢？直接把所有特征都放进模型里不行吗？这里有很重要的原因在于训练效率的问题。使用太多特征，很明显会降低训练的效率，提高硬件和时间成本，甚至产生“维数灾难”，这一点和降维学习有异曲同工之处。而且，去除不相关的特征有利于降低学习的难度，毕竟我们更希望解决一个更简单的问题，而不是把问题复杂化。

        另外，在所有特征中还存在一部分“冗余特征”（redundant feature）,即必须排除的特征。比如，一个圆的特征包括了圆心、半径、面积，但是我们很明显可以发现，面积完全由半径所决定，因此半径和面积具有强相关性，就必须去除某一个特征。

特征子集的搜索机制/评价机制

        基于以上的讨论，我们可以发现特征选择的必要性。但是，我们可能没有任何的先验信息，比如对于一个瓜的好坏，我们完全不知道叶子大小是否重要，也不知道它和根茎粗细是否有相关性。而这个时候，笨方法就是遍历所有可能的特征子集，但其缺点也非常明显，即浪费了太多算力。一种可行的方法是，我们先找出一个“候选子集”，评价一下他的好坏，在根据这个候选子集和新的特征子集的比较，选一个更好的，不断提高分数，直到找到最好的子集。这里包含了两个问题：我们怎么找下一个新的候选子集？我们怎么知道哪个子集好？对应着特征子集的搜索机制和评价机制。

        子集搜索。我们对于特征集合{},我们可以先选择单一的特征最优子集，比如我们在所有单特征中发现是最优的，就把它作为第一个候选子集；然后在这个子集的基础上一个一个增加最优候选子集，直到无法再提高子集的评价，这种方法叫做“前向（forward）”搜索。那反过来，从全集开始，一步步剔除特征，就是“后向（backward）”搜索。

        显然这种搜索方法是基于贪心策略的，即每一步都寻求当时最优解。

        子集评价。在分类任务中，我们可以通过计算信息增益的方式，衡量每个候选子集对于分类的帮助程度。更一般的来说，一个特征子集A实际上确定了对数据集D的一种划分，而通过样本的标记我们可以知道真实的划分结果Y，当这两者相差越小，说明划分的越正确，评价就越高。

        基于以上讨论，我们终于可以了解具体的特征选择方法，主要介绍三种：过滤式、包裹式、嵌入式。

过滤式（filter）

        过滤式的核心思路是在训练学习器之前，就把特征筛选好，而不影响后续的学习过程。这里介绍经典的Relief方法，该方法的核心是设计了一个“相关统计量”来衡量特征的重要性。

        “相关统计量”是一个向量，其中每个分量对应一个初始特征，而不同特征子集具有不同的部分分量，其重要性是由对应的相关统计量分量之和所决定的。这里我们可以使用启发式算法 ，设定一个阈值，只要比这个阈值大的相关统计量所对应的特征就可以加入候选。

        具体如何构造这个统计量呢？假设给定训练集,对于任意,Relief先在其同类样本中寻找最近邻,称为“猜中近邻（near hit）”；再从其异类样本中寻找最近邻，称为“猜错近邻（near miss）”。然后，相关统计量对于属性j的分量为：

        

其中表示在属性j上的取值，同理。diff（i，j）表示两者之间的距离，这一点关于不同的情况有不同的公式，比如离散型可以直接取0，1，分别表示相同和不同类型。

        分析以上公式可以发现，如果和猜中近邻的距离小于猜错近邻的距离，即整个式子大于0，那么这个分类就是有好处的（把异类区分了开来），相应的，相关统计量就会增大。可以发现，Relief算法的时间复杂度是线性增长的，所以效率是比较高的。

包裹式（wrapper）

        包裹式的核心思路与过滤式不同，其特征选择直接把最终的学习器的性能作为评价标准。换句话说，包裹式选择的是让学习器性能最好的特征子集（而不一定是包含最重要特征的子集），从这个角度看，包裹式比过滤式要更合理。但是，包裹式显然需要多次重复运行学习器，所以成本会更加高。

        这里介绍经典的LVW（Las Vegas Wrapper）方法。其使用随机策略来进行子集搜索，使用最终误差作为评价标准，假设数据集D，特征集A，停止条件控制参数T，算法简要如下：

                

        其中CrossValidation为使用交叉验证法来计算学习器的误差，如果误差下降，那么就更新特征子集，反之保留原子集 。其实这里有一点隐患，就是学习器的反复运行可能带来高昂的时间成本，甚至可能得不出解。

嵌入式（embeding)

        嵌入式的思想是将前文两种结合，将特征选择过程和学习器训练过程融合在一起，同时进行，形成一个整体的优化过程。即训练的同时进行特征选择，训练完成就是特征选择完成。   

         比如，给定训练集,我们不妨考虑简单的线性模型，优化目标为平方损失函数，再在后面加入一个正则化项，来综合衡量模型的复杂程度，也就是我们说的岭回归，即：

               

          那么，如果我们把范数换成范数,可不可以呢？答案是任意p-范数同样可以降低过拟合风险。其中，特殊的，范数会更容易带来“稀疏解”，即求解得到的w会有更少的非零分量，这是我们希望看到的，因为这样直接抹去了一些特征（即在特征前面乘了0），这难道不是一种特征选择吗？所以，以上的特征嵌入式选择方法成为基于正则化的学习方法。其实这一点引入了另一种学习思想——稀疏学习，但是这里就不展开了。       

总结

        总之呢，特征选择就像前期的数据清洗工作，虽然往往不被人所重视，但是却是机器学习及其重要的部分（因为涉及到成本问题），所以在这方面的学习还是很有必要的。

        希望你今天开心~