《模式识别原理与应用》课件第5章

第5章特征提取和选择5.1

基本概念5.2类的可分性判据5.3基于可分性判据的特征提取5.4

主分量分析(PCA)5.5独立分量分析(ICA)5.6基于核函数的方法5.7特征选择方法习题5.1基本概念5.1.1特征的特点

模式识别的主要功能在于利用计算机实现人的类识别能力,它是一个与领域专门知识有关的问题。在模式识别过程中,特征的确定比较复杂。研究领域不同,选择的特征也不同,但不论采用什么样的特征,都应该满足以下条件:

(1)特征是可获取的。因为模式识别系统的主要处理设备是计算机,所以作为观察对象的数字化表达,观察对象应该是可以通过数据采集设备输入到计算机的。目前,市场上有各种传感设备和数字化设备,如采集图像信息的图像卡和采集语音信息的声卡等。作为特征,既可以是数字化表达的结果,也可以是在数字化表达基础上形成的参数性质的值,如图像分割后的子目标特性表达。

(2)类内稳定。选择的特征对同一类应具有稳定性。由于模式类是由具有相似特性的若干个模式构成的,因此它们同属一类模式,其首要前提是特性相似,反映在取值上,就应该有较好的稳定性。

(3)类间差异。选择的特征对不同的类应该有差异。若不同类的模式的特征值差异很小,则说明所选择的特征对于不同的类没有什么差异,作为分类的依据时,容易使不同的类产生混淆,使误识率增大。一般来讲,特征的类间差异应该大于类内差异。5.1.2特征的类别

特征是用于描述模式性质的一种量,从形式上看可以分为三类:

1.物理特征物理特征是比较直接、人们容易感知的特征,一般在设计模式识别系统时容易被选用。如为了描述指定班级中的某个学生,可以用以下物理特征:性别、身高、胖瘦、肤色等外在特征。物理特征虽然容易感知,却未必能非常有效地表征分类对象。

2.结构特征结构特征的表达能力一般要高于物理特征,如汉字识别的成功实现离不开结构特征的选择。结构特征的表达是先将观察对象分割成若干个基本构成要素,再确定基本要素间的相互连接关系。通过要素和相互连接关系表达对象,可以较好地表达复杂的图像图形信息,在实际中已经有较多的成功应用,如指纹的识别就是基于结构信息完成的。结构信息对对象的尺寸往往不太敏感,如汉字识别时,识别系统对汉字大小不敏感,只对笔划结构信息敏感。结构特征比物理特征要抽象一些,但仍属比较容易感知的特征,如人的指纹特征、人脸的五官结构信息等,是认定人的身份的重要参数。

3.数字特征一般来说,数字特征是为了表征观察对象而设立的特征,如给每个学生设立一个学号,作为标志每个学生的特征。由于学号是人为设定的,可以保证唯一性,但这种特征是抽象的,不容易被人感知。数字特征有时和观察对象的固有特性没有任何联系,有时则是物理或结构特征的计算结果。5.1.3特征的形成

在设计一个具体的模式识别系统时,往往是先接触一些训练样本,由领域专家和系统工程师联合研究模式类所包含的特征信息,并给出相应的表述方法。这一阶段的主要目标是获取尽可能多的表述特征。在这些特征中,有些可能满足类内稳定、类间离散的要求,有的则可能不满足,不能作为分类的依据。根据样例分析得到一组表述观察对象的特征值,而不论特征是否实用,称这一步为特征形成,得到的特征称为原始特征。在这些原始特征中,有的特征对分类有效,有的则不起什么作用。若在得到一组原始特征后,不加筛选,全部用于分类函数确定,则有可能存在无效特征,这既增加了分类决策的复杂度,又不能明显改善分类器的性能。为此,需要对原始特征集进行处理,去除对分类作用不大的特征,从而可以在保证性能的条件下,通过降低特征空间的维数来减少分类方法的复杂度。实现上述目的的方法有两种:特征提取和特征选择。特征提取和特征选择都不考虑针对具体应用需求的原始特征形成过程,而是假设原始特征形成工作已经完成。然而在实际工作中,原始特征的获得并不容易,因为人具有非常直观的识别能力,有时很难明确描述用于分类的特性依据。如人脸的判定,人识别脸部特征非常容易,若用计算机来识别人脸,则需要得到多达上千个特征,难度很大。可以说,特征形成是模式识别过程中的重点和难点之一。5.1.4特征提取和选择的作用特征选择是指从一组特征中挑选出对分类最有利的特征,达到降低特征空间维数的目的。特征提取是指通过映射(或变换)的方法获取最有效的特征,实现特征空间的维数从高维到低维的变换。经过映射后的特征称为二次特征,它们是原始特征的某种组合,最常用的是线性组合。从定义可以看出,实现特征选择的前提是确定特征是否有效的标准,在这种标准下,寻找最有效的特征子集。用于特征选择的特征既可以是原始特征,也可以是经数学变换后得到的二次特征。需要注意,特征提取一定要进行数学变换,但数学变换未必就是特征提取。特征提取和特征选择的主要目的都是,在不降低或很少降低分类结果性能的情况下,降低特征空间的维数,其主要作用在于:

(1)简化计算。特征空间的维数越高,需占用的计算机资源越多,设计和计算也就越复杂。

(2)简化特征空间结构。由于特征提取和选择是去除类间差别小的特征,保留类间差别大的特征,因此,在特征空间中,每类所占据的子空间结构可分离性更强,从而也简化了类间分界面形状的复杂度。5.2类的可分性判据在特征提取与选择的过程中,高维特征变为低维特征的方法很多,究竟哪种方法最有效,需要通过某种标准来衡量,在数学上就是要构造某种准则(或判据)。这些准则应能很好地反映各类间的可分性以及各特征在分类识别中的重要性或贡献,因此人们希望可分性判据满足以下要求:

