机器学习中的特征选择.ppt

FeatureSelectionforClassification 李军政2017 5 10 2020 3 30 2 2020 3 30 3 综述 What从全部特征中选取一个特征子集 使构造出来的模型更好 Why在机器学习的实际应用中 特征数量往往较多 其中可能存在不相关的特征 特征之间也可能存在相互依赖 容易导致如下的后果 分析特征 训练模型耗时长模型复杂 推广能力差引起维度灾难 2020 3 30 4 维度灾难 随着维数的增加 特征空间的体积指数增加 从而导致各方面的成本指数增加样本数量存储空间计算量 如何从中选出有用的特征 2020 3 30 5 2020 3 30 6 特征选择流程 Generator Evaluation StopRule Validation Subset Yes No OriginalFeatureSet 2020 3 30 7 两个主要步骤 产生过程特征子集的产生可以看作是一个搜索过程 搜索空间中的每一个状态都是一个可能特征子集 搜索的算法分为完全搜索 Complete 启发式搜索 Heuristic 随机搜索 Random 3大类 评价函数评价函数是评价一个特征子集好坏的准则特征的评估函数分为五类 相关性 距离 信息增益 一致性和分类错误率 2020 3 30 8 搜索算法之完全搜索 完全搜索分为穷举搜索与非穷举搜索两类广度优先搜索 BFS 分支限界搜索 BAB 定向搜索 BS 最优优先搜索 BestFirstSearch BS 首先选择N个得分最高的特征作为特征子集 将其加入一个限制最大长度的优先队列 每次从队列中取出得分最高的子集 然后穷举向该子集加入1个特征后产生的所有特征集 将这些特征集加入队列 2020 3 30 9 搜索算法之启发式搜索 启发式搜索序列前向选择 SFS 序列后向选择 SBS 双向搜索 BDS 增L去R选择算法 LRS L和R的选择是关键序列浮动选择 SequentialFloatingSelection 决策树 DTM LRS两种形式 算法从空集开始 每轮先加入L个特征 然后从中去除R个特征 使得评价函数值最优 L R 在训练样本集上运行C4 5或其他决策树生成算法 待决策树充分生长后 再在树上运行剪枝算法 则最终决策树各分支处的特征就是选出来的特征子集 一般使用信息增益作为评价函数 L和R怎么确定 2020 3 30 10 搜索算法之随机算法 随机算法随机产生序列选择算法 RGSS 随机产生一个特征子集 然后在该子集上执行SFS与SBS算法模拟退火算法 SA 以一定的概率来接受一个比当前解要差的解 因此有可能会跳出这个局部的最优解 达到一个全局次最优解遗传算法 GA 共同缺点 依赖于随机因素 有实验结果难以重现 2020 3 30 11 评价函数 作用是评价产生过程所提供的特征子集的好坏按照其工作原理 评价函数可以分为三种模型 过滤模型 FilterModel 封装模型 WrapperModel 混合模型 EmbeddedModel 被称为特征选择的经典三刀 飞刀 Filter 弯刀 Wrapper 电刀 Embedded 2020 3 30 12 评价函数 过滤模型 根据特征子集内部的特点来衡量其好坏 如欧氏距离 相关性 信息熵等特征子集在学习算法运行之前就被选定学习算法用于测试最终特征子集的性能特点 简单 效率高 但精度差 2020 3 30 13 评价函数 封装模型 学习算法封装在特征选择的过程中 用特征子集在学习算法上得到的挖掘性能作为特征子集优劣的评估准则 与过滤模型相比 精度高 但效率低 根本区别在于对学习算法的使用方式 2020 3 30 14 评价函数 混合模型 混合模型把这两种模型进行组合 先用过滤模式进行初选 再用封装模型来获得最佳的特征子集 2020 3 30 15 常用评价函数 特征的评价函数分为五类 相关性 距离 信息增益 一致性 分类错误率前四种属于过滤模型 分类错误率属于封装模型从概率论的角度相关系数 值域范围 1 1 绝对值越大 相关性越大 2020 3 30 16 常用评价函数 从数理统计的角度 假设检验 T检验检验与相关系数在理论上非常接近 但更偏重于有限样本下的估计T检验统计量 其中 n为样本容量 为样本均值和方差 为总体方差 2020 3 30 17 常用评价函数 从信息论角度条件熵与 相关性 负相关信息增益相对信息增益互信息量 MutualInformation 2020 3 30 18 常用评价函数 IR领域的度量 逆 文档词频 inversedocumentfrequency 词强度 termstrength 已知一个词 特征 在某文档 实例 中出现 该词在同类 目标函数值相同 文档中出现的概率为词强度 包含词 特征 t的文档数 2020 3 30 19 常用评价函数 学习相关的度量分类准确率准确率 召回率 F值 AUC等用单一维特征进行分类训练 某种分类准确率指标作为特征的有效性度量复杂度较大不一定有合适的准确率指标 2020 3 30 20 2020 3 30 21 过滤模型 FishScore FisherScore 计算两个分布的距离第i个特征的权重公式为 其中uij和pij分别是第i个特征在第j类中的均值和方差 nj为第j类中实例的个数 ui为第i个特征的均值 K为总类别数 缺点 容易产生冗余特征 f1 f2忽略组合特征 f1 f2 2020 3 30 22 过滤模型 Chi Squaredtest 卡方检验利用统计学中的假设检验思想 利用卡方统计量来衡量特征和类别之间的相关程度 卡方值公式 其中 N是文档总数 A是包含词t且属于c类的文档数目B是包含词t且不属于c类的文档数目C是不包含词t且属于c类的文档数目D是不包含词t且不属于c类的文档数目sklearn feature selection chi2 X y 2020 3 30 23 过滤模型 Relief Relief 根据各个特征和类别的关系赋予特征不同的权重 权重小于某阈值的将被移除 2020 3 30 24 Relief算法的缺点 Relief算法属于特征权重算法 该算法缺点在于 他们可以捕获特征与目标概念间的相关性 却不能发现特征间的冗余性 Relief F是Relief的升级版 可用于多分类经验证明除了无关特征对学习任务的影响 冗余特征同样影响学习算法的速度和准确性 也应尽可能消除冗余特征 2020 3 30 25 封装模型 增量法 封装模型首先需要选用较好学习算法 如RF SVM LR KNN等可以使用前面提到的各种缩小搜索空间的尝试 其中最经典的是启发式搜索 概括来说主要分为两大类 增量法 SFS sequentialforwardselection 减量法 SBS 2020 3 30 26 增量法试验结果 2020 3 30 27 增 减量法优缺点复杂度关于维数为或选单个特征采用评价准则排序的方式为一次选单个特征采用测试全部特征的方式为二次本质上是贪心算法某些组合无法遍历可能陷入局部极值 2020 3 30 28 2020 3 30 数据挖掘中的特征选择 29 总结 1 2 3 特征选择是机器学习领域中重要的步骤 具有重要的学术意义和研究价值 根据不同的搜索策略和评价函数 可以组合出多种特征选择方法 主要分三