基于稀疏判别分析的流形嵌入降维方法

基于稀疏判别分析的流形嵌入降维方法

0新方法及其特点在搜索、文本分类、数据处理和生物计算应用程序中面临的数据是高维的。由于维数灾难,直接处理这些数据变得非常困难。最常用的方法就是通过使用降维(DimensionalityReduction,DR)技术来降低这些高维数据的维数。降维的目的就是在低维空间中尽量真实地刻画输入数据,减少它们的复杂性,提高计算效率。基于降维后所期望得到的信息,现有的降维可以分为三类:判别方法、几何方法和基于判别和几何方法。基于可获得的先验信息,降维方法又可分为:监督方法和无监督方法。上述多数方法都可以被统一到图嵌入框架中,因此,图的构建成为这些方法的核心问题。事实上,对这些方法来说,构建一个高质量的图仍是个开放问题。目前,流形嵌入方法(manifoldembedding)使用k近邻技术和ε球近邻技术来构建近邻图(neighborhoodgraph)。一旦这种近邻图被构建,边的权值由Gaussian函数或者局部重构关系来决定。这种近邻图构建方法通常存在以下几个问题:首先,大多数算法中的近邻图是预先构建,因此,它未必有益于后续的降维工作;其次,近邻图通常是在高维空间中构建,这样构建的图在后续的工作中表现差强人意;最后,近邻图需要的两个参数,即近邻的大小(k)和热核参数(σ),通常不容易赋给合适的值。因此,在降维方法中研究图的构建显得尤为重要。另外,多数无监督降维方法在寻找投影方向过程中忽略了部分先验信息的作用,以至于它们往往不能得到最优的投影。监督降维方法需要大量有标记样本作训练样本,限制了它的应用。最近,半监督降维方法得到越来越多研究人员的关注[3,5,7,10,13,14,15]。这类方法是利用少量有标记样本和大量无标记样本寻找最优的投影方向。与监督方法相比,它更适合实际应用,与无监督方法相比,有较高的效率。然而,现有的一些半监督降维方法通常面临和流形嵌入方法相同的问题,即近邻图构建。如:半监督判别分析算法(Semi-SupervisedDiscriminantAnalysis,SDA)和半监督局部Fisher判别分析算法(Semi-supervisedLocalFisherDiscriminantAnalysis,SELF)。为了解决这些问题,本文提出一个新颖的稀疏判别分析(SparsEDiscriminantAnalysis,SEDA)算法,SEDA通过使用稀疏重建技术解决流形嵌入方法中近邻图构建问题。同时,新方法在降维过程中又能同时利用有标记和无标记样本寻找投影,提高了算法效率。具体地说,SEDA有以下4个特点。1)SEDA拥有同其他半监督降维方法(如SDA、SELF)相同的特征。如,它是线性的方法,也容易地拓展到非线性空间。因此,可以解决外样本问题。另外,SEDA使用稀疏重构技术来保存样本的几何结构,这有利于降低算法的计算复杂度。2)SEDA不需要调节模型参数,如热核宽度和近邻参数。通常,这些参数需要使用交叉验证技术给它们分配数值,但交叉验证方法既需要训练样本,还非常耗时。相比之下,SEDA不需要处理这些参数。因此,它简单实用。3)与Fisher判别分析(FisherDiscriminantAnalysis,FDA)相同,SEDA是一个全局算法。但不同的是,SEDA使用稀疏表示来重构样本,以至于它包含了局部几何信息。4)由于SEDA在求解投影向量过程中使用了有标记和无标记样本,因此,它与流形嵌入方法相比有好的效率。同时,SEDA可以容易地拓展到监督降维中。1基于成对约束的类标记根据先验信息的不同类型,半监督降维方法一般可分为两类:一类是使用有类标号的样本来引导降维过程;另一类是使用成对约束(must-link和cannot-link)来指导降维[3,5,7,10,15,20,21]。事实上,使用有类标号的样本可以得到成对约束,但不能由成对约束得到样本的类标号。因此,这两类方法之间存在着一定的相关性。下面简单回顾三个有代表性的半监督降维算法。1.1构建近邻图的基本思想半监督判别分析算法(SDA)是一个较为流行的基于样本标号的半监督降维方法。它使用基于FDA判别准则寻找投影,其实质是FDA的半监督化。SDA首先需要刻画高维空间中近邻样本之间的关系。详细地说,给定一个样本集X,构建一个k近邻的近邻图G来建模近邻样本之间的关系。如果图中两个顶点xi和xj互为近邻,那么它们之间就存在一条边,相应的权值矩阵为P,其定义如下:Ρij={exp{-∥xi-xj∥22σ2}‚xi∈Νk(xj)或xj∈Νk(xi)0,其他(1)构建近邻图的目的是高维空间中的两个近邻样本被投影到低维空间时,自然地期望这两个样本仍保持近邻。为此,最小化下列目标函数:JL(a)=∑i,j(aΤxi-aΤxj)2Ρij(2)进一步简化式(2),得到:JL(a)=aTX(D-P)XTa=aTXLXTa(3)其中,L=D-P,P是对称矩阵,Dii=∑jΡij。SDA优化下面的目标函数:maxaaΤSbaaΤ(St+ηXLX)a(4)最大化式(4)求解上述最优的投影向量,等价于求解下面的广义特征值问题:Sba=λ(St+ηXLX)a(5)1.2sldr的特征及类型化半监督局部维数约减(Semi-supervisedLocalDimensionalityReduction,SLDR)旨在利用成对约束找到最优的投影方向。它的思想是当数据被投影到低维空间时,涉及到cannot-link约束中样本点对之间距离更远、must-link约束中样本点对之间距离更近,并保持数据的内在几何信息。SLDR最小化下面的目标函数:J(a)=12n∑i,j(aΤxi-aΤxj)2Ρij-12n∑i,j(aΤxi-aΤxj)2+12nΜ∑(xi,xj)∈Μ(aΤxi-aΤxj)2-12nC∑(xi,xj)∈C(aΤxi-aΤxj)2(6)其中:M是must-link约束集合,C是cannot-link约束集合。式(6)中第一项表达了在低维空间中无标号样本的近邻关系,其实质是局部保持投影(LocalityPreservingProjection,LPP);第二项描述在投影空间中所有样本之间的平均距离,该项使用的是主成分分析(PrincipalComponentAnalysis,PCA)标准;第三项和第四项刻画成对约束的属性。SLDR的优点在于利用无标号样本的局部信息、全局信息以及成对约束关系求解投影方向,提高算法性能;另一方面,在成对约束较少时,能比其他两个半监督降维算法得到更稳定的解。为了进一步刻画SLDR的目标函数,式(6)可以改写成下列形式:J(a)=12∑i,j(aΤxi-aΤxj)2Fij(7)其中:Fij={Ρij-1n+1nΜ,(xi,xj)∈ΜΡij-1n-1nC,(xi,xj)∈CΡij-1n,其他(8)简化式(7),得到:JF(a)=aTX(D-F)XTa=aTXLXTa(9)其中L=D-F,矩阵D是对角阵,且Dii=∑jFij。SLDR优化下面的目标函数:minJ(a)=aTXLXTas.t.aTa=1(10)显然,最小化目标函数(10),SLDR寻找的最优投影向量由求解式(11)的广义特征值问题得到:XLXTa=λa(11)1.3正则化局部类间散布矩阵半监督局部Fisher判别分析(SELF)借助于部分有类标号样本解决多模态数据降维问题。与SDA相似,它也是FDA的一个半监督化变异。SELF分别定义如下的正则化局部类间散布Srlb和正则化局部类内散布矩阵Srlw:Srlb=(1-β)Slb+βSt(12)Srlw=(1-β)Slw+βId(13)其中Slb和Slw分别描述类间近邻样本的散布矩阵和类内近邻样本的散布矩阵,它们的表达形式如下:Slb=12n′∑i,j=1Wlbij(xi-xj)(xi-xj)Τ(14)Slw=12n′∑i,j=1Wlwij(xi-xj)(xi-xj)Τ(15)SELF寻找的最优投影向量转换为求解广义特征值问题得到:Srlba=λSrlwa(16)2前l个样本的标记类型给定数据集X=[x1,…,xl,xl+1,…,xn](xi∈Rd),其中:前l个样本是有标号的,属于c个类,{xl+1,…,xn}是无标号样本集。稀疏判别分析算法(SEDA)需要找到一个变换矩阵A=[a1,…,ar]∈Rd×r,将n个样本投影到低维空间里:yi=ATxi∈Rr;r<d(17)2.1稀疏矩阵的计算和描述既然近邻图的构建存在问题,在这一小节里,采用稀疏表示来构建稀疏图,克服近邻图的不足。稀疏表示首先要为每个重构的样本xi寻找一个稀疏权值,为此,最小化l1范式:minsi∥si∥1s.t.xi=Xsiand1=1Τsi(18)其中:si=[si1,…,si,i-1,0,si,i+1,…,sin]T是n维向量,其第i个元素是0表示xi从X中移掉,其他元素j≠i表示使用xj重构xi;1是个n维元素都是1的向量。使用Lasso方法能有效地计算出式(18)中的最优稀疏向量si。这组最优稀疏向量构成了稀疏矩阵S=[s1,s2,…,sn]。显然,sij不是像LPP算法中那样简单地描述样本xi和xj之间的相似性度量。因此,S不等同于流形嵌入方法中的邻接权值矩阵P(如式(1)所示)。事实上,S在某种程度上刻画出数据内在的几何信息,并自然地保持判别信息。因此,有了稀疏矩阵S,使用低维嵌入刻画高维空间中样本时,自然地能够保存输入数据特有的属性。如同其他流形算法,使用所有样本构建如下的目标函数:Jr(a)=1nn∑i=1∥aΤxi-aΤXsi∥2(19)式(19)等价于稀疏保持投影。进一步简化(19)得到:Jr(a)=aΤX(1n(Ι-S-SΤ+SΤS))XaΤ=aΤXΜXaΤ(20)其中M为:Μ=1n(Ι-S-SΤ+SΤS)(21)2.2稀疏解决方案给l个有标号样本{x1,x2,…,xl},构建类间散布矩阵Sb和类内散布矩阵Sw:Sb=c∑k=1nk(uk-u)(uk-u)Τ(22)Sw=c∑k=1∑xi∈Ck(xi-uk)(xi-uk)Τ(23)其中:uk是第k类的样本均值,u是所有l个样本的均值。显然,St=Sb+Sw。借助于Fisher判别标准,SEDA优化下面的目标函数:maxaaΤSbaaΤ(St+ηXΜX)a(24)最大化上述目标函数,求解最优的投影向量转变为由求解下面式子的广义特征值问题,得到:Sba=λ(St+ηXMX)a(25)式(25)前r个最大特征值对应的特征向量,构成所求的投影矩阵A=[a1,…,ar]。基于上述分析,稀疏判别分析算法(SEDA)如算法1所示。算法1SEDA。输入:给定样本集{x1,…,xl,xl+1,…,xn},l个有标号样本{x1,x2,…,xl},n-l个{xl+1,…,xn}样本没有类标号。输出:一个投影矩阵A∈Rd×r。1)构建一个稀疏图G,并使用式(18)和(21)分别计算稀疏权值矩阵S和矩阵M;2)根据(22)和(23),计算类间散布矩阵Sb和类内散布矩阵Sw,并得到总散布矩阵St;3)计算式(25)的广义特征值问题,输出A=[a1,…,ar]。根据上述理论分析,得到如下结论。1)从算法1不难发现,SEDA简单且易执行。自从Liu等改进Lasso算法以后,优化l1范式的计算复杂度已经减少到线性时间。因此,第一步较容易地计算稀疏权值矩阵S。第三步借助于谱回归计算出投影向量,并使用Nystrom方法解决大规模数据降维问题。2)对于每一个样本xi,利用稀疏约束,其重构都是使用样本集的所有样本。因此,通过使用稀疏权值矩阵S,SEDA能自然地保持判别信息。3)不同于现有半监督算法使用局部保持技术来求解投影,SEDA使用稀疏保持投影作为正则化项寻找投影方向。所以,它不需要调节模型参数,如热核宽度和近邻参数。3半监督降维算法下面使用8个真实数据来验证文中所提出稀疏判别分析算法(SEDA)。为了综合评价新算法的性能,使用5个最新提出的典型算法与SEDA进行对比。算法分别如下。1)局部保持投影(LPP)。是一个无监督降维算法,它使用近邻图来指导降维。2)稀疏保持投影(SparsityPreservingProjection,SPP)。是无监督降维算法,它使用稀疏表示寻找投影。3)半监督判别分析(SDA)。基于Fisher标准的半监督降维算法,构建近邻图作为正则化项。4)半监督局部Fisher判别分析(SELF)。联合FDA和LPP进行降维的一个半监督算法。5)基于流形学习的半监督降维算法(Semi-SupervisedDimensionalityReductionFramework,SDRF)。一个最新提出的半监督降维框架。为了公平比较,在使用上述降维方法投影数据到低维空间后,使用最近邻分类方法来计算各个算法的性能。6个算法在每个数据集运行40次,取平均值作为最终的分类性能。3.1webbc4算法性能分析首先使用4个高维数据集进行实验,它们分别是:Reuters是一个文本数据集,它包含135类21578个文本。在本实验中,选择常用的18类6750个样本;WebACE包括20个不同标题2340个文本;WebKB包含7类(student,faculty,staff,course,project,department和other)8280个文本;WebKB4是WebKB的一个子集。4个数据集的属性如表1所示。实验中,有标号样本数分别选择为每个数据集样本数的5%,10%,15%和20%。具体实验结果如图1～4所示。从图1～4中可以看出,本文提出的SEDA在Reuters,WebKB4和WebKB得到最好的识别率。特别是在WebKB上,SEDA的识别率比LPP高出13%,比最新提出的半监督算法SDRF高出大约6%。尽管在WebACE数据集上SDRF的精度高于SEDA,但它们两者之间的差距并不明显。因此,SEDA相对有效。另外,不难发现,4个半监督算法要比两个无监督算法的性能好。原因是这两个算法没有使用任何先验信息。在无监督算法中,一部分使用先验信息,确实能够提高无监督算法的性能。3.2人脸图像的设置下面进一步通过4个人脸数据集(ORL,AR,CMUPIE和YaleFaceB)来验证SEDA算法的性能。首先,ORL数据集由400幅不同表情和光照的人脸图像组成,其中每个人有10幅图像。在实验中,ORL数据集人脸图像被设置成大小32×32像素的256级灰度图像。其次,AR数据集由126类4000幅人脸图像组成。在本实验中,选择100个人(50个男人和50个女人)2600幅人脸图像,图像设置成66×48大小的灰度图像;再次,CMUPIE人脸数据集包括68个人41368幅图像。选择5组接近正面姿态的图像(C05,C07,C09,C27和C29)。对于每一类,选择170幅32×32灰度图像进行实验。最后,YaleFaceB数据集包括38个人16128幅人脸图像。从每个人脸库里选择120幅32×32灰度图像。在实验中,分别从每个人脸数据集里选择10%,20%和30%的样本作为有标号样本,实验环境和3.1节设置相同。实验结果如表2～4所示。3.3seda的不足通过上面的理论分析以及6个算法在8个高维数据集上的实验,可以得出以下结