(1)与错误概率(或是错误概率的上、下界)有单调关系,使判据的极大值对应错误概率的最小值或较小值。

(2)非负性,即(5-1)其中,Jij表示第i,j两类间的可分性判据。

(3)对称性,即

Jij=Jji(5-2)该特性表明有效性判据对类别号没有方向性,而只强调对区分两类的贡献。

(4)当特征独立时,判据应具有可加性,即(5-3)

(5)单调性。对于特征向量而言,加入新的特征分量不会减少判据值,即(5-4)5.2.1基于距离的可分性判据

模式识别的结果实际上是将特征空间划分为不同类的决策区域。为了有利于分类,我们总是希望不同类之间的距离大一些,而同类的样本较集中,这样类别的可分性才越好。因此,利用类间距离构造类别的可分性判据是可行的。

1.两类之间的距离设两类为ωi、ωj,分别有Ni、Nj个样本,即(5-5)(5-6)两类间的距离可由下式给出:(5-7)其中,D(xir,xjs)为向量xir、xjs间的距离。由点间距离的对称性可知,类间距离也具有对称性。常用的点间距离有以下几种:

(1)欧几里德(Euclidean)距离:(5-8)其中,d为向量的维数。

(2)加权欧几里德距离:(5-9)

(3)汉明(Hamming)距离:(5-10)(4)马氏(Mahalanobis)距离:(5-11)其中,M为一正定阵,wij为矩阵M－1的元素。

(5)明可夫斯基(Minkowsky)距离:(5-12)其中:当q=1时,D(x,y)为汉氏距离;当q=2时,D(x,y)为欧氏距离。

(6)切比雪夫(Chebyshev)距离:(5-13)

2.各类样本之间的平均距离设N个样本分别属于m类,ωi={xik,k=1,2,…,Ni},i=1,2,…,m,各类之间的平均距离为(5-14)其中,是先验概率P(ωi)的估计,即N为样本总数,即若点间距离取欧氏距离的平方,以表示第i类的向量平均值,以表示的统计平均值,即(5-15)(5-16)(5-17)则式(5-14)可化为(5-18)且有关系式(5-19)令(5-20)(5-21)则(5-22)式(5-20)、式(5-21)和式(5-22)中的分别是利用有限样本集得到的类均值μi、总体均值μ、类内离散度矩阵Sw和类间离散度矩阵Sb的估计值,μi、μ,Sw、Sb的定义式如下:(5-23)(5-24)(5-25)(5-26)为了使所使用的特征能够有效地进行分类,我们希望类间离散度尽量大,同时类内离散度尽量小,从直观上看可以构造下面各种判据:(5-27)(5-28)(5-29)(5-30)(5-31)为了有效地分类,它们的值越大越好。基于距离的可分性判据虽然简单直观,但只是对于类间无重叠的情况效果较好,若类间存在重叠,则效果会受到影响。基于概率的可分性判据能够较好地解决类间有重叠的问题。5.2.2基于概率密度函数的可分性判据基于概率密度函数的可分性判据主要考虑的是两类的概率分布情况。考虑如图5-1所示两种极端情况,容易看出,图5-1(a)中两类是完全可分的,图5-1(b)中两类是完全不可分的,两类概率密度函数的重叠程度反映了两类的可分性,因此,可以利用类条件概率密度函数构造可分性判据。图5-1一维情况下两类类条件概率密度分布情况两类概率密度函数完全分开；两类概率密度函数完全重叠基于类条件概率密度函数p(x|ω1)、p(x|ω2)的可分性判据Jp应满足以下四个条件:

(1)非负性:(5-32)(2)对称性:(5-33)(3)最大值:当两类完全可分时,Jp具有最大值。

(4)最小值:当两类完全不可分时,Jp具有最小值,即Jp=0。下面介绍三种典型的基于概率密度函数的可分性判据。

1.巴氏(Bhattacharyya)距离

Bhattacharyya距离的定义式为(5-34)它与最小错误概率判决准则的错误概率Pe具有如下关系:(5-35)证明过程如下:

2.切诺夫(Chernoff)界限距离

Chernoff界限距离的定义式为(5-36)由定义式可见,当s=1/2时,Chernoff界限距离就是Bhattacharyya距离。一般情况下JC的计算比较困难,当ω1、ω２的类条件概率密度函数分别为正态分布密度函数(μi,Σi)和(μj,Σj)时,可以推导出(5-37)

3.散度

在第2章的讨论中,对于两类的分类问题,最大后验概率判决准则可以通过似然比和某个阈值的比较实现,显然似然比对于分类来说是一个重要的度量。对于给定某个阈值,P(ω1|x)/P(ω2|x)越大,对类ω1来讲可分性越好,该比值反映了两类类条件概率密度函数的重叠程度。为了保证概率密度函数完全重叠时判据为零,应对该比值取对数。又因为x具有不同的值,应该考虑类ω1的均值。定义类ω1相对于类ω2的平均可分性信息为(5-38)类ω2相对于类ω1的平均可分性信息为(5-39)对于ω1和ω2两类总的平均可分性信息称为散度,其定义为(5-40)将式(5-38)、式(5-39)代入式(5-40)可得(5-41)5.2.3基于熵函数的可分性判据由信息论可知,对于一组概率分布而言,分布越均匀,平均信息量越大,分类的错误概率越大;分布越接近0-1分布,平均信息量越小,分类的错误概率越小,可分性越好。因此,可以建立基于熵函数的可分性判据,其中熵函数表征平均信息量。对于后验概率P(ωi|x)而言,分类效果最不好的情形为m类分布等概率的情形:(5-42)分类时任取一类判决,正确率为1/m,错误率为(m－1)/m。若后验概率为0-1分布,即(5-43)则应判x对应的模式属于第i类,错误概率等于0。从特征选择与提取的角度看,人们希望采用具有最小不确定性的那些特征进行分类,也就是保留熵函数小的特征。为此可定义基于熵函数的可分性判据:(5-4４)由上式可知,H是P(ω1|x),P(ω2|x),…,P(ωm|x)的函数,它满足以下几个条件:

