1、Feature Selection for Classification李军政2017.5.101PPT课件单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结12342PPT课件综述nWhat 从全部特征中选取一个特征子集，使构造出来的模型更好。nWhy 在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：l分析特征、训练模型耗时长l模型复杂、推广能力差l引起维度灾难3PPT课件维度灾难n随着维数的增加，特征空间的体积指数增加，从而导致各方面的成本指数增加n样
2、本数量n存储空间n计算量n如何从中选出有用的特征？如何从中选出有用的特征？4PPT课件单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结12345PPT课件特征选择流程GeneratorEvaluationStop RuleValidationSubsetYesNoOriginal Feature Set6PPT课件两个主要步骤n产生过程产生过程q特征子集的产生可以看作是一个搜索过程，搜索空间中的每一个状态都是一个可能特征子集。q搜索的算法分为完全搜索(Complete)，启发式搜索(Heuristic)，随机搜索(Ran
3、dom) 3大类。n评价函数评价函数q评价函数是评价一个特征子集好坏的准则q特征的评估函数分为五类：相关性，距离，信息增益，一致性和分类错误率。 7PPT课件搜索算法之完全搜索n完全搜索分为穷举搜索与非穷举搜索两类完全搜索分为穷举搜索与非穷举搜索两类q广度优先搜索(BFS )q分支限界搜索(BAB) q定向搜索 (BS)q最优优先搜索(Best First Search)BS: 首先选择N个得分最高的特征作为特征子集，将其加入一个限制最大长度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入1个特征后产生的所有特征集，将这些特征集加入队列。8PPT课件搜索算法之启发式搜索n启发式
4、搜索启发式搜索q序列前向选择(SFS)q序列后向选择(SBS)q双向搜索(BDS)q增L去R选择算法 (LRS)nL和R的选择是关键q序列浮动选择(Sequential Floating Selection)q决策树(DTM)LRS两种形式: 算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。( L R )在训练样本集上运行C4.5或其他决策树生成算法，待决策树充分生长后，再在树上运行剪枝算法。则最终决策树各分支处的特征就是选出来的特征子集。一般使用信息增益作为评价函数。L和R怎么确定？9PPT课件搜索算法之随机算法n随机算法随机算法q随机产生序列选择算法(RGSS
5、)n随机产生一个特征子集，然后在该子集上执行SFS与SBS算法q模拟退火算法(SA)n以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到一个全局次最优解q遗传算法(GA)共同缺点：依赖共同缺点：依赖于随机因素，有实验结果难以重现于随机因素，有实验结果难以重现10PPT课件评价函数u作用是评价产生过程所提供的特征子集的好坏作用是评价产生过程所提供的特征子集的好坏u按照其工作原理，评价函数可以分为三种模型：按照其工作原理，评价函数可以分为三种模型：n过滤模型（Filter Model）n封装模型（Wrapper Model ）n混合模型（Embedded Model ）
6、u被称为特征选择的经典三刀：被称为特征选择的经典三刀：n飞刀（Filter）n弯刀（Wrapper）n电刀（Embedded ）11PPT课件评价函数过滤模型u根据特征子集内部的特点来衡量其好坏，如欧氏距离、相关性、信息熵等特征子集在学习算法运行之前就被选定学习算法用于测试最终特征子集的性能u特点：简单、效率高，但精度差12PPT课件评价函数封装模型u学习算法封装在特征选择的过程中，用特征子集在学习算法上得到的挖掘性能作为特征子集优劣的评估准则。u与过滤模型相比，精度高、但效率低。u根本区别在于对学习算法的使用方式13PPT课件评价函数混合模型u混合模型把这两种模型进行组合，先用过滤模式进行初
7、选，再用封装模型来获得最佳的特征子集。14PPT课件常用评价函数n特征的评价函数分为五类：相关性；距离；信息增益；一致性；分类错误率相关性；距离；信息增益；一致性；分类错误率前四种属于过滤模型，分类错误率属于封装模型前四种属于过滤模型，分类错误率属于封装模型u从概率论的角度从概率论的角度 相关系数：相关系数：q值域范围：-1, +1q绝对值越大，相关性越大 YXYXiii,cov15PPT课件常用评价函数u从数理统计的角度从数理统计的角度(假设检验假设检验)nT检验n 检验n与相关系数在理论上非常接近，但更偏重于有限样本下的估计T检验统计量：其中，n为样本容量， 、 为样本均值和方差， 为总体
8、方差。2x16PPT课件常用评价函数u从信息论角度从信息论角度n条件熵q与“相关性”负相关n信息增益n相对信息增益n互信息量(Mutual Information) iiXYHYHXYIG| YHXYHYHXYRIGii/| dYdXYPXPYXPYXPiMIiiii,log,17PPT课件常用评价函数uIR领域的度量领域的度量n（逆）文档词频(inverse document frequency)n词强度(term strength)q已知一个词(特征)在某文档(实例)中出现，该词在同类(目标函数值相同)文档中出现的概率为词强度ttDDidflog总文档数总文档数包含词包含词(特征特征)t的
9、文档数的文档数 jyYiyYdtdtPts|18PPT课件常用评价函数u学习相关的度量学习相关的度量n分类准确率 准确率、召回率、F值、AUC等q用单一维特征进行分类训练，某种分类准确率指标作为特征的有效性度量q复杂度较大q不一定有合适的准确率指标19PPT课件单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结123420PPT课件过滤模型Fish ScorenFisher Score：计算两个分布的距离n第i个特征的权重公式为: 其中uij和pij分别是第i个特征在第j类中的均值和方差，nj为第j类中实例的个数，ui为第
10、i个特征的均值，K为总类别数。n缺点：容易产生冗余特征，f1,f2 忽略组合特征，f1 | f221PPT课件过滤模型Chi-Squared testn卡方检验利用统计学中的假设检验思想，利用卡方统计量来衡量特征和类别之间的相关程度。n卡方值公式：其中，N是文档总数，A是 包含词t且 属于c类的文档数目B是 包含词t且不属于c类的文档数目C是不包含词t且 属于c类的文档数目D是不包含词t且不属于c类的文档数目nsklearn.feature_selection.chi2(X, y)22PPT课件过滤模型ReliefnRelief： 根据各个特征和类别的关系赋予特征不同的权重，权重小于某阈值的将
11、被移除。23PPT课件nRelief算法属于特征权重算法，该算法缺点在于：他们可以捕获特征与目标概念间的相关性，却不能发现特征间的冗余性。nRelief-F是Relief的升级版，可用于多分类n经验证明除了无关特征对学习任务的影响，冗余特征同样影响学习算法的速度和准确性，也应尽可能消除冗余特征。24PPT课件封装模型增量法n封装模型首先需要选用较好学习算法，如RF、SVM、LR、KNN等n可以使用前面提到的各种缩小搜索空间的尝试，其中最经典的是启发式搜索，概括来说主要分为两大类：增量法(SFS: sequential forward selection)减量法(SBS)25PPT课件增量法试验
12、结果26PPT课件q增/减量法优缺点n复杂度关于维数为 或q选单个特征采用评价准则排序的方式为一次q选单个特征采用测试全部特征的方式为二次n本质上是贪心算法q某些组合无法遍历q可能陷入局部极值 NO2NO27PPT课件单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结123428PPT课件总结123特征选择是机器学习领域中重要的步骤，具有重要的学术意义和研究价值根据不同的搜索策略和评价函数，可以组合出多种特征选择方法。主要分三类：过滤、封装、混合模型，在实际应用中各有优缺，我们应从效率、精准度等角度综合考虑对比，选用最优的特征选择方法先利用过滤模型去除一部分无用或贡献度不大的特征，再利用封装模型进行特征选择，是一个不错的步骤29PPT课件谢谢！30PPT课件
