模式识别课件

第8章特征选择与提取特征抽取的目的是获取一组“少而精”的分类特征，即获取特征数目少且分类错误概率小的特征向量。特征抽取常常分几步进行。第一步：特征形成第二步：特征选择第三步；待征提取本章只讨论特征选择和特征提取的方法

第8章特征选择与提取特征抽取8.1类别可分性准则

特征选择或特征提取的任务是从n个特征中求出对分类最有效的m个特征（m＜n)。需要一个定量的准则来衡量选择结果的好坏。8.1类别可分性准则从理论上讲，设计分类器，那么用分类器的错误概率作为准则就行了。但是，从第四章中错误概率的计算公式就会发现，即使在类条件概率密度已知的情况下错误概率的计算就很复杂，何况实际问题中概率分布常常不知道，这使得直接用错误概率作为准则来评价特征的有效性比较困难。希望找出另外一些更实用的准则来衡量各类间的可分性。从理论上讲，设计分类器，那么用分类器的错希望实用的可分性准则满足下列几条要求：①与错误概率有单调关系。②度量特性：

这里是第i类和第j类的可分性准则函数，越大，两类的分离程度就越大。③单调性，即加入新的特征时，准则函数值不减小。希望实用的可分性准则满足下列几条要求：

8.1.1基于距离的可分性准则各类样本之间的距离越大，则类别可分性越大。因此，可以用各类样本之间的距离的平均值作为可分性准则 （8.1-1）式中，c为类别数；Ni为类中样本数；Nj为类中样本数；是相应类别的先验概率；是样本与之间的距离。8.1.1基于距离的可分性准则如果采用欧氏距离，即有（8.1-2）（8.1-3）式中，表示第i类样本集的均值向量表示所有各类的样本集总平均向量如果采用欧氏距离，即有也可以用下面定义的矩阵写出的表达式。令 （8.1-4） （8.1-5）则

其中表示取矩阵的迹。为类内离散度矩阵，为类间离散度矩阵。也可以用下面定义的矩阵写出的表达式。我们希望类内离散度尽量小，类间离散度尽量大，因此除外，还可以提出下列准则函数

我们希望类内离散度尽量小，类间离散度尽量大，因此除8.1.2基于熵函数的可分性准则最佳分类器由后验概率确定，所以可由特征的后验概率分布来衡量它对分类的有效性。如果对某些特征，各类后验概率是相等的，即其中c为类别数，则我们将无从确定样本所属类别，或者我们只能任意指定x属于某一类(假定先验概率相等或不知道)，此时其错误概率为8.1.2基于熵函数的可分性准则另一个极端情况是，如果能有一组特征使得

此时x划归类，其错误概率为0。可见后验概率越集中，错误概率就越小。后验概率分布越平缓(接近均匀分布)，则分类错误概率就越大。为了衡量后验概率分布的集中程度，需要规定一个定量准则，我们可以借助于信息论中关于熵的概念。另一个极端情况是，如果能有一组特征使得设为可能取值的一个随机变量，它的取值依赖于分布密度为的随机向量x(特征向量)。我们想知道的是：给定某一x后，我们从观察的结果中得到了多少信息？或者说的不确定性减少了多少？从特征抽取的角度看，用具有最小不确定性的那些特征进行分类是有利的。设为可能取值在信息论中用“熵”作为不确定性的度量，它是，，…，的函数。可定义如下形式的广义熵：式中，是一个实的正参数，。在信息论中用“熵”作为不确定性的度量，不同的值可以得到不同的熵分离度量，例如当趋近于1时，根据L’Hospital法则有

当＝2时，得到平方熵不同的值可以得到不同的熵分离度显然，为了对所提取的特征进行评价，我们要计算空间每一点的熵函数。在熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠。因此熵函数的期望值 可以表征类别的分离程度，它可用来作为所提取特征的分类性能的准则函数。显然，为了对所提取的特征进行评价，我们

