第6章特征提取与选择模式识别的主要任务是设计分类器，将样本划分为相应的类别，获得好的分类性能。而前面章节讨论的分类器设计方法，都是认为样本的特征已经确定，各类样本都分布在由该特征所决定的空间内。因此分类器设计问题是一个使用什么方法，将已确定的特征空间合理划分的问题。分类器设计方法固然重要，但样本的特征选择与提取也是模式识别系统的一个关键的问题。好的特征可以使同类样本的分布更具加紧密，不同类别样本则在该特征空间中更加分开，这就为分类器设计奠定了良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。本章要讨论的问题就是给定训练样本集，如何设计特征空间的问题。6.1 类别可分性判据特征选择与提取的实质是要对原始特征空间进行优化，这就需要对优化的结果进行评价，在实际应用中经常采用的评价方法，是对分类系统的性能进行测试，最直接的测试指标当然是识别率，其它指标还有识别计算速度、存储容量等。本章讨论的评价方法目的在于找出对特征空间进行优化的具体算法。对特征空间进行优化的任务是求出一组对分类最有效的特征，所谓有效是指在特征维数减少到同等水平时，其分类性能达到最优。因此需要设计出定量分析方法，判断所得到的特征或所选取的特征维数是否对分类最有利，这种用以定量检验分类性能的准则称为类别可分离性判据。一般说来分类器最基本的性能评估是其分类的错误率，如果能用反映错误率大小的准则，在理论上是最合适的。但是正如在前述章节讨论中提到的，对错误率的计算是极其复杂的，以至于很难构筑直接基于错误率的判据。为此人们设法从另一些更直观的方法出发，设计出一些类别可分离性判据的准则，用来检验不同的特征组合对分类性能好坏的影响，进而导出特征选择与特征提取的方法。通常希望所构造的可分性判据满足下列要求：（1）与误判概率有单调关系。(2）当模式的特征独立时，判据有可加性，即J,(X,X2,",Xa)=ZJ,(X)k=l（3）判据具有距离的某些特性，即[J,>0,ijJ,=0,i=j[J,=Jj
第 6 章 特征提取与选择 模式识别的主要任务是设计分类器，将样本划分为相应的类别，获得好的分类性能。而 前面章节讨论的分类器设计方法，都是认为样本的特征已经确定，各类样本都分布在由该特 征所决定的空间内。因此分类器设计问题是一个使用什么方法，将已确定的特征空间合理划 分的问题。分类器设计方法固然重要，但样本的特征选择与提取也是模式识别系统的一个关 键的问题。好的特征可以使同类样本的分布更具加紧密，不同类别样本则在该特征空间中更 加分开，这就为分类器设计奠定了良好的基础。反之，如果不同类别的样本在该特征空间中 混杂在一起，再好的设计方法也无法提高分类器的准确性。本章要讨论的问题就是给定训练 样本集，如何设计特征空间的问题。 6.1 类别可分性判据 特征选择与提取的实质是要对原始特征空间进行优化，这就需要对优化的结果进行评 价，在实际应用中经常采用的评价方法，是对分类系统的性能进行测试，最直接的测试指标 当然是识别率，其它指标还有识别计算速度、存储容量等。本章讨论的评价方法目的在于找 出对特征空间进行优化的具体算法。 对特征空间进行优化的任务是求出一组对分类最有效的特征，所谓有效是指在特征维 数减少到同等水平时，其分类性能达到最优。因此需要设计出定量分析方法，判断所得到的 特征或所选取的特征维数是否对分类最有利，这种用以定量检验分类性能的准则称为类别可 分离性判据。 一般说来分类器最基本的性能评估是其分类的错误率，如果能用反映错误率大小的准 则，在理论上是最合适的。但是正如在前述章节讨论中提到的，对错误率的计算是极其复杂 的，以至于很难构筑直接基于错误率的判据。为此人们设法从另一些更直观的方法出发，设 计出一些类别可分离性判据的准则，用来检验不同的特征组合对分类性能好坏的影响，进而 导出特征选择与特征提取的方法。通常希望所构造的可分性判据满足下列要求： （1） 与误判概率有单调关系。 （2） 当模式的特征独立时，判据有可加性，即 1 2 1 ( , , , ) ( ) d ij d ij k k J X X X J X （3） 判据具有距离的某些特性，即 0, 0, ij ij ij ji J i j J i j J J
（4）对特征数目是单调不减的，即J,(Xi,X2,",Xa)≤J,(Xr,X2,"",Xa,Xa+)在实际应用，有些判据并不一定同时能满足上述四个条件，但并不影响其使用。6.2.基于距离的可分性判据基于距离的可分性判据的实质是Fisher准则的延伸，即同时考虑样本的类内聚集程度与类间的离散程度这两个因素。这种判据对特征空间优化的结果较好地体现类内密集、类间分离的目的，也就是说，一些不能体现类间分隔开的特征在对特征空间进行优化的过程中很可能被剔除了。基于距离度量在几何上具有直观性，因为一般情况下同类样本在特征空间呈聚类状态，即从总体上说同类样本由于具有共性，因此类内样本间距离应比类间样本间距离小。Fisher准则正是以使类间距离尽可能大同时又保持类内距离较小这一思想设计的。同样在特征选择与特征提取中也使用类似的思想，称为基于距离的可分性判据。为了度量类内、类间的距离，也可用另一种描述方法，即描述样本的离散程度的方法。在讨论Fisher准则时曾用过两个描述离散度的矩阵。一个是类间离散矩阵S，，即S,=(m-m2)(m-m)(6-1)另一个是类内离散度矩阵S，有(6-2)S=S,+S其中, S=Z(X-m)(X-m),i=1,2XeN以上式子是针对两类别情况的，如果推广至类情况，同时考虑各类的先验概率P不相等，则可将上列各式表示成S,=Zp(m-m)(m-m)(6-3)i=lS. =ZPE,[(X-m,)(X-m)"(6-4)i=l其中，m为所有样本的总均值向量，E,表示i类的期望符号。利用(6-3)与(6-4)式可以将基于距离的可分性判据表示如下几种形式。（1）特征向量间平均距离的判据J(X)= tr(Sw + S,)(6-5)其中，“tr”表示矩阵的迹。式（6-5)实际上是从计算特征向量间总平均距离的公式推导得到的，该式可写成
（4） 对特征数目是单调不减的，即 1 2 1 2 1 ( , , , ) ( , , , , ) ij d ij d d J X X X J X X X X 在实际应用，有些判据并不一定同时能满足上述四个条件，但并不影响其使用。 6.2.基于距离的可分性判据 基于距离的可分性判据的实质是 Fisher 准则的延伸，即同时考虑样本的类内聚集程度 与类间的离散程度这两个因素。这种判据对特征空间优化的结果较好地体现类内密集、类间 分离的目的，也就是说，一些不能体现类间分隔开的特征在对特征空间进行优化的过程中很 可能被剔除了。 基于距离度量在几何上具有直观性，因为一般情况下同类样本在特征空间呈聚类状态， 即从总体上说同类样本由于具有共性，因此类内样本间距离应比类间样本间距离小。Fisher 准则正是以使类间距离尽可能大同时又保持类内距离较小这一思想设计的。同样在特征选择 与特征提取中也使用类似的思想，称为基于距离的可分性判据。 为了度量类内、类间的距离，也可用另一种描述方法，即描述样本的离散程度的方法。 在讨论 Fisher 准则时曾用过两个描述离散度的矩阵。一个是类间离散矩阵 b S ，即 1 2 1 2 T b S m m m m (6-1) 另一个是类内离散度矩阵 w S ，有 w 1 2 S S S (6-2) 其中， , 1,2 T w i i X S X m X m i 以上式子是针对两类别情况的，如果推广至 c 类情况，同时考虑各类的先验概率 Pi 不 相等，则可将上列各式表示成 1 c T b i i i i S P m m m m (6-3) 1 c T w i i i i i S PE X m X m (6-4) 其中，m 为所有样本的总均值向量， Ei 表示 i 类的期望符号。利用(6-3)与(6-4)式可以将基 于距离的可分性判据表示如下几种形式。 （1） 特征向量间平均距离的判据 1 ( ) tr( ) w b J X S S (6-5) 其中，“ tr ”表示矩阵的迹。式(6-5)实际上是从计算特征向量间总平均距离的公式推导得 到的，该式可写成
8(x,x)Ja(X)= 1(6-6)22台nn,台台其中，P、P,分别表示各类的先验概率n,、n,分别是第i与j类的样本个数，s(xl),x(")表示第i类的第k个与j类第1个样本之间的距离度量，在欧氏距离情况下有8(x0,x()=(x()-x() (x) -X()(6-7)分别用m和m表示第i类样本的均值向量与总体样本的均值向量，有12xO(6-8)m.=n,=im=ZPm(6-9)1=1将式（6-8）和式（6-9）代入式(6-6)，得P[12(x@ -m) (x@ -m,)+(m-m) (m,-m)Ja(X)=pl(6-10)nhi=l式（6-10)中右边括弧里的第一项为类内各特征向量之间的平方距离，第二项为第i类的均值向量与总体均值向量之羊的平方距离，第二项可表示为Zp(m-m)(m-m)=ZP(m,-m)(m,-m)(6-11)2台月i=l显然，利用式(6-10)与式(6-11)就可得到式(6-5)。需指出的是由(6-6)推导的各式是利用有限样本数据，因此得到的都是母体各量的估计值，而（6-5)式用的是母体的离散度矩阵。（2）类内类间距离的判据判据J.（X）是建立在计算特征向量的总平均距离基础上的一种距离度量，直观上我们希望变换后特征向量的类间离散度尽量大，类内离散度尽量小，因此还可以提出以下各种实用的判据。(6-12)J,(X)= tr(S-'S.)[Is,] J(X)=In(6-13)LIs,1]tr(S,)J(X) =(6-14)tr(S,)
( ) ( ) 1 1 1 1 1 1 ( ) , 2 j i n n c c i j d i j k l i j k l i j J X P P X X n n (6-6) 其中，Pi 、Pj 分别表示各类的先验概率 i n 、 j n 分别是第 i 与 j 类的样本个数， ( ) ( ) , i j X X k l 表示第 i 类的第 k 个与 j 类第 l 个样本之间的距离度量，在欧氏距离情况下有 ( ) ( ) ( ) ( ) ( ) ( ) , T i j i j i j X X X X X X k l k l k l (6-7) 分别用 mi 和 m 表示第 i 类样本的均值向量与总体样本的均值向量，有 (i) 1 1 i n i k i k m X n (6-8) 1 c i i i m Pm (6-9) 将式（6-8）和式（6-9）代入式(6-6)，得 (i) (i) 1 1 1 ( ) i c n T T d i k i k i i i i k i J X P X m X m m m m m n (6-10) 式(6-10)中右边括弧里的第一项为类内各特征向量之间的平方距离，第二项为第 i 类的 均值向量与总体均值向量之羊的平方距离，第二项可表示为 1 1 1 1 2 c c c T T i i i i j i j i j i i j P m m m m P P m m m m (6-11) 显然，利用式(6-10)与式(6-11)就可得到式(6-5)。需指出的是由(6-6)推导的各式是利用有 限样本数据，因此得到的都是母体各量的估计值，而(6-5)式用的是母体的离散度矩阵。 （2） 类内类间距离的判据 判据 1 J X( ) 是建立在计算特征向量的总平均距离基础上的一种距离度量，直观上我们 希望变换后特征向量的类间离散度尽量大，类内离散度尽量小，因此还可以提出以下各种实 用的判据。 1 2 ( ) tr( ) w b J X S S (6-12) 3 ( ) ln b w S J X S (6-13) 4 tr(S ) ( ) tr(S ) b w J X (6-14)
IS,+S,Js(X)=(6-15)Sw其中，表示是矩阵对应的行列式。由上述判据的构造可知，当类模内模式比较密集，类间模式比较分散时，此时所得判据值也较大，分类就更加容易。6.3按概率距离判据的特征提取方法上一节依据样本在特征空间的分布距离，建立了特征提取的判据。这种判据原则具有思路直观、计算简便的优点，其缺点是没有考虑各类样本的概率分布。因此当不同类样本中有部分在特征空间中交选分布时，简单地按距离划分，无法表明判据与错误概率之间的联系。基于概率分布的可分性判据则依据如下观察到的现象。如果我们不考虑各类的先验概率，或假设两类样本的先验概率相等，那末从两类条件概率分布可以看出，如果两类条件概率分布互不交迭，即对P(Xの)处都有P(Xの)，如图6-1（a）所示，则这两类就完全可分：另一种极端情况是对所有X都有P(Xの）=P(Xの），如图6-1(b)所示，则两类就完全不可分。P(x/w)P(x/w.)P(x/ w2)(a)(b)图6-1两类样本的条件概率密度分布因此人们设计出与概率分布交迭程度有关的距离度量方法，这些距离J，有以下几个共同点：（1）J,是非负，即J,≥0（2）当两类完全不交选时J，达到其最大值（3）当两类分布密度相同时，J，=0这种函数的一般式可表示为J = Jg[p(X|), p(X|o), P, P2](6-16)下面讨论一些常用的概率距离度量。（1）Bhattacharya距离和Chermoff界限Bhattacharyya距离的定义为Js=-In J[p(X|)p(Xo,)]" dx(6-17)
5 ( ) w b w S S J X S (6-15) 其中， 表示是矩阵对应的行列式。由上述判据的构造可知，当类模内模式比较密集，类 间模式比较分散时，此时所得判据值也较大，分类就更加容易。 6.3 按概率距离判据的特征提取方法 上一节依据样本在特征空间的分布距离，建立了特征提取的判据。这种判据原则具有 思路直观、计算简便的优点，其缺点是没有考虑各类样本的概率分布。因此当不同类样本中 有部分在特征空间中交迭分布时，简单地按距离划分，无法表明判据与错误概率之间的联系。 基于概率分布的可分性判据则依据如下观察到的现象。 如果我们不考虑各类的先验概率，或假设两类样本的先验概率相等，那末从两类条件 概率分布可以看出，如果两类条件概率分布互不交迭，即对 2 P X( ) 处都有 1 P X( ) ，如 图 6-1(a) 所 示 ， 则 这 两 类 就 完 全 可 分 ； 另 一 种 极 端 情 况 是 对 所 有 X 都 有 1 2 P X P X ( ) ( ) ，如图 6-1(b)所示，则两类就完全不可分。 P x w | 1 P x w | 2 P x w | 1 (a) (b) 图 6-1 两类样本的条件概率密度分布 因此人们设计出与概率分布交迭程度有关的距离度量方法，这些距离 p J 有以下几个共 同点： （1） p J 是非负，即 0 p J （2）当两类完全不交迭时 p J 达到其最大值 （3）当两类分布密度相同时， 0 p J 这种函数的一般式可表示为 1 1 1 2 J g p X p X p p ( ), ( ), , (6-16) 下面讨论一些常用的概率距离度量。 (1) Bhattacharyya 距离和 Chernoff 界限 Bhattacharyya 距离的定义为 1/2 1 2 ln ( ) ( ) B J p X p X dX (6-17)
由式（6-17）可以看出，当P(Xの）=P(Xの）对所有X值成立时JB=0，而当两类的分布完全不交选时JB为无穷大。Chernoff界限的定义为J=-In J[p'(X|)p-s(Xo2) dX(6-18)其中，S取[0，1]区间的一个参数，当S=0.5时式(6-18)即为式(6-17)，因此JB是J的一个特例。(2）散度另一种常用的基于概率距离度量的判据是利用似然比或对数似然比。对两类问题，其对数似然比为I, =In P(Xla)(6-19)p(X|o,)如果对某个X，P(Xo)=P(Xの,)，则1,=0，反之若两者差异越大，则1,的绝对值也大。式(6-19)只是对某一X值而言，为了对整个特征空间概率分布的差异程度做出评价，0类相对の,的可分性信息定义为1,=[;()]-[ p(X(a)n le) ax(6-20)p(X|o,)の,类相对の,的可分性信息定义为1,=[()]-[ p(X(0,)In (l) ax(6-21)p(X0,)N而总的平均可分信息则可表示成J=I,+,=J[p(X(a)-(X[)]in)ax(6-22)p(X0,)J，被称为散度，从其数学构造上来看，式中被积函数概率密度之差和概率密度之比能反映出两个类样本分布的重叠程度，同时被积函数中两因式永远同号，故其乘积非负。有关散度的具体含意将结合正态分布的例子说明。（3）正态分布时基于概率分布距离度量显然在一般情况下由于概率分布本身的复杂形式，以上这些基于概率分布的判据相当复杂。但当模式的概率分布具有某种特定参数形式，尤其是呈正态分布时，判据的表达式可以得到进一步简化。下面讨论两类别正态分布时散度判据的表达式。设两类的概率密度函数为
由式（6-17）可以看出，当 1 2 P X P X ( ) ( ) 对所有 X 值成立时 0 B J ，而当两 类的分布完全不交迭时 B J 为无穷大。 Chernoff 界限的定义为 1 1 2 ln ( ) ( ) s S C J p X p X dX (6-18) 其中， S 取[0，1]区间的一个参数，当 S 0.5 时式(6-18)即为式(6-17)，因此 B J 是 C J 的一 个特例。 (2) 散度 另一种常用的基于概率距离度量的判据是利用似然比或对数似然比。对两类问题，其对 数似然比为 ( ) ln ( ) i ij j p X l p X (6-19) 如果对某个 X ， ( ) ( ) P X P X i j ，则 0 ij l ，反之若两者差异越大，则 ij l 的绝对值也 大。式(6-19)只是对某一 X 值而言，为了对整个特征空间概率分布的差异程度做出评价， i 类相对 j 的可分性信息定义为 ( ) (X) ( )ln ( ) i ij ij i j p X I E l p X dX p X (6-20) j 类相对 i 的可分性信息定义为 ( ) (X) ( )ln ( ) j ji ji j i p X I E l p X dX p X (6-21) 而总的平均可分信息则可表示成 ( ) ( ) ( ) ln ( ) i D ij ji i j j p X J I I p X p X dX p X (6-22) D J 被称为散度，从其数学构造上来看，式中被积函数概率密度之差和概率密度之比能反映 出两个类样本分布的重叠程度，同时被积函数中两因式永远同号，故其乘积非负。有关散度 的具体含意将结合正态分布的例子说明。 (3) 正态分布时基于概率分布距离度量 显然在一般情况下由于概率分布本身的复杂形式，以上这些基于概率分布的判据相当复 杂。但当模式的概率分布具有某种特定参数形式，尤其是呈正态分布时，判据的表达式可以 得到进一步简化。下面讨论两类别正态分布时散度判据的表达式。 设两类的概率密度函数为