机器学习之特征选择.pdf

《机器学习之特征选择.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、特征选择FeatureSelection重庆大学余俊良特征选择•什么是特征选择–特征选择(FeatureSelection)也称特征子集选择(FeatureSubsetSelection,FSS)，或属性选择(AttributeSelection)，是指从全部特征中选取一个特征子集，使构造出来的模型更好。•为什么要做特征选择–在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：•特征个数越多，分析特征、训练模型所需的时间就越长。•特征个数越多，容易引起“维度灾难”，模型也会越复

2、杂，其推广能力会下降。特征选择特征选择能剔除不相关(irrelevant)或亢余(redundant)的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。特征选择的一般过程特征选择包含子集搜索与子集评价两个过程。首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准则好就停止，否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。特征选择的子集产生过程产生

3、过程是搜索特征子空间的过程。搜索的算法分为完全搜索(Complete)，启发式搜索(Heuristic)，随机搜索(Random)3大类特征选择的子集产生过程1.完全搜索完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(Non-Exhaustive)两类。(1)广度优先搜索(BreadthFirstSearch)算法描述：广度优先遍历特征子空间。算法评价：枚举了所有的特征组合，属于穷举搜索，时间复杂度是O(2n)，实用性不高。(2)分支限界搜索(BranchandBound)算法描述：在穷举搜索的基础上加入分支限界。例如：若断定某些

4、分支不可能搜索出比当前找到的最优解更优的解，则可以剪掉这些分支。特征选择的子集产生过程(3)定向搜索(BeamSearch)算法描述：首先选择N个得分最高的特征作为特征子集，将其加入一个限制最大长度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入1个特征后产生的所有特征集，将这些特征集加入队列。(4)最优优先搜索(BestFirstSearch)算法描述：与定向搜索类似，唯一的不同点是不限制优先队列的长度。特征选择的子集产生过程2.启发式搜索(1)序列前向选择(SFS,SequentialForwardSelection)算

5、法描述：特征子集X从空集开始，每次选择一个特征x加入特征子集X，使得特征函数J(X)最优。简单说就是，每次都选择一个使得评价函数的取值达到最优的特征加入，其实就是一种简单的贪心算法。算法评价：缺点是只能加入特征而不能去除特征。例如：特征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集，然后又将B与C加入，那么特征子集中就包含了多余的特征A。特征选择的子集产生过程(2)序列后向选择(SBS,SequentialBackwardSelection)算法描述：从特征全集O开始，每次从特征集

6、O中剔除一个特征x，使得剔除特征x后评价函数值达到最优。算法评价：序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能加入。另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。特征选择的子集产生过程(3)双向搜索(BDS,BidirectionalSearch)算法描述：使用序列前向选择(SFS)从空集开始，同时使用序列后向选择(SBS)从全集开始搜索，当两者搜索到一个相同的特征子集C时停止搜索。双向搜索的出发点是2𝑁𝑘/2<𝑁𝑘。如下图所示，O点代表搜索起点，A点代表搜索目标。灰色的圆代表单向搜索可能的搜索范围，绿色的2个圆

7、表示某次双向搜索的搜索范围，容易证明绿色的面积必定要比灰色的要小。特征选择的子集产生过程(4)增L去R选择算法(LRS,Plus-LMinus-RSelection)该算法有两种形式:<1>算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。(L>R)<2>算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得评价函数值最优。(L

8、列浮动选择由增L去R选择算法发展而来，该算法与增L去R选择算法的不同之处在于：序列浮动选择的L与R不是固定的，而是“浮动”的，也就是会变化的。特征选择的子集产生过程(6)