(1)非负性:H≥0(5-45)(2)对称性:(5-46)(3)最小值:完全可分出现在后验概率为0-1分布的情形:(5-47)此时信息熵具有最小值。

(4)最大值:最大值对应分类效果最不好的情形。在多类情况下,分类效果最差的出现条件是各类后验概率相等,即(5-48)满足上述性质的广义熵表达形式很多,作为一个广义熵的表述,其定义为(5-49)其中α是一实的正参数,α≠1。对应不同的α值可得到不同的可分性判据。当α→1时,根据洛必达法则可得Shannon熵(5-50)当α=2时,可以得到平方熵(5-51)由于需要考虑到特征空间中每个样本点的熵函数,因此用熵函数在整个特征空间的统计平均(5-52)作为可分性判据。5.3基于可分性判据的特征提取特征提取作为一种特征空间维数压缩方法,其主要特点在于通过变换的方法实现对原始特征的计算,使变换后的二次特征可以去掉一些分量。从数学上看,任何定义在原始特征空间上的任何数学计算都是一种变换。本节主要讨论线性变换。对于任何一种给定的线性变换而言,变换后的特征是否对分类有效,决定了变换方法的有效性。考虑到特征的有效性是由可分性判据来表征的,因此,变换方法的有效性可以借助于变换结果的有效性表达。可分性判据的基础主要有三类:距离、概率密度函数和熵函数,因此,基于可分性判据的特征提取方法也有相应的三种:基于距离可分性判据的特征提取方法、基于概率密度函数可分性判据的特征提取方法和基于熵函数可分性判决的特征提取方法。上述方法的基本思路如下:对于n个原始特征构成的特征向量x=(x1,x2,…,xn)T,特征提取就是对x作线性变换,产生d维向量y=(y1,y2,…,yd)T,d≤n,即y=WTx

(5-53)式中,W=Wn×d称为特征提取矩阵或简称变换矩阵。基于可分性判据的特征提取就是在一定的可分性判据下,如何求最优的变换矩阵W。5.3.1基于距离可分性判据的特征提取方法前面研究了基于距离的可分性判据,得到了相应判据,它们都反映了一个基本思想,即类内距离小和类间距离大的要求。下面我们以J2准则为例讨论特征提取的方法。设Sw和Sb为原始特征空间的类内离散度矩阵和类间离散度矩阵,S*w和S*b为变换后特征空间的类内离散度矩阵和类间离散度矩阵,W为变换矩阵。则有(5-54)(5-55)在变换域中,(5-56)为了求使J2(W)最大的变换,就要求J2(W)对W的各分量的偏导数为零。这里我们不做详细的推导,只给出求解变换矩阵的解析解法。设矩阵S-1wSb的特征值为λ1,λ2,…,λn,按大小顺序排列为相应的正交化、归一化的特征向量为选前d个特征向量作为变换矩阵:此结论对于J4判据也适用。5.3.2基于概率密度函数可分性判据的特征提取方法基于概率密度函数的可分性判据的方法需要知道各类的概率密度函数的解析形式,难度较大,计算量也较大。一般地,只有当概率密度函数为某些特殊的函数形式时才便于使用,这里只研究多元正态分布的两类问题。对于基于概率密度函数可分性判据的特征提取方法而言,通常选用的变换仍为线性变换,设n维原始特征向量x经线性变换后的二次特征向量为y,即(5-57)在映射后的特征空间内建立某种准则函数,使得它为变换矩阵W的函数:(5-58)其中,Jc为基于概率密度函数的可分性判据,如前面介绍的Bhattacharyya距离和Chernoff距离等可分性判据。通过求解判据的极值点即可得到使映射后的特征组可分性最好的变换矩阵。在Jc(W)可微的情况下,就是求解偏微分方程:(5-59)下面以Chernoff距离为例,分析特征提取方法。当两类都是正态分布时,两类的分布函数分别为(5-60)(5-61)变换后的判据Jc是W的函数,记为Jc(W)(5-62)式中,M=(μ1－μ2)(μ1－μ2)T。因为Jc(W)是标量,可以对W的各个分量求偏导,并令其为零,简化后的矩阵方程为(5-63)上式是W的非线性函数,只能采用数值优化的方法得到近似最优解。但是在以下两种特殊情况下可以得到最优的解析解。

1)Σ1=Σ2=Σ,μ1≠μ2

在此种情况下,最优特征提取矩阵是由Σ-1M矩阵的特征向量构成的。又因为矩阵M的秩为1,故Σ-1M只有一个非零特征值,对应于特征值为零的那些特征向量对Jc(W)没有影响,因此可以舍去,所以最优变换W是Σ-1M的非零特征值对应的特征向量v,不难得到W=v=Σ-1(μ1－μ2)(5-64)这个结果与Fisher的线性判别式的解相同。

2)Σ1≠Σ2,μ1=μ2

在此种情况下,最优特征矩阵是由Σ-12Σ1满足下列关系:(5-65)的前d个特征值所对应的特征向量构成的,此时Jc(W)取最大值。5.3.3基于熵函数可分性判据的特征提取方法

