模式识别 课件 第8章 特征选择

第8章特征选择主要内容8.1概述8.2特征的评价准则8.3特征选择的优化算法8.4过滤式特征选择方法8.5包裹式特征选择方法8.6嵌入式特征选择方法8.1概述特征选择从已有特征中挑选出比较重要的、有代表性的、对分类有利的特征，以便降低样本的维数，降低分类器设计的难度。三个关键问题对特征的要求，即选择什么样的特征具有充分的识别信息量，即应具有充分的可分性。尽可能的独立性，重复的、相关性强的特征不能提供更多信息，只选一个。数量尽量少，同时损失的信息量小。8.1概述特征选择的标准：即评价准则，衡量特征的可分性、独立性、信息量等，简言之，选出的特征是否有利于分类三个关键问题特征选择的方法：即如何进行特征选择利用待识别对象的特点从特征和分类的角度出发8.2特征的评价准则希望选出的特征最有利于分类，因此利用分类器的性能度量作为特征的评价准则，例如，错误率等。做法：利用不同的特征组合设计分类器，计算分类器的性能度量值，并从中选出分类器性能最好的一组特征。优点：选出的特征对于分类器而言针对性较强，性能更好。存在的问题：错误率的计算复杂；计算量很大。定义便于计算的类别可分性准则，以衡量一组特征下类之间的可分程度，也称为可分性判据8.2特征的评价准则评价准则要求与误判概率有单调关系：J最大时，错误率最小当特征相互独立时，判据有可加性判据具有度量特性：具有距离的某些特性对特征数目是单调不减的：加入新的特征，不会使判据减小8.2特征的评价准则（1）基于类内类间距离的可分性判据若样本可分，必然位于特征空间的不同区域，这些不同的区域之间必定有一定的距离，距离越大，分得越开。所以，可以用距离作为模式分布状态的测度。距离有多种定义方式，均可以作为类别可分性判据，常采用欧氏距离。概述8.2特征的评价准则相关散布矩阵定义类内散布矩阵：类间散布矩阵：总体类内散布矩阵：

混合散布矩阵

8.2特征的评价准则可分性判据

8.2特征的评价准则例题

8.2特征的评价准则

8.2特征的评价准则判据优缺点计算方便直观概念清楚没有考虑各类的概率分布，不能确切表明各类重叠情况，与错误概率没有直接联系8.2特征的评价准则（2）基于概率分布的可分性判据

概述8.2特征的评价准则

散度8.2特征的评价准则常用的概率距离度量

散度

对数似然比

8.2特征的评价准则Chernoff界限s∈[0,1]Bhattacharyya距离

这些量表达了两类模式的差异性，并且具有距离函数的性质，称为概率距离度量。8.2特征的评价准则例题

8.2特征的评价准则

8.2特征的评价准则（3）基于熵函数的可分性判据概述

用具有最小不确定性的特征进行分类最为有利。8.2特征的评价准则熵在信息论中，熵表示不确定性，熵越大不确定性越大。Shannon熵：广义熵：基于熵的可分性判据

JE越小，可分性越好。8.2特征的评价准则相对熵：交叉熵：

8.2特征的评价准则（4）基于统计检验的可分性判据采用统计检验的方法可以检验某一变量在两类样本间是否存在显著差异，给出统计量反映这种差别，在两类间有显著差异的特征有利于分类。u-检验t-检验秩和检验8.2特征的评价准则（5）特征的相关性评价Pearson相关系数

Spearman秩相关系数

相关系数8.2特征的评价准则互信息

8.3特征选择的优化算法（1）概述穷举法（全局最优搜索）从n个特征中挑出m个，列举所有可能的组合，计算每个J，以选择最优特征组计算量太大采用某些搜索技术使计算量有所降低非穷举法不能保证结果最优8.3特征选择的优化算法（2）分支定界算法（BranchAndBound）一种自上而下方法，从包含所有候选特征开始，逐步去掉不被选中的特征，具有回溯功能通过合理地组织搜索过程，使得有可能避免计算某些特征组合而不影响结果为最优主要利用可分离性判据的单调性整个搜索过程可用树表示出来，称为搜索树或解树基本思想8.3特征选择的优化算法例题

8.3特征选择的优化算法