8.2特征选择从n个特征中挑选出m(m＜n)个最有效的特征，这就是特征选择的任务。最直接的特征选择方法是根据专家的知识挑选那些对分类最有影响的特征。另一种是用数学方法进行筛选比较，找出最有分类信息的特征。本节只讨论用数学方法进行特征选择。8.2特征选择要完成特征选择的任务，必须解决两个问题：选择的标准，这可以用前面讲的类别可分性准则，选出使某一可分性达到最大的特征组来。找一个较好的算法，以便在较短的时间内找出最优的那一组特征。有两个极端的特征选择算法，一个是单独选择法，另一个是穷举选择法。要完成特征选择的任务，必须解决两个问题：1.单独选择法

就是把n个特征每个特征单独使用时的可分性准则函数值都算出来，按准则函数值从大到小排序，如 J(x1)＞J(x2)＞…＞J(xm)＞…J(xn)然后，取使J较大的前m个特征作为选择结果。问题：这样得到的m个特征是否就是一个最优的特征组呢？

1.单独选择法2.穷举选择法从n个特征中挑选m个，把所有可能的组合的可分性准则函数值都算出来，然后看哪一种特征组合的准则函数值最大，我们就选中该种组合的m个特征。这就是穷举选择法。一般，穷举法的计算量太大，以至无法实现。因此，我们常采用一些优化算法进行特征选择。2.穷举选择法3.穷举法的快速算法穷举法的快速算法的基本技术是合理地组织搜索过程和特征组合，避免具体计算所有的特征组合，同时又能把所有的特征组合都考虑到，不影响达到的最优结果，使选出的一组特征的准则J（·）最大。快速算法的主要依据是分类准则的单调性，若用表示剔除k个特征后的特征组合，则若有则必有3.穷举法的快速算法

分支定界算法是穷举法的一种快速算法。是一种自上而下的搜索方法，且具有回溯功能，首先搜索最右边的分支，按由上到下的顺序搜索完一个子树后，再回到根节点，按由右到左的顺序，依次搜索其它的分支。（说明）分支定界算法是穷举法的一种快速算法。是一种自上而下的搜

8.3基于距离可分性准则的特征提取特征选择是在一定准则下从n个特征中挑选出最优的m个特征，其余的n-m个特征被取消了。一般来说，原来的n-m个特征多多少少都含有一些分类信息，简单地把这些特征抛弃了，有点可惜。那么能不能把n个特征的分类信息尽量集中到m个特征中去？这就是特征提取要研究的问题。8.3基于距离可分性准则的特征提取特征提取就是通过某种数学变换，把n个特征压缩为m个特征，即 （8.3-1）式中，x是具有n个特征的向量，变换矩阵A是一个n×m阶的矩阵，经变换后的向量y是m维的,m＜n。特征提取的关键问题是求出最佳的变换矩阵，使得变换后的m维模式空间中，类别可分性准则值最大。特征提取就是通过某种数学变换，把n以可分性准则为例，详细讨论一下基于的特征提取问题。采用变换后，我们希望在m维的y空间里，样本的类别可分性好，即希望在y空间里，准则函数达到最大值。y空间里的协方差矩阵与x空间里的协方差矩阵有如下关系： （8.3-2）（证明）以可分性准则这样，y空间里的类内离散度矩阵可用x空间里的类内离散度矩阵计算得到： 同样有 因此，特征提取问题就变成求变换矩阵A，使得y空间里的准则函数达到最大值。（具体过程）这样，y空间里的类内离散度矩阵例8.1给定先验概率相等的两类，其均值向量分别为，，协方差矩阵分别为

求用的特征提取。例8.1给定先验概率相等的两类，其均值向量分别为8.4基于K-L变换的特征提取8.4.1离散K-L展开式K-L变换是一种常用的正交变换。假设x为n维的随机向量，x可以用n个基向量的加权和来表示： （8.4-1）式中，为基向量，为加权系数。

