1、第章特征提取和选择第第5章特征提取和选择章特征提取和选择5.1基本概念基本概念5.2类的可分性判据类的可分性判据5.3基于可分性判据的特征提取基于可分性判据的特征提取5.4主分量分析主分量分析(PCA)5.5独立分量分析独立分量分析(ICA)5.6基于核函数的方法基于核函数的方法5.7特征选择方法特征选择方法习题习题第章特征提取和选择5.1基基 本本 概概 念念5.1.1特征的特点特征的特点模式识别的主要功能在于利用计算机实现人的类识别能力,它是一个与领域专门知识有关的问题。在模式识别过程中,特征的确定比较复杂。研究领域不同,选择的特征也不同,但不论采用什么样的特征,都应该满足以下条件:第章特
2、征提取和选择(1)特征是可获取的。因为模式识别系统的主要处理设备是计算机,所以作为观察对象的数字化表达,观察对象应该是可以通过数据采集设备输入到计算机的。目前,市场上有各种传感设备和数字化设备,如采集图像信息的图像卡和采集语音信息的声卡等。作为特征,既可以是数字化表达的结果,也可以是在数字化表达基础上形成的参数性质的值,如图像分割后的子目标特性表达。第章特征提取和选择(2)类内稳定。选择的特征对同一类应具有稳定性。由于模式类是由具有相似特性的若干个模式构成的,因此它们同属一类模式,其首要前提是特性相似,反映在取值上,就应该有较好的稳定性。第章特征提取和选择(3)类间差异。选择的特征对不同的类应
3、该有差异。若不同类的模式的特征值差异很小,则说明所选择的特征对于不同的类没有什么差异,作为分类的依据时,容易使不同的类产生混淆,使误识率增大。一般来讲,特征的类间差异应该大于类内差异。第章特征提取和选择5.1.2特征的类别特征的类别特征是用于描述模式性质的一种量,从形式上看可以分为三类:1.物理特征物理特征物理特征是比较直接、人们容易感知的特征,一般在设计模式识别系统时容易被选用。如为了描述指定班级中的某个学生,可以用以下物理特征:性别、身高、胖瘦、肤色等外在特征。物理特征虽然容易感知,却未必能非常有效地表征分类对象。第章特征提取和选择2.结构特征结构特征结构特征的表达能力一般要高于物理特征,
4、如汉字识别的成功实现离不开结构特征的选择。结构特征的表达是先将观察对象分割成若干个基本构成要素,再确定基本要素间的相互连接关系。第章特征提取和选择通过要素和相互连接关系表达对象,可以较好地表达复杂的图像图形信息,在实际中已经有较多的成功应用,如指纹的识别就是基于结构信息完成的。结构信息对对象的尺寸往往不太敏感,如汉字识别时,识别系统对汉字大小不敏感,只对笔划结构信息敏感。结构特征比物理特征要抽象一些,但仍属比较容易感知的特征,如人的指纹特征、人脸的五官结构信息等,是认定人的身份的重要参数。第章特征提取和选择3.数字特征数字特征一般来说,数字特征是为了表征观察对象而设立的特征,如给每个学生设立一
5、个学号,作为标志每个学生的特征。由于学号是人为设定的,可以保证唯一性,但这种特征是抽象的,不容易被人感知。数字特征有时和观察对象的固有特性没有任何联系,有时则是物理或结构特征的计算结果。第章特征提取和选择5.1.3特征的形成特征的形成在设计一个具体的模式识别系统时,往往是先接触一些训练样本,由领域专家和系统工程师联合研究模式类所包含的特征信息,并给出相应的表述方法。这一阶段的主要目标是获取尽可能多的表述特征。在这些特征中,有些可能满足类内稳定、类间离散的要求,有的则可能不满足,不能作为分类的依据。根据样例分析得到一组表述观察对象的特征值,而不论特征是否实用,称这一步为特征形成,得到的特征称为原
6、始特征。第章特征提取和选择在这些原始特征中,有的特征对分类有效,有的则不起什么作用。若在得到一组原始特征后,不加筛选,全部用于分类函数确定,则有可能存在无效特征,这既增加了分类决策的复杂度,又不能明显改善分类器的性能。为此,需要对原始特征集进行处理,去除对分类作用不大的特征,从而可以在保证性能的条件下,通过降低特征空间的维数来减少分类方法的复杂度。第章特征提取和选择实现上述目的的方法有两种:特征提取和特征选择。特征提取和特征选择都不考虑针对具体应用需求的原始特征形成过程,而是假设原始特征形成工作已经完成。然而在实际工作中,原始特征的获得并不容易,因为人具有非常直观的识别能力,有时很难明确描述用
7、于分类的特性依据。如人脸的判定,人识别脸部特征非常容易,若用计算机来识别人脸,则需要得到多达上千个特征,难度很大。可以说,特征形成是模式识别过程中的重点和难点之一。第章特征提取和选择5.1.4特征提取和选择的作用特征提取和选择的作用特征选择是指从一组特征中挑选出对分类最有利的特征,达到降低特征空间维数的目的。特征提取是指通过映射(或变换)的方法获取最有效的特征,实现特征空间的维数从高维到低维的变换。经过映射后的特征称为二次特征,它们是原始特征的某种组合,最常用的是线性组合。第章特征提取和选择从定义可以看出,实现特征选择的前提是确定特征是否有效的标准,在这种标准下,寻找最有效的特征子集。用于特征
8、选择的特征既可以是原始特征,也可以是经数学变换后得到的二次特征。需要注意,特征提取一定要进行数学变换,但数学变换未必就是特征提取。第章特征提取和选择特征提取和特征选择的主要目的都是,在不降低或很少降低分类结果性能的情况下,降低特征空间的维数,其主要作用在于:(1)简化计算。特征空间的维数越高,需占用的计算机资源越多,设计和计算也就越复杂。(2)简化特征空间结构。由于特征提取和选择是去除类间差别小的特征,保留类间差别大的特征,因此,在特征空间中,每类所占据的子空间结构可分离性更强,从而也简化了类间分界面形状的复杂度。第章特征提取和选择5.2类的可分性判据类的可分性判据在特征提取与选择的过程中,高
9、维特征变为低维特征的方法很多,究竟哪种方法最有效,需要通过某种标准来衡量,在数学上就是要构造某种准则(或判据)。这些准则应能很好地反映各类间的可分性以及各特征在分类识别中的重要性或贡献,因此人们希望可分性判据满足以下要求:第章特征提取和选择(1)与错误概率(或是错误概率的上、下界)有单调关系,使判据的极大值对应错误概率的最小值或较小值。(2)非负性,即0 0 ijijJijJij(5-1)其中,Jij表示第i,j两类间的可分性判据。(3)对称性,即 Jij=Jji (5-2)第章特征提取和选择该特性表明有效性判据对类别号没有方向性,而只强调对区分两类的贡献。(4)当特征独立时,判据应具有可加性
10、,即121(,)()dijdijkkJxxxJx(5-3)(5)单调性。对于特征向量而言,加入新的特征分量不会减少判据值,即 12121(,)(,)ijdijddJ x xxJ x xx x(5-4)第章特征提取和选择5.2.1基于距离的可分性判据基于距离的可分性判据模式识别的结果实际上是将特征空间划分为不同类的决策区域。为了有利于分类,我们总是希望不同类之间的距离大一些,而同类的样本较集中,这样类别的可分性才越好。因此,利用类间距离构造类别的可分性判据是可行的。1.两类之间的距离两类之间的距离设两类为i、j,分别有Ni、Nj个样本,即 2,iiiiiiN x xx12,jjjjjN x xx
11、(5-5)(5-6)第章特征提取和选择两类间的距离可由下式给出:jiD111(,)jiijNNijrsrsijDDN Nx x(5-7)其中,D(xir,xjs)为向量xir、xjs间的距离。由点间距离的对称性可知,类间距离也具有对称性。常用的点间距离有以下几种:(1)欧几里德(Euclidean)距离:第章特征提取和选择2112)(),(diiiyxDyx(5-8)其中,d为向量的维数。(2)加权欧几里德距离:2112)(),(diiiiyxwDyx(5-9)第章特征提取和选择(3)汉明(Hamming)距离:diiiyxD1|),(yx(5-10)(4)马氏(Mahalanobis)距离:
12、2111(,)()()()()ddTijiijjijDw xyxyx yxyMxy(5-11)其中,M为一正定阵,wij为矩阵M1的元素。第章特征提取和选择(5)明可夫斯基(Minkowsky)距离:qdiqiiyxD11|),(yx(5-12)其中:当q=1时,D(x,y)为汉氏距离;当q=2时,D(x,y)为欧氏距离。(6)切比雪夫(Chebyshev)距离:iidiyxD1max),(yx(5-13)第章特征提取和选择2.各类样本之间的平均距离各类样本之间的平均距离设N个样本分别属于m类,i=xik,k=1,2,Ni,i=1,2,m,各类之间的平均距离为111111()()()(,)2j
13、iNNmmijijrsijrsijJPPDN Nxx x(5-14)其中,是先验概率P(i)的估计,即()iP第章特征提取和选择()/iiPNN1,2,imN为样本总数,即 1miiNN若点间距离取欧氏距离的平方,以表示第i类的向量平均值,以表示的统计平均值,即ii)()(),(yxyxyxTD(5-15)第章特征提取和选择11iNiilliNx(5-16)1111()iNmmiiiliilPNx(5-17)则式(5-14)可化为 111111()()()(,)2jiNNmmijijrsijrsijJPPDN Nxx x111()()()()()mNiTiTiririiiiriPNxx(5-1
14、8)第章特征提取和选择且有关系式 1111()()()()()()()2mmmTTijijijiiiijiPPP(5-19)令111()()()()()mmTTbiiiiiiiiPNNS (5-20)111111()()()()()iiNNmmiiTiiTwikikikikiikikiPNNSxxxx(5-21)第章特征提取和选择则()()wbJtrxSS(5-22)式(5-20)、式(5-21)和式(5-22)中的分别是利用有限样本集得到的类均值i、总体均值、类内离散度矩阵Sw和类间离散度矩阵Sb的估计值,i、,Sw、Sb的定义式如下:,iwb SS(|)iipdxxx(5-23)xE(5-
15、24)第章特征提取和选择1()()()mTbiiiiPS(5-25)11()()()()()()(|)mmTTwiiiiiiiiiiPEPpdSxxxxxx(5-26)为了使所使用的特征能够有效地进行分类,我们希望类间离散度尽量大,同时类内离散度尽量小,从直观上看可以构造下面各种判据:第章特征提取和选择1bwJ SS(5-27)12()wbJtrS S(5-28)3lnbwJSS(5-29)4()()bwtrJtrSS(5-30)第章特征提取和选择5|wbwJSSS(5-31)为了有效地分类,它们的值越大越好。基于距离的可分性判据虽然简单直观,但只是对于类间无重叠的情况效果较好,若类间存在重叠
16、,则效果会受到影响。基于概率的可分性判据能够较好地解决类间有重叠的问题。第章特征提取和选择5.2.2基于概率密度函数的可分性判据基于概率密度函数的可分性判据基于概率密度函数的可分性判据主要考虑的是两类的概率分布情况。考虑如图5-1所示两种极端情况,容易看出,图5-1(a)中两类是完全可分的,图5-1(b)中两类是完全不可分的,两类概率密度函数的重叠程度反映了两类的可分性,因此,可以利用类条件概率密度函数构造可分性判据。第章特征提取和选择图5-1 一维情况下两类类条件概率密度分布情况(a)两类概率密度函数完全分开；(b)两类概率密度函数完全重叠 第章特征提取和选择基于类条件概率密度函数p(x|1
17、)、p(x|2)的可分性判据Jp应满足以下四个条件:(1)非负性:0pJ(5-32)(2)对称性:1121(|),(|)(|),(|)ppJppJppxxxx(5-33)(3)最大值:当两类完全可分时,Jp具有最大值。(4)最小值:当两类完全不可分时,Jp具有最小值,即Jp=0。下面介绍三种典型的基于概率密度函数的可分性判据。第章特征提取和选择1.巴氏巴氏(Bhattacharyya)距离距离Bhattacharyya距离的定义式为1212ln (|)(|)BJppd xxx(5-34)它与最小错误概率判决准则的错误概率Pe具有如下关系:1212()()exp()eBPPPJ(5-35)第章特
18、征提取和选择证明过程如下:211122()(|)()(|)eRRPPpdPpdxxxx1122min()(|),()(|)PpPpdxxx121122()(|)()(|)PpPpdxxx1212()()exp()BPPJ第章特征提取和选择2.切诺夫切诺夫(Chernoff)界限距离界限距离Chernoff界限距离的定义式为112ln(|)(|)0,1sscJppds xxx(5-36)由定义式可见,当s=1/2时,Chernoff界限距离就是Bhattacharyya距离。第章特征提取和选择一般情况下JC的计算比较困难,当1、的类条件概率密度函数分别为正态分布密度函数(i,i)和(j,j)时,
19、可以推导出11(1)11(1)()(1)()ln22ijTcijijijssijssJssss(5-37)第章特征提取和选择3.散度散度在第2章的讨论中,对于两类的分类问题,最大后验概率判决准则可以通过似然比和某个阈值的比较实现,显然似然比对于分类来说是一个重要的度量。对于给定某个阈值,P(1|x)/P(2|x)越大,对类1来讲可分性越好,该比值反映了两类类条件概率密度函数的重叠程度。为了保证概率密度函数完全重叠时判据为零,应对该比值取对数。又因为x具有不同的值,应该考虑类1的均值。定义类1相对于类2的平均可分性信息为 第章特征提取和选择1112122(|)(|)ln(|)ln(|)(|)pp
20、IEpdppxxxxxx(5-38)类2相对于类1的平均可分性信息为 2221211(|)(|)ln(|)ln(|)(|)ppIEpdppxxxxxx(5-39)第章特征提取和选择对于1和2两类总的平均可分性信息称为散度,其定义为 1221DJII(5-40)将式(5-38)、式(5-39)代入式(5-40)可得 1122(|)(|)(|)ln(|)DpJppdpxxxxx(5-41)第章特征提取和选择5.2.3基于熵函数的可分性判据基于熵函数的可分性判据由信息论可知,对于一组概率分布而言,分布越均匀,平均信息量越大,分类的错误概率越大;分布越接近0-1分布,平均信息量越小,分类的错误概率越小
21、,可分性越好。因此,可以建立基于熵函数的可分性判据,其中熵函数表征平均信息量。对于后验概率P(i|x)而言,分类效果最不好的情形为m类分布等概率的情形:第章特征提取和选择1(|)(1,2,)iPimmx(5-42)分类时任取一类判决,正确率为1/m,错误率为(m1)/m。若后验概率为0-1分布,即(|)1,(|)0,ijPPjixx且(5-43)则应判x对应的模式属于第i类,错误概率等于0。从特征选择与提取的角度看,人们希望采用具有最小不确定性的那些特征进行分类,也就是保留熵函数小的特征。为此可定义基于熵函数的可分性判据:第章特征提取和选择1(|),(|)mHf PPxx(5-4)由上式可知,
22、H是P(1|x),P(2|x),P(m|x)的函数,它满足以下几个条件:(1)非负性:H0(5-45)(2)对称性:1221(|),(|),(|)(|),(|),(|)mmHf PPPf PPPxxxxxx(5-46)第章特征提取和选择(3)最小值:完全可分出现在后验概率为0-1分布的情形:00(|)1 (|)0 iiPiiP iixx(5-47)此时信息熵具有最小值。(4)最大值:最大值对应分类效果最不好的情形。在多类情况下,分类效果最差的出现条件是各类后验概率相等,即第章特征提取和选择12111(|),(|),(|),mHf PPPfm mmxxx(5-48)满足上述性质的广义熵表达形式很
23、多,作为一个广义熵的表述,其定义为 11121(|),(|),(|)(21)(|)1mmiiHPPPPxxxx(5-49)第章特征提取和选择其中是一实的正参数,1。对应不同的值可得到不同的可分性判据。当1时,根据洛必达法则可得Shannon熵 121()(|)log(|)miiiHPPP xx(5-50)第章特征提取和选择当=2时,可以得到平方熵 )|(1 2)(122miiPPHx(5-51)由于需要考虑到特征空间中每个样本点的熵函数,因此用熵函数在整个特征空间的统计平均12(|),(|),(|)HmJE HPPPxxx(5-52)作为可分性判据。第章特征提取和选择5.3基于可分性判据的特征
24、提取基于可分性判据的特征提取特征提取作为一种特征空间维数压缩方法,其主要特点在于通过变换的方法实现对原始特征的计算,使变换后的二次特征可以去掉一些分量。从数学上看,任何定义在原始特征空间上的任何数学计算都是一种变换。本节主要讨论线性变换。第章特征提取和选择对于任何一种给定的线性变换而言,变换后的特征是否对分类有效,决定了变换方法的有效性。考虑到特征的有效性是由可分性判据来表征的,因此,变换方法的有效性可以借助于变换结果的有效性表达。可分性判据的基础主要有三类:距离、概率密度函数和熵函数,因此,基于可分性判据的特征提取方法也有相应的三种:基于距离可分性判据的特征提取方法、基于概率密度函数可分性判
25、据的特征提取方法和基于熵函数可分性判决的特征提取方法。第章特征提取和选择上述方法的基本思路如下:对于n个原始特征构成的特征向量x=(x1,x2,xn)T,特征提取就是对x作线性变换,产生d维向量y=(y1,y2,yd)T,dn,即y=WTx (5-53)式中,W=Wnd称为特征提取矩阵或简称变换矩阵。基于可分性判据的特征提取就是在一定的可分性判据下,如何求最优的变换矩阵W。第章特征提取和选择5.3.1基于距离可分性判据的特征提取方法基于距离可分性判据的特征提取方法前面研究了基于距离的可分性判据,得到了相应判据,它们都反映了一个基本思想,即类内距离小和类间距离大的要求。下面我们以J2准则为例讨论
26、特征提取的方法。设Sw和Sb为原始特征空间的类内离散度矩阵和类间离散度矩阵,S*w和S*b为变换后特征空间的类内离散度矩阵和类间离散度矩阵,W为变换矩阵。则有第章特征提取和选择*TwwSW S W*TbbSW S W(5-54)(5-55)在变换域中,*1*12()()()()TTwbwbJtrtrWSSW S WW S W(5-56)为了求使J2(W)最大的变换,就要求J2(W)对W的各分量的偏导数为零。这里我们不做详细的推导,只给出求解变换矩阵的解析解法。第章特征提取和选择设矩阵S-1wSb的特征值为1,2,n,按大小顺序排列为 12n相应的正交化、归一化的特征向量为 12,n 选前d个特
27、征向量作为变换矩阵:12,dn dW 此结论对于J4判据也适用。第章特征提取和选择5.3.2基于概率密度函数可分性判据的特征提取方法基于概率密度函数可分性判据的特征提取方法基于概率密度函数的可分性判据的方法需要知道各类的概率密度函数的解析形式,难度较大,计算量也较大。一般地,只有当概率密度函数为某些特殊的函数形式时才便于使用,这里只研究多元正态分布的两类问题。对于基于概率密度函数可分性判据的特征提取方法而言,通常选用的变换仍为线性变换,设n维原始特征向量x经线性变换后的二次特征向量为y,即第章特征提取和选择TyW x(5-57)在映射后的特征空间内建立某种准则函数,使得它为变换矩阵W的函数:(
28、)ccJJW(5-58)其中,Jc为基于概率密度函数的可分性判据,如前面介绍的Bhattacharyya距离和Chernoff 距离等可分性判据。通过求解判据的极值点即可得到使映射后的特征组可分性最好的变换矩阵。在Jc(W)可微的情况下,就是求解偏微分方程:第章特征提取和选择()cJW0W(5-59)下面以Chernoff距离为例,分析特征提取方法。当两类都是正态分布时,两类的分布函数分别为 111111/2/2111(|)exp()()2(2)Tnpxxuxu(5-60)122221/2/2211(|)exp()()2(2)Tnpxxuxu(5-61)第章特征提取和选择变换后的判据Jc是W的
29、函数,记为Jc(W)112121()(1)(1)21ln(1)2TTTCTTJss trssssWW MWW WW WW WW W1211(1)lnln22TTssW WW W(5-62)式中,M=(12)(12)T。因为Jc(W)是标量,可以对W的各个分量求偏导,并令其为零,简化后的矩阵方程为第章特征提取和选择1121211112221(1)(1)()()TTTTTTTssssIMW W WW WW WW MW WW WW W W IW WW W0(5-63)上式是W的非线性函数,只能采用数值优化的方法得到近似最优解。但是在以下两种特殊情况下可以得到最优的解析解。第章特征提取和选择1)1=2
30、=,12在此种情况下,最优特征提取矩阵是由-1M矩阵的特征向量构成的。又因为矩阵M的秩为1,故-1M只有一个非零特征值,对应于特征值为零的那些特征向量对Jc(W)没有影响,因此可以舍去,所以最优变换W是-1M的非零特征值对应的特征向量v,不难得到W=v=-1(12)(5-64)这个结果与Fisher的线性判别式的解相同。第章特征提取和选择 2)12,1=2在此种情况下,最优特征矩阵是由-121满足下列关系:1122111)1(.)1()1(snsnssssssssss(5-65)的前d个特征值所对应的特征向量构成的,此时Jc(W)取最大值。第章特征提取和选择5.3.3基于熵函数可分性判据的特征
31、提取方法基于熵函数可分性判据的特征提取方法基于熵函数的可分性判据的提出,主要是考虑不同分布特性对判决的影响。当多类的分布呈均匀分布时,信息熵为最大值,此时具有最差的可分性。当多类呈0-1分布时,信息熵达到最小值,此时,具有最好的可分性。基于信息熵的可分性判据和信息熵呈反比关系,为了提取出熵函数可分性判据意义上的最佳特征组,也是选择线性变换,可将变换矩阵带入判据表达式:第章特征提取和选择11Tdd nnyWx(5-66)()HHJJW(5-67)通过求解判据的极值点即可得到使映射后的特征组可分性最好的变换矩阵。在JH(W)可微的情况下,就是求解偏微分方程:()HJW0W(5-68)求出极值点即为
32、所求的线性变换,在本书中不展开讨论,有需要者可参看有关参考文献。第章特征提取和选择5.4主分量分析主分量分析(PCA)一种处理多维的方法是采用组合特征的方法来降低维数,其中,特征的线性组合计算简单且能够进行解析分析。从本质上来说,线性变换就是将高维空间的数据投影到低维空间的过程。主分量分析是一种有效的特征线性变换方法,也称为KL变换。KL变换是一种基于目标统计特性的最佳正交变换,它的最佳性体现在变换后产生的新的分量正交或不相关。第章特征提取和选择设n维随机向量x=(x1,x2,xn)T,x经标准正交矩阵A正交变换后成为向量y=(y1,y2,yn)T,即 TyA x(5-69)y的相关矩阵为()
33、TTTTEEyxRyyA xx AA R A(5-70)其中,Rx为x的相关矩阵,是对称矩阵。选择矩阵A=(a1,a2,an),且满足 第章特征提取和选择iiixR aa(5-71)这里,i为Rx的特征根,并且12n,ai为i的正交化、归一化特征向量,即aTiai=1,aTiaj=0(ij;i,j=1,2,n)。Ry是对角矩阵:12(,)Tndiag yxRA R A(5-72)若Rx是正定的,则它的特征值是正的。此时变换式(5-69)称为K-L变换。第章特征提取和选择由式(5-69)可得121121()(,)nTniiinyyyyxAyAya aaa(5-73)我们选择x关于ai的展开式的前
34、m项在最小均方误差准则下估计x,这时估计式表示为 1,(1)miiiymnxa(5-74)第章特征提取和选择估计的均方误差为 22221111()nnnnTTiiiiiii mi mi mi mmEEyE yExxaaxx a(5-75)我们希望选择使估计的均方误差最小的特征向量,因此要选择相关矩阵Rx的m个最大的特征值对应的特征向量构成变换矩阵A,这样得到的均方误差将会最小,是nm个极小特征值之和。可以证明,与m维向量中的其他x逼近值相比,这个结果是最小均方误差解。这就是K-L变换也称为主分量分析(PCA)的原因。第章特征提取和选择上述分析中采用的是样本的相关矩阵,也可以采用样本的协方差矩阵
35、进行分析。例如,在人脸识别中,PCA是一种常用的特征提取方法。设一幅pq大小的人脸图像,可以将它看成是一个矩阵(fij)pq,fij正比于图像在该点的灰度级。若将该矩阵按列相连构成一个pq维向量x=(f11,f21,fp1,f21,f22,fp2,f1q,f2q,fpq)T。设训练样本集为 X=x1,x2,xN,包含N个图像。其协方差矩阵为第章特征提取和选择11()()NTiiiNRxx xx(5-76)其中，11NiiNxx(5-77)求出矩阵R的前m个最大特征值1,2,m及其对应的正交化、归一化特征向量1,2,m。分别将这m个特征向量化为p行q列矩阵,得到m幅图像,称为“特征脸”。图5-2
36、 显示的是对应前30个最大特征值的特征向量的图像。第章特征提取和选择图5-2“特征脸”图像第章特征提取和选择将每一幅人脸图像投影到由a1,a2,am张成的子空间中,对应于该子空间的一个点,该点的坐标系数对应于图像在子空间的位置,可以作为识别人脸的依据。对于任意待识别样本y,可通过向“特征脸”子空间投影获得系数向量y=(a1,a2,am)Ty。第章特征提取和选择5.5独立分量分析独立分量分析(ICA)独立分量分析(Independent Component Analysis,ICA)的基本思路是在特征空间上寻找到最能使数据相互独立的方向。5.5.1ICA概述概述1.ICA的定义的定义为了给出IC
37、A的严格定义,我们可以使用统计上的“隐变量”模型。假设观测变量x=(x1,x2,xn)T可由n个独立分量y1,y2,yn线性组合得到:第章特征提取和选择1122(1,2,)iiiinnxa ya ya yin(5-78)式中,aij(i,j=1,2,n)是实系数。令y=(y1,y2,yn)T,A=(aij),式(5-78)可写成矩阵形式:x=Ay (5-80)第章特征提取和选择例如,ICA可以用于提取人脸图像的独立特征,图5-3是人脸脸谱合成和分解模型。由模型可知,人脸图像集X=x1,x2,xN被认为是由一个未知的统计独立图像集Y=y1,y2,yN和未知的混合矩阵A线性合成的。ICA的目的就是
38、在只给出观察样本集时,求出解混合矩阵W和人脸图像的独立图像集Y。第章特征提取和选择图5-3 ICA人脸图像合成与分解过程第章特征提取和选择ICA所提取的人脸图像的特征向量是每个人脸图像在这些独立图像上的投影系数V=(v1,v2,vN)T,如图5-4所示图 5-4ICA提取人脸特征向量第章特征提取和选择2.ICA的约束的约束为了保证上面给出的ICA模型能够被估计出来,我们必须给出一定的假设和约束。(1)独立分量是统计独立的。该假设是ICA能够成立的前提,为保证模型能够被估计,这个约束已经基本足够,这也是ICA能够在许多领域的应用中成为强有力的方法的原因。(2)混合矩阵A是方阵并且可逆。这个假设说
39、明独立分量的个数与样本的个数是相同的。这个假设在某些情况下是不严谨的,但该假设可以大大简化估计过程。第章特征提取和选择(3)独立分量必须具有非高斯分布。高斯分布是非常简单的一种统计分布,其所有高阶累计量都为零,但这样的高阶信息对于估计ICA模型却是必需的。可以通过一个例子来解释:考虑一个只有两个观测的ICA模型,假定混合矩阵是正交的,独立分量yi为高斯分布,具有单位方差,因为观察变量x1和x2是独立源的线性组合,故x1和x2也是不相关的具有单位方差的高斯随机变量,那么它们的联合概率密度函数为第章特征提取和选择2212121(,)exp()22xxp x x(5-81)从图5-5可以看出,分布是
40、完全对称的,因此,它不提供任何混合矩阵A各列的方向信息,也就是说无法估计出A。在多个独立成分是高斯的,其他独立成分是非高斯的情况下,可以估计出所有的非高斯成分,但是无法估计出其中的高斯成分,因为估计出的高斯成分可能是那些高斯成分的某种线性组合。因此,在独立分量分析中,应该假设至多只有一个独立分量为高斯分布,否则就无法估计出ICA模型。第章特征提取和选择图5-5 式（5-81）图解第章特征提取和选择3.ICA的预处理的预处理在应用ICA之前,通常要对数据作些预处理,使得ICA估计更加简单,更符合前面约定的条件。1)中心化不失一般性,我们可以假定所有混合变量与独立分量均具有零均值,这样可以在一定程
41、度上简化理论和算法。如果实际情况不满足零均值假设,则我们可以通过中心化处理使其满足要求。中心化其实就是去均值,将随机变量的中心移向零点。去均值是为了简化ICA的估计算法。用经过去均值处理的数据估计独立分量y,再把y的均值A-1m加回去即可,其中m为x的均值。第章特征提取和选择2)白化给定一组样本,通过线性变换将它们转变为相互无关的方法称为白化。将样本x通过一个白化滤波器,得到白色的,其目的是为了加快收敛速度。的元素是不相关的,而且具有单位方差。也就是说,的协方差矩阵是一个单位阵,即 xxxTExxI(5-82)通常白化处理采用特征值分解的办法。假定E(xxT)=QQT,其中Q为E(xxT)的特
42、征向量阵,为特征值对角阵,则下式可完成对数据的白化处理:第章特征提取和选择1/2TxQ x(5-83)这里,12(,)ndiag，1/212(,)ndiag。1/2TMQ为白化变换矩阵,它不是唯一的。容易看出,任何矩阵UM(U为正交矩阵)也是白化矩阵。显然,1/2TMQQ也是白化矩阵。第章特征提取和选择5.5.2基于累积量的基于累积量的ICA估计估计ICA有多种不同的估计原理和算法,但就其本质而言,都是先设计一个目标函数,然后选择某种优化算法使目标函数达到极值。我们可以用下面的“方程”来表达这一点:ICA方法=目标函数+优化算法在目标函数明确的情况下,我们可以使用任何经典的优化算法,比如(随机
43、)梯度法和牛顿法等。ICA方法的性质依赖于目标函数和优化算法,特别地,ICA的统计特性(如一致性、渐进方差、鲁棒性)取决于目标函数的选择;算法的性质(如收敛速度、存储需求、数值稳定性)取决于优化算法。第章特征提取和选择常用的ICA估计方法有极大化非高斯性的ICA估计方法、ICA的极大似然估计方法、极小化互信息的ICA估计方法、基于高阶累积张量的ICA估计方法、基于非线性去相关和非线性PCA的ICA估计方法等。这里主要介绍基于2阶和4阶累积量的ICA估计以及ICA的极大似然估计方法,其他方法可以参考相关文献。第章特征提取和选择ICA方法是根据PCA方法直接生成的。K-L变换使用2阶统计量,变换后
44、特征之间的交叉相关性为零,相应地,变换后样本的相关矩阵是对角矩阵。在ICA中,变换后特征之间是统计独立的,也就是说,要求所有高次的交叉累积量为零。交叉累积量是指累积量中至少有两个变量不同,例如k2(y1y2);若累积量中所有变量都相同,则称为自累积量,例如k4(yiyiyiyi)=k4(yi)为4阶自累积量。将运算限制在4阶对很多应用已经足够了,因此,我们只讨论4阶累积量。y的4个累积量分别为第章特征提取和选择1()0iik yE y(5-84)2()ijijky yE y y(5-85)3()ijkijkky y yE y y y(5-86)4()ijkrijkrijkrikjrirjkky
45、 y y yE y y y yE y y E y yE y y E y yE y y E y y(5-87)第章特征提取和选择在实际应用中,经常会遇到均值为零且概率密度函数是对称的情况,在这种情况下，所有奇数阶累积量为零,所以,问题可以简化为寻找一个矩阵W,使得变换后特征之间的2阶和4阶交叉累积量为零。具体的计算步骤如下:(1)对输入数据进行PCA变换,即TyB x(5-88)其中B是K-L变换中的正交矩阵。因此变换后 的各分量之间是不相关的。y第章特征提取和选择(2)计算另一个正交矩阵,使得变换后的样本各分量的4阶交叉累积量为零 BTyB y(5-89)这等同于寻找一个矩阵，使得4阶自累积量
46、的平方和最大,即 B24 1()()maxTniikyBBIB(5-90)上面两个步骤完成后,最后逼近的独立分量的特征向量可以由下式得到()TyBBxWx(5-91)第章特征提取和选择5.5.3ICA的极大似然估计方法的极大似然估计方法估计ICA模型的一个常用方法是极大似然估计方法,其基本思想是采用那些使所得观测量具有最大概率的参数估计值。混合向量x=Ay的概率密度函数可以写为()|det|()|det|()iiippp yxyxWyW(5-92)式中,W=A-1,pi表示独立分量的概率密度函数。上式可以表示为矩阵W=(w1,w2,wn)T和向量x的函数第章特征提取和选择()|det|()Ti
47、iippxxWw x(5-93)假设有x的T个观测值x(1),x(2),x(T),那么似然函数可以通过将T个点密度估计相乘得到,似然函数记为L,将它作为W的函数11()()|det|TnTiitiLpt Ww xW(5-94)在实际中普遍使用对数似然函数以方便运算，对数似然函数可由下式给出：第章特征提取和选择11log()log|det|log()TnTiitiLTptWWw x(5-95)式(5-94)和式(5-95)表明,要进行极大似然估计,先要估计出独立分量的概率密度函数,这是非常困难的。为了得到极大似然估计,需要能够极大化似然函数的数值算法。这里介绍广泛使用的自然梯度法和FastICA
48、算法。第章特征提取和选择1.自然梯度法自然梯度法利用梯度法求解极大似然估计的算法为1()TTE gWWy x(5-96)其中:期望运算E是从观测数据中计算的平均值,并非理论上的数学期望;y=Wx;g(y)是一个逐元素的向量函数,即1122()(),(),()Tnngg ygygyy(5-97)也可以使用该算法的随机版本,即忽略其中的期望运算,且在算法中每次只使用一个数据点,即第章特征提取和选择1()TTgWWy x(5-98)这种算法经常称为Bell-Sejnowski算法。梯度法收敛速度非常缓慢,改进措施是对数据作白化处理,以及采用自然梯度。自然梯度方法也称为相对梯度方法,它在相当程度上简化
49、了原来的梯度方法。自然梯度的原理比较复杂,抛开数学原理,具体实施办法相当于在式(5-98)右边乘以WT=W,这样得到第章特征提取和选择()TgWIy yW(5-99)该算法可以解释为非线性去相关。在梯度法的运行过程中,g(y)=g1(y1),g2(y2),gn(yn)T中函数gi(i=1,2,n)在两种非线性函数之间选择,根据下面矩的值来确定:2tanh1tanhiiiiEyyy(1,2,)in(5-100)第章特征提取和选择若i0,则()ig y()2tanh()gyy=(5-101)否则()ig y=_()tanh()gyyy或()ig y=3()gyy(5-102)第章特征提取和选择其中
50、1 exp()tanh()1 exp()yyy(5-103)在迭代过程中,可以对i进行更新,利用i的更新值,结合式(5-101)和式(5-102)选择函数gi,得到 1122()(),(),()Tnngg ygygyy进而更新W,再更新y,即 2(1)tanh1tanhiiiiiEyyy(1,2,)in(5-104)第章特征提取和选择()TgWWIy yW(5-105)yWx(5-106)其中:和为学习速率;W和i(i=1,2,n)的初始值可以随机选取,或利用先验信息选取。第章特征提取和选择2.FastICA算法算法在许多不需要自适应地调整参数的场合,梯度法反而会出现问题,而且梯度法的收敛速度