基于熵函数的可分性判据的提出,主要是考虑不同分布特性对判决的影响。当多类的分布呈均匀分布时,信息熵为最大值,此时具有最差的可分性。当多类呈0-1分布时,信息熵达到最小值,此时,具有最好的可分性。基于信息熵的可分性判据和信息熵呈反比关系,为了提取出熵函数可分性判据意义上的最佳特征组,也是选择线性变换,可将变换矩阵带入判据表达式:(5-66)(5-67)通过求解判据的极值点即可得到使映射后的特征组可分性最好的变换矩阵。在JH(W)可微的情况下,就是求解偏微分方程:(5-68)求出极值点即为所求的线性变换,在本书中不展开讨论,有需要者可参看有关参考文献。5.4主分量分析(PCA)一种处理多维的方法是采用组合特征的方法来降低维数,其中,特征的线性组合计算简单且能够进行解析分析。从本质上来说,线性变换就是将高维空间的数据投影到低维空间的过程。主分量分析是一种有效的特征线性变换方法,也称为K－L变换。K－L变换是一种基于目标统计特性的最佳正交变换,它的最佳性体现在变换后产生的新的分量正交或不相关。设n维随机向量x=(x1,x2,…,xn)T,x经标准正交矩阵A正交变换后成为向量y=(y1,y2,…,yn)T,即(5-69)y的相关矩阵为(5-70)其中,Rx为x的相关矩阵,是对称矩阵。选择矩阵A=(a1,a2,…,an),且满足(5-71)这里,λi为Rx的特征根,并且λ1≥λ2≥…≥λn,ai为λi的正交化、归一化特征向量,即aTiai=1,aTiaj=0(i≠j;i,j=1,2,…,n)。Ry是对角矩阵:(5-72)若Rx是正定的,则它的特征值是正的。此时变换式(5-69)称为K-L变换。由式(5-69)可得(5-73)我们选择x关于ai的展开式的前m项在最小均方误差准则下估计x,这时估计式表示为(5-74)估计的均方误差为(5-75)我们希望选择使估计的均方误差最小的特征向量,因此要选择相关矩阵Rx的m个最大的特征值对应的特征向量构成变换矩阵A,这样得到的均方误差将会最小,是n－m个极小特征值之和。可以证明,与m维向量中的其他x逼近值相比,这个结果是最小均方误差解。这就是K-L变换也称为主分量分析(PCA)的原因。上述分析中采用的是样本的相关矩阵,也可以采用样本的协方差矩阵进行分析。例如,在人脸识别中,PCA是一种常用的特征提取方法。设一幅p×q大小的人脸图像,可以将它看成是一个矩阵(fij)p×q,fij正比于图像在该点的灰度级。若将该矩阵按列相连构成一个p×q维向量x=(f11,f21,…,fp1,f21,f22,…,fp2,…,f1q,f2q,…,fpq)T

。设训练样本集为X={x1,x2,…,xN},包含N个图像。其协方差矩阵为(5-76)其中，(5-77)求出矩阵R的前m个最大特征值λ1,λ2,…,λm及其对应的正交化、归一化特征向量α1,α2,…,αm。分别将这m个特征向量化为p行q列矩阵,得到m幅图像,称为“特征脸”。图5-2显示的是对应前30个最大特征值的特征向量的图像。图5-2“特征脸”图像将每一幅人脸图像投影到由a1,a2,…,am张成的子空间中,对应于该子空间的一个点,该点的坐标系数对应于图像在子空间的位置,可以作为识别人脸的依据。对于任意待识别样本y,可通过向“特征脸”子空间投影获得系数向量y′=(a1,a2,…,am)Ty。5.5独立分量分析(ICA)独立分量分析(IndependentComponentAnalysis,ICA)的基本思路是在特征空间上寻找到最能使数据相互独立的方向。5.5.1

ICA概述

1.ICA的定义为了给出ICA的严格定义,我们可以使用统计上的“隐变量”模型。假设观测变量x=(x1,x2,…,xn)T可由n个独立分量y1,y2,…,yn线性组合得到:(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的目的就是在只给出观察样本集时,求出解混合矩阵W和人脸图像的独立图像集Y。图5-3

ICA人脸图像合成与分解过程

ICA所提取的人脸图像的特征向量是每个人脸图像在这些独立图像上的投影系数V=(v1,v2,…,vN)T,如图5-4所示图5-4

ICA提取人脸特征向量

2.ICA的约束为了保证上面给出的ICA模型能够被估计出来,我们必须给出一定的假设和约束。

(1)独立分量是统计独立的。该假设是ICA能够成立的前提,为保证模型能够被估计,这个约束已经基本足够,这也是ICA能够在许多领域的应用中成为强有力的方法的原因。

(2)混合矩阵A是方阵并且可逆。这个假设说明独立分量的个数与样本的个数是相同的。这个假设在某些情况下是不严谨的,但该假设可以大大简化估计过程。

(3)独立分量必须具有非高斯分布。高斯分布是非常简单的一种统计分布,其所有高阶累计量都为零,但这样的高阶信息对于估计ICA模型却是必需的。可以通过一个例子来解释:考虑一个只有两个观测的ICA模型,假定混合矩阵是正交的,独立分量yi为高斯分布,具有单位方差,因为观察变量x1和x2是独立源的线性组合,故x1和x2也是不相关的具有单位方差的高斯随机变量,那么它们的联合概率密度函数为(5-81)从图5-5可以看出,分布是完全对称的,因此,它不提供任何混合矩阵A各列的方向信息,也就是说无法估计出A。在多个独立成分是高斯的,其他独立成分是非高斯的情况下,可以估计出所有的非高斯成分,但是无法估计出其中的高斯成分,因为估计出的高斯成分可能是那些高斯成分的某种线性组合。因此,在独立分量分析中,应该假设至多只有一个独立分量为高斯分布,否则就无法估计出ICA模型。图5-5式（5-81）图解

3.ICA的预处理

在应用ICA之前,通常要对数据作些预处理,使得ICA估计更加简单,更符合前面约定的条件。

1)中心化不失一般性,我们可以假定所有混合变量与独立分量均具有零均值,这样可以在一定程度上简化理论和算法。如果实际情况不满足零均值假设,则我们可以通过中心化处理使其满足要求。中心化其实就是去均值,将随机变量的中心移向零点。去均值是为了简化ICA的估计算法。用经过去均值处理的数据估计独立分量y,再把y的均值A-1m加回去即可,其中m为x的均值。

