1、/-1:皿gw稀疏判別分析摘要：針對(duì)流形嵌入降維方法中在高維空間構(gòu)建近鄰圖無益于后續(xù)工作，以及不容易給近鄰大小和熱核參數(shù)賦合適值的問題，提出一種稀疏判別分析算法（seda）。首先使用稀疏表示構(gòu)建稀疏圖保持?jǐn)?shù)據(jù)的全局信息和幾何結(jié)構(gòu)，以克服流形嵌入方法的不足；其次,將稀疏保持作為正則化項(xiàng)使用fisher判別準(zhǔn)則，能夠得到最優(yōu)的投影。在一組高維數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，seda是非常有效的半監(jiān)督降維方法。關(guān)鍵詞:判別分析；稀疏表示；近鄰圖；稀疏圖sparsediscriminantanalysischenxiao.dong1*,linhuan.xiang21.schoolofinformationan

2、dengineering,zhejiangradioandtelevisionuniversity,hangzhouzhejiang310030,china2.schoolofinformationandelectronicengineering,zhejianguniversityofscieneeandtechnology,hangzhouzhejiang310023,chinaabstract:methodsformanifoldembeddingexistsinthefollowing論文發(fā)表專家一匸交發(fā)表專家一m國學(xué)朮發(fā)叢網(wǎng)issues:ononehand,neighborhoodg

3、raphisconstructedinsuchthehigh-dimensionalityoforiginalspacethatittendstoworkpoorly;ontheotherhand,appropriatevaluesfortheneighborhoodsizeandheatkernelparameterinvoIvedingraphconstructionisgenerallydifficulttobeassigned.toaddresstheseproblems,anovelsemi-superviseddimensionalityreductionalgorithmcall

4、edsparsediscriminantanalysis(seda)isproposed.firstly,sedasetsupasparsegraphtopreservetheglobalinformationandgeometricstructureofthedatabasedonsparserepresentation.secondly,itappliesbothsparsegraphandfishercriteriontoseektheoptimalprojection.experimentsonabroadrangeofdatasetsshowthatsedaissuperiortom

5、anypopulardimensionalityreductionmethods.methodsformanifoldembeddinghavethefollowingissues:ononehand,neighborhoodgraphisconstructedinsuchhigh.dimensionalityoforiginalspacethatittendstoworkpoorly;ontheotherhand,appropriatevaluesfortheneighborhoodsizeandheatkernelparameterinvoIvedingraphconstructionar

6、egenerallydifficulttobeassigned.toaddresstheseproblems,anewsemi.superviseddimensionalityreductionalgorithmcalledsparsediscriminantanalysis(seda)wasproposed.firstly,sedasetupasparsegraphtopreservetheglobalinformationandgeometricstructureofthedatabasedonsparserepresentation.secondly,itappliedbothspars

7、egraphandfishercriteriontoseektheoptimalprojection.theexperimentalresultsonabroadrangeofdatasetsshowthatsedaissuperiortomanypopulardimensionalityreductionmethods.keywords:discriminantanalysis;sparserepresentation;neighborhoodgraph;sparsegraph0引言在信息檢索、文本分類、圖像處理和生物計(jì)算等應(yīng)用中，所面臨的數(shù)據(jù)都是高維的。由于維數(shù)災(zāi)難，直接處理這些數(shù)據(jù)變得非

8、常困難1。最常用的方法就是通過使用降維(dimensionalityreduction,dr)技術(shù)來降低這些高維數(shù)據(jù)的維數(shù)。降維的目的就是在低維空間中盡量真實(shí)地刻畫輸入數(shù)據(jù)，減少它們的復(fù)雜性，提高計(jì)算效率。基于降維后所期望得到的信息，現(xiàn)有的降維可以分為三類：判別方法1-8、幾何方法9-11和基于判別和幾何方法12-14基于可獲得的先驗(yàn)信息，降維方法又可分為:15:監(jiān)督方法8,12,16-17和無監(jiān)督方法1,2,4,6,9,11論文發(fā)表專家一m國學(xué)朮發(fā)舌網(wǎng)上述多數(shù)方法都可以被統(tǒng)一到圖嵌入框架中8,11,因此，圖的構(gòu)建成為這些方法的核心問題。事實(shí)上，對(duì)這些方法來說，構(gòu)建一個(gè)高質(zhì)量的圖仍是個(gè)開放問題

