2.1.1 特征的提取与选择

特征选择与提取的目的是获取一组“少而精”的分类特征，它是模式识别中的关键问题之一，同时也是最困难的问题。

确定合适的特征空间是设计模式识别系统的关键问题之一。如果所选用的特征空间能使同类物体分布具有紧致性，将为分类器设计提供良好的基础；反之，如果不同类别的样本在特征空间中混杂在一起，再好的分类器设计方法也无法提高分类器的准确性。利用信息获取装置产生的模式（已经经过了适当的预处理）往往含有的数据量很大，或者说模式处于一个高维的模式空间中。从模式空间向特征空间的转换有两种方法：一种是特征提取，通过某种映射改造原特征空间，构造一个有较好紧致性的精简的特征空间；另一种是特征选择，从一组特征中挑选出一些最有效的特征，以达到降低特征空间维数的目的。

本节将在特征评判标准的基础上，介绍两种常用的特征选择和提取的方法：分支界定法和基于K-L变换的特征提取法。

1.特征评判标准——类别可分性判据

特征评判标准主要是衡量类别间的可分性，显然，能使分类器错误概率最小的特征就是最好的特征。从理论上讲这是正确的，但在实际应用中存在很大困难。因此，通常需要采用一些更实用的、更具有可操作性的评判标准，这些标准应满足以下几点：

·与错误概率有单调关系，这样可以保证使准则取极值时其分类错误概率也较小。

·具有度量特性，即满足：

式中，Jij是用于衡量类ωi和类ωj的准则函数。

·具有单调性，当加入新特征时，判据不减少，即

特征独立时，满足可加性，即

在特征提取中常用的特征评价标准有基于分类误差的可分性判据、基于概率距离度量的可分性判据、基于概率依赖度量的可分性判据、基于熵度量的概率可分性判据和基于距离的可分性判据。

基于距离的可分性判据直接依靠样本计算，直观简洁，物理概念清晰，应用最为广泛。基于距离的可分性判据的出发点是各类样本之间的距离越大、类内聚度越小，则类别的可分性越好。直观上，各类样本之间的距离越大，则类别可分性越大。因此，可以用各类样本之间的距离平均值作为可分性准则。用δ(ξik,ξjl)表示第i类中第k个模式和第 j类中第l个模式间距离的度量值，平均距离可定义为：

式中，C表示类别数；如果距离度量δ采用欧几里得距离，则有：

考虑到式（2-4）的计算比较复杂，可将其转化为相应的矩阵来度量和处理。

第i类类内散布矩阵：

总体类内散布矩阵：

总体类间散布矩阵：

总体散布矩阵：

存在关系：

上面各式中，为第i类均值向量；，为样本集的均值向量； 为第i类协方差 为样本总的协方差。

类内散布矩阵表征各样本点围绕它均值的散布情况，类间散布均值表征各类间的距离分布情况，它们依赖于样本类别属性和划分。而总体散布矩阵与样本划分及类别属性无关。

构造准则有迹和行列式两种方法，两种方法的示例分别如下。

迹准则：

行列式准则：

表2-1所示为以类内散布矩阵SW、类间散布矩阵SB和总体散布矩阵ST为基础的一些准则和它们的意义。

2.特征选择及分支界定法

特征选择实质上就是从D个特征中选出d（d<D）个最有效的特征。显然，要得到最有效的特征，必须依据前述的可分性准则，采用一定的算法才能实现。有两个极端的特征选择算法，一个是单独选择法，另一个是穷举选择法。

单独选择法就是把D个特征中的每一个特征单独使用时的可分性准则函数值算出来，然后按准则函数值从大到小排序，取使准则函数较大的前d个特征作为选择的结果。这种方法看起来很简单，但是其得到的特征组不能保证是最佳特征组，即使是所有的特征都相互独立，也无法保证所选出的是最佳特征组。

穷举法就是将从D个特征取出d个特征的组合对应的可分性准则函数值都计算出来，然后看哪种组合的准则函数值最大，就选中该种组合作为最佳特征。显然这种方法能够得到所期望的最佳特征组，但是，当特征数过多时，该方法计算量太大，以致无法实现。

除了以上两个极端选择算法外，还有一种非极端算法——分支界定算法，其是一种自上而下的搜索方法，具有回溯功能，不需要显示评估所有d个特征的可能组合而确定最佳特征组，计算量远小于穷举法。但是，该算法的应用需假定特征选择准则满足单调性。用 X( j)表示含有 j个特征的候选特征组，单调性指的是对于具有下列嵌套关系的特征组x(j)：

其准则函数J(xj)应满足

