特征选择的子集产生过程
(4) 增L去R选择算法 ( LRS , Plus-L Minus-R Selection )
该算法有两种形式:
<1> 算法从空集开始，每轮先加入L个特征，然后从中去除R 个特征，使得评价函数值最优。( L > R )
<2> 算法从全集开始，每轮先去除R个特征，然后加入L个特 征，使得评价函数值最优。( L < R ) 算法评价：增L去R选择算法结合了序列前向选择与序列后向 选择思想， L与R的选择是算法的关键。
算法评价：缺点是只能加入特征而不能去除特征。例如：特 征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A 就是多余的。假设序列前向选择算法首先将A加入特征集， 然后又将B与C加入，那么特征子集中就包含了多余的特征A。
特征选择的子集产生过程
(2)序列后向选择( SBS , Sequential Backward Selection )
(3) 遗传算法( GA, Genetic Algorithms )
算法描述：首先随机产生一批特征子集，并用评价 函数给这些特征子集评分，然后通过交叉、突变等 操作繁殖出下一代的特征子集，并且评分越高的特 征子集被选中参加繁殖的概率越高。这样经过N代 的繁殖和优胜劣汰后，种群中就可能产生了评价函 数值最高的特征子集。 随机算法的共同缺点：依赖于随机因素，有实验结 果难以重现。
算法描述：使用序列前向选择(SFS)从空集开始，同时使用序 列后向选择(SBS)从全集开始搜索，当两者搜索到一个相同的 特征子集C时停止搜索。
双向搜索的出发点是2������������/2 < ������ ������ 。如下图所示，O点代表搜 索起点，A点代表搜索目标。灰色的圆代表单向搜索可能的 搜索范围，绿色的2个圆表示某次双向搜索的搜索范围，容 易证明绿色的面积必定要比灰色的要小。
算法评价：枚举了所有的特征组合，属于穷举搜索，时间复 杂度是O(2n)，实用性不高。
(2)分支限界搜索( Branch and Bound )
算法描述：在穷举搜索的基础上加入分支限界。例如：若断 定某些分支不可能搜索出比当前找到的最优解更优的解，则 可以剪掉这些分支。
特征选择的子集产生过程
(3) 定向搜索 (Beam Search )
特征选择的子集产生过程
2FS , Sequential Forward Selection )
算法描述：特征子集X从空集开始，每次选择一个特征x加入 特征子集X，使得特征函数J( X)最优。简单说就是，每次都选 择一个使得评价函数的取值达到最优的特征加入，其实就是 一种简单的贪心算法。
������ ������=1
������������ − ������ ������ ������������
2
(1)
当样本特征很多，而样本数相对较少时，式(1)很容 易陷入过拟合，为了缓解过拟合问题，可对式(1)引 入正则化项，若使用L1范数正则化，则有 ������������������������ = ������������������
为什么L1易获得稀疏解？ （解释一） L1 正则化时，X=0点为不可导点，导函数不存在， 此时只要正则化项的系数λ大于原先费用函数在 0 点 处的导数的绝对值，左右导函数异号，x = 0 就会变 成一个极小值点。
嵌入式选择与L1正则化
为什么L1易获得稀疏解？ （解释二）
嵌入式选择与L1正则化
注意到������取得稀疏解意味着初试的d个特征中仅有对 应着������的非零向量的特征才会出现在最终模型中， 于是，求解L1范数正则化的结果是得到了仅才用一 部分初始特征值的模型，换言之，基于L1正则化的 学习方法就是一种嵌入式特征选择方法，其特征选 择过程与学习器训练过程融为一体，同时完成。 L1正则化问题求解可使用近端梯度下降（Proximal Gradient Descent,简称PGD）
算法描述：从特征全集O开始，每次从特征集O中剔除一个特 征x，使得剔除特征x后评价函数值达到最优。 算法评价：序列后向选择与序列前向选择正好相反，它的缺 点是特征只能去除不能加入。
另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。
特征选择的子集产生过程
(3) 双向搜索( BDS , Bidirectional Search )
嵌入式选择与L1正则化
在过滤式和包裹式特征选择方法中，特征选择过程 与学习器训练过程有明显的分别；于此不同，嵌入 式特征选择是将特征选择过程与学习器训练过程融 为一体，两者在同一个优化过程中完成，即在学习 器训练过程中自动地进行了特征选择。最典型的例 子就是带剪枝的决策树。
嵌入式选择与L1正则化
������ ������=1
������������ − ������ ������ ������������
2
+ λ||������||1
(2)
式(2)称为LASSO（Least Absolute Shrinkage and Selection Operator 最小绝对收缩算子）
嵌入式选择与L1正则化
特征选择的子集评价
( 2) 距离 (Distance Metrics )
运用距离度量进行特征选择是基于这样的假设：好的特征子 集应该使得属于同一类的样本距离尽可能小，属于不同类的 样本之间的距离尽可能远。
常用的距离度量（相似性度量）包括欧氏距离、标准化欧氏 距离、马氏距离等。 (3) 信息增益( Information Gain ) 假设存在特征子集A和特征子集B，分类变量为C，若IG( C|A ) > IG( C|B ) ，则认为选用特征子集A的分类结果比B好，因此 倾向于选用特征子集A。
算法评价：可作为SFS与SBS的补充，用于跳出局部最优值。
(2) 模拟退火算法( SA, Simulated Annealing )
算法评价：模拟退火一定程度克服了序列搜索算法容易陷入 局部最优值的缺点，但是若最优解的区域太小（如所谓的 “高尔夫球洞”地形），则模拟退火难以求解。
特征选择的子集产生过程
特征选择的子集评价
通过子集搜索产生的特征子集需要用评价尺度来进行评价， 常见的评价方法如下： (1) 相关性( Correlation)
运用相关性来度量特征子集的好坏是基于这样一个假设：好 的特征子集所包含的特征应该是与分类的相关度较高（相关 度高），而特征之间相关度较低的（亢余度低）。 可以使用线性相关系数(correlation coefficient) 来衡量向量之 间线性相关度。
特征选择
Feature Selection
重庆大学 余俊良
特征选择
• 什么是特征选择
– 特征选择 ( Feature Selection )也称特征子集选择 ( Feature Subset Selection , FSS ) ，或属性选择( Attribute Selection ) ，是指从全部特征中选取一个特征子集，使 构造出来的模型更好。
产生过程是搜索特征子空间的过程。搜索的算法分为完全搜 索(Complete)，启发式搜索(Heuristic)，随机搜索(Random) 3 大类
特征选择的子集产生过程
1.完全搜索
完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(NonExhaustive)两类。 (1) 广度优先搜索( Breadth First Search ) 算法描述：广度优先遍历特征子空间。
特征选择的常用方法
将特征子集搜索与子集评价相结合，即可得到特征 选择方法，例如将前向搜索与信息熵相结合，这显 然与决策树算法非常相似。事实上，决策树可用于 特征选择，树结点的划分属性所组成的集合就是选 择出的特征子集。 常见的特征选择方法大致可分为三类：过滤式(filter)、 包裹式(wrapper)和嵌入式(embedding)。
������ ������=1
������������ − ������ ������ ������������
2
+ λ||������||1
(2)
嵌入式选择与L1正则化
L1范数和L2范数正则化都有助于降低过拟合风险，但 前者还会带来一个额外的好处：它比后者更易于获 得“稀疏”解，即它求得的������会有更少的非零分量. ������������������������ = ������������������
给定数据集D={(������1,������1), (������2, ������2),…(������������,������������)}，其中 ������ ∈ ������������ , ������ ∈ ������ ，考虑最简单的线性回国模型，以平 方误差为损失函数，则优化目标为 ������������������������ = ������������������
特征选择的子集评价
(4)一致性( Consistency )
若样本1与样本2属于不同的分类，但在特征A、 B上的取值完 全一样，那么特征子集{A，B}不应该选作最终的特征集。 (5)分类器错误率 (Classifier error rate )
使用特定的分类器，用给定的特征子集对样本集进行分类， 用分类的精度来衡量特征子集的好坏。
包裹式选择
一般而言，由于包裹式特征选择方法直接针对给定 学习器进行优化，因此从最终学习器性能来看，包 裹式特征选择比过滤式特征选择更好，但另一方面， 由于在特征选择过程中需多次训练学习器，因此包 裹式特征选择的计算开销通常比过滤式特征选择大 得多。
前面介绍的评价尺度中，相关性、距离、信息增益、 一致性属于过滤式，而分类器错误率属于包裹式。
算法描述：首先选择N个得分最高的特征作为特征子集，将 其加入一个限制最大长度的优先队列，每次从队列中取出得 分最高的子集，然后穷举向该子集加入1个特征后产生的所 有特征集，将这些特征集加入队列。 (4) 最优优先搜索 ( Best First Search ) 算法描述：与定向搜索类似，唯一的不同点是不限制优先队 列的长度。