2)白化给定一组样本,通过线性变换将它们转变为相互无关的方法称为白化。将样本x通过一个白化滤波器,得到白色的,其目的是为了加快收敛速度。的元素是不相关的,而且具有单位方差。也就是说,的协方差矩阵是一个单位阵,即(5-82)通常白化处理采用特征值分解的办法。假定E(xxT)=QΛQT,其中Q为E(xxT)的特征向量阵,Λ为特征值对角阵,则下式可完成对数据的白化处理:(5-83)这里,，。为白化变换矩阵,它不是唯一的。容易看出,任何矩阵UM(U为正交矩阵)也是白化矩阵。显然,也是白化矩阵。5.5.2基于累积量的ICA估计

ICA有多种不同的估计原理和算法,但就其本质而言,都是先设计一个目标函数,然后选择某种优化算法使目标函数达到极值。我们可以用下面的“方程”来表达这一点:ICA方法=目标函数+优化算法在目标函数明确的情况下,我们可以使用任何经典的优化算法,比如(随机)梯度法和牛顿法等。ICA方法的性质依赖于目标函数和优化算法,特别地,ICA的统计特性(如一致性、渐进方差、鲁棒性)取决于目标函数的选择;算法的性质(如收敛速度、存储需求、数值稳定性)取决于优化算法。常用的ICA估计方法有极大化非高斯性的ICA估计方法、ICA的极大似然估计方法、极小化互信息的ICA估计方法、基于高阶累积张量的ICA估计方法、基于非线性去相关和非线性PCA的ICA估计方法等。这里主要介绍基于2阶和4阶累积量的ICA估计以及ICA的极大似然估计方法,其他方法可以参考相关文献。

ICA方法是根据PCA方法直接生成的。K-L变换使用2阶统计量,变换后特征之间的交叉相关性为零,相应地,变换后样本的相关矩阵是对角矩阵。在ICA中,变换后特征之间是统计独立的,也就是说,要求所有高次的交叉累积量为零。交叉累积量是指累积量中至少有两个变量不同,例如k2(y1y2);若累积量中所有变量都相同,则称为自累积量,例如k4(yiyiyiyi)=k4(yi)为4阶自累积量。将运算限制在4阶对很多应用已经足够了,因此,我们只讨论4阶累积量。y的4个累积量分别为(5-84)(5-85)(5-86)(5-87)在实际应用中,经常会遇到均值为零且概率密度函数是对称的情况,在这种情况下，所有奇数阶累积量为零,所以,问题可以简化为寻找一个矩阵W,使得变换后特征之间的2阶和4阶交叉累积量为零。具体的计算步骤如下:

(1)对输入数据进行PCA变换,即(5-88)其中B是K-L变换中的正交矩阵。因此变换后的各分量之间是不相关的。

(2)计算另一个正交矩阵,使得变换后的样本各分量的4阶交叉累积量为零(5-89)这等同于寻找一个矩阵，使得4阶自累积量的平方和最大,即(5-90)上面两个步骤完成后,最后逼近的独立分量的特征向量可以由下式得到(5-91)5.5.3ICA的极大似然估计方法估计ICA模型的一个常用方法是极大似然估计方法,其基本思想是采用那些使所得观测量具有最大概率的参数估计值。混合向量x=Ay的概率密度函数可以写为(5-92)式中,W=A-1,pi表示独立分量的概率密度函数。上式可以表示为矩阵W=(w1,w2,…,wn)T和向量x的函数(5-93)假设有x的T个观测值x(1),x(2),…,x(T),那么似然函数可以通过将T个点密度估计相乘得到,似然函数记为L,将它作为W的函数(5-94)在实际中普遍使用对数似然函数以方便运算，对数似然函数可由下式给出：(5-95)式(5-94)和式(5-95)表明,要进行极大似然估计,先要估计出独立分量的概率密度函数,这是非常困难的。为了得到极大似然估计,需要能够极大化似然函数的数值算法。这里介绍广泛使用的自然梯度法和FastICA算法。

1.自然梯度法利用梯度法求解极大似然估计的算法为(5-96)其中:期望运算E是从观测数据中计算的平均值,并非理论上的数学期望;y=Wx;g(y)是一个逐元素的向量函数,即(5-97)也可以使用该算法的随机版本,即忽略其中的期望运算,且在算法中每次只使用一个数据点,即(5-98)这种算法经常称为Bell-Sejnowski算法。梯度法收敛速度非常缓慢,改进措施是对数据作白化处理,以及采用自然梯度。自然梯度方法也称为相对梯度方法,它在相当程度上简化了原来的梯度方法。自然梯度的原理比较复杂,抛开数学原理,具体实施办法相当于在式(5-98)右边乘以WT=W,这样得到(5-99)该算法可以解释为非线性去相关。在梯度法的运行过程中,g(y)=［g1(y1),g2(y2),…,gn(yn)］T中函数gi(i=1,2,…,n)在两种非线性函数之间选择,根据下面矩的值来确定:(5-100)若γi>0,则=

