《模式识别导论》课件第7章

第7章特征提取与选择7.1特征提取与选择的基本概念7.2基于距离的特征提取7.3基于离散K-L变换的特征提取7.4特征选择方法前面几章讨论传统模式识别方法时，一直假定给定的数据集的特征都是对识别问题非常重要的。然而在很多实际问题中，数据的某些特征可能和识别任务是不相关的或者特征之间存在冗余。特征提取与选择的主要任务是研究如何从众多的特征中求出那些对分类识别任务最有效的特征。

为使特征能够代表对象，且便于实际操作和算法实现，并使分类结果真实可靠，要求所选用的特征应满足以下五个条件：

(1)真实性，特征应能准确地包含分类对象的物理信息。(2)有效性，所选用的特征和特征组合对分类是有效的，尽量使得对象易于分类识别。

(3)简约性，信息充分且数据冗余量少。

(4)鲁棒性，当所选用的特征受到测量误差较大影响时，尽量使得算法的有效性不被破坏。

(5)提取特征方便经济，便于实际操作。

本章不涉及具体的应用背景，因此不对(1)、(4)和(5)进行讨论，主要针对(2)和(3)的一些重要理论和技术进行详细介绍。

本章主要讨论特征提取与选择的基本概念、基于距离的特征提取、基于离散K-L变换的特征提取以及特征选择方法。

7.1特征提取与选择的基本概念

7.1.1特征的种类

特征是描述待分析对象性质的一种量，是对对象的一种抽象。从形式上看，特征可以分为以下三类：

1.物理特征

物理特征是根据对象的外在表现抽取的特征。例如为了描述某个人，通常采用性别、身高、胖瘦、肤色等特征，这些特征都属于物理特征。物理特征是比较直接、容易感知的特征，一般在设计模式识别系统时被选用。

2.结构特征

结构特征是能表征观察对象结构信息的特征。例如人的指纹具有小桥、环、分叉点、三角点和端点等特征，这些特征都属于结构特征。结构特征的获取是先将观察对象分割成若干基本构成要素，然后确定基本要素间的相互连接关系，通过各个要素和相互的连接关系表达对象。结构特征比物理特征要抽象一些，但仍属比较容易感知的特征，其表达能力一般要高于物理特征。结构特征在实际模式识别问题中已经有较多的成功应用，例如指纹识别和人脸识别等。

3.数学特征

数学特征是为了表征观察对象而人为设定的特征。例如每个学生的学号就是一种数学特征。数学特征有时和观察对象的固有属性没有关系，有时则是观察对象的物理或结构特征的计算结果。需要指出，数学特征是人为设定的，可以保证唯一性，但这种特征是抽象的，不容易被人感知。由于物理和结构特征很容易被视觉、触觉以及其他感觉器官所发现，因此人们通常利用这些特征来识别对象，但是这些特征对于计算机而言有时比较复杂。计算机在抽取和处理数学特征的能力方面要比人强得多。在本章中，计算机使用的数学特征包括统计平均值、相关矩阵和协方差矩阵的特征值及特征向量等。7.1.2特征提取与选择

特征提取是指通过映射或变换获取有效特征的过程。提取后的特征称为二次特征，它们是原始特征的某种组合，最常见的是线性组合。需要强调的是，特征提取一定要进行数学变换。特征选择是指从一组特征中挑选出对分类最有效的特征，实现特征选择的前提是确定特征是否有效的标准，在这种标准下方可寻找最有效的特征子集。用于特征选择的特征既可以是原始特征，也可以是经特征提取后得到的二次特征。在实现特征提取和选择的目标之前，需要首先制定特征提取和选择的标准，这些标准应该能够反映各类在特征空间的分布情况或刻画出特征对分类识别的重要性。在具体实施特征提取和选择时可以遵循如下两个基本的途径：

(1)已知可分性判据J，在使得该判据取得最大值的目标下，对原始特征进行变换降维，即对原始特征空间进行坐标变换，再取子空间。该类变换方法主要有基于距离可分性测度的特征提取方法和基于离散K-L变换的特征提取方法等。

(2)直接寻找原始特征空间中的低维子空间，即直接选择法。在选择的过程中，寻找能够使得可分性判据最大化的那组低维特征空间组合。直接特征选择方法包括最优搜索法和次优搜索法等。特征提取和特征选择都是在不降低或较少降低分类性能的情况下，降低特征空间的维数。其主要作用在于：

(1)简化计算。特征空间的维数越高，需要占用的计算机资源越多，计算的复杂度也就越高。

