模式识别 第七章 特征提取与选择精选文档.ppt

模式识别 第七章 特征提取与选择1本讲稿第一页，共四十九页第七章第七章 特征提取与选择特征提取与选择 7.1 7.1 概概 述述2本讲稿第二页，共四十九页 模式识别的三大核心问题模式识别的三大核心问题:第七章第七章 特征提取与选择特征提取与选择7.1概述概述特征数据采集特征数据采集分类识别分类识别特征提取与选择特征提取与选择 分类识别的正确率取决于对象的表示、训练学习和分类识别的正确率取决于对象的表示、训练学习和分类识别算法，我们在前面各章的介绍中详细讨论了后分类识别算法，我们在前面各章的介绍中详细讨论了后两方面的内容。本章介绍的特征提取与选择问题则是对两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。象表示的一个关键问题。3本讲稿第三页，共四十九页 通常在得到实际对象的若干具体特征之后，通常在得到实际对象的若干具体特征之后，再由这些原始特征产生出对分类识别最有效、再由这些原始特征产生出对分类识别最有效、数目最少的特征，这就是特征提取与选择的任数目最少的特征，这就是特征提取与选择的任务。从本质上讲，我们的目的是使在最小维数务。从本质上讲，我们的目的是使在最小维数特征空间中异类模式点相距较远（类间距离较特征空间中异类模式点相距较远（类间距离较大），而同类模式点相距较近（类内距离较小）大），而同类模式点相距较近（类内距离较小）。第七章第七章 特征提取与选择特征提取与选择7.1概述概述4本讲稿第四页，共四十九页7.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基本途径主要方法有：主要方法有：分支定界法分支定界法、用回归建模技术确定相关特用回归建模技术确定相关特征征等方法。等方法。（1 1）直接选择法：）直接选择法：当实际用于分类识别的特征数目当实际用于分类识别的特征数目d d 确定后，确定后，直接从已获得的直接从已获得的n n 个原始特征中选出个原始特征中选出d d 个特征个特征 ，使可分性判据，使可分性判据J J 的值满足下式：的值满足下式：式中式中 是是n 个原始特征中的任意个原始特征中的任意d 个特征，个特征，上式表示直接寻找上式表示直接寻找n 维特征空间中的维特征空间中的d 维子空间。维子空间。5本讲稿第五页，共四十九页（2 2）变换法）变换法，在使判据，在使判据J J 取最大的目标下，对取最大的目标下，对n n 个原个原始特征进行变换降维，即对原始特征进行变换降维，即对原n n 维特征空间进行坐标维特征空间进行坐标变换，然后再取子空间。变换，然后再取子空间。7.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基本途径主要方法有：主要方法有：基于可分性判据的特征选择基于可分性判据的特征选择、基于误判概率基于误判概率的特征选择的特征选择、离散离散K-LK-L变换法变换法(DKLT)(DKLT)、基于决策界的特基于决策界的特征选择征选择等方法。等方法。6本讲稿第六页，共四十九页7.2 7.2 类别可分性判据类别可分性判据第七章第七章 特征提取与选择特征提取与选择7本讲稿第七页，共四十九页7.2 类别可分性判据类别可分性判据 为确立特征提取和选择的准则：引入类别可分性判据，来为确立特征提取和选择的准则：引入类别可分性判据，来刻划特征对分类的贡献。为此希望所构造的可分性判据满足刻划特征对分类的贡献。为此希望所构造的可分性判据满足下列要求：下列要求：构造可分性判据构造可分性判据(1)(1)与误判概率与误判概率(或误分概率的上界、下界或误分概率的上界、下界)有单调关系。有单调关系。(2)(2)当特征相互独立时，判据有可加性，即当特征相互独立时，判据有可加性，即 ：式中，式中，是对不同种类特征的测量值，是对不同种类特征的测量值，表示使用括号中特征时第表示使用括号中特征时第i 类与第类与第j类可分性判据函数。类可分性判据函数。8本讲稿第八页，共四十九页7.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据(3)(3)判据具有判据具有“距离距离”的某些特性，即的某些特性，即 ：，当，当时；时；，当，当时；时；(4)(4)对特征数目是单调不减，即加入新的特征后，判据对特征数目是单调不减，即加入新的特征后，判据值不减。值不减。9本讲稿第九页，共四十九页7.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据值得注意的是值得注意的是：上述的构造可分性判据的要求，即：上述的构造可分性判据的要求，即“单调单调性性”、“叠加性叠加性”、“距离性距离性”、“单调不减性单调不减性”。在。在实际应用并不一定能同时具备，但并不影响它在实际实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。使用中的价值。10本讲稿第十页，共四十九页7.2 类别可分性判据类别可分性判据7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据一般来讲，不同类的模式可以被区分是由于它们所属类一般来讲，不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。别在特征空间中的类域是不同的区域。显然，区域重叠的部分越小或完全没有重叠，类别的显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。可分性就越好。因此可以用距离或离差测度（散度）来构造类别的可分因此可以用距离或离差测度（散度）来构造类别的可分性判据。性判据。11本讲稿第十一页，共四十九页(一一)点与点的距离点与点的距离 (二二)点到点集的距离点到点集的距离用用均方欧氏距离均方欧氏距离表示表示7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据12本讲稿第十二页，共四十九页(三三)类内及总体的均值矢量类内及总体的均值矢量 各类模式的总体均值矢量各类模式的总体均值矢量 类的均值矢量：类的均值矢量：为相应类的先验概率，为相应类的先验概率，当用统计量代替先验概当用统计量代替先验概率时，总体均值矢量可表示为：率时，总体均值矢量可表示为：7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据13本讲稿第十三页，共四十九页(四四)类内距离类内距离 类内均方欧氏距离类内均方欧氏距离 类内均方距离也可定义为：类内均方距离也可定义为：7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据14本讲稿第十四页，共四十九页(五五)类内离差矩阵类内离差矩阵 显然显然(六六)两类之间的距离两类之间的距离 7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据15本讲稿第十五页，共四十九页(七七)各类模式之间的总的均方距离各类模式之间的总的均方距离 当取欧氏距离时，总的均方距离为当取欧氏距离时，总的均方距离为7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据16本讲稿第十六页，共四十九页(八八)多类情况下总的类内、类间及总体离差矩阵多类情况下总的类内、类间及总体离差矩阵 类内离差类内离差类间离差类间离差总体离差总体离差 易导出易导出7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据17本讲稿第十七页，共四十九页7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据18本讲稿第十八页，共四十九页7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据在特征空间中，当类内模式较密聚，而不同类的模式相距在特征空间中，当类内模式较密聚，而不同类的模式相距较远时，从直觉上我们知道分类就较容易，由各判据的构较远时，从直觉上我们知道分类就较容易，由各判据的构造可知，这种情况下所算得的判据值也较大。由判据的构造可知，这种情况下所算得的判据值也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。造我们还可以初步了解运用这类判据的原则和方法。19本讲稿第十九页，共四十九页7.2 7.2 类别可分性判据类别可分性判据7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据考虑两类问题。上图是一维的两类概率分布密度。考虑两类问题。上图是一维的两类概率分布密度。(a)(a)表示两类是完全可分的。表示两类是完全可分的。(b)(b)是完全不可分的。是完全不可分的。20本讲稿第二十页，共四十九页可用两类概密函数的重叠程度来度量可分性，构可用两类概密函数的重叠程度来度量可分性，构造基于类概密的可分性判据。此处的所谓重叠程度是造基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。指两个概密函数相似的程度。7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据21本讲稿第二十一页，共四十九页7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据(一一)BhattacharyyaBhattacharyya 判据判据(J JB B)受相关概念与应用的启发，我们可以构造受相关概念与应用的启发，我们可以构造B-判判据，它的计算式为据，它的计算式为 W W-=xdxpxpJBr rr rr r2121)()(ln 式中式中W W表示特征空间。在最小误判概率准则下，误判表示特征空间。在最小误判概率准则下，误判概率有概率有 BJPPeP-exp)()()(21210 22本讲稿第二十二页，共四十九页7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据（二）（二）Chernoff判据判据(JC)23本讲稿第二十三页，共四十九页(三三)散度散度J JD D(Divergence)(Divergence)i i类对类对 j j类的平均可分性信息为：类的平均可分性信息为：7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 j j 对对 i i 类的平均可分性信息为：类的平均可分性信息为：24本讲稿第二十四页，共四十九页7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据对于对于 i i和和 j j两类总的平均可分性信息称为散度，其定义两类总的平均可分性信息称为散度，其定义为两类平均可分性信息之和，即为两类平均可分性信息之和，即 (三三)散度散度JD(Divergence)25本讲稿第二十五页，共四十九页大盖小问题大盖小问题 在特征空间中，若有某两类间的在特征空间中，若有某两类间的JB、JC或或JD很大，可很大，可使平均判据变大，这样就掩盖了某些类对的判据值较小使平均判据变大，这样就掩盖了某些类对的判据值较小的情况存在，从而可能降低总的分类正确率，即所谓的的情况存在，从而可能降低总的分类正确率，即所谓的大盖小问题大盖小问题。为改善这种情况，可对每个类对的判据采用变。为改善这种情况，可对每个类对的判据采用变换的方法，使对小的判据较敏感。例如，对换的方法，使对小的判据较敏感。例如，对JD，可采用变换，可采用变换26本讲稿第二十六页，共四十九页这样，当这样，当 i和和 j两类模式相距很远时，两类模式相距很远时，JD(i,j)变得很变得很大，但大，但 也只能接近于也只能接近于1。但对于散度。但对于散度JD(i,j)小的小的情况，情况，又变得较敏感。于是，总的平均又变得较敏感。于是，总的平均(变换变换)判据判据为为 7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据27本讲稿第二十七页，共四十九页同样对于同样对于JB，单类与平均判据分别为：，单类与平均判据分别为：单类：单类：平均判据：平均判据：7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据28本讲稿第二十八页，共四十九页7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据在信息论中，在信息论中，熵熵(Entropy)(Entropy)表示不确定性表示不确定性，熵越大不，熵越大不确定性越大。可以借用熵的概念来描述各类的可分性。确定性越大。可以借用熵的概念来描述各类的可分性。对于对于c c类问题，给定各类的后验概率类问题，给定各类的后验概率 可以写成如下形式：可以写成如下形式：熵的定义：熵的定义：由洛必达法则知：当由洛必达法则知：当 时时29本讲稿第二十九页，共四十九页7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据例如：例如：显然这时能实现完全正确的分类识别显然这时能实现完全正确的分类识别 30本讲稿第三十页，共四十九页7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据31本讲稿第三十一页，共四十九页7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据熵的主要性质：熵的主要性质：(4)(4)其中其中说明当类别较少时，分类识别的不确定性变小。说明当类别较少时，分类识别的不确定性变小。从特征选择角度看，我们从特征选择角度看，我们应选择使熵最小的那些特征应选择使熵最小的那些特征用于分类用于分类即选用具有最小不确定性的特征进行分类是即选用具有最小不确定性的特征进行分类是有益的。有益的。32本讲稿第三十二页，共四十九页使熵最小的特征利于分类，取熵的期望：使熵最小的特征利于分类，取熵的期望：广义熵广义熵（具有熵的性质，利于计算）定义为定义为:式中0，1。不同的值可得不同的可分性度量。当当1时，由洛必达法则可得时，由洛必达法则可得Shannon熵熵当当=2时，可得平方熵时，可得平方熵本讲稿第三十三页，共四十九页使用使用 判据进行特征提取与选择时，我们的目标是使判据进行特征提取与选择时，我们的目标是使。同理，我们亦可用点熵在整个特征空间的概率平均同理，我们亦可用点熵在整个特征空间的概率平均作为可分性判据。作为可分性判据。7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据34本讲稿第三十四页，共四十九页第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用35本讲稿第三十五页，共四十九页7.5.1 离散离散K-L变换（变换（DKLT）DKLT的性质：的性质：1.使变换后产生的新的分量正交或不相关使变换后产生的新的分量正交或不相关;2.以部分新分量表示原矢量均方误差最小以部分新分量表示原矢量均方误差最小;3.使变换矢量更趋确定、能量更趋集中。使变换矢量更趋确定、能量更趋集中。有限离散有限离散K-LK-L变换（变换（DKLTDKLT）,又称霍特林又称霍特林(Hotelling)(Hotelling)变换或主分量分解变换或主分量分解,它是一种基于目标统计特性的最佳它是一种基于目标统计特性的最佳正交变换。正交变换。36本讲稿第三十六页，共四十九页7.5.1 离散离散K-L变换（变换（DKLT）设设n维随机矢量维随机矢量r rLLxx xxn=(,)12T，其均，其均值矢量值矢量 r rr rxE x=，相关阵，相关阵 RE xxxr rr r r r=T，协方，协方差阵差阵 CE xx xxxr rr rr rr rr r=-()()T，r rx经正交变换后经正交变换后产生矢量产生矢量r rLLyy yyn=(,)12T，37本讲稿第三十七页，共四十九页设有标准正交变换矩阵设有标准正交变换矩阵T，（即，（即 TT=I）取前取前m项为项为 的估计值的估计值（称为（称为 的的K-LK-L展开式）展开式）其均方误差为其均方误差为38本讲稿第三十八页，共四十九页xtyiir rr r=在在TT=I的约束条件下的约束条件下,要使均方误差要使均方误差为此作准则函数为此作准则函数由由 可得可得即即39本讲稿第三十九页，共四十九页 i是是 的特征值，而的特征值，而 是相应的特征矢量。是相应的特征矢量。由由表明表明:利用上式有利用上式有:7.5.1 离散离散K-L变换（变换（DKLT）在在上上述述的的估估计计式式中中，如如果果不不是是简简单单地地舍舍弃弃后后(n-m)项项，而而是是用用预预选选的的常常数数bi代代替替yi,i=m+1,n，此此时时的的估计式为估计式为:40本讲稿第四十页，共四十九页7.5.1 离散离散K-L变换（变换（DKLT）的均方误差为的均方误差为:（1）最佳的）最佳的bi可通过可通过 求得求得 41本讲稿第四十一页，共四十九页7.5.1 离散离散K-L变换（变换（DKLT）42本讲稿第四十二页，共四十九页7.5.1 离散离散K-L变换（变换（DKLT）因为因为为非负定阵，故有为非负定阵，故有上述的讨论可归纳为上述的讨论可归纳为:当我们用简单的当我们用简单的“截断截断”方式产生估计式时方式产生估计式时,使均方误使均方误差最小的正交变换矩阵是随机矢量差最小的正交变换矩阵是随机矢量x x的相关阵的相关阵R Rx x的特征矢量的特征矢量矩阵矩阵;当估计式除了选用当估计式除了选用m m个分量个分量y yi i(i=1,2,(i=1,2,m),m)之外之外,还还用余下的各用余下的各y yi i的均值的均值b bi i代替相应的分量时代替相应的分量时,使均方误差最使均方误差最小的正交变换矩阵是小的正交变换矩阵是x x的协方差阵。的协方差阵。这表明对于相同的这表明对于相同的m m，第一种估计式，第一种估计式比第二种估计式的均方差大。比第二种估计式的均方差大。43本讲稿第四十三页，共四十九页DKLTDKLT的性质的性质(1)(1)变换后各特征分量正交或不相关变换后各特征分量正交或不相关 的自相关阵和协方差阵为变换后的矢量的各分量是正交的,或不相关的(因为C=R-E(x)E(x)，当E(x)=0时，不相关即是正交)；i=E(yi2),或i=Eyi-E(yi)2(方差)44本讲稿第四十四页，共四十九页 妈妈新开了个淘宝店，欢迎前来捧场妈妈新开了个淘宝店，欢迎前来捧场妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自己的一份力，帮忙宣传一下。己的一份力，帮忙宣传一下。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。欢迎大家来逛逛欢迎大家来逛逛【扬州五亭龙玩具总动员扬州五亭龙玩具总动员】个人小广告：个人小广告：45本讲稿第四十五页，共四十九页46本讲稿第四十六页，共四十九页(2)(2)最佳逼近性最佳逼近性(3)(3)使能量向某些分量相对集中，增强随机矢量使能量向某些分量相对集中，增强随机矢量总体的确定性总体的确定性DKLTDKLT的性质的性质47本讲稿第四十七页，共四十九页例例:已知两类样本已知两类样本 试用试用K-LK-L变换做一维特征提取。变换做一维特征提取。解：解：（1 1）（3 3）求求R R的特征值、特征矢量的特征值、特征矢量（2 2）48本讲稿第四十八页，共四十九页（4）选选 1 1对应的对应的 作为变换矩阵作为变换矩阵得由由 得变换后的一维模式特征为得变换后的一维模式特征为49本讲稿第四十九页，共四十九页