稀疏判别分析

稀疏判别分析摘要:针对流形嵌入降维方法中在高维空间构建近邻图无益于后续工作，以及不容易给近邻大小和热核参数赋合适值的问题，提出一种稀疏判别分析算法（seda）。首先使用稀疏表示构建稀疏图保持数据的全局信息和几何结构，以克服流形嵌入方法的不足；其次，将稀疏保持作为正则化项使用fisher判别准则，能够得到最优的投影。在一组高维数据集上的实验结果表明，seda是非常有效的半监督降维方法。关键词:判别分析；稀疏表示；近邻图；稀疏图sparsediscriminantanalysischenxiao.dong1*,linhuan.xiang21．schoolofinformationandengineering,zhejiangradioandtelevisionuniversity,hangzhouzhejiang310030,china;2．schoolofinformationandelectronicengineering,zhejianguniversityofscienceandtechnology,hangzhouzhejiang310023,chinaabstract:methodsformanifoldembeddingexistsinthefollowingissues:ononehand,neighborhoodgraphisconstructedinsuchthehigh-dimensionalityoforiginalspacethatittendstoworkpoorly;ontheotherhand,appropriatevaluesfortheneighborhoodsizeandheatkernelparameterinvolvedingraphconstructionisgenerallydifficulttobeassigned.toaddresstheseproblems,anovelsemi-superviseddimensionalityreductionalgorithmcalledsparsediscriminantanalysis(seda)isproposed.firstly,sedasetsupasparsegraphtopreservetheglobalinformationandgeometricstructureofthedatabasedonsparserepresentation.secondly,itappliesbothsparsegraphandfishercriteriontoseektheoptimalprojection.experimentsonabroadrangeofdatasetsshowthatsedaissuperiortomanypopulardimensionalityreductionmethods.methodsformanifoldembeddinghavethefollowingissues:ononehand,neighborhoodgraphisconstructedinsuchhigh.dimensionalityoforiginalspacethatittendstoworkpoorly;ontheotherhand,appropriatevaluesfortheneighborhoodsizeandheatkernelparameterinvolvedingraphconstructionaregenerallydifficulttobeassigned.toaddresstheseproblems,anewsemi.superviseddimensionalityreductionalgorithmcalledsparsediscriminantanalysis(seda)wasproposed.firstly,sedasetupasparsegraphtopreservetheglobalinformationandgeometricstructureofthedatabasedonsparserepresentation.secondly,itappliedbothsparsegraphandfishercriteriontoseektheoptimalprojection.theexperimentalresultsonabroadrangeofdatasetsshowthatsedaissuperiortomanypopulardimensionalityreductionmethods.keywords:discriminantanalysis;sparserepresentation;neighborhoodgraph;sparsegraph0引言在信息检索、文本分类、图像处理和生物计算等应用中，所面临的数据都是高维的。由于维数灾难，直接处理这些数据变得非常困难1］。最常用的方法就是通过使用降维（dimensionalityreduction，dr）技术来降低这些高维数据的维数。降维的目的就是在低维空间中尽量真实地刻画输入数据，减少它们的复杂性，提高计算效率。基于降维后所期望得到的信息，现有的降维可以分为三类：判别方法1-8］、几何方法9-11］和基于判别和几何方法12-14］。基于可获得的先验信息，降维方法又可分为［15］：监督方法8,12,16-17］和无监督方法1,2,4,6,9,11］。上述多数方法都可以被统一到图嵌入框架中8,11］，因此，图的构建成为这些方法的核心问题。事实上，对这些方法来说，构建一个高质量的图仍是个开放问题17］。目前，流形嵌入方法（manifoldembedding）使用k近邻技术和ε建近邻图（neighborhoodgraph）9,18］。一旦这种近邻图被构建，边的权值由gaussian函数或者局部重构关系来决定。这种近邻图构建方法通常存在以下几个问题19］：首先，大多数算法中的近邻图是预先构建，因此，它未必有益于后续的降维工作；其次，近邻图通常是在高维空间中构建，这样构建的图在后续的工作中表现差强人意；最后，近邻图需要的两个参数，即近邻的大小k）和热核参数（σ），通常不容因此，在降维方法中研究图的构建显得尤为重要。另外，多数无监督降维方法在寻找投影方向过程中忽略了部分先验信息的作用，以至于它们往往不能得到最优的投影3,14］。监督降维方法需要大量有标记样本作训练样本，限制了它的应用14］。最近，半监督降维方法得到越来越多研究人员的关注［3,5,7,10,13-15］。这类方法是利用少量有标记样本和大量无标记样本寻找最优的投影方向。与监督方法相比，它更适合实际应用，与无监督方法相比，有较高的效率。然而，现有的一些半监督降维方法通常面临和流形嵌入方法相同的问题，即近邻图构建。如:半监督判别分析算法（semi.superviseddiscriminantanalysis，sda）10］和半监督局部fisher判别分析算法（semi.supervisedlocalfisherdiscriminantanalysis，self）14］。为了解决这些问题，本文提出一个新颖的稀疏判别分析（sparsediscriminantanalysis，seda）算法，seda通过使用稀疏重建技术解决流形嵌入方法中近邻图构建问题。同时，新方法在降维过程中又能同时利用有标记和无标记样本寻找投影，提高了算法效率。具体地说，seda有以下4个特点。1）seda拥有同其他半监督降维方法（如sda、self）相同的特征。如，它是线性的方法，也容易地拓展到非线性空间。因此，可以解决外样本问题。另外，seda使用稀疏重构技术来保存样本的几何结构，这有利于降低算法的计算复杂度。2）seda不需要调节模型参数，如热核宽度和近邻参数。通常，这些参数需要使用交叉验证技术给它们分配数值，但交叉验证方法既需要训练样本，还非常耗时。相比之下，seda不需要处理这些参数。因此，它简单实用。3）与fisher判别分析（fisherdiscriminantanalysis，fda）16］相同，seda是一个全局算法。但不同的是，seda使用稀疏表示来重构样本，以至于它包含了局部几何信息。4）由于seda在求解投影向量过程中使用了有标记和无标记样本，因此，它与流形嵌入方法相比有好的效率。同时，seda可以容易地拓展到监督降维中。1相关工作根据先验信息的不同类型，半监督降维方法一般可分为两类：一类是使用有类标号的样本来引导降维过程10,14,20,22-23］；另一类是使用成对约束（must.link和cannot.link）来指导降维［3,5,7,10,15,20-21］。事实上，使用有类标号的样本可以得到成对约束，但不能由成对约束得到样本的类标号。因此，这两类方法之间存在着一定的相关性。下面简单回顾三个有代表性的半监督降维算法。1.1半监督判别分析半监督判别分析算法（sda）10］是一个较为流行的基于样本标号的半监督降维方法。它使用基于fda判别准则寻找投影，其实质是fda的半监督化。sda首先需要刻画高维空间中近邻样本之间的关系。详细地说，给定一个样本集x，构建一个k近邻的近邻图g来建模近邻样本之间的关系。如果图中两个顶点xi和xj互为近邻，那么它们之间就存在一条边，相应的权值矩阵为p，其定义如下：根据上述理论分析，得到如下结论。1）从算法1不难发现，seda简单且易执行。自从liu等26］改进lasso算法以后，优化l1s。第三步借助于谱回归10］计算出投影向量，并使用nystrom27］2）对于每一个样本xi，利用稀疏约束，其重构都是使用样本集的所有样本。因此，通过使用稀疏权值矩阵s，seda3）不同于现有半监督算法使用局部保持技术来求解投影，seda使用稀疏保持投影作为正则化项寻找投影方向。所以，它不需要调节模型参数，如热核宽度和近邻参数。3实验下面使用8个真实数据来验证文中所提出稀疏判别分析算法（seda）。为了综合评价新算法的性能，使用5个最新提出的典型算法与seda进行对比。算法分别如下。1）局部保持投影（lpp）9］。是一个无监督降维算法，它使用近邻图来指导降维。2）稀疏保持投影（sparsitypreservingprojection，spp）4］。是无监督降维算法，它使用稀疏表示寻找投影。3）半监督判别分析（sda）10］。基于fisher标准的半监督降维算法，构建近邻图作为正则化项。4）半监督局部fisher判别分析（self）14］。联合fda和lpp进行降维的一个半监督算法。5）基于流形学习的半监督降维算法（semi.superviseddimensionalityreductionframework，sdrf）23］。一个最新提出的半监督降维框架。为了公平比较，在使用上述降维方法投影数据到低维空间后，使用最近邻分类方法来计算各个算法的性能。6个算法在每个数据集运行40次，取平均值作为最终的分类性能。3.1在一组高维数据集上的实验首先使用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所示。3.2在人脸数据集上的实验下面进一步通过4个人脸数据集（orl，ar，cmupie和yalefaceb）来验证seda算法的性能。首先，orl数据集由400幅不同表情和光照的人脸图像组成，其中每个人有10幅图像。在实验中，orl数据集人脸图像被设置成大小32×32像