(2)简化特征空间结构。特征提取和选择是去除类间差别小的特征，保留类间差别大的特征，使得每类所占据的子空间结构可分离性更强，从而也可以简化类间分界面形状的复杂度。

需要指出，特征提取和选择并不是截然分开的。例如，可以先将原始特征空间映射到维数较低的空间，然后在这个空间中进行特征选择来进一步降低维数。

7.2基于距离的特征提取

特征提取与选择的目的是获得一组对于分类识别最有效的特征，从而实现特征空间维数的约简。然而，把一个高维特征变为低维特征的方法是很多的，需要一个标准来衡量哪种方法最有效，这种标准即为类别可分性测度。一般希望所构造的可分性判据应满足下列几个要求：

(1)与错误率(或错误率的上界及下界)有单调关系，即使得可分性测度取最大(或最小)值时，错误率也最小。

(2)当特征相互独立时，可分性测度具有可加性,即

这里，x1，x2，…，xd是对象不同种类特征的测量值;Jij(·)是第i类和第j类之间的可分性测度函数，Jij越大，表示两类的分离程度就越大。

(3)度量特性，主要包括非负性和对称性：

Jij>0，当i≠j时

Jij=0，当i=j时(7-2)

Jij=Jji

(7-1)

(4)单调性，即加入新的特征后，该可分性测度的值不会减小：

Jij(x1，x2，…，xd)≤Jij(x1，x2，…，xd，xd+1)

(7-3)

很多人在这方面做了不少工作，提出了各种可分性测度，本节主要介绍基于距离的类别可分性测度，以及基于这些可分性测度的特征提取方法。7.2.1基于距离的类别可分性测度

一般地讲，各类中的样本可以被分开是因为它们位于特征空间中的不同区域，我们总是希望不同类的样本之间的距离大一些，而同类的样本较集中。不同类区域之间距离越大或者重叠的部分越小，类别可分性就越好，因此，利用距离准则来构造类别可分性判据是可行的。我们在第6章的6.2节给出了多类情况下总的类内离散度矩阵SW、类间离散度矩阵SB和总的离散度矩阵ST的定义，并给出了利用它们构造的聚类准则函数J1~J6。实际上，这些聚类准则函数可以作为类别可分性判据来进行特征提取，这里，把它们称之为基于距离的类别可分性测度。除了第6章给出的J1~J6这六个类别可分性测度，下面给出另外三个类别可分性测度；(7-4)(7-5)(7-6)为了使所使用的特征能够有效地进行分类，我们希望类间离散度尽量大，同时类内离散度尽量小。所以，J4、J5和J6这三个测度越小越好，剩余六个测度则是越大越好。这些类别可分性测度之间存在关联，有的可分性测度之间几乎等

价，但性能上略有不同。7.2.2基于距离可分性测度的特征提取

设原始样本为x=(x1，x2，…，xq)T，其中，q为特征的维数。对x作线性变换，产生d维特征向量y=(y1，y2，…，yd)T，d≤q，即

y=WTx

(7-7)

其中，q×d矩阵W为特征提取矩阵或者变换矩阵。本小

节我们讨论在基于距离的类别可分性测度准则下，如何求得最优变换矩阵W。采用基于距离的类别可分性测度J1~J9进行特征提取时，需要求矩阵的迹最大(最小)或者行列式值最大(最小)。下面我们先以J1测度为例说明如何求矩阵迹最大化，再以J9测度为例说明如何求行列式值最大，其他类别可分性测度可类似处理。J1的定义如下；

其中，SW和SB分别为原始样本的类内和类间离散度矩阵。在新的变换特征空间中，新样本的类内和类间离散度矩阵S*W和S*B可定义为；(7-8)(7-9)

在新的变换特征空间中

若W为非奇异矩阵，可以等价为，这表明在非奇异变换条件下，原特征空间的类可分判据与新空间的判据是相同的。设WT是标准正交矩阵，利用该矩阵对进行对角化，得到(7-10)(7-11)(7-12)其中，λi(i=1，2，…，q)为的特征值，WT的列向量wi是对应于特征值λi的特征向量。由于一个方阵的迹等于它的所有特征值之和，因此可得

当新特征空间的维数d确定之后，取出的d个较大特征值对应的特征向量wi构造特征提取矩阵W，即

W=(w1，w2，…，wd)

(7-14)

此时采用W对x作变换，可分性测度J1达到了最大值,即(7-13)(7-15)其中，λ1≥λ2≥…≥λd≥…≥λq。

下面以J9为例，介绍如何运用以行列式形式出现的可分性测度求最优变换矩阵W。

易知SW是对称正定矩阵，存在非奇异矩阵A，使得