8.3特征选择的优化算法

0

确定后继节点要舍弃的特征8.3特征选择的优化算法

0

8.3特征选择的优化算法

0

8.3特征选择的优化算法

0

8.3特征选择的优化算法最终搜索树完整的搜索树8.3特征选择的优化算法避免了部分m个特征组合的判据计算，与穷举相比节约了时间由于搜索过程中要计算中间的判据，在m很小或很接近n时，不如使用穷举法必须采用具有单调性的判据理论上具有单调性的判据，在实际运用样本计算时，可能不再具备单调性算法分析对每一个特征单独计算类别可分性判据，根据单个特征的判据值排队，选择其中前m个特征前提假设是单独作用时性能最优的特征，组合起来也是性能最优的与很多实际情况不相符单独最优特征的组合（3）特征选择的次优算法8.3特征选择的优化算法顺序前进法Sequentialforwardselection，SFS从底向上的方法，第一个特征选择单独最优的特征，第二个特征从其余特征中选择与第一个特征组合在一起后准则最优的特征，后面每一个特征都选择与已经入选的特征组合起来最优的特征第一个特征仅靠单个特征的准则选择特征一旦入选无法剔除，即使它与后面选择的特征并不是最优的组合广义顺序前进法，每一次不是选择一个新特征，而是选择l个新特征8.3特征选择的优化算法顺序后退法Sequentialbackwardselection，SBS从顶向下的方法，从所有特征开始注意剔除不被选中的特征，每次剔除的特征都是使得剩余的特征的准则函数值最优的特征因为从顶向下，很多计算在高维空间进行，计算量比顺序前进法大特征一旦剔除无法再选入广义顺序后退法，每一次不是剔除一个特征，而是剔除r个新特征8.3特征选择的优化算法结合SFS和SBS方法，在选择或剔除过程引入一个回溯的步骤，使得依据局部准则选择或剔除的特征因为与其他特征间的组合而重新被考虑从底向上时，l>r，首先逐步增选l个特征，然后再逐步剔除r个与其他特征组合起来准则最差的特征，依此类推，直到选择到所需要数目的特征从顶向下时，l<r，首先逐步剔除r个特征，然后再从已经被剔除的特征中逐步选择l个与其他特征组合起来准则最优的特征，直到剩余的特征数目达到所需的数目增l减r法8.3特征选择的优化算法（4）特征选择的启发算法模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性，从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解启发式算法（HeuristicAlgorithm），一类得到近似最优解的优化算法，基于直观或经验构造，在可接受的计算代价下，给出优化问题每个实例的一个可行解，但多数情况下不能得到最优解，也无法描述解与最优解的近似程度。8.3特征选择的优化算法模拟退火（SimulatedAnnealingAlgorithm）起源于生物进化的思想，物竞天择，适者生存。应用于数学上的优化问题：将每一个可能的解看作群体中的一个个体，生成群体根据预定的目标函数对群体中每个个体进行评价，给出一个适应度值通过遗传算子对个体进行选择、交叉和变异操作，得到一个新群体不断重复遗传、变异过程，一代比一代适应度更高经过若干代，找出最优的个体作为优化问题的解8.3特征选择的优化算法遗传算法（GeneticAlgorithm，GA）模拟系统利用局部信息从而可以产生不可预测的群行为。蚁群算法：模拟自然界蚂蚁的觅食过程，基于信息正反馈原理寻找最优解粒子群优化算法：源于对鸟群捕食行为的研究，通过群体中个体之间的协作和信息共享来寻找最优解8.3特征选择的优化算法群智能算法（SwarmIntelligence）8.4过滤式特征选择方法先进行特征选择，再训练分类器，特征选择过程和后续分类器设计无关。特征选择时，需要先选定特征的评价准则，在特征集合中进行寻优，找到最优的特征组合。8.4过滤式特征选择方法利用互信息实现冗余度和关联度的量化度量，找出与类别标签之间关联最大、特征之间冗余最小的特征组合典型方法最小冗余最大相关（MinimumRedundancyMaximumRelevance，MRMR）算法根据各个特征和类别的相关性赋予特征不同的权重，再根据要选择的特征个数或者权重阈值选择若干个权重大的特征。Relief和ReliefF算法8.5包