机器学习之特征选择

特征选择重庆大学余俊良FeatureSelection特征选择•什么是特征选择–特征选择(FeatureSelection)也称特征子集选择(FeatureSubsetSelection,FSS)，或属性选择(AttributeSelection)，是指从全部特征中选取一个特征子集，使构造出来的模型更好。•为什么要做特征选择–在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：•特征个数越多，分析特征、训练模型所需的时间就越长。•特征个数越多，容易引起“维度灾难”，模型也会越复杂，其推广能力会下降。特征选择特征选择能剔除不相关(irrelevant)或亢余(redundant)的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。特征选择的一般过程特征选择包含子集搜索与子集评价两个过程。首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准则好就停止，否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。特征选择的子集产生过程产生过程是搜索特征子空间的过程。搜索的算法分为完全搜索(Complete)，启发式搜索(Heuristic)，随机搜索(Random)3大类特征选择的子集产生过程1.完全搜索完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(Non-Exhaustive)两类。(1)广度优先搜索(BreadthFirstSearch)算法描述：广度优先遍历特征子空间。算法评价：枚举了所有的特征组合，属于穷举搜索，时间复杂度是O(2n)，实用性不高。(2)分支限界搜索(BranchandBound)算法描述：在穷举搜索的基础上加入分支限界。例如：若断定某些分支不可能搜索出比当前找到的最优解更优的解，则可以剪掉这些分支。特征选择的子集产生过程(3)定向搜索(BeamSearch)算法描述：首先选择N个得分最高的特征作为特征子集，将其加入一个限制最大长度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入1个特征后产生的所有特征集，将这些特征集加入队列。(4)最优优先搜索(BestFirstSearch)算法描述：与定向搜索类似，唯一的不同点是不限制优先队列的长度。特征选择的子集产生过程2.启发式搜索(1)序列前向选择(SFS,SequentialForwardSelection)算法描述：特征子集X从空集开始，每次选择一个特征x加入特征子集X，使得特征函数J(X)最优。简单说就是，每次都选择一个使得评价函数的取值达到最优的特征加入，其实就是一种简单的贪心算法。算法评价：缺点是只能加入特征而不能去除特征。例如：特征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集，然后又将B与C加入，那么特征子集中就包含了多余的特征A。特征选择的子集产生过程(2)序列后向选择(SBS,SequentialBackwardSelection)算法描述：从特征全集O开始，每次从特征集O中剔除一个特征x，使得剔除特征x后评价函数值达到最优。算法评价：序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能加入。另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。特征选择的子集产生过程(3)双向搜索(BDS,BidirectionalSearch)算法描述：使用序列前向选择(SFS)从空集开始，同时使用序列后向选择(SBS)从全集开始搜索，当两者搜索到一个相同的特征子集C时停止搜索。双向搜索的出发点是2𝑁𝑘/2𝑁𝑘。如下图所示，O点代表搜索起点，A点代表搜索目标。灰色的圆代表单向搜索可能的搜索范围，绿色的2个圆表示某次双向搜索的搜索范围，容易证明绿色的面积必定要比灰色的要小。特征选择的子集产生过程(4)增L去R选择算法(LRS,Plus-LMinus-RSelection)该算法有两种形式:1算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。(LR)2算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得评价函数值最优。(LR)算法评价：增L去R选择算法结合了序列前向选择与序列后向选择思想，L与R的选择是算法的关键。(5)序列浮动选择(SequentialFloatingSelection)算法描述：序列浮动选择由增L去R选择算法发展而来，该算法与增L去R选择算法的不同之处在于：序列浮动选择的L与R不是固定的，而是“浮动”的，也就是会变化的。特征选择的子集产生过程(6)决策树(DecisionTreeMethod,DTM)算法描述：在训练样本集上运行C4.5或其他决策树生成算法，待决策树充分生长后，再在树上运行剪枝算法。则最终决策树各分支处的特征就是选出来的特征子集了。决策树方法一般使用信息增益作为评价函数。特征选择的子集产生过程3随机算法(1)随机产生序列选择算法(RGSS,RandomGenerationplusSequentialSelection)算法描述：随机产生一个特征子集，然后在该子集上执行SFS与SBS算法。算法评价：可作为SFS与SBS的补充，用于跳出局部最优值。(2)模拟退火算法(SA,SimulatedAnnealing)算法评价：模拟退火一定程度克服了序列搜索算法容易陷入局部最优值的缺点，但是若最优解的区域太小（如所谓的“高尔夫球洞”地形），则模拟退火难以求解。特征选择的子集产生过程(3)遗传算法(GA,GeneticAlgorithms)算法描述：首先随机产生一批特征子集，并用评价函数给这些特征子集评分，然后通过交叉、突变等操作繁殖出下一代的特征子集，并且评分越高的特征子集被选中参加繁殖的概率越高。这样经过N代的繁殖和优胜劣汰后，种群中就可能产生了评价函数值最高的特征子集。随机算法的共同缺点：依赖于随机因素，有实验结果难以重现。特征选择的子集评价通过子集搜索产生的特征子集需要用评价尺度来进行评价，常见的评价方法如下：(1)相关性(Correlation)运用相关性来度量特征子集的好坏是基于这样一个假设：好的特征子集所包含的特征应该是与分类的相关度较高（相关度高），而特征之间相关度较低的（亢余度低）。可以使用线性相关系数(correlationcoefficient)来衡量向量之间线性相关度。特征选择的子集评价(2)距离(DistanceMetrics)运用距离度量进行特征选择是基于这样的假设：好的特征子集应该使得属于同一类的样本距离尽可能小，属于不同类的样本之间的距离尽可能远。常用的距离度量（相似性度量）包括欧氏距离、标准化欧氏距离、马氏距离等。(3)信息增益(InformationGain)假设存在特征子集A和特征子集B，分类变量为C，若IG(C|A)IG(C|B)，则认为选用特征子集A的分类结果比B好，因此倾向于选用特征子集A。特征选择的子集评价(4)一致性(Consistency)若样本1与样本2属于不同的分类，但在特征A、B上的取值完全一样，那么特征子集{A，B}不应该选作最终的特征集。(5)分类器错误率(Classifiererrorrate)使用特定的分类器，用给定的特征子集对样本集进行分类，用分类的精度来衡量特征子集的好坏。特征选择的常用方法将特征子集搜索与子集评价相结合，即可得到特征选择方法，例如将前向搜索与信息熵相结合，这显然与决策树算法非常相似。事实上，决策树可用于特征选择，树结点的划分属性所组成的集合就是选择出的特征子集。常见的特征选择方法大致可分为三类：过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)。过滤式选择过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程和后续学习方法无关。这相当于先用特征选择过程对初试特征进行“过滤”，再用过滤后的特征来训练模型。包裹式选择与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能，“量身订做”的特征子集。包裹式选择一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。前面介绍的评价尺度中，相关性、距离、信息增益、一致性属于过滤式，而分类器错误率属于包裹式。嵌入式选择与L1正则化在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别；于此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。最典型的例子就是带剪枝的决策树。嵌入式选择与L1正则化给定数据集D={(𝑥1,𝑦1),(𝑥2,𝑦2),…(𝑥𝑛,𝑦𝑛)}，其中𝑥∈𝑅𝑛,𝑦∈𝑅，考虑最简单的线性回国模型，以平方误差为损失函数，则优化目标为𝐿𝑜𝑠𝑠=𝑚𝑖𝑛𝑦𝑖−𝑤𝑇𝑥𝑖2𝑚𝑖=1(1)当样本特征很多，而样本数相对较少时，式(1)很容易陷入过拟合，为了缓解过拟合问题，可对式(1)引入正则化项，若使用L1范数正则化，则有𝐿𝑜𝑠𝑠=𝑚𝑖𝑛𝑦𝑖−𝑤𝑇𝑥𝑖2𝑚𝑖=1+λ||𝑤||1(2)嵌入式选择与L1正则化L1范数和L2范数正则化都有助于降低过拟合风险，但前者还会带来一个额外的好处：它比后者更易于获得“稀疏”解，即它求得的𝑤会有更少的非零分量.𝐿𝑜𝑠𝑠=𝑚𝑖𝑛𝑦𝑖−𝑤𝑇𝑥𝑖2𝑚𝑖=1+λ||𝑤||1(2)式(2)称为LASSO（LeastAbsoluteShrinkageandSelectionOperator最小绝对收缩算子）嵌入式选择与L1正则化为什么L1易获得稀疏解？（解释一）L1正则化时，X=0点为不可导点，导函数不存在，此时只要正则化项的系数λ大于原先费用函数在0点处的导数的绝对值，左右导函数异号，x=0就会变成一个极小值点。嵌入式选择与L1正则化为什么L1易获得稀疏解？（解释二）嵌入式选择与L1正则化注意到𝑤取得稀疏解意味着初试的d个特征中仅有对应着𝑤的非零向量的特征才会出现在最终模型中，于是，求解L1范数正则化的结果是得到了仅才用一部分初始特征值的模型，换言之，基于L1正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，同时完成。L1正则化问题求解可使用近端梯度下降（ProximalGradientDescent,简称PGD）小结特征选择是一个重要的数据预处理过程，通过特征选择降低原始数据的维度并降低学习任务的难度，将纷繁复杂的因素抽丝剥茧，只留下关键因素。特征选择一般包含特征子集搜索和子集评价两个过程。常见的特征选择方法由过滤式、包裹式、嵌入式。过滤式方法与学习器无关，包裹式方法为学习器量身选择最适合特征，嵌入式方法将特征选择与学习器训练合为一个过程。参考资料周志华《机器学习》://