ATSWA=I

(7-16)

其中，I为单位矩阵。有标准正交矩阵V，可使V-1ATSTAV

=，为对角阵，而

令U=AV，则存在非奇异矩阵U，使得(7-17)且

UTSWU=I

(7-18)

对上式两边同时取逆，有

对上式两边左乘(7-16)式两边，得

再对上式左乘U，则有

从上式可知，U和分别为的特征向量构成的矩阵及特征值构成的对角阵。由于(7-19)(7-20)(7-21)

所以

即

如果设的特征值矩阵Λ=diag(λ1，λ2，…，λq)，则

那么(7-22)(7-23)(7-24)(7-25)(7-26)对于给定的d，取的前d个较大特征值对应的特征向量构成变换矩阵W，可使可分性测度J9达到最大值,即

其中，λ1≥λ2≥…≥λd≥…≥λq。(7-27)例7.1给定具有两个模式类的样本集X={x1，x2，…，x7}，其中，ω1：x1=(1，1)T，x2=(1，2)T，x3=(3，1)T，x4=(3，3)T；ω2：x5=(－2，－2)T，x6=(－2，－3)T，

x7=(－3，－2)T。利用类别可分性测度J9将样本特征维数变为一维。

解(1)计算矩阵。首先分别计算各类样本均值向量mi(i=1，2)和样本总体均值向量m。

然后计算每一类的类内离散度矩阵，i=1，2,即接着计算总的类内离散度矩阵SW；然后计算总的离散度矩阵ST；

最后计算

(2)计算D的特征值和特征向量。根据|D-λI|=0，可得

λ1=14.09，λ2=1.00

根据，可得λ1和λ2对应的特征向量分别为；

w1=(0.60，0.80)T

w2=(-0.69，0.73)T

(3)选择w1构成变换矩阵W，即

W=w1

(4)利用W对样本集X中的每一个样本进行特征提取，即

yi=WTxi

最终结果为

y1=1.40，y2=2.20，y3=2.60，y4=4.20

y5=－2.80，y6=－3.60，y7=－3.40

特征提取结果如图7.1所示。图7.1基于类别可分性测度J9的特征提取结果

7.3基于离散K-L变换的特征提取

离散K-L变换又称为霍特林变换或主成分分析，是一种基于目标统计特性的正交变换。该变换具有如下重要性质：(1)变换后产生的新分量是正交或者不相关的；(2)变换后各分量的非零平方期望或方差更趋于不均；(3)采用部分新分量表示原向量时均方误差最小，即具有最佳逼近性；(4)变换后向量能量更加集中，即变换使能量向某些分量相对集中；(5)变换后向量在总体上更趋确定性。鉴于离散K-L变换具有上述诸多性质，它已经在特征提取方面得到了极为重要的应用。7.3.1离散K-L变换(DKLT)

设q维随机向量x=(x1，x2，…，xq)T，其均值向量为，相关矩阵为Rx=E［xxT］，协方差矩阵为

。x经过标准正交矩阵WT正交变换后变成向量y=(y1，y2，…，yq)T，即(7-28)明显可以看出，y的各个分量为

而且由于WT为正交矩阵，因此，i=1，2，…，q

(7-29)(7-30)选择x关于yi的展开式的l项在最小均方误差准则下来线性估计x，此时，x的估计式为，1≤l≤q

(7-31)该估计式与x的均方误差为

为了使得均方误差ε2(l)在W为标准正交矩阵的约束下(即

)取得最小值，可以采用下式作为准则函数：

由可得(7-32)(7-33)

即

Rxwi=λiwi，i=l+1，…，q

(7-35)

式中，λi为x的相关矩阵Rx的特征值；wi为Rx的对应于λi的特征向量。将上式代入均方误差ε2(l)表达式(7-32)中，可得

如果在x的估计式中保留l个yi，而余下的q-l个分量yi(i=l+1，…，q)分别由预选的q-l个常数bi代替，此时的估计式可以表示为i=l+1，…，q

(7-34)(7-36)

估计的均方误差为

最佳的bi可以通过ε2/bi=0求得，即

可得(7-37)(7-38)(7-39)(7-40)于是

在W为标准正交矩阵的约束下，求使得ε2(l)→min的wi的方法和前面类似，构造准则函数为

由可得

Cxwi=λiwi，i=l+1，…，q

(7-43)(7-41)(7-42)从上式可以看出，λi和wi分别为x的协方差矩阵Cx的特征值和相应的特征向量。将上式代入均方误差ε2(l)表达式(7-41)中，可得

