模式识别特征的选择和提取

模式识别特征的选择和提取第一页，共六十二页，编辑于2023年，星期六7.1引言

以前讨论分类器设计时，都假定模式的特征向量已经提取出来了（有多少特征确定了）。

特征的多少（维数）、”好坏”对分类器的设计和性能有很大的影响。

好的特征容易把类分开，或表示时误差较小。

1.

特征的维数和特征的“好坏”第二页，共六十二页，编辑于2023年，星期六

特征选择和提取的任务是如何从许多特征中找出那些最有效的特征，把高维特征空间压缩到低维特征空间。

特征的种类有物理的、结构的、数学的。物理的、结构的特征，人的感觉器官容易感受，数学的特征，如均值、相关系数、协方差矩阵的特征值和特征向量等。

物理和结构特征和所处理的具体问题有关，在解决实际问题时可以依据具体问题而定。

这一节研究一般的特征提取和选择的方法。

第三页，共六十二页，编辑于2023年，星期六2.

几个术语的含义

在一些书籍和文献中，在不完全相同的意义上使用“特征提取”和“特征选择”的术语。例如“特征提取”，有的专指特征的形成过程，有的指特征的形成、经选择或变换后得到有效特征的过程。

为了方便以后的讨论，我们把特征提取、特征选择的含义明确一下。

第四页，共六十二页，编辑于2023年，星期六

模式特征的产生过程一般包括以下步骤：

1．原始特征的形成：用仪表或传感器测量出来的一些特征量，或通过计算得到的一些特征（对波形和图象），称为原始特征、原始测量或一次特征。

第五页，共六十二页，编辑于2023年，星期六

2．特征提取：原始特征的数量可能很大，需要通过变换（映射）把高维特征空间降到低维空间，这时的特征叫二次特征，它们一般是原始特征的某种组合。

通过变换A：X

Y，

测量空间特征空间

需要尽可能多地保留对分类和表示有利的信息。

好处：减少计算量;在样本少时，便于估计密度函数；提高分类器设计的性能。第六页，共六十二页，编辑于2023年，星期六

3．特征选择：从得到的一组特征中，挑选最有效的特征以进一步减少特征空间的维数，得到它的一个有效子集。

第七页，共六十二页，编辑于2023年，星期六

特征的提取和选择是人类的一项基本智能活动，从相关和不相关信息中找出主要因素。

例如在细胞识别中，用变换的方法→较少的特征，用选择的方法→专家意见，或用数学方法进行筛选，从n个→m个。

但“提取”和“选择”不是截然分开的。

具体指什么要从上下文去理解。

特征选择时，前m个最好的不一定组合后也是最好的。

第八页，共六十二页，编辑于2023年，星期六

特征提取可以看作是在减少维数的同时，又能代表、表示原观测向量。

模式识别的任务是判别、分类。维数减少、一般错误率要增加，要限制在一定范围内。

第九页，共六十二页，编辑于2023年，星期六7.2基于特征向量分析的特征提取方法

这一节讨论基于相关矩阵或协方差矩阵的特征向量的特征抽取方法。这一方法和统计上的主因子分析以及随机过程中的K-L（Karhunen-Loeve）变换（展开）有密切关系。第十页，共六十二页，编辑于2023年，星期六1.

模式最优表示特征的提取

假定有一n维向量x，希望能用m（<n）个向量的线性组合来近似x，这m个向量来自一组标准正交基{uj，j=1，2，…，n}。

即把x近似表示为前m个基的组合：

=y1u1+y2u2+…+ymum

式中

yj=ujT

x

第十一页，共六十二页，编辑于2023年，星期六

写成矩阵形式，

=Umy

(n

×

m，m×

1)→n

×

1

y=UmT

x

(m×n，n×1)→m×1

其中:

y1↑↑↑

y=Um=

u1

u2…um

ym↓↓↓

第十二页，共六十二页，编辑于2023年，星期六

由于{uj，j

=1，2，…，n}是标准正交基，用表示x时的误差（残差）为

ε

=

x-

=

其中，yj

=

ujT

x,j>m

问题是找一组基{uj

}，使得均方误差

ε

=E[|ε|2]=E[|x-|2]最小。

这时的yi

就是从x导出的特征，而

y=umT

x就表示特征变换（由n维→m维）。

第十三页，共六十二页，编辑于2023年，星期六

根据误差公式和基是标准正交的条件，

ε

=

E[εT

ε]

=

E[（

）（）]=

如果把yj2

写成

yj2

=（yj）·（yj）=（ujTx）(xTuj)

则

E[yj2]=ujT

E[xxT]uj

=ujTRuj

，