9、17。目前，流形嵌入方法(manifoldembedding)使用k近鄰技術(shù)和e球ill鄰技術(shù)來構(gòu)建近鄰圖(neighborhoodgraph)9,18。一旦這種近鄰圖被構(gòu)建，邊的權(quán)值由gaussian函數(shù)或者局部重構(gòu)關(guān)系來決定。這種近鄰圖構(gòu)建方法通常存在以下幾個(gè)問題19:首先，大多數(shù)算法中的近鄰圖是預(yù)先構(gòu)建，因此，它未必有益于后續(xù)的降維工作；其次，近鄰圖通常是在高維空間中構(gòu)建，這樣構(gòu)建的圖在后續(xù)的工作中表現(xiàn)差強(qiáng)人意；最后，近鄰圖需要的兩個(gè)參數(shù)，即近鄰的大小(k)和熱核參數(shù)(T),通常不容易賦給介適的值。因此，在降維方法中研究圖的構(gòu)建顯得尤為重要。另外，多數(shù)無監(jiān)督降維方法在尋找投影方向過程中忽

10、略了部分先驗(yàn)信息的作用，以至于它們往往不能得到最優(yōu)的投影3,14。監(jiān)督降維方法需要大量有標(biāo)記樣本作訓(xùn)練樣本，限制了它的應(yīng)用14。最近，半監(jiān)督降維方法得到越來越多研究人員的關(guān)注:3,5,7,10,13-15。這類方法是利用少量有標(biāo)記樣本和大量無標(biāo)記樣本尋找最優(yōu)的投影方向。與監(jiān)督方法相比，它更適合實(shí)際應(yīng)用，與無監(jiān)督方法相比，有較高的效率。論文發(fā)表專家一m國學(xué)朮發(fā)叢廚www.qikanwangmt然而，現(xiàn)有的一些半監(jiān)督降維方法通常面臨和流形嵌入方法相同的問題，即近鄰圖構(gòu)建。如：半監(jiān)督判別分析算法(semi.superviseddiscriminantanalysis，sda)10和半監(jiān)督局咅B(yǎng)fis

11、her判另U分析算法(semi.supervisedlocalfisherdiscriminantanalysis,self)14。為了解決這些問題，本文提出一個(gè)新穎的稀疏判別分析(sparsediscriminantanalysis,seda)算法，seda通過使用稀疏重建技術(shù)解決流形嵌入方法中近鄰圖構(gòu)建問題。同時(shí)，新方法在降維過程中又能同時(shí)利用有標(biāo)記和無標(biāo)記樣本尋找投影，提高了算法效率。具體地說，seda有以下4個(gè)特點(diǎn)。1) seda擁有同其他半監(jiān)督降維方法(如sda、self)相同的特征。如，它是線性的方法，也容易地拓展到非線性空間。因此，可以解決外樣本問題。另外，seda使用稀疏重構(gòu)技

12、術(shù)來保存樣本的幾何結(jié)構(gòu)，這有利于降低算法的計(jì)算復(fù)雜度。2) seda不需要調(diào)節(jié)模型參數(shù)，如熱核寬度和近鄰參數(shù)。通常，這些參數(shù)需要使用交叉驗(yàn)證技術(shù)給它們分配數(shù)值，但交叉驗(yàn)證方法既需要訓(xùn)練樣本，還非常耗時(shí)。相比之下，seda不需要處理這些參數(shù)。因此，它簡單實(shí)用。3) 與fisher判別分析(fisherdiscriminantanalysis,fda)_16相同，seda是一個(gè)全局算法。但不同的是，seda使用稀疏表示來重構(gòu)樣本，以至于它包含了局部幾何信息。4) 由于seda在求解投影向量過程中使用了有標(biāo)記和無標(biāo)記樣本,論文發(fā)表專宅、m國學(xué)朮發(fā)叢網(wǎng)因此，它與流形嵌入方法相比有好的效率。同時(shí)，sed