8.4基于K-L变换的特征提取式(8.4-1)还可以用矩阵形式表示： （8.4-2）式中，，式(8.4-1)还可以用矩阵形式表示：取基向量为正交向量，即由正交向量构成，是正交矩阵，即 （8.4-3）将式(8.4-2)两边左乘，得 （8.4-4）即 （8.4-5）

我们希望向量的各个分量间互不相关。那么如何保证的各个分量间互不相关呢?这取决于选用什么样的正交向量集取基向量为正交向量，即

下面来导出所需的正交向量集设随机向量的总体自相关矩阵为

将代入上式，得我们要求向量的各个分量间互不相关，即应满足下列关系：

下面来导出所需的正交向量集写成矩阵形式，应使则

将上式两边右乘，得 写成矩阵形式，应使因是正交矩阵，所以得

即

可以看出：是的自相关矩阵R的本征值，是对应的本征向量。因为R是实对称矩阵，其不同本征值对应的本征向量应正交。因是正交矩阵，所以得综上所述，K-L展开式的系数可用下列步骤求出：①求随机向量x的自相关矩阵

②求出自相关矩阵R的本征值和对应的本征向量，得到矩阵

③展开式系数即为

综上所述，K-L展开式的系数可用下列步骤求出：8.4.2基于K-L变换的数据压缩我们从n个本征向量中取出m个组成变换矩阵A，即

这时，A是一个n×m维矩阵，x为n维向量，经过变换，得到降维为m的新向量。现在的问题是选取哪m个本征向量构成变换矩阵A，使降维的新向量在最小均方误差准则下接近原来的向量x？8.4.2基于K-L变换的数据压缩对于式(8.4-1)，即

现在只取m项，对略去的项用预先选定的常数bj来代替，这时对x的估计值为 由此产生的误差为均方误差为 （8.4-6）

对于式(8.4-1)，即（8.4-6）要使最小，对bj的选择应满足所以（8.4-7）这就是说，对于省略掉的那些中的分量，应该用它们的期望值来代替。要使最小，对bj的选择应满足如果在K-L变换前，将模式总体的均值向量作为新坐标系的原点，即在新坐标系中，E[x]＝0，根据式(8.4-7)得

这样，由式(8.4-6)给出的均方误差变为

如果在K-L变换前，将模式总体的均值向量作为新坐标式中是x的自相关矩阵R的第j个本征值；是与对应的本征向量。显然，所选的值越小，均方误差也越小。综上所述，基于K-L变换的数据压缩的步骤如下：①平移坐标系，将模式总体的均值向量作为新坐标系的原点；②求出自相关矩阵R；③求出R的本征值及其对应的本征向量；式中是x的自相关矩阵R的第j个本征值；④将本征值按从大到小排序，如：

取前m个大的本征值所对应的本征向量构成变换矩阵：

⑤将n维的原向量变换成m维的新向量：④将本征值按从大到小排序，如：例8-2给出样本数据如下：试用K-L变换作一维数据压缩。例8-2给出样本数据如下：解.①求样本总体均值向量无需作坐标系平移。②求自相关矩阵解.③求本征值和本征向量。解本征值方程即解得本征值由，可解得本征向量为③求本征值和本征向量。解本征值方程④取作为变换矩阵⑤将原样本变换为一维的样本：其结果如图8-2所示。④取作为变换矩阵8.4.3基于K-L变换的特征提取K-L变换适用任何概率分布，它是在均方误差最小的意义下获得数据压缩的最佳变换。采用大本征值对应的本征向量构成变换矩阵，起了减小相关性、突出差异性的效果，有人称之为主分量变换。不过，采用K-L变换作为模式分类的特征提取时要注意保留不同类别的模式分类识别信息。单纯考虑尽可能准确地代表原模式的主分量，有时分类效果并不好。8.4.3基于K-L变换的特征提取(1)采用模式总体自相关矩阵作K-L变换这是把多类模式合并起来看成是一个总体分布，按其自相关矩阵作K-L变换，采用与大本征值对应的本征向量构成变换矩阵，使降维模式能在均方误差最小的条件下逼近原来的模式，这就是上面8.4.2小节中讨论过的情况。采用自相关矩阵能保留模式原有分布的主要结构。如果原来的多类模式在总体分布上存在可分性好的特征，用总体自相关矩阵的K-L变换便能尽量多地保留可分性信息。(1)采用模式总体自相关矩阵作K-L变换(2)采用离散度矩阵作K-L变换为了强调模式的分类识别信息，可用作K-L变换。如果模式类别数为c，则类间离散度矩阵的秩不会大于c-1。假使类内离散度矩阵为满秩矩阵，则的秩也不会大于c-1，只多有c-1个非零本征值。我们可求出的c-1个非零本征值，按从大到小排序，如：