(5-101)否则=或=(5-102)其中(5-103)在迭代过程中,可以对γi进行更新,利用γi的更新值,结合式(5-101)和式(5-102)选择函数gi,得到进而更新W,再更新y,即(5-104)(5-105)(5-106)其中:μ和μγ为学习速率;W和γi(i=1,2,…,n)的初始值可以随机选取,或利用先验信息选取。

2.

FastICA算法在许多不需要自适应地调整参数的场合,梯度法反而会出现问题,而且梯度法的收敛速度经常是比较慢。astICA算法正是针对这种情况而提出的,也是各种文献中提的较多的一种算法。FastICA算法的学习准则就是找到一个单位向量,以便投影向量的非高斯性最大。

FastICA的基本迭代公式如下:(5-107)式中：，，，，g′是g的导数,，，这里所有的gi都固定为tanh函数。每步迭代后,矩阵W必须投影为白化矩阵:(5-108)式中:C=E(xxT)是数据相关矩阵;矩阵(WCWT)-1/2可以通过求矩阵平方根的经典方法来实现。具体方法如下。矩阵WCWT的特征值分解为(5-109)其中:E为WCWT的正交化、归一化特征向量组成的正交矩阵;D=diag(d1,d2,…,dn)为对角矩阵,di为WCWT的特征根。令，可得(5-110)容易验证,(WCWT)-1/2W是白化矩阵。5.6基于核函数的方法

5.6.1基于核函数方法的基本思想前面几节讨论的特征提取方法所采用的变换都是线性变换,然而,实际中遇到的问题往往较复杂,呈现出非线性特性,对于这种非线性问题,我们可以利用核函数加以解决。基于核函数的特征提取方法的基本思想是,通过一个映射将输入样本映射到高维特征空间中,使之变为线性问题,然后在高维空间中利用前面提到的线性特征提取方法间接地解决非线性特征提取问题。设非线性映射为:Φ:Rd→H,x→Φ(x),其中,H为某个Hilbert空间。如果在高维空间H中只涉及Φ(xi)的内积运算,即〈Φ(xi),Φ(xj)〉,而没有单独的Φ(xi)出现,则可以用原始空间的函数实现这种内积运算,而没有必要知道非线性映射Φ的具体形式。统计学习理论指出,根据HilbertSchmidt原理,只要一种运算满足Mercer条件,它就可以作为这里的内积使用。

定理5.1(Mercer条件)对于任意的对称函数K(x,y),它是某个Hilbert空间H的内积函数的充分必要条件是,对于任意的Φ(x)≠0且有(5-111)其中,函数K(x,y)称为核函数,K(x,y)=〈Φ(x),Φ(y)〉。核函数方法逐步成为一种重要的,将非线性问题线性化的普适方法,例如:

(1)将核函数方法用于主分量分析(PCA)得到基于核函数的主分量分析方法(KPCA),从而将原本用于线性相关分析的PCA方法扩展到了非线性相关分析的领域;

(2)将核函数方法用于独立分量分析(ICA)得到基于核函数的独立分量分析(KICA),使得原本用于分解独立信号线性叠加的ICA方法也可以用于独立信号的非线性混叠;

(3)将核函数方法用于线性判别分析(LDA)得到核线性判别分析(KLDA);

(4)支持向量机通过引入核函数,有效地解决了模式分类中的线性不可分问题。可见,以前解决线性问题时的许多技术手段,都可以尝试通过核函数方法扩展到非线性领域。5.6.2基于核函数的主分量分析在5.4节中讨论的PCA方法是在最小均方误差准则下,找到一个d维子空间,使其能够最好地表达原始的高维数据。如果原始数据存在复杂的非线性关系,那么线性子空间的表示性能将很差。为了使PCA方法能够处理非线性问题,将核函数方法的思想引入PCA,得到基于核函数的主分量分析(KPCA)。

