logo资料库

模式识别之特征选择综述.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.20M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    1 综述
     2 特征选择过程
    参考资料
    特征选择常用算法综述 Posted on 2011-01-02 14:40 苍梧 阅读(8948) 评论(10) 编辑 收藏 1 综述 (1) 什么是特征选择 特征选择 ( Feature Selection )也称特征子集选择( Feature Subset Selection , FSS ) ，或属 性选择( Attribute Selection ) ，是指从全部特征中选取一个特征子集，使构造出来的模型更好。 (2) 为什么要做特征选择 在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间 也可能存在相互依赖，容易导致如下的后果：  特征个数越多，分析特征、训练模型所需的时间就越长。  特征个数越多，容易引起“维度灾难”，模型也会越复杂，其推广能力会 下降。 特征选择能剔除不相关(irrelevant)或亢余(redundant )的特征，从而达到减少特征个数， 提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使 研究人员易于理解数据产生的过程。 2 特征选择过程 2.1 特征选择的一般过程 特征选择的一般过程可用图 1 表示。首先从特征全集中产生出一个特征子集，然后用评 价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准则好 就停止，否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要 验证其有效性。 综上所述，特征选择过程一般包括产生过程，评价函数，停止准则，验证过程，这 4 个 部分。 (1) 产生过程( Generation Procedure ) 产生过程是搜索特征子集的过程，负责为评价函数提供特征子集。搜索特征子集的
    过程有多种，将在 2.2 小节展开介绍。 (2) 评价函数( Evaluation Function ) 评价函数是评价一个特征子集好坏程度的一个准则。评价函数将在 2.3 小节展开介 绍。 (3) 停止准则( Stopping Criterion ) 停止准则是与评价函数相关的，一般是一个阈值，当评价函数值达到这个阈值后就 可停止搜索。 (4) 验证过程( Validation Procedure ) 在验证数据集上验证选出来的特征子集的有效性。 图 1. 特征选择的过程 ( M. Dash and H. Liu 1997 ) 2.2 产生过程 产生过程是搜索特征子空间的过程。搜索的算法分为完全搜索(Complete)，启发式搜索 (Heuristic)，随机搜索(Random) 3 大类，如图 2 所示。
    图 2. 产生过程算法分类 ( M. Dash and H. Liu 1997 ) 下面对常见的搜索算法进行简单介绍。 2.2.1 完全搜索 完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(Non-Exhaustive)两类。 (1) 广度优先搜索( Breadth First Search ) 算法描述：广度优先遍历特征子空间。 算法评价：枚举了所有的特征组合，属于穷举搜索，时间复杂度是 O(2n)，实用性 不高。 (2)分支限界搜索( Branch and Bound ) 算法描述：在穷举搜索的基础上加入分支限界。例如：若断定某些分支不可能搜索 出比当前找到的最优解更优的解，则可以剪掉这些分支。 (3) 定向搜索 (Beam Search ) 算法描述：首先选择 N 个得分最高的特征作为特征子集，将其加入一个限制最大长 度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入 1 个特征后产生 的所有特征集，将这些特征集加入队列。
    (4) 最优优先搜索 ( Best First Search ) 算法描述：与定向搜索类似，唯一的不同点是不限制优先队列的长度。 2.2.2 启发式搜索 (1)序列前向选择( SFS , Sequential Forward Selection ) 算法描述：特征子集 X 从空集开始，每次选择一个特征 x 加入特征子集 X，使得 特征函数 J( X)最优。简单说就是，每次都选择一个使得评价函数的取值达到最优的特征加 入，其实就是一种简单的贪心算法。 算法评价：缺点是只能加入特征而不能去除特征。例如：特征 A 完全依赖于特征 B 与 C，可以认为如果加入了特征 B 与 C 则 A 就是多余的。假设序列前向选择算法首先将 A 加入特征集，然后又将 B 与 C 加入，那么特征子集中就包含了多余的特征 A。 (2)序列后向选择( SBS , Sequential Backward Selection ) 算法描述：从特征全集 O 开始，每次从特征集 O 中剔除一个特征 x，使得剔除特 征 x 后评价函数值达到最优。 算法评价：序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能 加入。 另外，SFS 与 SBS 都属于贪心算法，容易陷入局部最优值。 (3) 双向搜索( BDS , Bidirectional Search ) 算法描述：使用序列前向选择(SFS)从空集开始，同时使用序列后向选择(SBS)从全 集开始搜索，当两者搜索到一个相同的特征子集 C 时停止搜索。 双向搜索的出发点是 。如下图所示，O 点代表搜索起点，A 点代表 搜索目标。灰色的圆代表单向搜索可能的搜索范围，绿色的 2 个圆表示某次双向搜索的搜索 范围，容易证明绿色的面积必定要比灰色的要小。
    图 2. 双向搜索 (4) 增 L 去 R 选择算法 ( LRS , Plus-L Minus-R Selection ) 该算法有两种形式: <1> 算法从空集开始，每轮先加入 L 个特征，然后从中去除 R 个特征，使得 评价函数值最优。( L > R ) <2> 算法从全集开始，每轮先去除 R 个特征，然后加入 L 个特征，使得评价 函数值最优。( L < R ) 算法评价：增 L 去 R 选择算法结合了序列前向选择与序列后向选择思想， L 与 R 的选择是算法的关键。 (5) 序列浮动选择( Sequential Floating Selection ) 算法描述：序列浮动选择由增 L 去 R 选择算法发展而来，该算法与增 L 去 R 选择 算法的不同之处在于：序列浮动选择的 L 与 R 不是固定的，而是“浮动”的，也就是会变 化的。 序列浮动选择根据搜索方向的不同，有以下两种变种。 <1>序列浮动前向选择( SFFS , Sequential Floating Forward Selection ) 算法描述：从空集开始，每轮在未选择的特征中选择一个子集 x，使加入子集
    x 后评价函数达到最优，然后在已选择的特征中选择子集 z，使剔除子集 z 后评价函数达到 最优。 <2>序列浮动后向选择( SFBS , Sequential Floating Backward Selection ) 算法描述：与 SFFS 类似，不同之处在于 SFBS 是从全集开始，每轮先剔除特 征，然后加入特征。 算法评价：序列浮动选择结合了序列前向选择、序列后向选择、增 L 去 R 选择 的特点，并弥补了它们的缺点。 (6) 决策树( Decision Tree Method , DTM) 算法描述：在训练样本集上运行 C4.5 或其他决策树生成算法，待决策树充分生长后， 再在树上运行剪枝算法。则最终决策树各分支处的特征就是选出来的特征子集了。决策树方 法一般使用信息增益作为评价函数。 2.2.3 随机算法 (1) 随机产生序列选择算法(RGSS, Random Generation plus Sequential Selection) 算法描述：随机产生一个特征子集，然后在该子集上执行 SFS 与 SBS 算法。 算法评价：可作为 SFS 与 SBS 的补充，用于跳出局部最优值。 (2) 模拟退火算法( SA, Simulated Annealing ) 模拟退火算法可参考 大白话解析模拟退火算法 。 算法评价：模拟退火一定程度克服了序列搜索算法容易陷入局部最优值 的缺点，但是若最优解的区域太小（如所谓的“高尔夫球洞”地形），则模拟退火 难以求解。 (3) 遗传算法( GA, Genetic Algorithms ) 遗传算法可参考 遗传算法入门 。 算法描述：首先随机产生一批特征子集，并用评价函数给这些 特征子集评分，然后通过交叉、突变等操作繁殖出下一代的特征子集，
    并且评分越高的特征子集被选中参加繁殖的概率越高。这样经过 N 代的 繁殖和优胜劣汰后，种群中就可能产生了评价函数值最高的特征子集。 随机算法的共同缺点：依赖于随机因素，有实验结果难以重现。 2.3 评价函数 评价函数的作用是评价产生过程所提供的特征子集的好坏。 评价函数根据其工作原理，主要分为筛选器(Filter)、封装器( Wrapper )两大类。 筛选器通过分析特征子集内部的特点来衡量其好坏。筛选器一般用作预处理，与分类器 的选择无关。筛选器的原理如下图 3：
    图 3. Filter 原理(Ricardo Gutierrez-Osuna 2008 ) 封装器实质上是一个分类器，封装器用选取的特征子集对样本集进行分类，分类的精度 作为衡量特征子集好坏的标准。封装器的原理如图 4 所示。 图 4. Wrapper 原理 (Ricardo Gutierrez-Osuna 2008 ) 下面简单介绍常见的评价函数。 (1) 相关性( Correlation) 运用相关性来度量特征子集的好坏是基于这样一个假设：好的特征子集所包含的特 征应该是与分类的相关度较高（相关度高），而特征之间相关度较低的（亢余度低）。 可以使用线性相关系数(correlation coefficient) 来衡量向量之间线性相关度。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料