其中R是自相关矩阵

(*)第十四页，共六十二页，编辑于2023年，星期六

ε=

要找一组基，使ε最小，同时要满足： ujTuj

=1，j=m+1,…,n.

把约束ujTuj

=1用拉格朗日乘子（法）写入误差中，有

ε’=+（*）式的误差化为：第十五页，共六十二页，编辑于2023年，星期六

=2(Ruj－uj)=0,j=m+1，…,n

上式说明uj必须是R的特征向量。

（Re=λe）

这样，ε===

∴为了使ε最小，特征向量um+1，…，un

必须是对应最小特征值的，而近似x时所用的m个特征向量是对应m个最大特征值的。

使ε’取极值的必要条件是：+第十六页，共六十二页，编辑于2023年，星期六

上面推导出的特征还有其它意义上的最优性质。

一个分布的熵定义为H=-E[㏑p(y)]

粗略地说，当分布很平、延伸很广时，熵最大。如果x是零均值的高斯分布，那么可以证明所选择的特征向量具有最大熵。

这些特征向量沿最大方差方向，这样的方向是最随机的，最不确定的，这些方向应保留下来作为特征。对最不确定的事，若有信息（测量），最有用。

第十七页，共六十二页，编辑于2023年，星期六

例三维观测向量的特征提取

有一三维观测向量，其相关矩阵为

3-10

R=-130

0

03

它的特征值和特征向量为

λ1=4，λ2=3，λ3=2第十八页，共六十二页，编辑于2023年，星期六

1/0

1/

e1

=-1/e2

=0

e3

=1/

0

1

0

要选一个特征，应选e1方向，均方误差是λ2

+λ3

=5，

要选两个特征，应选e1

、e2方向，均方误差是λ3

=2.

第十九页，共六十二页，编辑于2023年，星期六表示模式的特征和用于分类的特征的不同

（1）

均值大小的影响

若均值较大，均值就会起大作用，特征在均值方向。

当两类问题的均值相差较大时，可以分类；但若均值差不多，则不会有好的效果。

m∵R=Σ+mmT第二十页，共六十二页，编辑于2023年，星期六

（2）也可以使用协方差矩阵，以均值为参考点，相对于均值。

（3）最好的表示特征不一定是最好的分类特征。

（3）有时可将坐标系移到一个类的均值处，这时相关矩阵的最大特征值的特征向量将沿两个均值的方向排列。

第二十一页，共六十二页，编辑于2023年，星期六*7.3多类问题的特征提取

下面介绍的方法是Fukunaga和Koontz在1970年提出的。

出发点是要同时考虑所有的类。

第二十二页，共六十二页，编辑于2023年，星期六1.

两类时的情况

令R1和R2分别是两类观测向量的相关矩阵。即Ri=Ei[xxT]，i=1，2

另Q=R1+R2

令S是一线性变换，使得

STQS=STR1S+STR2S=I(*)

(R1’+R2’

=I)

第二十三页，共六十二页，编辑于2023年，星期六

其中

↑↑↑1/

S=v1v2…vn

1/

↓↓↓…1/

vi和ui分别为Q的特征向量和特征值。

第二十四页，共六十二页，编辑于2023年，星期六

一般地说，S并不把R1和R2对角化，但通过S的线性变换，它把观测向量x变为：

x’=STx

变换后的相关矩阵为

Ri’=STRiS

由（*）式有R1’+R2’

=I

（**）

STQS=STR1S+STR2S=I第二十五页，共六十二页，编辑于2023年，星期六

现在考虑在变换后新坐标系下的特征。

首先，注意到R1’和R2’的特征向量是相同的。

∵假设e是R1’的一个特征向量，相应的特征值是λ，

由（**）式：

R2’

e=(I－R1’)e=e-λe=(1-λ)e

∴

e也是R2’的特征向量，相应的特征值是(1－λ)

R1’+R2’

=I第二十六页，共六十二页，编辑于2023年，星期六

由于相关矩阵的R1’

、R2’是半正定的，它们的特征值是非负的，

∴0≤λ≤1

这样，R1’的大特征值正好是R2’的小特征值，

R1’的小特征值正好是R2’的大特征值，

第二十七页，共六十二页，编辑于2023年，星期六这个关系如下图：

R1’λ1e1

1－λ1R2’

重λ2e21－λ2

要︰︰︰

性λn-1en-1

1－λn-1

减λnen1－λn

小

重要性减小

第二十八页，共六十二页，编辑于2023年，星期六

对类1是最好的表示方向，对类2是最坏的，反之亦然。

如何来选特征呢？有两种可能的方法。