13、a可以容易地拓展到監(jiān)督降維中。1相關(guān)工作根據(jù)先驗(yàn)信息的不同類型，半監(jiān)督降維方法一般可分為兩類：一類是使用有類標(biāo)號(hào)的樣本來引導(dǎo)降維過程10,14,20,22-23;另一類是使用成對(duì)約束（must.link和cannot.link）來指導(dǎo)降維3,5,7,10,15,20-21。事實(shí)上，使用有類標(biāo)號(hào)的樣本可以得到成對(duì)約束，但不能由成對(duì)約束得到樣本的類標(biāo)號(hào)。因此，這兩類方法之間存在著一定的相關(guān)性。下面簡單回顧三個(gè)有代表性的半監(jiān)督降維算法。1.1半監(jiān)督判別分析半監(jiān)督判別分析算法（sda）10是一個(gè)較為流行的基于樣本標(biāo)號(hào)的半監(jiān)督降維方法。它使用基于fda判別準(zhǔn)則尋找投影，其實(shí)質(zhì)是fda的半監(jiān)督化。sda首

14、先需要刻畫高維空間中近鄰樣本之間的關(guān)系。詳細(xì)地說，給定一個(gè)樣本集x,構(gòu)建一個(gè)k近鄰的近鄰圖g來建模近鄰樣本之間的關(guān)系。如果圖中兩個(gè)頂點(diǎn)xi和xj互為近鄰，那么它們之間就存在一條邊，相應(yīng)的權(quán)值矩陣為p,其定義如下：根據(jù)上述理論分析，得到如下結(jié)論。1）從算法1不難發(fā)現(xiàn)，seda簡單且易執(zhí)行。自從liu等26改進(jìn)lasso算法以后，優(yōu)化I1范式的計(jì)算復(fù).雜度lA經(jīng)減少到線性時(shí)間。囚此，第一步較容易地計(jì)算稀疏權(quán)值矩陣s。第三步借助于譜回歸10計(jì)算出投影向量，并使用nystrom27方法解決大規(guī)模數(shù)據(jù)降維問題。2）對(duì)于每一個(gè)樣本xi，利用稀疏約束，其重構(gòu)都是使用樣本集的所有樣本。因此，通過使用稀疏權(quán)值矩

15、陣s,seda能口獄地保持判別信息o3）不同于現(xiàn)有半監(jiān)督算法使用局部保持技術(shù)來求解投影，seda使用稀疏保持投影作為正則化項(xiàng)尋找投影方向。所以，它不需要調(diào)節(jié)模型參數(shù)，如熱核寬度和近鄰參數(shù)。3實(shí)驗(yàn)下面使用8個(gè)真實(shí)數(shù)據(jù)來驗(yàn)證文中所提出稀疏判別分析算法（seda）。為了綜合評(píng)價(jià)新算法的性能，使用5個(gè)最新提出的典型算法與seda進(jìn)行對(duì)比。算法分別如下。1）局部保持投影（Ipp）9。是一個(gè)無監(jiān)督降維算法，它使用近鄰圖來指導(dǎo)降維。,spp)2) 稀疏保持投影(sparsitypreservingprojection:4。是無監(jiān)督降維算法，它使用稀疏表示尋找投影。3）半監(jiān)督判別分析（sda）10。基于fis

16、her標(biāo)準(zhǔn)的半監(jiān)督降維算法，構(gòu)建近鄰圖作為正則化項(xiàng)。4）半監(jiān)督局部fisher判別分析（self）L14。聯(lián)合fda和論文發(fā)表專樂一B國學(xué)朮發(fā)舌網(wǎng)Ipp進(jìn)行降維的一個(gè)半監(jiān)督算法。5) 基于流形學(xué)習(xí)的半監(jiān)督降維算法(semi.superviseddimensionalityreductionframework,sdrf)23。一個(gè)最新提出的半監(jiān)督降維框架。為了公平比較，在使用上述降維方法投影數(shù)據(jù)到低維空間后，使用最近鄰分類方法來計(jì)算各個(gè)算法的性能。6個(gè)算法在每個(gè)數(shù)據(jù)集運(yùn)行40次，取平均值作為最終的分類性能。3.1在一組高維數(shù)據(jù)集上的實(shí)驗(yàn)首先使用4個(gè)高維數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，它們分別是：reuters是

17、一個(gè)文本數(shù)據(jù)集，它包含135類21578個(gè)文本。在本實(shí)驗(yàn)中，選擇常用的18類6750個(gè)樣本；webace包括20個(gè)不同標(biāo)題2340個(gè)文本；webkb包含7類(student，faculty，staff，course，project，department和other)8280個(gè)文本；webkb4是webkb的一個(gè)子集。4個(gè)數(shù)據(jù)集的屬性如表1所示。實(shí)驗(yàn)中，有標(biāo)號(hào)樣本數(shù)分別選擇為每個(gè)數(shù)據(jù)集樣本數(shù)的5%10%15呀口20%具體實(shí)驗(yàn)結(jié)果如圖14所示。3.2在人臉數(shù)據(jù)集上的實(shí)驗(yàn)下面進(jìn)一步通過4個(gè)人臉數(shù)據(jù)集(orl,ar,cmupie和yalefaceb)來驗(yàn)證seda算法的性能。首先，orl數(shù)據(jù)集由400