KPCA算法的基本思想是,对于一个非线性问题,先通过一个非线性映射函数Φ:Rd→H,将原空间Rd中每个向量x映射到一个高维线性特征空间H中,然后,在高维空间H中进行线性PCA。高维空间的线性PCA对于原始空间来说就是进行非线性PCA。设Φ(xi)(i=1,2,…,N)已经去均值,即，则Ｈ空间上样本集的协方差矩阵为(5-112)这时,高维空间H中的PCA就是求解(5-113)将高维空间中的每个样本与式(5-113)作内积可得(5-114)假设特征空间H中的所有向量都可由Φ(xi)(i=1,2,…,N)线性表示,即(5-115)合并式(5-112)、式(5-113)和式(5-115),可得(5-116)定义一个N×N核矩阵K=(Kij),其中(5-117)则式(5-116)可简化为(5-118)因为满足(5-119)的解必然满足式(5-118)。通过求解式(5-119)可获得要求的特征值和特征向量。结合式(5-115)可知,由矩阵K的特征向量α=(α1,α2,…,α/N)T可以求出C的特征向量v,得到特征空间的主元方向。矩阵K可以通过选择核函数来确定。对矩阵K实行对角化,用λΦ1≥λΦ2≥…≥λΦN表示其特征值,α(1),α(2),…,α(N)为相应的正交化、归一化特征向量,选择前m个非零特征根λΦ1,λΦ2,…,λΦm及其特征向量α(k)=(α(k)1,α(k)2,…,α(k)N)(k=1,2,…,m)。由式(5-116)可(5-120)为了提取主元特征,计算测试样本在H空间中向量v(k)上的投影系数为(5-121)其中:x为原始空间的输入向量;Φ(x)为高维空间的映射向量。上述算法是在假设映射数据均值为零的情况下推导的,但实际上由于没有显示的映射函数Φ,所以不能直接去除均值。一种方法是直接用H空间上样本集的相关矩阵代替C;另一种方法是先不去均值求得K,然后求(5-122)其中:K为去均值前的核矩阵;为去均值后的核矩阵;IN是所有元素为1/N的矩阵。5.6.3基于核函数的独立分量分析和主分量分析法一样,独立分量分析(ICA)也是一种基于线性模型的方法,将核函数的思想应用于ICA,将其扩展到非线性的形式就得到基于核函数的独立分量分析(KICA)。与KPCA算法一样,首先进行一个非线性映射Φ:Rd→H,将原空间Rd中每个向量x映射到一个高维线性特征空间H中,然后在高维特征空间中进行ICA变换。在高维特征空间中首先要对Φ(xi)进行白化处理,这里的白化过程就是要在高维特征空间中求解协方差矩阵的特征值和对应的特征向量。这个问题在KPCA算法中已得到解决。在KPCA算法中,通过求解特征方程NλΦα=Kα得到特征值和对应的特征向量,这里的矩阵K的元素为k(xi,xj)=〈Φ(xi),Φ(xj)〉。由此求出的特征向量为和相应的特征值λΦ1,λΦ2,…,λΦm。设VΦ=(v(1),v(2),…,v(m)),这样高维空间中的白化变换矩阵为(5-123)高维特征空间中白化后的样本为。的计算不涉及非线性映射Φ的具体形式,只与两个函数的内积有关,即核函数。得到后,再通过FastICA算法求出相应的分离矩阵WΦ。5.6.4基于核函数的Fisher线性判别在第4章介绍的Fisher线性判别方法适用于样本线性可分的条件,但是实际的很多模式识别问题并不具备线性可分性,这时Fisher线性判别就显得无能为力,因此必须寻找另一种途径,解决更为复杂的问题。一个可行性的方法就是利用核函数的思想先把样本数据采用某一非线性映射进行预处理,然后应用线性方法解决问题。将核方法的思想引入Fisher线性判别,得到基于核的Fisher线性判别方法(KFDA)。

KFDA克服了线性Fisher判别法的局限性,利用非线性映射实现输入空间Rd到高维空间H的映射,即Φ:Rd→H。设输入空间的样本集合共有N个样本{x1,x2,…,xN},这些样本通过非线性映射形成高维空间的样本集合{Φ(x1),Φ(x2),…,Φ(xN)}。在高维空间中定义Fisher线性判别的各参数如下:各类样本均值向量:(5-124)样本类内离散度矩阵SΦi和总类内离散度矩阵Sw:(5-125)(5-126)样本类间离散度矩阵SΦb:(5-127)设KFDA在高维空间H中寻找最优投影方向为w,则Fisher线性判别函数化为(5-128)使上式最大化的最佳投影方向为(5-129)根据核函数理论,w可表示为Φ(x1),Φ(x2),…,Φ(xN)的线性组合,即有(5-130)根据式(5-124)和式(5-130)可得(5-131)其中，(5-132)结合式(5-127)和式(5-130)可得(5-133)式(5-133)中,定义(5-134)结合式(5-126)和式(5-130)可得(5-135)式（5-135）中，定义(5-136)其中:Ki(i=1,2)是N×Ni矩阵,矩阵元素(Ki)jk=K(xj,xk)(xk∈ωi;j=1,2,…,N);I为Ni×Ni单位矩阵;INi为Ni×Ni矩阵,它的所有元素均为1/Ni。因此,KFDA的目标函数变为(5-137)最终,高维空间中的Φ(x)在w上的投影变换为(5-138)基于核函数的Fisher判决方法的分界点可选为(5-139)或(5-140)其中,为高维空间H中投影后的各类的平均值,(5-141)5.7特征选择方法根据特征选择的定义,要从n个特征分量中选出d个最有效的特征。一般情况下,原始特征向量的维数是已知的,在保证分类效果的前提下,压缩后的特征空间维数d未知。因此,特征选择的目的,不仅在于选出所要保留的特征,而且需确定保留多少个特征,即需要解决两个问题:什么是有效特征组;寻找有效特征组的方法。特征组可以通过上节介绍的各种可分性判据来判断其有效性。对于特征选择问题,由于选择后的特征维数未知,即d的选择范围在1~n之间的任何一个自然数,因此可以有的特征组合为(5-142)当n=100,d=10时,100个里面选10的组数为17310309456440。若d遍取1~99,则需计算的可分性判据的个数为(5-143)可见,选择范围是非常大的。因此人们提出了一系列搜索技术,其中一些是次优的,一些是最优的。5.7.1最优搜索算法