1．每类各选m/2个最大特征值所对应的特征向量，当m是奇数时，再选一个不管哪类的最大特征值所对应的特征向量。

2．从两类的特征值中，不管哪一类，选最大的m个特征值所对应的特征向量。

一般地说，这两种方法谁好谁坏和具体问题有关。

第二十九页，共六十二页，编辑于2023年，星期六

一旦特征向量选好后，则特征变换由下式确定：

←ej1T

→

y=Tx=←ej2T

→STx，

：

←ej1T

→

其中S是满足STQS=I的矩阵。

第三十页，共六十二页，编辑于2023年，星期六*2.

C类时的情况

现在考虑将模式分为C类时的特征提取问题。

模式原来是用n维测量空间的向量x来表示的。每类的相关矩阵为Ri=Ei[xxT]

假定各个相关矩阵的最大特征值λmax≤1，这并不失一般性，可以通过调整线性空间的比例来实现。

又由于相关矩阵是半正定的，∴各Ri的特征值在0～1之间。

第三十一页，共六十二页，编辑于2023年，星期六

和前面一样，令{uj，j=1，2，…，n}是观测空间的标准正交基。另x是任一观测向量,x~是它的截尾表示形式，

x~=y1u1+y2u2+…+ymum

对于第i类，我们选择一组uj，它能使第i类的均方误差最小，

εi=Ei[|x-x~|2]=

（*）

第三十二页，共六十二页，编辑于2023年，星期六

而同时使其它类的均方误差最大。

εk

=Ek[|x-x~|2]=

(k=1，2，…，c，k≠i)(**)

单独使εi最小，而不管上式的条件已在前面讨论过。

若同时也满足（**）式的条件，将使得所选择的基能最优的表示第i类，但不能最优的表示其它类。

由于一般不能同时使εi最小，而εk最大，下面引入另外一个相关的准则。

第三十三页，共六十二页，编辑于2023年，星期六

和7.2节一样，可以表示

εk=，k=1，2，…，c

由于Ri是半正定的，且λmax≤1，

∴εk的大小为下式限定：

0≤

εk≤n-m，

k

=1，2，…,c

这样，使（**）式最大等价于使下式最小（k≠i）

(n－m)－εk

=

=

εk

=Ek[|x-x~|2]=(k=1，2，…，c，k≠i)(**)第三十四页，共六十二页，编辑于2023年，星期六

最大k（k≠i，k=1，2，…,c）和最小i的准则可以写成下面的组合形式，并用类数标准化。

Ci=

第三十五页，共六十二页，编辑于2023年，星期六

把i=和（n－m）－k的表达式代入，有

Ci=

式中，Gi=(*)

上式的准则在形式上和7.2节讨论的一样。

∴为了选取m个特征向量ui来表示x~,以使Ci最小，这时的特征向量应是Gi

的最大的m个特征值所对应的特征向量。

第三十六页，共六十二页，编辑于2023年，星期六

下面的分析说明确实是这样。假定e是Gi的标准特征向量，那么相应特征值λ可以表示为

λ=

eTGie

=

由于λmax≤1和相关矩阵的半正定性质，∴上式括号中每一个二次项的特征值在0～1之间，∴0≤λ≤1。

而且λ接近于1时要求eTRie→1,而eTRke(k≠i)却→0，第三十七页，共六十二页，编辑于2023年，星期六

这样，Gi的相应于特征值接近1的特征向量对应着i类最重要的特征。

当e=2时，（*）式变为

G1+G2=I

这和两类时的情况相似，G1

和G2

的特征向量相同，其特征值间的关系和变换后的矩阵R1’

、R2’时的一样。

第三十八页，共六十二页，编辑于2023年，星期六

当C＞2时，情况就复杂了。

上述的方法还可以进一步简化。

可以把相关矩阵进行变换，使它满足

==I

线性变换S的推导和上节一样。当使用变换后的相关矩阵时，

Gi简化为Gi’=1/c[2

Ri’

+(C－2)I]

当C=2时，Gi’=Ri’，和前面的结果相同。第三十九页，共六十二页，编辑于2023年，星期六7.4图像特征抽取的奇异值分解法

一幅图像可以表示为按一定顺序排列的像素的一个阵列（矩阵）。

假定阵列有N行N列，这时观测向量就由N2个像素的灰度值组成。由于观测向量的维数很大，我们希望用（抽取）图像的特征来表示图像。

第四十页，共六十二页，编辑于2023年，星期六

图像特征抽取的方法有许多种。例如从二维频率谱中抽取特征。

这一节我们讨论由一组基图像的加权和表示图像的方法，这种方法和前面讨论过的利用特征值的特征抽取的方法很相似。

