1、第二章 特征选择方法我们已经知道,在使用模式识别方法时,必须引入各种特征,即与分类有关的各种因素。特征的引入，通常要经过一个从少到多，又从多到少的过程。所谓从少到多，就是在设计识别方案的初期阶段应该尽量多地列举出各种可能与分类有关的特征。这样可以充分利用各种有用的信息，吸收各方面专家的经验，改善分类效果。这一步骤称为特征提取或特征抽取。但是，特征的无限增加对于分类也会带来不利的影响：（1） 特征的增加会给计算带来困难，过多的数据要占用大量的存储空间和计算时间；（2） 大量的特征中肯定会包含着许多彼此相关的因素，从而造成信息的重复和浪费；（3） 特征数是与样品点数有关的。当样品点数固定时，特征数
2、过多，会造成分类效果的恶化。例如，如果把 100 个样品点放在三维特征空间中，虽然难免会出现混淆或重复，它们总还可能分别形成一些类；而如果把它们放到 1000 维的空间中，就极可能出现样品点十分分散，无法找出规律。卡纳尔(Kanal, L.)提出：首先，如果想使误差估计值比较准确，样品个数N 必须不小于某个客观存在的界限。其次，如果希望得到对于误分概率的良好估计，样品数 N 与特征数 n 之比应该足够大；再次，如果 N 已经确定，那么当n 增加时，分类性能先是得到改善，但是当 n 达到某个最优值后，再增加 n，分类性能变坏。通常，样品数 N 应是特征数 n 的 5 倍到 10 倍左右。为了使特
3、征数目从多变少，需要进行所谓特征选择。特征选择通常包括两方面内容：一方面是对单个特征的选择，即对每个特征分别进行评价，从中找出那些对识别作用最大的特征。另一方面是从大量原有特征出发，构造少数有效的新特征。在模式识别中，最常用的特征选择方法是降维映射。本节要讲述的内容包括：对于单个特征的评价方法; 主成分分析及对应分析方法; 几种常用线性映射及其性质。2.1 对于单个特征的评价在本节中介绍几个对于单个特征进行评价的方法。评价每个特征的标准通常是它的分类能力。通过对于各个特征的评价，可以选出那些对于分类最有效的特征，淘汰那些无效的特征。2.1.1 K-W 检验K-W(Kruskal and Wal
4、lis)检验是一种常用的特征选择方法。假定要检验某个特征 x 对于分类的有效程度，已知一批样品共有 N 个，这批样品分为 m 类，第 i 类包括 Ni 个样品，N 1+N2+Nm=N，则检验方法如下：(1) 列出全部样品所对应的特征 x 的取值；(2) 按照 x 取值从小到大的顺序给每个样品编号。例如，x 取最小的样品编号为 1，x 取次小的样品编号为 2，等等。若有几个样品所对应的 x 值相同，可以对它们随机编号，也可以采用平均编号的办法。例如，假定前 5 号已经排出，而当前取值最小的样品有两个，则可以随机地把其中之一排为 6 号，另一个排为 7 号。也可以把这两个样品的编号都取做（6+7
5、）/2=6.5 ，而再下一个样品编号取作 8。(3) 取每类各样品编号的平均值，分别记作 。mR,21(4) 计算统计量 H，公式为(2-1)miiNRN12)()(2H 满足自由度为 m-1 的 分布。但是，在实用中一般只需比较各特征的2H 值。H 越大时，特征的分类能力越强。例 2-1 设有 N=10 个样品，共分 m=2 类，每个样品取 4 个特征。用 K-W检验比较特征的分类能力。原始资料矩阵见表 2-1。表 2-1 原始矩阵w1 w2X1 X2 X3 X4 X5 X6 X7 X8 X9 X10x1 0.36 0.41 0.20 0.18 0.27 0.54 0.52 0.68 0.4
6、9 0.81x2 0.10 0.20 0.30 0.40 2.50 0.60 0.70 0.80 0.90 0.50x3 0.10 0.32 0.54 0.78 0.91 0.22 0.46 0.62 0.87 0.99x4 0.21 0.35 0.36 0.40 0.69 0.61 0.72 0.75 0.84 0.85首先对 x1 将各样品按取值大小编号。X 4 所对应的 x1 值最小，编号为第 1号，X 3 编为第 2 号，全部编号结果列在表 2-2 的第一行中。于是对于 x1 有， 1R8则 H1=12/(10*11) 5*(3-11/2)2+5*(8-11/2)2=6.82对于 x2
7、 ，x 3，x 4 分别有 H2=2.45, H3=0.27, H4=5.77 。所以，特征 x1 的分类能力最强，x 4 次之，x 3 最差。表 2-2 对于各样品的重新编号X1 X2 X3 X4 X5 X6 X7 X8 X9 X10x1 4 5 2 1 3 8 7 9 6 10x2 1 2 3 4 10 6 7 8 9 5x3 1 3 5 7 9 2 4 6 8 10x4 1 2 3 4 6 5 7 8 9 10K-W 检验的原理是清楚的。首先，式中(N+1)/2 是全体样品编号的均值，而 是各类样品编号的均值，iR因此 H 相当于特征 x 对应编号的组间离差。其次，用编号代替特征 x 的
8、原有取值也是不难理解的。表 2-1 中，两类样品所对应的特征 x2 的原有取值的平均值都是 0.7，即两类均值完全相同，从这一事实来看，x 2 应该是一个很坏的特征。但是，用 x2 对样品进行分类时，如果取 0.4 和 0.5 之间的某个数作为分界点，被分错的只有一个点 X5。这又说明这个特征并不太坏。可见，这完全是由于 X5 点的 x2 值太大造成的。用编号代替特征值则可以排除这种干扰。2.1.2 直方图方法我们考虑例 2-1。特征 x1 的变化范围在 0.1 到 0.9 之间。我们把这一范围分成几个长度为 0.1 的区间,在每个区间内画出落在该区间内的样品点数与总点数之比(f)。这样的图形
9、称为特征值-样品频数直方图。x 1 和 x3 的直方图见图 2-1。在图 2-1 中，我们可以看到，在 x1 的直方图中，两类样品可以比较清楚地分开，而在特征 x3 的直方图中两类样品则有较多的混淆现象。因此，直方图可以作为检验特征分类能力的一种工具。f0.40.200.2 0.4 0.6 0.8 1.0 x1图 2-1（a ） x1 的直方图f0.40.200.2 0.4 0.6 0.8 1.0 x1图 2-1（b ） x3 的直方图从直方图出发可以构造可接受的运算特征（ROC）曲线。一个一般的直方图如图 2-2（ a）所示。任意取 x 轴上一点 t 作为分界点。第一类样品被判错部分的面积记
10、作 ，第二类被判错部分记作 。不断改变 t 的位置，并将点（ ,）1画在平面上，便形成图 2-2（b）中的 ROC 曲线。图中的面积 A 表示特征 x 的分类能力。A 越大，x 的分类能力越强。现在我们来做例 2-1 中特征 x4 的 ROC 曲线。使 t 从 x4=0.1 开始逐渐增加直到 x4=0.9，对应的 与 值记在表 2-3 中，ROC 曲线见图 2-2（c ） 。表 2-3 特征 x4 的 ROC 曲线计算步骤分界点 t 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9第一类判错个数 51.051.040.820.410.210.200.000.000.0第二
11、类判错个数00.000.000.000.000.000.010.230.651.0从直方图出发还可以设计另外的特征选择方法。例如，在图 2-1(a) 中，把t x2-2（a）1- A0 11 2-2（b）A0 112-2（c）图 2-2 ROC 曲线两类中互不混淆的部分分别记作 A1 和 A2。当有多个特征时，先从中挑选一个使 A1+A2 之值最大的特征，并且去掉那些可以用这个特征分开的样品，再从剩下的样品中挑选其他的特征。2.1.3 利用不确定性选择特征不确定性或熵是信息论中的概念。假定要考查某个特征 x 的分类能力。首先把 x 的取值范围分为 k 段，把样品点落到其中第 j 段的频率记作
12、P(bj)。又设样品共有 m 类，把第 i 类样品点落到第 j 段的频率记作 。然后计算熵：(jibp(2-2)(log)()1 jimkjmi jijbpA熵越小则 x 的分类能力越强。例 2-2 设有 40 个样品点共分两类，其中某特征 x 的变化范围在 0.20 到 0.90 之间。将这个范围分为两段，所得结果列在表 2-4 中。表 2-4 特征 x 之熵的计算步骤段号j变化范围 第一类样品数第二类样品数样品总数P(bj)1 0.20-0.59 14 4 18 18/40=0.452 0.60-0.90 6 16 22 22/40=0.55表 2-4(续 )段号j )(1jbp(2jbp
13、)(log12jbp)(log2jbp1 14/18=0.7778 4/18=0.2222 -0.3626 -2.17022 6/22=0.2727 16/22=0.7273 -1.8748 -0.4594由表 2-4,求出A=-(0.45*0.7778*(-0.3626)+0.2222*(-2.1702)+0.55*0.2727*(-1.8748)+0.7273*(-0.4594)=0.8089熵的原理可以用两个极端的例子说明。在上例中，若第一段中只有第一类样品，而第二段中只有第二类样品，则=1， =0， =0， =1)(1bp)(21bp)(12bp)(2bp=0， =0loglog最后，
14、A=0。另一方面，如果每段内的两类样品数都相等，则=0.5, i,j=1,2)(jibp, i,j=1,212/loglog2 ji最后得到 A=P(b1)+P(b2)=1。以上两种情形分别对应于 x 的分类能力最强和最弱两种状态。2.2 主成分分析和对应分析 在上一节中，我们介绍了评价单个特征分类能力的一些方法，利用这些方法可以挑出最有效的特征。但是，已经有人证明了以下事实：如果我们依次挑选出前 M 个最有效的单个特征，那么这 M 个特征放在一起却不一定是 M 个特征的最佳组合。例如：假定我们在诊断某种疾病时发现体温是最有效的特征，而白血球个数是下一个有效的特征，那么，由于体温与白血球个数之
15、间有着很密切的关系-相关性，因此这两个特征组合在一起实质上只相当于一个特征。从本节开始，我们讲述另外一些特征选择方法。它们的共同特点是：不再从原有的特征中进行选择和淘汰，而是用原有的各个特征去构造一批新特征。每个特征都是原有各特征的函数，但是新特征的总数应该少于原有特征总数。这样，我们的新特征集合既保留了原有各特征的主要信息，又达到了减少特征维数，即降低空间维数的目的。这一类方法可以统称为降维方法。2.2.1 主成分分析1、基本概念现在来考虑更一般的情况。假定对每个样品取 n 个特征，即 X=(x1,x2,xn)T。要求构造 n 个新特征 y1,y2,yn，并使它们满足以下的条件：1） 每个新
16、特征是原有各特征的线性组合，即yi=ui1x1+ui2x2+uinxn, i=1,2,n,或i=1,2,n (2-3),),(,21TiniiTii uuX其中各 是常数。iju2） 各个新变量之间是不相关的，即相关系数为零：, i=1,2,n; (2-4)0),(jiyrji3） 使 的方差达到极大， 使 的方差达到次大，等等。1u2uy满足以上条件的新特征 y1,y2,yn 分别称为样品点的第 1,2,n 个主成分。下面讨论怎样求出各个 yi，或者说怎样求出各个 ui。首先求出全体样品点的协方差矩阵nnnxssssS 212112这里 S 的下标 x 表示这是对应于旧特征 x1,x2,xn
17、 的协方差矩阵。然后，求出Sx 的 n 个特征值 和与之对应的特征向量 u1,u2,un。每个 是一个数，n,21 i而与之对应的特征向量 是一个列向量 ui=(ui1,ui2,uin)T，它们之间的关系是iu，i=1,2,n (2-5)iixS因此，求 和 相当于解以上方程。具体的解法请参见计算方法（如雅可比方法） 。ii如果我们在解方程时还要求正交归一条件 jinjiujTi ;,21,0(2-6)i,成立，则各个 就是唯一确定的。iu现在我们来说明,，用以上方法所求出的各个 就可以满足前面所说的条件（1）-（3） 。iu令 ，即niXyTii ,21, nnnn xuuy 2121122
18、1或Y=UX （2-7 ）于是 y1,y2,yn 就是由 x1,x2,xn 经线性变换而得到的新特征。可以证明，当经过上述形式的线性变换后，如果对应于 X 的的协方差矩阵是 Sx，那么对应于Y 的协方差矩阵就是 Sy=USxUT (2-8)注意到 UT 的每列恰好是 Sx 的一个特征向量，并利用条件（2-5） ，得到TnTx U0021其中是以 为主对角线元素的对角阵。再利用正交归一化条件（2-6 ） ，又可n,21以得到Sy=USxUT= UUT= （2-9）这就是说：新特征 y1,y2,yn 两两之间的协方差为零，即它们是不相关的。这样，我们就找到解决主成分分析问题的关键，即求原始协方差矩
19、阵的特征值和特征向量。讨论：主成分分析三条件的作用。条件（1）是线性条件。它反映新老特征之间的关系是简单的，便于计算；条件（2）是不相关性。它要求每个特征都有着独立的作用；条件（3）是方差极大条件。每个特征的方差数值在一定意义下反应了它所包含的信息量。当前几个新特征的信息量足够大时，便可以舍弃其余的新特征，从而达到减少特征个数的目的。2、计算步骤假定原始资料矩阵已知，则计算步骤如下：（1） 根据公式，计算原有特征的协方差矩阵 Sx。（2） 用任意一种计算方法求出 Sx 的全部特征值 和对应的特征n,21向量 u1,u2,un。并将各特征值按从小到大的顺序排列（2-10 ）n21特征向量也应按照
20、对应特征值的顺序排列。由前面的推导我们知道：新特征与旧特征的特征值相同。这时已经可以求出 n 个新特征 y1,y2,yn，它们满足条件 Y=UX。其特征值亦为.n,21（3） 我们定义第 i 个主成分 yi 的“方差贡献率”为（2-11 ）)/(21ni 前 m 个主成分 y1,y2,ym 的“累计方差贡献率”为（12）)/()(212 nm当前 m 个主成分的累计方差贡献率已经足够大时（ 70%，80%或者更大） ，就可以只取前 m 个主成分作为新的特征，这时有（2-13）nmmnxuuy 21211221其后的 n-m 个新特征可以舍去。主成分分析的计算到这里本来已经完成了，下面是两点补充
21、。我们称第 k 个新特征 yk 与第 i 个旧特征 xi 之间的相关系数 为 xi 在),(ikyyk 上的 “因子负荷量” ，计算公式为（2-14）nkisuxykiik ,21,/),( 求出全体 并作出因子负荷量矩阵：),(ik ),(),(),( , )()()(21 22 1121 nnn nxyxy 这个矩阵有以下两点特点：1）每行元素平方之和为 1。2）第 k 列各元素平方再乘以对应原有元素方差之和为 ， 即kkni ikxys12),(由此出发，也可以定义前 m 个主成分对原有变量 xi 的累计贡献率为mkikiki suy1212)( /),(当 足够大时，可以认为前 m 个
22、主成分 y1,y2,ym 已经包含了 xi 中的主要信)(mi息量。例 2-3 假设有一批样品，样品数为 N=4，特征数为 n=2，样品的原始资料矩阵见表 2-5。表 2-5 样品的原始资料矩阵X1 X2 X3 X4x1 1 -1 2 -2x2 1 -1 2 -2（1）首先计算样品的协方差矩阵，结果为， 3/10xS（2）计算特征值和特征向量，得到， ，/12,)/1,(Tu;)2/1,(2Tu（3）则对于样品利用主成分分析所得到的新特征是2121/xy即 ，21x2/1xy这一公式表示新特征即主成分所对应的坐标系相当于将原坐标系旋转 45 度而得，见图 2-3（a） 。下面计算主成分的累计方
23、差贡献率。， ，%10)/(21%0.)/(212即只用第一主成分已可包含了原数据的全部信息。这一点是显而易见的，因为全部 4 个点都分布在 y1 轴上。例 2-4 同上，假设有一批样品，样品数为 N=4，特征数为 n=2，样品的原始资料矩阵见表 2-6。表 2-6 两批样品的原始资料矩阵X1 X2 X3 X4x1 1 -1 2 -2x2 -1 1 2 -2计算方法同上：（1）首先计算样品的协方差矩阵，结果为， 3/102xS（2）计算特征值和特征向量，得到，/61,/42,),(Tu ;)2/1,(Tu（3）则利用主成分分析所得到的新特征是2121/xy(a) A-2 -1 1 2-221-1x1x2y1y2(b) B-2 -1 2-221 -1 x1x2 y1y2 1图 2-3 主成分分析的几何解释
