机器学习中的特征选择

FeatureSelectionforClassification李军政2017.5.102019/11/132单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结1234综述What从全部特征中选取一个特征子集，使构造出来的模型更好。Why在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：分析特征、训练模型耗时长模型复杂、推广能力差引起维度灾难2019/11/133维度灾难随着维数的增加，特征空间的体积指数增加，从而导致各方面的成本指数增加样本数量存储空间计算量……2019/11/134如何从中选出有用的特征？？2019/11/135单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结1234特征选择流程2019/11/136GeneratorEvaluationStopRuleValidationSubsetYesNoOriginalFeatureSet两个主要步骤产生过程特征子集的产生可以看作是一个搜索过程，搜索空间中的每一个状态都是一个可能特征子集。搜索的算法分为完全搜索(Complete)，启发式搜索(Heuristic)，随机搜索(Random)3大类。评价函数评价函数是评价一个特征子集好坏的准则特征的评估函数分为五类：相关性，距离，信息增益，一致性和分类错误率。2019/11/137搜索算法之完全搜索完全搜索分为穷举搜索与非穷举搜索两类广度优先搜索(BFS)分支限界搜索(BAB)定向搜索(BS)最优优先搜索(BestFirstSearch)2019/11/138BS:首先选择N个得分最高的特征作为特征子集，将其加入一个限制最大长度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入1个特征后产生的所有特征集，将这些特征集加入队列。搜索算法之启发式搜索启发式搜索序列前向选择(SFS)序列后向选择(SBS)双向搜索(BDS)增L去R选择算法(LRS)L和R的选择是关键序列浮动选择(SequentialFloatingSelection)决策树(DTM)2019/11/139LRS两种形式:1算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。(LR)在训练样本集上运行C4.5或其他决策树生成算法，待决策树充分生长后，再在树上运行剪枝算法。则最终决策树各分支处的特征就是选出来的特征子集。一般使用信息增益作为评价函数。L和R怎么确定？？搜索算法之随机算法随机算法随机产生序列选择算法(RGSS)随机产生一个特征子集，然后在该子集上执行SFS与SBS算法模拟退火算法(SA)以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到一个全局次最优解遗传算法(GA)共同缺点：依赖于随机因素，有实验结果难以重现2019/11/1310评价函数作用是评价产生过程所提供的特征子集的好坏按照其工作原理，评价函数可以分为三种模型：过滤模型（FilterModel）封装模型（WrapperModel）混合模型（EmbeddedModel）被称为特征选择的经典三刀：飞刀（Filter）弯刀（Wrapper）电刀（Embedded）2019/11/1311评价函数—过滤模型2019/11/1312根据特征子集内部的特点来衡量其好坏，如欧氏距离、相关性、信息熵等特征子集在学习算法运行之前就被选定学习算法用于测试最终特征子集的性能特点：简单、效率高，但精度差评价函数—封装模型学习算法封装在特征选择的过程中，用特征子集在学习算法上得到的挖掘性能作为特征子集优劣的评估准则。与过滤模型相比，精度高、但效率低。根本区别在于对学习算法的使用方式2019/11/1313评价函数—混合模型混合模型把这两种模型进行组合，先用过滤模式进行初选，再用封装模型来获得最佳的特征子集。2019/11/13142019/11/1315常用评价函数特征的评价函数分为五类：相关性；距离；信息增益；一致性；分类错误率前四种属于过滤模型，分类错误率属于封装模型从概率论的角度相关系数：值域范围：[-1,+1]绝对值越大，相关性越大YXYXiii,cov常用评价函数从数理统计的角度(假设检验)T检验检验与相关系数在理论上非常接近，但更偏重于有限样本下的估计T检验统计量：其中，n为样本容量，、为样本均值和方差，为总体方差。2019/11/13162x𝑡=𝑋−𝜇𝜎𝑥𝑛−1𝑋𝜎𝑥𝜇常用评价函数从信息论角度条件熵与“相关性”负相关信息增益相对信息增益互信息量(MutualInformation)2019/11/1317iiXYHYHXYIG||YHXYHYHXYRIGii/||dYdXYPXPYXPYXPiMIiiii,log,常用评价函数IR领域的度量（逆）文档词频(inversedocumentfrequency)词强度(termstrength)已知一个词(特征)在某文档(实例)中出现，该词在同类(目标函数值相同)文档中出现的概率为词强度2019/11/1318ttDDidflog总文档数包含词(特征)t的文档数jyYiyYdtdtPts|常用评价函数学习相关的度量分类准确率准确率、召回率、F值、AUC等用单一维特征进行分类训练，某种分类准确率指标作为特征的有效性度量复杂度较大不一定有合适的准确率指标2019/11/13192019/11/1320单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结1234过滤模型—FishScoreFisherScore：计算两个分布的距离第i个特征的权重公式为:其中uij和pij分别是第i个特征在第j类中的均值和方差，nj为第j类中实例的个数，ui为第i个特征的均值，K为总类别数。缺点：容易产生冗余特征，f1,f2忽略组合特征，f1|f22019/11/1321过滤模型—Chi-Squaredtest卡方检验利用统计学中的假设检验思想，利用卡方统计量来衡量特征和类别之间的相关程度。卡方值公式：其中，N是文档总数，A是包含词t且属于c类的文档数目B是包含词t且不属于c类的文档数目C是不包含词t且属于c类的文档数目D是不包含词t且不属于c类的文档数目sklearn.feature_selection.chi2(X,y)2019/11/1322过滤模型—ReliefRelief：根据各个特征和类别的关系赋予特征不同的权重，权重小于某阈值的将被移除。2019/11/1323Relief算法的缺点Relief算法属于特征权重算法，该算法缺点在于：他们可以捕获特征与目标概念间的相关性，却不能发现特征间的冗余性。Relief-F是Relief的升级版，可用于多分类经验证明除了无关特征对学习任务的影响，冗余特征同样影响学习算法的速度和准确性，也应尽可能消除冗余特征。2019/11/1324封装模型—增量法封装模型首先需要选用较好学习算法，如RF、SVM、LR、KNN等可以使用前面提到的各种缩小搜索空间的尝试，其中最经典的是启发式搜索，概括来说主要分为两大类：增量法(SFS:sequentialforwardselection)减量法(SBS)2019/11/1325增量法试验结果2019/11/1326增/减量法优缺点复杂度关于维数为或选单个特征采用评价准则排序的方式为一次选单个特征采用测试全部特征的方式为二次本质上是贪心算法某些组合无法遍历可能陷入局部极值2019/11/1327NO2NO2019/11/1328单击此处添加文字内容综述单击此处添加文字内容特征选择流程单击此处添加文字内容几种常用的特征选择算法单击此处添加文字内容总结1234总结2019/11/13数据挖掘中的特征选择29123特征选择是机器学习领域中重要的步骤，具有重要的学术意义和研究价值根据不同的搜索策略和评价函数，可以组合出多种特征选择方法。主要分三类：过滤、封装、混合模型，在实际应用中各有优缺，我们应从效率、精准度等角度综合考虑对比，选用最优的特征选择方法先利用过滤模型去除一部分无用或贡献度不大的特征，再利用封装模型进行特征选择，是一个不错的步骤2019/11/1330谢谢！