哈尔滨工业大学-模式识别课程-6．特征的提取与选择4学时

哈尔滨工业大学主讲人：李君宝第5章特征的选择与提取主要内容1.引言2类别可分离性判据3特征选择4.特征提取1.引言

对特征空间的改造、优化、主要的目的是降维，即把维数高的特征空间改成维数低的特征空间。降维主要有两种途径。一种是删选掉一些次要的特征，问题在于如何确定特征的重要性，以及如何删选。另一种方法是使用变换的手段，在这里主要限定在线性变换的方法上，通过变换来实现降维，这两种方法的区分要弄清楚。【问题的提出】1．什么叫特征空间？如果我们用颜色、尺寸、重量来衡量水果的构造的特特空间是几维空间？2．如果用颜色、尺寸与重量组成的特征空间来区分苹果与梨，这三种度量中的哪种最有效？

为什么？

能否想像这两种水果在这个三维空间的分布？如果用这个特征空间来区分红苹果与樱桃，你想像一下这两类水果在特征空间如何分布？

能否对这两种情况设计更经济有效的特征空间？【问题的提出】3．如果两类物体在一个二维特征空间如图分布,能否用删除其中任一维来优化特征空间？有没有什么方法能得到一个对分类很有利的一维特征空间？【问题的提出】

4．上题的答案可用右图Y1与Y2组成的空间表示？你认为哪个分量可以删掉？

5．将原在X1、X2空间表示的数改成用Y1、Y2空间表示？【问题的提出】1．描述事物方法的选择与设计方案1.从框架的左边框到数字之间的距离变化反映了不同数字的不同形状，这可以用来作为数字分类的依据。方案2.强调分析不同截面的信号，如在框架的若干部位沿不同方向截取截面分析从背景到字，以及从字到背景转换的情况,如AB截面切割字符三次，CD截面切割字符一次等。【问题的提出】2．特征空间的优化这个层次的工作发生在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，如何对它进行改造与优化的问题。一般说来要对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化，优化后的特征空间应该更有利于后续的分类计算例用RGB颜色空间和HSI颜色空间【问题的提出】【问题的提出】【问题的提出】【概念】【概念】【概念】2类别可分离性判据【概念】特征选择与提取的任务是找出一组对分类最有效的特征，因此需一准则。概念：数学上定义的用以衡量特征对分类的效果的准则实际问题中需根据实际情况人为确定。误识率判据：理论上的目标，实际采用困难（密度未知，形式复杂，样本不充分，…）可分性判据：实用的可计算的判据【概念】【用于可分性判据的类内类间距离】【用于可分性判据的类内类间距离】定义【用于可分性判据的类内类间距离】常用的基于类内类间距离的可分性判据：特点：直观，易于实现（用样本计算），较常用。不能确切表明各类分布重叠情况，与错误率无直接联系。当各类协差相差不大时，用此种判据较好。【用于可分性判据的类内类间距离】几种常见的距离度量（1）MinkovskiMetric(oforders)（2）城市块（CityBlock）（3）欧氏距离（Euclidean）Chobychev距离平方距离非线性距离度量【用于可分性判据的类内类间距离】选择原则：ii.计算简单，易于实现。iii.数学上容易处理。准则函数的递推计算问题:每增/减一个特征，只影响向量中的一个元素，矩阵的一行和一列。【用于可分性判据的类内类间距离】i.实际分类问题需要，找与分类性能关系密切者。【基于概率分布的可分性判据】考查两类分布密度之间的交叠程度【基于概率分布的可分性判据】定义：两个密度函数之间的距离：它必须满足三个条件：【基于概率分布的可分性判据】具体定义有多种：Bhattacharyya距离Chernoff界散度【基于概率分布的可分性判据】正态分布情况下：【基于概率分布的可分性判据】几种常见的概率距离准则(J)和概率相关性准则(I)【熵可分性判据】熵：事件不确定性的度量A事件的不确定性大（熵大），则对A事件的观察所提供的信息量大。思路：【熵可分性判据】定义熵函数满足如下条件①规一化②对称性③确定性④扩张性⑤连续性⑥分枝性【熵可分性判据】常用的熵函数Shannon熵：平方熵：广义熵：【熵可分性判据】结论【熵可分性判据】举例：图像分割3.特征选择问题：从D维特征中选取d维（d<D），使分类性能最佳（J最大）。【问题的提出】一、穷举算法：计算每一可能的组合，逐一比较准则函数。适用于：d或D−d很小（组合数较少）的情况。二、分支定界算法：从顶向下，有回溯应用条件：准则函数单调性基本思想：按照一定的顺序将所有可能的组合排成一棵树，沿树进行搜索，避免一些不必要的计算，使找到最优解的机会最早。【最优搜索方法】算法要点：·