第四十一页，共六十二页，编辑于2023年，星期六

假定图像是用一个N×N的矩阵B表示的，B的元素表示像素的灰度值。考虑两个N×N的标准正交矩阵U和V，矩阵B可以变换为另一矩阵A，

A=UTBV

由于U和V是标准正交的，所以信息并无损失。B可以通过下式（***）

B=UAVT=

式中aij

是A的元素，Ui、Vj

是U和V的列向量。

第四十二页，共六十二页，编辑于2023年，星期六

由于每一UiVjT都是一个N×N矩阵，所以上式可以看作B图像在一组基图像下的展开，而aij是展开时的系数。

特征抽取的思路是找一组基（图像），从而可以用少数n个系数aij来表示原图像。这时的图像B是上式的截尾形式。而aij即它的特征。Hadamard、Harr和Fourier变换都可以实现这一目的。第四十三页，共六十二页，编辑于2023年，星期六

下面要介绍的奇异值分解是另外一种方法。它使得矩阵A的元素只有对角线的元素非零。在这种基图像下，原图像只要用N个（或更少）的系数就可以表示了。

第四十四页，共六十二页，编辑于2023年，星期六

考虑下面的矩阵的积

BBT=UAVT.VATUT=UAATUT

容易证明，BBT是对称的和半正定的。因此它有N个非零的实特征值和N个线性独立的特征向量。

A=UTBVB=UAVT第四十五页，共六十二页，编辑于2023年，星期六

如果U的列向量取BBT的特征向量，则AAT是由BBT的特征值所形成的对角矩阵。为了下面分析的方便，将AAT表示为（*）

λ12

AAT

=λ22

…

λN2

同样，可以形成矩阵

BTB=VATUT.UAVT=VATAVT

第四十六页，共六十二页，编辑于2023年，星期六

如果V矩阵的列向量是BTB的列向量，则ATA必定有对角线形式

λ1’2

ATA

=λ2’2

（**）

…

λN’2

第四十七页，共六十二页，编辑于2023年，星期六

（*）和（**）能同时满足的条件是λi=λi’

。此时A是一对角矩阵，其对角线元素是λ1

，λ2

，…，λn

这时B化为

B

=

其中ui和vi分别是BBT和BTB的特征向量。而{λi}则由下式确定

λi=uiTBvi

i=1，2，…,N

{λi}称为B的奇异值。

第四十八页，共六十二页，编辑于2023年，星期六

上式可以用来计算图像B（或类似数据）的N个特征来表示B。另外，也可以选m(＜n)个最大的奇异值而放弃其余的奇异值。

当矩阵B不是方阵时，仍然可以进行奇异值分解。但奇异值的数目只能等于B的较小的维数。

第四十九页，共六十二页，编辑于2023年，星期六

当我们要把两类或更多的类进行分类时，所抽取的特征应该是最有效地保留了类的分离性。类的分离性准则和坐标系无关，而且和（信号）类的表示准则是完全不同的。*7.5用于分类的特征的提取第五十页，共六十二页，编辑于2023年，星期六

类的分离性准则不仅和类的分布有关，而且和所用的分类器有关。例如，对线性分类器最好的特征集，对其它类型的分类器就不一定是最好的特征集。

为了避免这种额外的复杂性，我们假定要找的最优的特征集是以贝叶斯分类器为基准的。

这样，类的可分性就等价于贝叶斯分类器的错误率。因此，从理论上说，贝叶斯错误率是特征的有效性的最好度量。

第五十一页，共六十二页，编辑于2023年，星期六

用贝叶斯错误率作为准则的一个主要缺点是较难得到它的数学表达式（除了少数特殊情况外）。在第三章我们曾经分析过，即使对正态分布，除了等协方差的情况外，贝叶斯错误率的计算也要用到数值积分。

第五十二页，共六十二页，编辑于2023年，星期六

下面将给出的几个准则都有很好的数学表达形式，它们是从物理概念中得到的。应当提醒的是，当提出一种准则时，这种准则的性能的分析都要和贝叶斯错误率联系起来。第五十三页，共六十二页，编辑于2023年，星期六一、分类特征提取时的一些问题

1．模式“表示”和模式“分类”的不同

模式分类特征的提取和模式表示特征的提取在许多方面是不同的，特别是所用的准则和所用的变换。

第五十四页，共六十二页，编辑于2023年，星期六

例如，在描述人类时，两眼、嘴、两只手、两条腿……但是在区别东方人和欧洲人时，这些特征毫无用途。

因此，用于分类的特征的有效性准则是用类的重叠和分离来度量的，而不是均方误差的拟合。