当采用式(7-31)估计x时，使均方误差最小的正交变换矩阵是随机向量x的相关矩阵Rx的特征向量矩阵的转置；而当采用式(7-37)估计x时，使均方误差最小的正交变换矩阵是x的协方差矩阵Cx的特征向量矩阵的转置。无论上述哪种情况，为使ε2(l)最小化，都是采用前l个较大特征值对应的特征向量构造l×q的变换矩阵。总结上面的内容，我们给出下面的定理。(7-44)定理7.1在一切标准正交变换z=VTx=(v1v2…vq)Tx中，用随机向量x的协方差矩阵Cx的特征向量矩阵(w1w2…wq)对其进行变换所得的向量y可使

式中，(w1

w2…wq)的各列对应的特征值满足λ1≥λ2≥…≥λq，。

这种采用x的相关矩阵Rx或者协方差矩阵Cx的特征向量矩阵作为变换矩阵的变换称为离散K-L变换，此时，式(7-30)称为x的K-L展开。

(7-45)7.3.2离散K-L变换在特征提取中的应用

设X={x1，x2，…，xn}表示一个具有c个模式类的样本集合，其中，每个样本xi是一个q维向量。下面介绍如何采用离散K-L变换对样本集进行特征提取，将样本的特征维数从q维降到d维。

(1)求c类样本集X的总体自相关矩阵R。

(2)求R的特征值λi和对应的特征向量wi，i=1，2，…，q，并将特征值按照从大到小的顺序进行排列。(7-46)

(3)将R的前d个较大特征值对应的特征向量wi构成变换矩阵W，即

W=［w1，w2，…，wd]

(7-47)

(4)对样本集X={x1，x2，…，xn}中的每一个样本xi进行K-L变换，得到相应的d维向量yi，即

yi=WTxi

(7-48)上面我们介绍了利用样本集的自相关矩阵R进行特征提取，同理可以先获得样本集的协方差矩阵C，形式如下：

然后利用C进行特征提取，该过程与上述过程类似，这里就不再赘述。(7-49)例7.2利用K-L变换将例7.1中样本集的特征维数由两维降为一维。

解(1)计算X的总体自相关矩阵R。

(2)计算R的特征值和特征向量。根据|]R-λI|=0，可得

λ1=9.37，λ2=0.49

根据Rwi=λiwi，可得λ1和λ2对应的特征向量分别为；

w1=［0.74，0.68］T

w2=［-0.68，0.74］T

(3)选择w1构成变换矩阵W，即

W=w1

(4)利用W对样本集X中的每一个样本进行K-L变换，即

yi=WTxi

变换结果为

y1=1.42，y2=2.10，y3=2.90，y4=4.26

y5=－2.84，y6=－3.52，y7=－3.58

7.4特征选择方法

7.2和7.3节介绍了对原始特征空间进行变换来获得有效特征的方法。我们也可以采用特征选择的方法，依据某种准则或者策略从原始特征中挑选出一些最有代表性的，分类性能最好的特征出来。因此，特征选择方法需要解决以下两个问题：(1)如何评价特征组合的有效性；(2)寻找有效特征组合的方法和策略。一般情况下，原始特征空间的维数是已知的，为保证选择出的特征具有一定的分类性能，可以通过7.2节介绍的各种可分性判据对特征组合的有效性进行度量。此外，由于选择后的特征维数d一般是未知的，假设原始特征空间维数为q，则d的选择范围是1~q之间的任何一个自然数，因此，所有可能的特征组合数目为。显而易见，这是一个典型的组合优化问题，如果q值很大，选择的特征数目也很多，则特征选择的复杂度是非常高的。为此，人们提出了一系列特征选择的策略。本节介绍两种特征选择方法：最优搜索法和次优搜索法。7.4.1最优搜索法

分支定界法是一种经典的最优搜索方法。在该算法中，寻找全局最优特征组合的搜索过程可以用一个树形结构来描述，称其为搜索树。搜索方案是沿着搜索树从上而下、从右向左进行，由于该树的每个节点代表一种特征组合，因此所有的特征组合都被考虑到了。分支定界法的关键是利用了特征选择可分性判据J的单调性，即对于两个特征子集X和Y,有