分支界定法是一种不包括穷举搜索的最优搜索方法,它的搜索过程可以用一个树结构来描述,它是一种自上而下的方法。这种方法主要利用了特征选择可分性判据的单调性,即对于两个特征子集X和Y,有。下面用一个例子来描述这种方法。假设希望从5个特征中选择最好的3个特征,整个搜索过程采用树结构表示出来,节点所标的数字是剩余特征的标号。每一级在上一级的基础上去掉1个特征。5个特征中选3个,两级即可。为了使子集不重复,仅允许按增序删除特征,这样就避免了计算中不必要的重复。假定已获得树结构如图5-6所示,我们从分支数量不密集的部分到分支数最密集的部分(图5-6中的从右到左)搜索树结构。搜索过程在总体上是由上至下,从右至左地进行。在这个过程中包含几个子过程:向下搜索、更新界值、向上回溯、停止回溯再向下搜索。图5-6分支界定法树型图图5-7中将计算出的每个节点的可分性判据值标于相应节点。开始时置界值B=0,首先从树的根节点沿最右边的一支自上而下搜索,直接到达叶节点,得到特征集(1,2,3),可分性判据值为J=77.2,此时更新界值B=77.2,搜索回溯到最近的分支节点,并向下行进到该节点下一个最右的分支,计算J({1,2,4,5}),然后计算J({1,2,4}),发现该值比当前界值小,因此抛弃该特征组合,并回溯到上一级节点,再向下搜索到节点(1,2,5)并计算J({1,2,5}),该值大于界值,则更新界值B=80.1。图5-7分支界定法搜索回溯示意图类似地计算J({1,3,4,5}),由于其值小于界值,因此中止对该节点以下部分的树结构搜索,因为根据单调性,该特征集合的所有子集的可分性判据都低于其自身的可分性判据。这时该算法回溯到最近的分支节点并向下进行到下一个最右分支(2,3,4,5)。计算J({2,3,4,5}),同样,由于其值低于界值,该节点以下的其余部分也无需计算。这样,尽管并没有计算所有三个变量的可能组合的可分性判据,但该算法仍然是最优的。该算法高效的原因在于:(1)利用了判据J值的单调性;(2)树的右边比左边结构简单,而搜索过程正好是从右至左进行的5.7.2次优搜索算法

1.单独最优特征组合从n个特征中直接选出d个特征,若要直接计算,需要计算所有可能特征组合的可分性判据以寻找其中最优的一组特征,计算量相对较大,单独最优特征组合方法提出了一种较简单的方法。单独最优特征组合方法的基本思路是,计算每个特征单独使用时的有效性判据值,并根据该值对特征进行排序,使选择前d个分类效果最好的特征作为特征集。这种方法在特征之间不相关时,能够得到合理的特征集,然而,如果特征之间是相关的,则选择的特征集将是次优的,其原因是该方法忽略了各特征之间的相关性。

2.顺序前进法顺序前进法(SequentialForwardSelection,SFS)的基本思路是从空集开始,每次从未选入的特征中选择一个特征,使它与已选入的特征组合在一起的有效性判据最大,直到选入特征数目达到指定维数为止。该方法是一种自下而上的搜索方法。

SFS法考虑了所选特征与已入选特征之间的相关性,因此其性能优于单独最优特征组合方法,但这种方法的主要缺点是一旦某个特征被选入特征组合,即使加入新的特征使它变得多余,也无法再将其剔除。

SFS法每次增加一个特征,它没有考虑未入选特征之间的相关性,为了克服这一缺点,人们将SFS算法进行推广,在增加特征时每次增加r个特征,即每次从未入选的特征中选择r个特征,使r个特征加入后有效性判据最大,这种方法称为广义顺序前进法(GeneralizedSequentialForwardSelection,GSFS)。

3.顺序后退法顺序后退法(SequentialBackwardSelection,SBS)的基本思路是从全部特征开始,每次剔除一个特征,所剔除的特征应使保留下的特征组合的有效性判据最大。该方法是一种自上而下的搜索方法。顺序后退法的计算是在高维空间中进行的,因此计算量比顺序前进法要大。此方法也可以推广到每次剔除r个特征的广义顺序后退法(GeneralizedSequentialBackwardSelection,GSBS)。

4.增l减r法

增l减r

法(l－r法)克服了前面方法中一旦特征被选入(或剔除)就不能再剔除(或选入)的缺点,在特征选择过程中允许回溯。该算法步骤如下(假设已经选入k个特征,达到特征组Xk):

(1)用SFS法在未选入的特征中逐个选入l个特征,形成新的特征组Xk+l,置k=k+l,Xk=Xk+l。

(2)用SBS法从Xk中逐个剔除r个特征,形成新的特征组Xk－r,置k=k－r,Xk=Xk－r。若k=d,则结束;否则转至(1)步。需要指出的是,若l>r,则l－r法是自下而上的算法,先执行(1),然后执行(2),起始时置

;若l<r,则l－r法是自上而下的算法,先执行(2),然后执行(1),起始时置k=N,X0={x1,x2,…,xN}。5.7.3遗传算法特征的选择是一个组合优化问题,因此可以使用解决优化问题的方法解决特征选择问题。遗传算法作为一种通用的优化算法,由于其编码技术和遗传操作比较简单,优化不受限制性条件约束以及其并行性和全局解空间搜索,越来越受到人们的重视。遗传算法主要从达尔文的生物进化论得到启迪。生物在自然界中的生存繁衍,显示出了其对自然环境优异的自适应能力。受其启发,人们致力于对生物各种生存特性的机理研究和行为模拟,为人工自适应系统的设计和开发提供了广阔的前景。基于对生物遗传和进化过程的计算机模拟,产生了遗传算法,它使得各种人工系统有优良的自适应能力和优化能力。我们习惯上把Holland在1975年提出的基本遗传算法称为经典遗传算法或者叫做传统遗传算法(CanonicalGeneticAlgorithm,CGA)。运用基本遗传算法进行问题求解的过程如下:

(1)编码:GA在进行搜索之前先将解空间的可行解数据表示成遗传空间的基因型结构数据,这些结构数据的不同组合就构成了不同的可行解。

(2)初始群体的生成:随机产生N个初始结构数据,每个结构数据称为一个个体,N个个体构成了一个群体。GA以这N个结构数据作为初始点开始迭代。

(3)适应度评估检测:适应度函数表明个体或者解的优劣性。不同的问题,适应度函数的定义方式不同。

(4)选择:是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想,进行选择的原则是适应度强的个体为下一代贡献一个或者多个后代的概率大。选择实现了达尔文的适者生存原则。

(5)交叉:是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体,新个体继承了父代个体的特性。交叉体现了信息交换的思想