主要内容：
- 为什么要进行特征选择？
- 什么是特征选择？
- 怎么进行特征选择
特征选择：
在现实生活中，一个对象往往具有很多属性（以下称为特征），这些特征大致可以被分成三种主要的类型：
相关特征：对于学习任务（例如分类问题）有帮助，可以提升学习算法的效果；
无关特征：对于我们的算法没有任何帮助，不会给算法的效果带来任何提升；
冗余特征：不会对我们的算法带来新的信息，或者这种特征的信息可以由其他的特征推断出；
但是对于一个特定的学习算法来说，哪一个特征是有效的是未知的。因此，需要从所有特征中选择出对于学习算法有益的相关特征。而且在实际应用中，经常会出现维度灾难问题，尤其是在文本处理中。例如，可以把一篇文档表示成一个词向量，但是往往会使用所有的单词作为字典，因此对于一篇可能仅仅包含100或者200个单词的文档，可能需要上万的维度（也就是特征）。如果可以从中选择一部分相关特征构建模型，这个问题就可以得到一定程度的解决。所以，特征选择和降维有一定的相似之处。另外，从上面的例子中可以发现，如果只选择所有特征中的部分特征构建模型，那么可以大大减少学习算法的运行时间，也可以增加模型的可解释性。
因此，进行特征选择的主要目的：
- 降维
- 降低学习任务的难度
- 提升模型的效率
定义：
从N个特征中选择其中M（M 特征选择想要做的是：选择尽可能少的子特征，模型的效果不会显著下降，并且结果的类别分布尽可能的接近真实的类别分别。机器学习 特征选择的过程： 对于一个有N个特征的对象，可以产生2^N个特征子集，特征选择就是从这些子集中选出对于特定任务最好的子集。特征选择主要包括四个过程： 生成过程其实是一个搜索过程，这个过程可以从以下几种情况开始： 1.没有特征； 2.所有特征； 3.随机特征子集。 在前两种情况下，每次迭代可以增加、删除特征；但是在最后一种情况下，每次迭代随机增加或者删除特征。 评价函数用来评价生成过程中生成的特征子集，产生一个值用来比较当前特征子集和当前最优特征子集，如果这个特征子集更好，那么就取代当前最优子集。 停止条件用来决定迭代过程什么时候停止，生成过程和评价函数可能会对于怎么选择停止条件产生影响。停止条件有以下四种选择： 达到预定义的最大迭代次数； 达到预定义的最大特征数； 增加（删除）任何特征不会产生更好的特征子集； 根据评价函数，产生最优特征子集； 
验证过程并不是特征选择本身的一部分，但是选择出的特征必须是有效。因此，需要使用不同的测试集、学习方法验证选择出来的特征子集，然后比较这些验证结果。
生成过程：
生成过程是一个搜索过程，这个过程主要有以下三个策略：
- 完全搜索：根据评价函数做完全搜索。完全搜索主要有两种：穷举搜索和非穷举搜索;
- 启发式搜索：根据一些启发式规则在每次迭代时，决定剩下的特征是应该被选择还是被拒绝。这种方法很简单并且速度很快，因为它的搜索空间是O(n^2);
- 随机搜索：每次迭代时会设置一些参数，参数的选择会影响特征选择的效果。由于会设置一些参数（例如最大迭代次数），所以搜索空间也远远小于O(2^n);
评价函数：
评价函数主要用来评价选出的特征子集的好坏，一个特征子集是最优的往往指相对于特定的评价函数来说的。评价函数主要用来度量一个特征（或者特征子集）可以区分不同类别的能力。根据具体的评价方法主要有三类：
- 过滤式（filter): 先进行特征选择，然后去训练学习器，所以特征选择的过程与学习器无关。相当于先对于特征进行过滤操作，然后用特征子集来训练分类器。
- 包裹式（wrapper）：直接把最后要使用的分类器作为特征选择的评价函数，对于特定的分类器选择最优的特征子集。
- Filter和Wrapper组合式算法：先使用Filter进行特征选择，去掉不相关的特征，降低特征维度；然后利用Wrapper进行特征选择。
嵌入式（embedding）：把特征选择的过程与分类器学习的过程融合一起，在学习的过程中进行特征选择。最常见的使用L1正则化进行特征选择。
一般有5种比较常见的评价函数：
- 距离度量：如果 X 在不同类别中能产生比 Y 大的差异，那么就说明 X 要好于 Y;
- 信息度量：主要是计算一个特征的信息增益（度量先验不确定性和期望后验不确定性之间的差异）；
- 依赖度量：主要用来度量从一个变量的值预测另一个变量值的能力。最常见的是相关系数：用来发现一个特征和一个类别的相关性。如果 X 和类别的相关性高于 Y与类别的相关性，那么X优于Y。对相关系数做一点改变，用来计算两个特征之间的依赖性，值代表着两个特征之间的冗余度。
- 一致性度量：对于两个样本，如果它们的类别不同，但是特征值是相同的，那么它们是不一致的；否则是一致的。找到与全集具有同样区分能力的最小子集。严重依赖于特定的训练集和 最小特征偏见（Min-Feature bias）的用法；找到满足可接受的不一致率（用户指定的参数）的最小规模的特征子集。
- 误分类率度量：主要用于Wrapper式的评价方法中。使用特定的分类器，利用选择的特征子集来预测测试集的类别，用分类器的准确率来作为指标。这种方法准确率很高，但是计算开销较大。
特征选择算法：
根据上面的三种不同的搜索策略和五种不同的评价函数，会有很多具体的特征选择算法。以下是主要的分类：
照三种不同的搜索策略，简单介绍几种具体的算法：
完全搜索：
广度优先搜索（Breadth First Search）
主要采用完全搜索策略和距离度量评价函数。使用广度优先算法遍历所有可能的特征子集，选择出最优的特征子集。
分支界限搜索（Branch & Bound）
主要采用完全搜索和距离度量。B&B从所有的特征上开始搜索，每次迭代从中去掉一个特征，每次给评价函数的值一个限制条件。因为评价函数满足单调性原理（一个特征子集不会好于所有包含这个特征子集的更大的特征子集），所以如果一个特征使得评价函数的值小于这个限制，那么就删除这个特征。类似于在穷举搜索中进行剪枝。
定向搜索（Beam Search）
主要采用完全搜索策略和误分类率作为评价函数。选择得分最高的特征作为特征子集，把它加入到一个有长度限制的队列中，从头到尾依次是性能最优到最差的特征子集。每次从队列总取得分最高的子集，然后穷举向该子集中加入一个特征后所有的特征集，按照得分把这些子集加入到队列中。
最优优先搜索（Best First Search）
和定位搜索类似，不同点在于不限制队列的长度。
启发式搜索
序列前向选择（SFS , Sequential Forward Selection）
使用误分类率作为评价函数。从空集开始搜索，每次把一个特征加入到这个特征子集中，使得评价函数达到最优值。如果候选的特征子集不如上一轮的特征子集，那么停止迭代，并将上一轮的特征子集作为最优的特征选择结果。
广义序列前向选择（GSFS ，Generalized Sequential Forward Selection）
该方法是SFS算法的加速算法，它可以一次性向特征集合中加入r个特征。在候选特征中选择一个规模为r的特征子集，使得评价函数取得最优值。
序列后向选择（SBS , Sequential Backward Selection）
把误分类率作为评价函数。从特征的全集开始搜索，每次从特征子集中去掉一个特征，使得评价函数达到最优值。
SFS和SBS都属于贪心算法，它们仅考虑使本轮选定集最优，因此容易陷入局部最优。
广义序列后向选择（GSBS，Generalized Sequential Backward Selection）
该方法是SBS的加速，可以一次性的从特征子集中去除一定数量的特征。是实际应用中的快速特征选择算法，性能相对较好。但是有可能消除操作太快，去除掉重要的信息，导致很难找到最优特征子集。
双向搜索（BDS , Bi-directional Search）
分别使用SFS和SBS同时进行搜索，只有当两者达到一个相同的特征子集时才停止搜索。为了保证能够达到一个相同的特征子集，需要满足两个条件：
被SFS选中的特征不能被SBS去除；
被SBS去除的特征就不能SFS选择；
增L去R选择算法（LRS , Plus L Minus R Selection）
采用误分类率作为评价函数。允许特征选择的过程中进行回溯，这种算法主要有两种形式：
当L>R时，是一种自下而上的方法，从空集开始搜索，每次使用SFS增加L个特征，然后用SBS从中去掉R个特征；
当L 序列浮动选择（Sequential Floating Selection） 和增L去R算法类似，只不过序列浮动算法的L和R不是固定的，每次会产生变化，这种算法有两种形式： 序列浮动前向选择（SFFS , Sequential Floating Forward Selection）:从空集开始搜索，每次选择一个特征子集，使得评价函数可以达到最优，然后在选择一个特征子集的子集，把它去掉使得评价函数达到最优； 序列浮动后向选择（SFBS , Sequential Floating Backward Selection）:从特征全集开始搜索，每次先去除一个子集，然后在加入一个特征子集。 决策树算法（DTM , Decision Tree Method） 采用信息增益作为评价函数。在训练集中使用C4.5算法，等到决策树充分增长，利用评价函数对决策树进行剪枝。最后，出现在任意一个叶子节点的路径上的所有特征子集的并集就是特征选择的结果。
閱讀更多 邵寒峰 的文章