因此某些特征组合并不需要计算且又不影响全局最优特征组合的搜索。此外，该算法先从结构简单的部分开始搜索，所以效率很高。(7-50)下面采用一个从5个特征中选择2个特征的例子来说明分支定界法的原理。设原空间中的5个特征为{x1，x2，x3，x4，x5}，整个搜索过程的树形结构如图7.2所示。在该图中，根节点代表全部特征，节点上的数字表示所选特征的编号，因此其上的数字为(1，2，3，4，5)。每个节点表示一个特征组合，子节点所代表的特征比其父节点代表的特征少一个，同父的各子节点分别代表从父节点的特征组合中舍弃不同的一个特征后余下的特征。由于每个节点只删除一个特征，如果是从q个特征中选择d个，那么根节点到叶节点的层数由q-d决定，因此本例中为3层(根节点在第0层)。为使各个特征子集不重复，从父节点到子节点的特征删除过程中，要按照特征编号的顺序依次删除一个不同的特征。例如在第1层中，从左往右各个子节点删除的特征分别为1、2和3。只有三个子节点的原因是由于对某个子节点来讲，其左边同父节点已丢弃的特征以后不能在要丢弃的特征组合里，这样可以防止得到重复的特征组合。另外，从图中可以看出，每个分支最右边的节点总是只有一个子节点。图7.2分支定界法搜索树示例分支定界法的基本原理是先找到一个d维组合，期望该特征组合的判据值尽可能的大，并以此为界，然后将后续搜索到的节点的判据值与该界值进行比较。如果某节点的特征组合的判据值小于界值，则由判据的单调性，该节点的所有子节点不可能是最优特征组合，也就不需要再进行搜索。在已获得树结构的条件下，特征组合搜索过程总体上是从分支数量不密集的部分到分支数最密集的部分，也就是从上到下、从右到左进行。在这个过程中包含几个可能的子过程：向下搜索、更新界值、向上回溯、停止回溯再向下搜索。在搜索之前先将界值B初始化为0，然后从树的根节点沿最右边的一支自上而下搜索。在搜索树中，一个节点的子树最右边一支总是无分支的，因此从根节点开始可以直接到达叶节点，得到特征集(1，2)。假设该叶节点的特征组合的可分性判据值为J(1，2)=75，此时更新界值B=75，然后向上回溯。一旦遇到有分支的节点就停止回溯，转而向下搜索。因此，从特征集为(1，2)的节点向上回溯遇到根节点停止，转而向特征集为(1，3，4，5)的节点分支进行搜索。由于J(1，3，4，5=82>J(1，2)，继续往右边分支进行搜索，从图7.3中可知，一直可以搜索到叶子节点并计算特征组合(1，3)的判据值J(1，3)=79

>B，因此更新界值B=79，然后再向上回溯。依此类推，可以搜索到特征组合(1，5)的判据值J(1，5)=81>B，因此更新界值B=81。从特征集为(1，5)的节点向上回溯遇到根节点停止，转而向特征集为(2，3，4，5)的节点分支进行搜索。由于J(2，3，4，5)=78<B，根据单调性，该特征集合的所有子集的可分性判据都低于其自身的可分性判据。此时分支定界法停止搜索，得到最优特征组合(1，5)。图7.3分支定界法搜索回溯示意图分支定界法的高效性在于：(1)利用了可分性判据的单调性，从而避免了有相当多的特征组合的判据计算。如果树上某个节点a的可分性判据值满足Ja≤B，可知a的子树上各节点的可分性判据值都不会大于B，因此节点A的子树节点都不用去搜索，这就是所谓的分支定界；(2)分支定界法的搜索过程是从右至左进行的，由于树的右边分支要比左边分支结构简单，因此分支定界法具有高效的性能。7.4.2次优搜索法

1.单独最优的特征选择法

单独最优特征选择法是最简单的一种特征选择算法。该算法首先计算每个特征单独使用时的可分性判据值，然后根据得到的判据值对各个特征进行排序，最后选择前d个分类效果最好的特征作为最终的特征组合。

一般情况下，即使各个特征之间是统计独立的，单独最优特征选择算法选出的d个特征也不一定是最优的特征组合。只有当可分性判据J写为如下形式时：或(7-51)这种算法才能获得最优的特征组合。例如在正态分布情况下，当各个特征是相互独立时，用马氏距离作为判据选出的d个特征就是最优的特征组合。

2.顺序前进法

顺序前进法(SequentialForwardSelection，SFS)也称为增添特征法，是一种最简单的自下而上的搜索算法。该算法的基本思路是,每次从未选入的特征中选择一个特征，使它与已选入的特征组合在一起的可分性判据最大，直到特征数目达到指定的数目d为止。假设已经选择了k个特征，记为Xk，把未选择的q-k个特征xj(j=1，2，…，q-k)逐个与Xk组合后计算可分性判据值J，若

则选择x*与Xk构成新的特征组合，该过程一直进行到选入的特征数目达到指定维数d为止。

顺序前进法考虑了所选特征与已选入