模式识别 第二章 特征选择方法.doc

第二章 特征选择方法我们已经知道,在使用模式识别方法时,必须引入各种特征,即与分类有关的各种因素。特征的引入，通常要经过一个从少到多，又从多到少的过程。所谓从少到多，就是在设计识别方案的初期阶段应该尽量多地列举出各种可能与分类有关的特征。这样可以充分利用各种有用的信息，吸收各方面专家的经验，改善分类效果。这一步骤称为特征提取或特征抽取。但是，特征的无限增加对于分类也会带来不利的影响：（1） 特征的增加会给计算带来困难，过多的数据要占用大量的存储空间和计算时间；（2） 大量的特征中肯定会包含着许多彼此相关的因素，从而造成信息的重复和浪费；（3） 特征数是与样品点数有关的。当样品点数固定时，特征数过多，会造成分类效果的恶化。例如，如果把100个样品点放在三维特征空间中，虽然难免会出现混淆或重复，它们总还可能分别形成一些类；而如果把它们放到1000维的空间中，就极可能出现样品点十分分散，无法找出规律。卡纳尔(Kanal, L.)提出：首先，如果想使误差估计值比较准确，样品个数N必须不小于某个客观存在的界限。其次，如果希望得到对于误分概率的良好估计，样品数N与特征数n之比应该足够大；再次，如果N已经确定，那么当n增加时，分类性能先是得到改善，但是当n达到某个最优值后，再增加n，分类性能变坏。通常，样品数N应是特征数n的5倍到10倍左右。为了使特征数目从多变少，需要进行所谓特征选择。特征选择通常包括两方面内容：一方面是对单个特征的选择，即对每个特征分别进行评价，从中找出那些对识别作用最大的特征。另一方面是从大量原有特征出发，构造少数有效的新特征。在模式识别中，最常用的特征选择方法是降维映射。本节要讲述的内容包括：对于单个特征的评价方法; 主成分分析及对应分析方法; 几种常用线性映射及其性质。2.1 对于单个特征的评价在本节中介绍几个对于单个特征进行评价的方法。评价每个特征的标准通常是它的分类能力。通过对于各个特征的评价，可以选出那些对于分类最有效的特征，淘汰那些无效的特征。2.1.1 K-W检验K-W(Kruskal and Wallis)检验是一种常用的特征选择方法。假定要检验某个特征x对于分类的有效程度，已知一批样品共有N个，这批样品分为m类，第i类包括Ni个样品，N1+N2+Nm=N，则检验方法如下：(1) 列出全部样品所对应的特征x的取值；(2) 按照x取值从小到大的顺序给每个样品编号。例如，x取最小的样品编号为1，x取次小的样品编号为2，等等。若有几个样品所对应的x值相同，可以对它们随机编号，也可以采用平均编号的办法。例如，假定前5号已经排出，而当前取值最小的样品有两个，则可以随机地把其中之一排为6号，另一个排为7号。也可以把这两个样品的编号都取做（6+7）/2=6.5，而再下一个样品编号取作8。(3) 取每类各样品编号的平均值，分别记作。(4) 计算统计量H，公式为 (2-1)H满足自由度为m-1的分布。但是，在实用中一般只需比较各特征的H值。H越大时，特征的分类能力越强。例2-1 设有N=10个样品，共分m=2类，每个样品取4个特征。用K-W检验比较特征的分类能力。原始资料矩阵见表2-1。表2-1 原始矩阵w1w2X1X2X3X4X5X6X7X8X9X10x10.360.410.200.180.270.540.520.680.490.81x20.100.200.300.402.500.600.700.800.900.50x30.100.320.540.780.910.220.460.620.870.99x40.210.350.360.400.690.610.720.750.840.85首先对x1将各样品按取值大小编号。X4所对应的x1值最小，编号为第1号，X3编为第2号，全部编号结果列在表2-2的第一行中。于是对于x1有， 则H1=12/(10*11) 5*(3-11/2)2+5*(8-11/2)2=6.82对于x2 ，x3，x4分别有H2=2.45, H3=0.27, H4=5.77 。所以，特征x1的分类能力最强，x4次之，x3最差。表2-2 对于各样品的重新编号X1X2X3X4X5X6X7X8X9X10x145213879610x212341067895x313579246810x412346578910K-W检验的原理是清楚的。首先，式中(N+1)/2是全体样品编号的均值，而是各类样品编号的均值，因此H相当于特征x对应编号的组间离差。其次，用编号代替特征x的原有取值也是不难理解的。表2-1中，两类样品所对应的特征x2的原有取值的平均值都是0.7，即两类均值完全相同，从这一事实来看，x2应该是一个很坏的特征。但是，用x2对样品进行分类时，如果取0.4和0.5之间的某个数作为分界点，被分错的只有一个点X5。这又说明这个特征并不太坏。可见，这完全是由于X5点的x2值太大造成的。用编号代替特征值则可以排除这种干扰。2.1.2 直方图方法我们考虑例2-1。特征x1的变化范围在0.1到0.9之间。我们把这一范围分成几个长度为0.1的区间,在每个区间内画出落在该区间内的样品点数与总点数之比(f)。这样的图形称为特征值-样品频数直方图。x1和x3的直方图见图2-1。在图2-1中，我们可以看到，在x1的直方图中，两类样品可以比较清楚地分开，而在特征x3的直方图中两类样品则有较多的混淆现象。因此，直方图可以作为检验特征分类能力的一种工具。f0.40.200.20.40.60.81.0x1图2-1（a ） x1 的直方图f0.40.200.20.40.60.81.0x1图2-1（b ） x3 的直方图从直方图出发可以构造可接受的运算特征（ROC）曲线。一个一般的直方图如图2-2（a）所示。任意取x轴上一点t作为分界点。第一类样品被判错部分的面积记作，第二类被判错部分记作。不断改变t的位置，并将点（,）画在平面上，便形成图2-2（b）中的ROC曲线。图中的面积A表示特征x的分类能力。A越大，x的分类能力越强。tx2-2（a）A0112-2（c）1-A0112-2（b）图2-2 ROC曲线现在我们来做例2-1中特征x4的ROC曲线。使t从x4=0.1开始逐渐增加直到x4=0.9，对应的与值记在表2-3中，ROC曲线见图2-2（c）。表2-3 特征x4的ROC曲线计算步骤分界点t0.10.20.30.40.50.60.70.80.9第一类判错个数51.051.040.820.410.210.200.000.000.0第二类判错个数00.000.000.000.000.000.010.230.651.0从直方图出发还可以设计另外的特征选择方法。例如，在图2-1(a) 中，把两类中互不混淆的部分分别记作A1和A2。当有多个特征时，先从中挑选一个使A1+A2之值最大的特征，并且去掉那些可以用这个特征分开的样品，再从剩下的样品中挑选其他的特征。2.1.3 利用不确定性选择特征不确定性或熵是信息论中的概念。假定要考查某个特征x的分类能力。首先把x的取值范围分为k段，把样品点落到其中第j段的频率记作P(bj)。又设样品共有m类，把第i类样品点落到第j段的频率记作。然后计算熵： (2-2)熵越小则x的分类能力越强。例2-2 设有40个样品点共分两类，其中某特征x的变化范围在0.20到0.90之间。将这个范围分为两段，所得结果列在表2-4中。表2-4 特征x之熵的计算步骤段号j变化范围第一类样品数第二类样品数样品总数P(bj)10.20-0.591441818/40=0.4520.60-0.906162222/40=0.55表2-4(续)段号j114/18=0.77784/18=0.2222-0.3626-2.170226/22=0.272716/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=0， =0最后，A=0。另一方面，如果每段内的两类样品数都相等，则=0.5, i,j=1,2, i,j=1,2最后得到A=P(b1)+P(b2)=1。以上两种情形分别对应于x的分类能力最强和最弱两种状态。2.2 主成分分析和对应分析 在上一节中，我们介绍了评价单个特征分类能力的一些方法，利用这些方法可以挑出最有效的特征。但是，已经有人证明了以下事实：如果我们依次挑选出前M个最有效的单个特征，那么这M个特征放在一起却不一定是M个特征的最佳组合。例如：假定我们在诊断某种疾病时发现体温是最有效的特征，而白血球个数是下一个有效的特征，那么，由于体温与白血球个数之间有着很密切的关系-相关性，因此这两个特征组合在一起实质上只相当于一个特征。从本节开始，我们讲述另外一些特征选择方法。它们的共同特点是：不再从原有的特征中进行选择和淘汰，而是用原有的各个特征去构造一批新特征。每个特征都是原有各特征的函数，但是新特征的总数应该少于原有特征总数。这样，我们的新特征集合既保留了原有各特征的主要信息，又达到了减少特征维数，即降低空间维数的目的。这一类方法可以统称为降维方法。2.2.1 主成分分析1、基本概念现在来考虑更一般的情况。假定对每个样品取n个特征，即X=(x1,x2,xn)T。要求构造n个新特征y1,y2,yn，并使它们满足以下的条件：1） 每个新特征是原有各特征的线性组合，即yi=ui1x1+ui2x2+uinxn, i=1,2,n,或 i=1,2,n (2-3)其中各是常数。2） 各个新变量之间是不相关的，即相关系数为零：, i=1,2,n; (2-4)3） 使的方差达到极大，使的方差达到次大，等等。满足以上条件的新特征y1,y2,yn分别称为样品点的第1,2,n个主成分。下面讨论怎样求出各个yi，或者说怎样求出各个ui。首先求出全体样品点的协方差矩阵这里S的下标x表示这是对应于旧特征x1,x2,xn 的协方差矩阵。然后，求出Sx的n个特征值和与之对应的特征向量u1,u2,un。每个是一个数，而与之对应的特征向量是一个列向量ui=(ui1,ui2,uin)T，它们之间的关系是，i=1,2,n (2-5)因此，求和相当于解以上方程。具体的解法请参见计算方法（如雅可比方法）。如果我们在解方程时还要求正交归一条件 (2-6)成立，则各个就是唯一确定的。现在我们来说明,，用以上方法所求出的各个就可以满足前面所说的条件（1）-（3）。令，即或Y=UX （2-7）于是y1,y2,yn就是由x1,x2,xn 经线性变换而得到的新特征。可以证明，当经过上述形式的线性变换后，如果对应于X的的协方差矩阵是Sx，那么对应于Y的协方差矩阵就是 Sy=USxUT (2-8)注意到UT的每列恰好是Sx的一个特征向量，并利用条件（2-5），得到其中是以为主对角线元素的对角阵。再利用正交归一化条件（2-6），又可以得到Sy=USxUT= UUT= （2-9）这就是说：新特征y1,y2,yn两两之间的协方差为零，即它们是不相关的。这样，我们就找到解决主成分分析问题的关键，即求原始协方差矩阵的特征值和特征向量。讨论：主成分分析三条件的作用。条件（1）是线性条件。它反映新老特征之间的关系是简单的，便于计算；条件（2）是不相关性。它要求每个特征都有着独立的作用；条件（3）是方差极大条件。每个特征的方差数值在一定意义下反应了它所包含的信息量。当前几个新特征的信息量足够大时，便可以舍弃其余的新特征，从而达到减少特征个数的目的。2、计算步骤假定原始资料矩阵已知，则计算步骤如下：（1） 根据公式，计算原有特征的协方差矩阵Sx。（2） 用任意一种计算方法求出Sx的全部特征值和对应的特征向量u1,u2,un。并将各特征值按从小到大的顺序排列 （2-10）特征向量也应按照对应特征值的顺序排列。由前面的推导我们知道：新特征与旧特征的特征值相同。这时已经可以求出n个新特征y1,y2,yn，它们满足条件Y=UX。其特征值亦为.（3） 我们定义第i个主成分yi的“方差贡献率”为 （2-11）前m个主成分y1,y2,ym的“累计方差贡献率”为 （12）当前m个主成分的累计方差贡献率已经足够大时（70%，80%或者更大），就可以只取前m个主成分作为新的特征，这时有 （2-13）其后的n-m个新特征可以舍去。主成分分析的计算到这里本来已经完成了，下面是两点补充。我们称第k个新特征yk与第i个旧特征xi之间的相关系数为xi在yk上的“因子负荷量”，计算公式为 （2-14）求出全体并作出因子负荷量矩阵：这个矩阵有以下两点特点：1） 每行元素平方之和为1。2） 第k列各元素平方再乘以对应原有元素方差之和为， 即由此出发，也可以定义前m个主成分对原有变量xi的累计贡献率为当足够大时，可以认为前m个主成分y1,y2,ym已经包含了xi中的主要信息量。例2-3 假设有一批样品，样品数为N=4，特征数为n=2，样品的原始资料矩阵见表2-5。表2-5 样品的原始资料矩阵X1X2X3X4x11-12-2x21-12-2（1）首先计算样品的协方差矩阵，结果为，（2）计算特征值和特征向量，得到 ， （3）则对于样品利用主成分分析所得到的新特征是 即，这一公式表示新特征即主成分所对应的坐标系相当于将原坐标系旋转45度而得，见图2-3（a）。 下面计算主成分的累计方差贡献率。 ，即只用第一主成分已可包含了原数据的全部信息。这一点是显而易见的，因为全部4个点都分布在y1轴上。(a) -2-112-221-1x1x2y1y2(b) -2-12-221-1x1x2y1y21图2-3 主成分分析的几何解释例2-4 同上，假设有一批样品，样品数为N=4，特征数为n=2，样品的原始资料矩阵见表2-6。表2-6 两批样品的原始资料矩阵X1X2X3X4x11-12-2x2-112-2计算方法同上：（1）首先计算样品的协方差矩阵，结果为，（2）计算特征值和特征向量，得到， （3）则利用主成分分析所得到的新特征是 即，这一公式表示新特征即主成分所对应的坐标系相当于将原坐标系旋转45度而得，见图2-3（b）。 下面计算主成分的累计方差贡献率。 ，即只用y1时要损失原有信息的20%。2.2.2 对应分析对应分析是另一种常用的线性降维映射方法。这一方法的提出要从主成分分析谈起。由上可知，主成分分析的目的在于从旧特征出发，构造新特征。不难想到，用同样的方法可以从原有样品出发构造一批新样品F，使得Fi=vi1X1+ vi2X2+ viNXN, i=1,2,N其中Xi是旧样品，Fi是新样品，vij是系数。在求Fi时，只要用样品间的某种相似系数（如夹角余弦）矩阵代替特征间的协方差矩阵即可。新样品Fi可以理解为具有代表性的典型样品。它通常不是原有样品中的某一个，而是综合原有样品的性质而得到的“标准”样品（如字符识别中的印刷体）。这种方法通常称为因子分析。也有些书中把对于特征的线性映射称为R型因子分析，而把对样品的线性映射称为Q型因子分析。因子分析（Q型）与主成分分析的原理虽然相同，但在计算上要困难得多。这是因为，通常情况下样品数目N要远远大于特征数目n。因此，样品相似系数矩阵将是一个庞大的矩阵，对它的计算要困难得多。对应分析便是针对这一问题而提出的一种方法。它可以利用特征间的协方差矩阵同时完成R型和Q型两种因子分析。步骤：（1） 资料的标准化在进行主成分分析时，对原始资料可以进行标准化，也可以不进行。但是，对应分析要求必须对资料进行特定的标准化。首先，假定原始资料矩阵的每个元素（如果xij0，只要将第i行的每个元素都加上该元素的最小值便可满足要求）。然后做以下两次变换。1) 令T等于原始资料阵全体元素之和，即然后进行“总和标准化”：总和标准化与常用的极差标准化或标准差标准化不同。它把原始资料的行与列同等对待，也就是把样品与特征同等对待。经过总和标准化后，全体pij之和为1，因此每个pij可以看成一种二维情形下的概率。由此将矩阵X变到P。2) 令pi.和p.j分别表示矩阵P的第i行及第j列元素之和，即，然后令得到新的资料矩阵Y，见表2-6。 由P到Y的变换可以这样解释：P中任意两点，可以写成， 求与的欧氏距离平方得则可以改用以下的加权欧氏距离平方就相当于先将pij变换成后，再求欧氏距离平方。表2-6 对应分析的变换步骤（2） R型因子分析下面来求各特征间的协方差矩阵S。根据协方差定义，应有, ,分别是第i,j行的平均值.现在将这一公式略加修改，令即把通常意义下的算术平均改为加权平均，再令, 便得到加权的协方差公式。另一种方法：若令, ; 则有或 S=ZZT下面的步骤与主成分分析相同：求S的各特征值与特征向量，按照累计方差贡献率求出前几个新的特征。由以上的步骤可以看出，若在第（1）步时直接令而得到新资料阵Z，则可令S=ZZT而进行R型因子分析。（3） Q型因子分析我们令样品之间的协方差矩阵为B= ZT ZB是N行N列矩阵，进行分析的计算量很大，但是，已经证明了以下结论：1） B和S的非零特征值相同。2） 若u是S的特征向量，则ZT u是B的特征向量。3） 若v是B的特征向量，则Zv是S的特征向量。根据以上的结论，如果已经求出了S的前k个特征向量u1,u2,uk，那么只需计算ZTu1, ZTu2, ZTuk便可得到B的特征向量，而无需直接计算了。2.3 考虑多类情形的线性降维法本节介绍另一种线性映射降维方法。在叙述这种方法之前，我们先对上节所介绍的两种方法做一个简单的回顾。首先，上节所谈的两种方法都是线性映射方法。从几何学的观点来看，线性映射相当于一次坐标旋转。例如，如果一批样品点散布在一个椭圆形的区域中，那么进行主成分分析的结果将使第一主成分y1指向椭圆的长轴方向，第二主成分y2指向短轴方向，如图2-4（a）所示。同理，如果样品点是散布在一个椭球或超椭球中，各个主成分便依次与最长轴、次长轴直至最短轴重合。其次，上节所讲的两种方法都没有考虑样品的类别，而是把全体样品作为一类加以处理的。因此，这类降维方法固然可以较好地保留样品分布的信息，但对于分类则并不一定有利。不妨举个极端的例子：如果全部样品点被分为图2-4（b）中所示的两类，那么显然可以看到，第一主成分y1的分类效果反而不及y2。本节讨论另一种线性映射降维方法，它在映射时将利用有关样品类别的信息，并且设法增强样品的“类别可分离性”。2.3.1 几种常用线性映射及其性质设有一批样品，每个样品用n个特征表示，即可写成X=(x1,x2,xn)T。对于个原有特征的一个线性变换可以表示为：yi=ai1x1+ai2x2+ainxn, i=1,2,m;m=n或Y=AX （2-15）其中A是变换矩阵，可以是方阵，也可以不是方阵，即m=n。每个yi是一个新特征。线性映射对原有样品分布情况的影响，集中地反映在对于样品的均值和协方差的影响上。设原有样品的均值为而协方差矩阵为Sx，可以证明，经过式(2-15)的映射后，在新特征空间中的样品均值和协方差矩阵分别变为：, （2-16）图2-4 主成分分析的几点解释（1） 正交归一变换我们在主成分分析中所用的变换称为正交归一变换。这时所用的变换矩阵A=U是以Sx的各个特征向量为列所形成的矩阵的转置，而Sy=是对角矩阵。还可以证明。在正交归一变换之下欧氏距离保持不变。或者说，这种变换只改变了坐标轴的方向，而没有改变分布形状，即坐标轴只被旋转（图2-4）。（2）白化变换如果令变换矩阵A=-1/2U，其中U和的含义同（1）。则由式（2-16）可知Sy=ASxAT=-1/2USxUT-1/2=-1/2-1/2=I （2-17）其中I是单位矩阵。这种变换称为白化变换。关于白化变换有两个重要性质：1） 经过白化变换以后，样品的分布形式将发生变化，或者说坐标将被压缩或者膨胀，见图2-5。2） 经过白化变换以后，由于协方差阵Sy已经是单位阵，所以再对Y进行任一种正交归一变换Z=UY后所得的新协方差阵Sz仍是单位阵，即Sz=USyUT= UIUT = UUT =I （2-18）UT=U-1是正交归一变换的性质。（3）一类归一变换 现在我们考虑多类情形。为简单起见，先考虑只有两类，的情况。假定两类样品均值分别为和，而协方差矩阵分别为S1x和S2x。如果我们对第一类样品实行白化变换，即求S1x的特征向量转置矩阵U1，和以特征值为对角线元素的对角矩阵1，并对两类样品同时做变换Y=-1/2U1X，则变换后的两类协方差矩阵将分别为：y2,z2y1,z10x1x2正交归一变换后白化变换后图2-5白化变换的几何解释 （2-19）这时，第一类样品的分布将变为圆形（球形，超球），而第二类样品的分布也将随之变为比较规整的形状，见图2-6。