根结点为全体特征（第0级）·

每个结点上舍弃一个特征，各个叶结点代表选择的各种组合·避免在整个树中出现相同组合的树枝和叶结点·记录当前搜索到的叶结点的最大准则函数值（界限B），初值置0·每级中将最不可能被舍弃（舍弃后J值最小）的特征放在最左侧·从右侧开始搜索【最优搜索方法】·从左侧同级中将舍弃的特征不在本结点以下各级中舍弃·搜索到叶结点后，更新B值，然后回溯到上一分支处·如果结点上J<B，则不向下搜索，向上回溯·每次回溯将已舍弃的特征放回（放回待舍弃之列）·如已回溯到顶（根）而不能再向下搜索，则J=B的叶结点即为解。【最优搜索方法】算法要点：特征总数D以及选择特征数d增加时，穷举法计算量迅速上升。【最优搜索方法】穷举法存在的问题：非最优，但某些情况下最优，实现简单（1）单独最优组合选前d个单独最佳的特征（2）SFS法（SequentialForwardSelection：顺序前进）：从底向上每加入一个特征寻优一次，使加入该特征后所得组合最大特点：考虑了特征间的相关性，但某特下一经入选，即无法淘汰（3）广义SFS法（GSFS）从底向上，每次增加l个特征。考虑了新增特征中的相关性计算量比SFS大，若l=d，（一步加满），则就是穷举法【非最优搜索方法】（4）SBS法（顺序后退，后向贯序）从顶向下，每次减一个特征与SFS相对，一旦失去，无法换回。（5）广义SBS法（GSBS）从顶向下，每次减r个特征模拟退火算法遗传算法【特征选择的几种新方法】模拟退火算法起源于物理退火物理退火过程：（1）加温过程（2）等温过程（3）冷却过程【模拟退火算法】

1953年，Metropolis提出重要的采样法，即以概率接受新状态，称Metropolis准则，计算量相对MonteCarlo方法显著减少。

1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。【模拟退火算法】Metropolis准则1）Metropolis准则提出固体在恒定温度下达到热平衡的过程可以用MorteCarol算法方法加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态。

采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。因此，Metropolis等在1953年提出了重要的采样法，即以概率接受新状态。假设在状态xold时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也从E(xold)变成E(xnew)，系统由状态xold变为状态xnew的接受概率p。1)随机产生一个初始解x0，令xbest＝x0，并计算目标函数值E(x0);2)设置初始温度T(0)=To，迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，则xbest=xnew；4)如果ΔE＞0，则p=exp(-ΔE/T(i));1)如果c=random[0,1]<p，xbest=xnew;否则xbest=xbest。5)Endfor4)i=i＋1；5)EndDo6)输出当前最优点，计算结束【模拟退火算法】3.特征选择(续)【复习】问题：从D维特征中选取d维（d<D），使分类性能最佳（J最大）。【复习】

基本遗传算法（SimpleGeneticAlgorithms，简称SGA），其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

【基本遗传算法】基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数

编码

GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。【基本遗传算法】几个术语

基因型：1000101110110101000111

表现型：0.637197编码解码个体（染色体）基因【基本遗传算法】初始种群：SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。适应度函数

：遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。【基本遗传算法】

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。【基本遗传算法】选择算子：交叉算子：所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点【基本遗传算法】交叉算子示意图

所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。【基本遗传算法】变异算子基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点【基本遗传算法】SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次【基本遗传算法】4特征提取特征提取：把D个特征变为d个新特征目的：更好分类和/或减少计算量【概念】【概念】【概念】准则函数J(w)：【欧氏距离准则下的特征提取】【欧氏距离准则下的特征提取】【欧氏距离准则下的特征提取】【欧氏距离准则下的特征提取】【欧氏距离准则下的特征提取】1.Chernoff概率距离【概率距离判据下的特征提取方法】【概率距离判据下的特征提取方法】