选出m个与大本征值对应的本征向量构成变换矩阵。这实际上就是8.3节讨论的基于距离可分性准则的特征提取。(2)采用离散度矩阵作K-L变换

8.5基于神经网络的特征提取8.5.1最大主分量的自适应提取图8-3给出的神经网络可以完成最大主分量的自适应提取。图8-38.5基于神经网络的特征提取图8-3网络结构确定了，下面的问题是该网络的权向量w按什么规则进行学习。我们定义目标函数为式中，是x的自相关矩阵。为了获取使达到最大值的权向量w，可由梯度下降法来实现。网络结构确定了，下面的问题是该网络相对于w的梯度为

我们规定，权向量w为归一化向量：，可得 （8.5-1）即用样本值代替随机向量，则上式为

相对于w的梯度为这样，权向量w的修正量为

该网络权向量的修正规则为 （8.5-2）该网络采用式(8.5-2)的权向量修正规则，经若干步迭代后，网络收敛。网络收敛后有以下三个结论：（1）（2）w位于R的最大本征向量方向上（3）输出方差最大，即w位于使最大的方向上这样，权向量w的修正量为以上结论告诉我们，该网络在式(8.5-2)学习规则下迭代，权向量w将收敛于R的最大本征值的归一化本征向量。因此，该网络完成了将n维的数据压缩为一维的数据，而且保证压缩结果，均方误差最小。以上结论告诉我们，该网络在式(8.5-8.5.2多主分量的自适应提取图8-3中的神经网络只有一个输出节点，可获得第一主分量。下面考虑图8-4所示的具有多个输出节点的神经网络。假定网络的前m-1个输出神经元的权向量已收敛于样本自相关矩阵R的前m-1个最大的本征向量，该网络经过学习，第m个神经元的权向量可以收敛于R的第m个最大的本征向量，该权向量与前m-1个权向量正交。8.5.2多主分量的自适应提取假设样本向量为，由前m-1个神经元的输出构成的向量为，由前m-1个神经元的权向量构成的矩阵为,第m个神经元的权向量为,前m-1个神经元与第m个神经元的连接权向量为。这样，网络的输入输出关系为 （8.5-5） （8.5-6）假设样本向量为我们确定网络权向量修正规则如下: （8.5-7） （8.5-8）不难看出，式(8.5-7)与8.5.1节中的权向量修正规则是相同的，式(8.5-8)具有正交归一化的功能。下面我们分析这种算法的收敛特性。我们确定网络权向量修正规则如下:

假设前m-1个神经元的权向量已分别收敛于R的前m-1个最大的本征向量，即

我们将展开成 （8.5-9）将式(8.5-5)和(8.5-6)代入式(8.5-7)，得假设前m-1个神经元的权向量对上式两边求统计平均，可得 （8.5-10）式中， （8.5-11）根据式(8.5-9)和式(8.5-10)，可得的修正规则为即 （8.5-12）式中，为R的第i个本征值。对上式两边求统计平均，可得类似地．对式(8.5-8)两边求统计平均可得 （8.5-13）将式(8.5-12)和(8.5-13)两式联立，并写成矩阵形式 （8.5-14）由于时，，因此我们对式(8.5-14)的讨论可以分成和两种情况来进行。类似地．对式(8.5-8)两边求统计平均可得第一种情况()：如果，那么式(8.5-14)的系数矩阵有—个二重本征值