18、幅不同表情和光照的人臉圖像組成，其中每個(gè)人有10幅圖像。在實(shí)驗(yàn)中，orl數(shù)據(jù)集人臉圖像被設(shè)置成大小32X32像素的256級(jí)灰度圖像。其次，論文發(fā)表專家一tn國學(xué)朮發(fā)叢網(wǎng)www.qikanwangmt論文發(fā)表仝泳一m國學(xué)朮發(fā)叢網(wǎng)ar數(shù)據(jù)集由126類4000幅人臉圖像組成。在本實(shí)驗(yàn)中，選擇100個(gè)人(50個(gè)男人和50個(gè)女人)2600幅人臉圖像，圖像設(shè)置成66X48大小的灰度圖像；再次，emupie人臉數(shù)據(jù)集包括68個(gè)人41368幅圖像。選擇5組接近正面姿態(tài)的圖像(c05,c07,c09,c27和c29)。對(duì)于每一類，選擇170幅32X32灰度圖像進(jìn)行實(shí)驗(yàn)。最后，yalefaceb數(shù)據(jù)集包括38個(gè)人

19、16128幅人臉圖像。從每個(gè)人臉庫里選擇120幅32X32灰度圖像。在實(shí)驗(yàn)中，分別從每個(gè)人臉數(shù)據(jù)集里選擇10%20呀口30%勺樣本作為有標(biāo)號(hào)樣本，實(shí)驗(yàn)環(huán)境和3.1節(jié)設(shè)置相同。實(shí)驗(yàn)結(jié)果如表24所示。3.3實(shí)驗(yàn)討論通過上面的理論分析以及6個(gè)算法在8個(gè)高維數(shù)據(jù)集上的實(shí)驗(yàn)，可以得出以下結(jié)論。1) seda在文中所用的大多數(shù)數(shù)據(jù)集上，包括3個(gè)高維數(shù)據(jù)集和4個(gè)人臉數(shù)據(jù)集，無論是在少量標(biāo)號(hào)樣本還是大量標(biāo)號(hào)樣本環(huán)境下，都能取得比其他5個(gè)算法好的性能。其中，在4個(gè)人臉數(shù)據(jù)集上，seda的優(yōu)勢更加明顯。因此，可以得到初步的結(jié)論：文中所提出的seda是一個(gè)相對(duì)有效的半監(jiān)督降維算法。2) 盡管在webace數(shù)據(jù)集上，

20、sdrf能夠得到較好的結(jié)果，但在其他數(shù)據(jù)集上，它沒有seda執(zhí)行得好，而且與其他數(shù)據(jù)集相比也沒有明顯優(yōu)勢。事實(shí)上，盡管sdrf試圖用hadamard動(dòng)力算子(hadamardpoweroperator)技術(shù)提高無標(biāo)號(hào)樣本的功效，但其實(shí)質(zhì)還是構(gòu)建近鄰圖來指導(dǎo)降維。因此，sdrf的效果并不令人滿意3) sda和self需要構(gòu)建近鄰圖來降維，所以分配合適的參數(shù)，對(duì)構(gòu)建近鄰圖至關(guān)重要。另一方面，近鄰圖的構(gòu)建是在原空間進(jìn)行的，當(dāng)維數(shù)特別高時(shí)，構(gòu)建的近鄰圖往往無益于降維。因此，在有標(biāo)記樣本較少時(shí)，sda和self的性能還沒有spp好。但當(dāng)標(biāo)記樣本數(shù)量逐漸增多時(shí)，sda和self的性能要好于spp。4) s