这点由构造特征评判准则的定义可得到保证。

为引出分支界定搜索算法的基本观点，以从5个特征中挑选2个特征值为例。特征中所有可能组合由图2-1所示的树表示，顶称为根结点，中间称枝结点，共有D-d+1层。

现假设按自底向上，再由上向下的搜索方式从右结点开始评估树的每个结点的特征，并进行特征选择。设初始叶结点的 J 为 J0（为x4 x5的准则函数），在每个结点处，将结点的准则函数值和目前最优特征组的J0值进行比较。如果结点准则函数值大于J0，则还有发现更佳特征组的机会，而且必须继续沿着最右边的未勘探分支搜索。如果到达了树底的结点且相应准则值大于J0，则此结点定义了当前新的最佳特征组，而J0则做相应的更新。

另一方面，如果在某结点的准则函数值小于 J0，则此结点为起始点的分支就不需勘探。因为根据单调性，再往下的特征组合将导致准则函数值的进一步减小。如此按这一规律，由底向上，再自上而下，从右向左搜索全树，可获得最佳的二特征组合。此搜索算法特别快捷有效。

3.特征提取及主分量分析

特征提取就是通过某种数学变换，把n个特征压缩为m个特征，即

式中，x是具有n个特征的向量；变换矩阵A是一个n×m阶的矩阵；经变换后的向量y是m维的，m<n。可见，与特征选择简单的舍去部分特征相比，特征提取力图尽可能地保留原来全体特征的信息。

特征提取的关键问题是，求取最佳变换矩阵，使得变换后的m维模式空间中，类别可分性准则值最大。

主分量分析是最常用且非常有效的特征提取方法，它是以离散K-L变换为基础的数据压缩技术，下面将主要介绍这种方法。

（1）离散K-L变换展开式

K-L变换是一种常用的正交变换。

假设x为n维的随机变量，x可以用n个基向量的加权和来表示：

式中，αi为加权系数，ϕi为正交基向量，满足：

式（2-16）还可以用矩阵的形式表示：

式中

Φ由正交向量构成，所以Φ是正交矩阵，即

考虑到Φ为正交矩阵，由x=Φα得：

即

我们希望向量α的各个向量间互不相关。那么如何保证α的各个分量互不相关呢？这取决于选取什么样的正交向量集{ϕj}。

设随机向量的总体自相关矩阵为

将x=Φα代入上式，得

我们要求向量α的各个分量间互不相关，即满足下列关系：

写成矩阵的形式是：

则

将上式两边右乘Φ，得

因为Φ是正交矩阵，所以得

即

可以看出，λj是x的自相关矩阵R的本征值，ϕj是对应的本征向量。因为R是实对称矩阵，其不同本征值对应的本征向量应正交。

综上所述，K-L变换展开式的系数可用下列步骤求出：

（a）求随机向量x的自相关矩阵即

（b）求出自相关矩阵R的本征值λj和对应的本征向量ϕj（j=1,2,…,n），得到如下矩阵：

（c）展开系数即

（2）主分量分析

从n个本征向量中取出m个组成变换矩阵A，即

这时A是一个n×m的矩阵，x为n维向量，经过ATx变换，得到降维为m的新向量。现在的问题是选取哪m个本征向量构成变换矩阵A，使降维的新向量在最小均方误差准则下接近原来的向量x。

对于式（2-16），现在取m项，对略去的项用预先选定的常数bj来代替，这时对x的估计值为

由此产生的误差为

均方误差为

要使最小，对bj的选择应满足：

所以有

这就是说，对于省略掉的那些α中的分量，应该用它们的期望值来代替。

如果在K-L变换前，将模式总体的均值向量作为新坐标系的原点，即在新坐标系中，E[x]=0，根据式（2-39）得

这样式子（2-37）给出的均方误差变为

式中，λj是x的自相关矩阵R的第j个本征值；ϕj是与λj对应的本征向量。显然，所选的λj值越小，均方误差也越小。

综上所述，基于K-L变换的特征提取的步骤如下：

（a）平移坐标系，将模式总体的均值向量作为新坐标的原点；

（b）求出自相关矩阵R；

（c）求出R的本征值λ1,λ2,…,λn及其对应的本征向量ϕ1,ϕ2,…,ϕn；

（d）将本征值按从大到小排序，如

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

（e）将n维的原向量变换成m维的新向量，即

K-L变换是在均方误差最小的情况下获得数据降维的最佳变换。如果采用大本征值对应的本征向量构成变换矩阵，则能对应地保留原样本中方差最大的数据，所以K-L变换达到了减小相关性、突出差异性的效果，因此K-L变换又称主分量分析。