21、pp的性能比lpp好，原因是前者使用稀疏表示進(jìn)行投影時(shí)，既保存了數(shù)據(jù)的全局信息，也兼顧了數(shù)據(jù)的幾何結(jié)構(gòu)。這也自然地解釋了seda為什么性能更好的原因。4結(jié)語本文提出一種簡單而有效的半監(jiān)督稀疏判別分析算法(seda)。具體地說，基于稀疏表示，seda搭建的稀疏圖得到稀疏重構(gòu)權(quán)值；其次，seda把稀疏保持作為正則化項(xiàng)使用fisher判別準(zhǔn)則來尋找最優(yōu)的投影。實(shí)驗(yàn)結(jié)果表明，seda的性能不僅優(yōu)于最新提出的幾個(gè)流形的半監(jiān)督降維方法sda,self和sdrf，更優(yōu)于無監(jiān)督降維方法。參考文獻(xiàn)：yej,zhao乙wum.discriminativek.meansforclusteringeb/ol.2011

22、-05-01.http:/www.kyb.mpg.de/publications/attachments/nips2007-ye_47100.pdf.:2chenht,changhw,liutl.localdiscriminantembeddinganditsvariantsc/cvpr05:proceedingsofthe2005ieeecomputersocietyconfereneeoncomputervisionandpatternrecognition.washington,dc:ieeecomputersociety,2005:846-853.:3尹學(xué)松，胡恩良，陳松燦.基于成對(duì)約

23、束的半監(jiān)督判別分析j.軟件學(xué)報(bào),2008,19(11):2791-2802.:4qiaol,chens,tanx.sparsitypreservingprojectionswithapplicationstofacerecognitionj.patternrecognition,2010,43(1):331-341.j.frontiersofyinx,hue.distancemetriclearningguidedadaptivesubspacesemi.supervisedclusteringcomputerscienceinchina,2011,5(1):100-108.c/cvprhoi

24、sch,liuw,lyumr,etal.learningdistancemetricswithcontextualconstraintsforimageretrieval論文發(fā)表專家一tn國3FJKSH網(wǎng)06:proceedingsofthe2006ieeecomputersocietyconferenceoncomputervisionandpatternrecognition.washington,dc:ieeecomputersociety,2006:2072-2078.:7陳小冬，尹學(xué)松，林煥祥.基于判別分析的半監(jiān)督聚類方法:j.計(jì)算機(jī)工程與應(yīng)用,2010,46(6):139-143.

25、:8yans,xud,zhangb,etal.graphembeddingandextensions:ageneralframeworkfordimensionalityreductioneb/ol.2011-08-01..sg/home/dongxu/tpami.ge.pdf.:9hexiao.fei,niyogip.localitypreservingprojectionseb/ol.2011-08-01./xiaofei/conference.24.pdf.:10caid,hex,hanj.semi

26、.superviseddiscriminantanalysiseb/ol.2011-08-01./hanj/pdf/iccv07_dengcai_sda.pdf.:11caideng,hexiao.fei,hanjia.wei.sparseprojectionsover論文發(fā)表專家一lgraph:eb/ol.2011-09-01./papers/aaai/2008/aaai08.097.pdf.12j.thejournalsugiyamam.dimensionalityreductionofmultimodallab

27、eleddatabylocalfisherdiscriminantanalysisofmachinelearningresearch,2007,8(5):1027-1061.:13尹學(xué)松，胡恩良.半監(jiān)督局部維數(shù)約減j.中國圖象圖形學(xué)報(bào),2011,16(9):2121-2131.:14sugiyamam,nakajimat,sesej.semi.supervisedlocalfisherdiscriminantanalysisfordimensionalityreductionj.machinelearning,2010:78(1/2):35-61.:15尹學(xué)松，胡恩良.半監(jiān)督正則化學(xué)習(xí)j.小型

28、微型計(jì)算機(jī)系統(tǒng)2010,31(12):2389-2393.16belhumeurp,hsspanhaj,kriegmand.eigenfacesvs.fisherfaces:recognitionusingclassspecificlinearprojectionj.ieeetransactionsonpatternanalysisandmachineintelligenee,1997,19(7):711-720.:17liuw,changs.f.robustmulti.classtransductivelearningwithgraphscIIproceedingsofieeeconfere

29、nceoncomputervisionandpatternrecognition.s.:ieee,2009:8.:18belkinm,niyogip.laplacianeigenmapsfordimensionalityreductionanddatarepresentationj.neuralcomputation,2003,15(6):1373-1396.:19zhangl,qiaol,chens.graph.optimizedlocalitypreservingprojectionsj.patternrecognition,2010,43(6):1993-2002.:20tangw,xiongh,zhongs,etal.enhancingsemi.supervisedclustering:afeatureprojectionperspectivecIIkdd07:proceedingsof