半監(jiān)督線性維數(shù)約減算法

半監(jiān)督線性維數(shù)約減算法

1半監(jiān)督維數(shù)約減方法在模式識(shí)別和機(jī)械學(xué)習(xí)領(lǐng)域，一些應(yīng)用程序，如人臉識(shí)別、圖像搜索和網(wǎng)絡(luò)挖掘，往往會(huì)導(dǎo)致高維數(shù)據(jù)。為了解決這個(gè)問題，自然地考慮找到一個(gè)低維流形式來表示這些高維數(shù)據(jù)。在此基礎(chǔ)上，維數(shù)約減法可以將高維數(shù)據(jù)投影到低維空間。此外，通過減小維數(shù)約法減少數(shù)據(jù)維數(shù)，排序和距離算法的執(zhí)行變得更加快速和直觀。因此，近年來，維數(shù)約減吸引了越來越多研究人員的興趣。基于可獲得的約束信息,現(xiàn)有的維數(shù)約減方法可分為三類:監(jiān)督維數(shù)約減方法,半監(jiān)督維數(shù)約減方法和無監(jiān)督維數(shù)約減方法.通常,無監(jiān)督維數(shù)約減方法尋找高維數(shù)據(jù)的低維流形時(shí),由于缺乏先驗(yàn)信息的引導(dǎo),很難得到令人滿意的投影結(jié)果;監(jiān)督維數(shù)約減方法需要大量有類標(biāo)號(hào)的數(shù)據(jù)作為訓(xùn)練樣本,能得到較為滿意的結(jié)果.然而,這類方法難以推廣到實(shí)際應(yīng)用中,因?yàn)樗璧臄?shù)據(jù)類標(biāo)號(hào)并不容易得到.半監(jiān)督維數(shù)約減方法是借助于一部分輔助信息和無標(biāo)號(hào)樣本來尋找高維數(shù)據(jù)的低維流行.該方法既能提高無監(jiān)督維數(shù)約減方法的性能,也無需大量的類標(biāo)號(hào).所以,半監(jiān)督維數(shù)約減方法已成最近研究的一個(gè)重要方向.最近,Sandler等人指出基于譜圖理論的方法需要計(jì)算近鄰樣本之間的距離,而這類距離一般難以正確地計(jì)算.他的方法將權(quán)向量的特征結(jié)構(gòu)作為正則化項(xiàng)引入到分類目標(biāo)函數(shù)中來求解分類方向.事實(shí)上,Sandler的方法忽略了數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)對(duì)求解分類方向的作用,而且,他的方法需要大量數(shù)據(jù)的類標(biāo)號(hào)作為訓(xùn)練樣本.為了克服上述問題,本文提出新穎的半監(jiān)督正則化學(xué)習(xí)算法(SSRL).新算法的重要思想就是通過對(duì)成對(duì)約束和大量無標(biāo)號(hào)樣本的學(xué)習(xí),得到一個(gè)光滑和有判別力的子空間.具體地說,分別使用成對(duì)約束信息和大量無標(biāo)號(hào)樣本得到數(shù)據(jù)的判別結(jié)構(gòu)和內(nèi)在幾何結(jié)構(gòu),并通過正則化技術(shù)合并投影向量的特征結(jié)構(gòu)到半監(jiān)督維數(shù)約減算法中求解最優(yōu)投影方向.輔助信息有多種形式,如類標(biāo)號(hào)信息,成對(duì)約束等.相比數(shù)據(jù)的類標(biāo)號(hào),得到成對(duì)約束更容易.因?yàn)閷?duì)一個(gè)專家或者用戶來說,指出兩個(gè)樣本是否屬于相同類要相對(duì)容易.而且由數(shù)據(jù)類標(biāo)號(hào)能得到成對(duì)約束,但不能由成對(duì)約束來得到數(shù)據(jù)的類標(biāo)號(hào).成對(duì)約束有must-link約束和cannot-link約束兩種形式,它們定義如下:一個(gè)must-link約束規(guī)定:兩個(gè)樣本屬于相同類;一個(gè)cannot-link約束規(guī)定:兩個(gè)樣本屬于不同類.2線性維數(shù)約減方法給定一個(gè)由n個(gè)樣本組成的數(shù)據(jù)集X,{x1,…,xn}∈Rd,線性維數(shù)約減方法需要找到一個(gè)變換矩陣A=(a1,…,ar)∈Rd×r,將n個(gè)樣本投影到低維空間里:2.1做st+sl的amoaaatsbaatCai等人將線性判別分析算法引入半監(jiān)督領(lǐng)域中,提出一種半監(jiān)督判別分析算法(SDA).SDA的目標(biāo)函數(shù)是:maxaaΤSbaaΤ(St+λSl)amaxaaTSbaaT(St+λSl)a(2)其中,Sl定義如下:Sl=12n2n∑i,j=1Sij(xi-xj)(xi-xj)ΤSl=12n2∑i,j=1nSij(xi?xj)(xi?xj)T(3)Sij度量?jī)蓚€(gè)樣本xi和xj之間的相似性,Sb是給定一部分有標(biāo)號(hào)樣本的類間散布矩陣.由于缺乏大量樣本的類標(biāo)號(hào),難以準(zhǔn)確計(jì)算類內(nèi)散布矩陣Sw.因此,Cai使用St=Sb+Sw代替Sw.2.2ssr目標(biāo)函數(shù)Zhang等人提出了一種半監(jiān)督維數(shù)約減算法(SSDR).不同于SDA使用一部分樣本類標(biāo)號(hào)作為先驗(yàn)知識(shí),對(duì)給定的must-link約束集合和cannot-link約束集合,Zhang使用成對(duì)約束來引導(dǎo)維數(shù)約減過程.SSDR最大化下面目標(biāo)函數(shù):J(a)=12n2n∑i,j=1(aΤxi-aΤxj)2+α2nc∑(xi,xj)∈C(aΤxi-aΤxj)2-β2nm∑(xi,xj)∈Μ(aΤxi-aΤxj)2(4)J(a)=12n2∑i,j=1n(aTxi?aTxj)2+α2nc∑(xi,xj)∈C(aTxi?aTxj)2?β2nm∑(xi,xj)∈M(aTxi?aTxj)2(4)其中,M和C分別表示must-link約束和cannot-link約束集合,α和β是折中參數(shù).式(4)實(shí)際上就是約束的主成份分析(PCA),或者是半監(jiān)督的主成份分析.該方法忽略了數(shù)據(jù)的局部幾何結(jié)構(gòu).2.3基于球形k-均值算法的樣本聚類方法相似于Zhang等人的方法,Tang等人借助于成對(duì)約束,提出基于球形K-均值的特征投影方法(SCREEN).SCREEN最大化下面的目標(biāo)函數(shù):J(A)=∑(xi,xj)∈C∥AΤxi-AΤxj∥2-∑(xi,xj)∈Μ∥AΤxi-AΤxj∥2(5)J(A)=∑(xi,xj)∈C∥ATxi?ATxj∥2?∑(xi,xj)∈M∥ATxi?ATxj∥2(5)s.t.aΤiaj={1ifi=j0ifi≠jaTiaj={1ifi=j0ifi≠j(6)在求出投影矩陣A后,SCREEN使用基于球形K-均值算法對(duì)所有樣本聚類.該方法僅僅使用成對(duì)約束來尋找高維數(shù)據(jù)的低維流形.顯然,SCREEN的缺點(diǎn)是不僅忽略大量無標(biāo)號(hào)樣本對(duì)維數(shù)約減的貢獻(xiàn),也沒有考慮到數(shù)據(jù)的局部幾何結(jié)構(gòu).因此,Tang得到的解并不是最優(yōu)的投影方向.2.4traaSong等人利用部分類標(biāo)號(hào),提出一個(gè)半監(jiān)督維數(shù)約減框架.在這個(gè)框架里他們分別優(yōu)化兩個(gè)目標(biāo)函數(shù).他們優(yōu)化的第一個(gè)目標(biāo)函數(shù)是:A=argmaxtr(AΤSbA)tr(AΤ(Sw+λ1Sl+λ2Ι)A)A=argmaxtr(ATSbA)tr(AT(Sw+λ1Sl+λ2I)A)(7)不難發(fā)現(xiàn),式(7)實(shí)質(zhì)上就是在SDA方法基礎(chǔ)上添加了一項(xiàng)Tikhonov正則化.Song等人優(yōu)化的第二個(gè)目標(biāo)函數(shù)是:A=argmaxAΤA=Ιtr(AΤ(Sb-λ1Sw-λ2Sl)A)A=argmaxATA=Itr(AT(Sb?λ1Sw?λ2Sl)A)(8)其中,tr(B)是求解矩陣B的跡.顯然,式(8)是半監(jiān)督化的最大間隔標(biāo)準(zhǔn)(MMC).3半監(jiān)督正則化學(xué)習(xí)算法大多數(shù)半監(jiān)督維數(shù)約減方法使用數(shù)據(jù)的局部幾何結(jié)構(gòu)來尋找投影空間.文中提出的半監(jiān)督正則化學(xué)習(xí)算法(SSRL)不僅保持了數(shù)據(jù)的局部幾何結(jié)構(gòu),還使用投影矩陣的特征結(jié)構(gòu)作為正則化項(xiàng)合并到目標(biāo)函數(shù)中,從而得到最優(yōu)的嵌入空間.3.1目標(biāo)函數(shù)的建立對(duì)所求的投影向量a,構(gòu)建一個(gè)無向圖G1=(V,E,P),頂點(diǎn)V={1,…,d}對(duì)應(yīng)于投影向量的每個(gè)特征,每條邊對(duì)應(yīng)于一個(gè)權(quán)值Pij,用來度量?jī)蓚€(gè)頂點(diǎn)i和j的相似性(P的求解見第四節(jié)實(shí)驗(yàn)部分).顯然,權(quán)值是一個(gè)非負(fù)實(shí)數(shù),而且權(quán)值越大,意味著相應(yīng)的頂點(diǎn)有更大的相似性.如果權(quán)值為0意味著這兩個(gè)頂點(diǎn)沒有相似性.類似于,優(yōu)化下面的目標(biāo)函數(shù):minJ(a)=d∑j=1(aj-∑kΡjkak)2minJ(a)=∑j=1d(aj?∑kPjkak)2(9)s.t.∑kΡjk=1s.t.∑kPjk=1(10)將式(9)寫成矩陣形式:J(a)=aTHa(11)其中,H=(I-P)T(I-P).3.2局部幾何結(jié)構(gòu)給定樣本集合X,構(gòu)建一個(gè)p近鄰無向圖G2來建模近鄰樣本之間的關(guān)系.詳細(xì)地說,如果圖中兩個(gè)頂點(diǎn)xi和xj互為近鄰,那么它們之間就存在一條邊,相應(yīng)的權(quán)值矩陣為S,其定義如下:Sij={1ifxi∈Νp(xj)orxj∈Νp(xi)0otherwise(12)Sij={1ifxi∈Np(xj)orxj∈Np(xi)0otherwise(12)其中,Np(xi)表示樣本xi的p近鄰集合.根據(jù)上述定義,如果兩個(gè)樣本之間存在一條邊,那么這兩個(gè)樣本有可能屬于相同類.因此,高維空間中的兩個(gè)近鄰樣本被投影到低維流形時(shí),自然地期望這兩個(gè)仍保持近鄰.為了達(dá)到這個(gè)目的,最小化下面目標(biāo)函數(shù):h(a)=n∑i,j=1(aΤxi-aΤxj)2Sijh(a)=∑i,j=1n(aTxi?aTxj)2Sij(13)最小化上述目標(biāo)函數(shù),在得到低維流形的同時(shí),保持了數(shù)據(jù)的局部幾何結(jié)構(gòu).設(shè)X=[x1,x2,…,xn],則h(a)=n∑i,j=1(aΤxi-aΤxj)2Sij=2n∑i=1aΤxiDiixΤia-2n∑i,j=1aΤxiSijxΤja=2aΤXDXΤa-2aΤXSXΤa(14)h(a)=∑i,j=1n(aTxi?aTxj)2Sij=2∑i=1naTxiDiixTia?2∑i,j=1naTxiSijxTja=2aTXDXTa?2aTXSXTa(14)其中,矩陣S是對(duì)稱陣,矩陣D是對(duì)角陣,且Dii=∑jSijDii=∑jSij.若aTXDXTa的值被固定,最小化h(a)等價(jià)于最大化aTXSXTa.3.3優(yōu)化目標(biāo)函數(shù)給定must-link和cannot-link成對(duì)約束集合M和C,文中的目標(biāo)就是讓屬于M集合的樣本對(duì)在投影空間中的距離盡可能的近,屬于C集合的樣本對(duì)在投影空間中的距離盡可能的遠(yuǎn).為此,通過下面式子計(jì)算給定的must-link成對(duì)約束之間的距離.dw=∑(xi,xj)∈Μ(aΤxi-aΤxj)2=aΤSwadw=∑(xi,xj)∈M(aTxi?aTxj)2=aTSwa(15)其中,Sw被稱為must-link約束散布矩陣,其表達(dá)式為:Sw=∑(xi,xj)∈Μ(xi-xj)(xi-xj)ΤSw=∑(xi,xj)∈M(xi?xj)(xi?xj)T(16)類似地,可以計(jì)算cannot-link成對(duì)約束之間的距離:db=∑(xi,xj)∈C(aΤxi-aΤxj)2=aΤSbadb=∑(xi,xj)∈C(aTxi?aTxj)2=aTSba(17)Sb被稱為cannot-link約束散布矩陣:Sb=∑(xi,xj)∈C(xi-xj)(xi-xj)ΤSb=∑(xi,xj)∈C(xi?xj)(xi?xj)T(18)為了達(dá)到最大化cannot-link成對(duì)約束之間的距離,而最小化must-link成對(duì)約束之間的距離,優(yōu)化下面的目標(biāo)函數(shù):maxaΤSbaaΤSwamaxaTSbaaTSwa(19)3.4半監(jiān)督維數(shù)約減目標(biāo)函數(shù)和半監(jiān)督維數(shù)約減目標(biāo)函數(shù)顯然,式(19)只是利用了給定的成對(duì)約束信息來求解投影向量.因此,最大化(19),得到的結(jié)果并非最優(yōu)的投影向量.為了得到最優(yōu)的投影向量,不僅要使用成對(duì)約束信息和數(shù)據(jù)的局部幾何結(jié)構(gòu),還要考慮到投影向量的特征結(jié)構(gòu).事實(shí)上,在現(xiàn)有的半監(jiān)督和無監(jiān)督維數(shù)約減領(lǐng)域中,大多數(shù)算法在求解投影向量時(shí)都忽略了它的特征結(jié)構(gòu).SSRL的目的就是將投影向量的特征結(jié)構(gòu)和數(shù)據(jù)的局部幾何結(jié)構(gòu)作為正則化項(xiàng)添加到半監(jiān)督維數(shù)約減目標(biāo)函數(shù)中,得到最優(yōu)的投影向量.根據(jù)上述分析,SSRL的目標(biāo)函數(shù)是:maxaΤ(Sb+λ1XSXΤ)aaΤ(Sw+λ2Η+λ3XDXΤ)amaxaT(Sb+λ1XSXT)aaT(Sw+λ2H+λ3XDXT)a(20)其中,λ1,λ2和λ3是正則化系數(shù).最大化這個(gè)目標(biāo)函數(shù),最優(yōu)的投影向量是由求解下面式子的廣義特征值問題得到:(Sb+λ1XSXT)a=η(Sw+λ2H+λ3XDXT)a(21)式(21)前r個(gè)最大特征值對(duì)應(yīng)的特征向量,構(gòu)成所求的投影矩陣A=(a1,…,ar).綜上分析,SSRL算法描述如下:輸入:樣本集X,成對(duì)約束集合M和C;輸出:投影矩陣A;第1步:構(gòu)建特征結(jié)構(gòu)的無向圖,求解矩陣H=(I-P)T(I-P);第2步:構(gòu)建數(shù)據(jù)的近鄰圖,由式(12),求解矩陣S和D;第3步:根據(jù)式(16)和(18),分別計(jì)算must-link約束散布矩陣Sw和cannot-link約束散布矩陣Sb;第4步:求解式(21)廣義特征值問題,對(duì)特征值降序排列,取前r個(gè)特征值對(duì)應(yīng)的特征向量,組成投影矩陣A=(a1,…,ar);第5步:輸出投影矩陣A.4實(shí)驗(yàn)結(jié)果——k均值算法實(shí)驗(yàn)本節(jié)使用UCI數(shù)據(jù)集,文本數(shù)據(jù)集和圖像數(shù)據(jù)集來驗(yàn)證文中所提出SSRL算法的有效性.為評(píng)價(jià)新算法的性能,文中使用最近發(fā)表DisKmeans,SCREEN,SSDR和LMDM與SSRL比較.由于K均值算法是一個(gè)簡(jiǎn)單有效的聚類算法,且在變換空間里,聚類性能充分反映維數(shù)約減算法的質(zhì)量,因此,在投影空間里,文中使用K均值算法來聚類投影結(jié)果.進(jìn)而,聚類結(jié)果作為最終衡量算法性能的依據(jù).實(shí)驗(yàn)中,式(21)中的三個(gè)正則化參數(shù)的值分別設(shè)置為0.01.在3.1節(jié)構(gòu)建的特征圖中,每個(gè)邊的權(quán)值Pij由這兩個(gè)頂點(diǎn)的余弦相似度確定.對(duì)某個(gè)特征來說,與其它特征相連的所有邊上,選擇余弦權(quán)值最大的20個(gè)邊作為k的值(在UCI數(shù)據(jù)集里,k=8).為公平比較,聚類數(shù)取數(shù)據(jù)的真正類數(shù),且所有算法對(duì)數(shù)據(jù)的維數(shù)都降到c-1維(c是聚類數(shù)).4.1實(shí)驗(yàn)2.2聚類結(jié)果文中使用聚類算法中常用的兩種度量來評(píng)價(jià)聚類結(jié)果.第一個(gè)度量是精度(Acc),其定義如下:Acc=1nn∑i=1f(si,map(ri))Acc=1n∑i=1nf(si,map(ri))(22)其中,n是樣本數(shù),si與ri分別是樣本xi的類標(biāo)號(hào)和聚類標(biāo)號(hào).如果x=y,則f(x,y)=1,否則為f(x,y)=0.map(ri)是個(gè)映射函數(shù),將聚類標(biāo)號(hào)轉(zhuǎn)換為該樣本的類標(biāo)號(hào).第二個(gè)度量是歸一化互信息(NMI),其定義為:ΝΜΙ=Ι(E,F)√Η(E)Η(F)NMI=I(E,F)H(E)H(F)√(23)其中,E是聚類結(jié)果,F是樣本的類標(biāo)號(hào).I(E,F)是E與F互信息量,H(E)和H(F)分別是E與F的熵.另外,所有的算法運(yùn)行在Matlab環(huán)境里.五個(gè)算法在每個(gè)數(shù)據(jù)集分別重復(fù)實(shí)驗(yàn)20次.在每次實(shí)驗(yàn)中隨機(jī)選擇300對(duì)成對(duì)約束并在整個(gè)數(shù)據(jù)集上來測(cè)試算法的性能,取20次的均值作為最終的聚類結(jié)果.4.2sslr的性能在這個(gè)小節(jié)里,使用4個(gè)UCI數(shù)據(jù)集來評(píng)價(jià)五個(gè)算法的性能.4個(gè)UCI數(shù)據(jù)集的描述如表1所示.相應(yīng)的實(shí)驗(yàn)結(jié)果如表2和圖1(見下頁)所示.從表2和圖1,能得到如下觀察:在Satimage,Pendigits和Soybean數(shù)據(jù)集上,SSRL的性能要明顯優(yōu)于其他4個(gè)算法.其中在Pendigits數(shù)據(jù)集上,SSRL的Acc值要比次優(yōu)的SSDR高出5個(gè)百分點(diǎn).在Solar數(shù)據(jù)集上,SSRL的性能也能SSDR相比.顯然,集成數(shù)據(jù)的局部幾何結(jié)構(gòu)以及投影向量的特征結(jié)構(gòu),能保證SSRL有很好的性能.SSDR的性能盡管次于SSRL,但優(yōu)于其它三個(gè)算法.原因是SSDR不僅使用了成對(duì)約束信息,還使用了所有的無標(biāo)號(hào)樣本來指導(dǎo)維數(shù)約減.而不論是SCREEN,還是LMDM,在算法執(zhí)行中都沒有考慮到無標(biāo)號(hào)樣本.在所有五個(gè)算法中,DisKmeans執(zhí)行的最差.不難理解,由于DisKmeans是無監(jiān)督維數(shù)約減,因此它并不能得到滿意的結(jié)果.這也說明一個(gè)事實(shí):半監(jiān)督維數(shù)約減算法能夠改進(jìn)無監(jiān)督維數(shù)約減算法的性能.4.3聚類性能對(duì)比為了進(jìn)一步驗(yàn)證SSRL算法的性能,在這個(gè)小節(jié)里,使用文本和圖像數(shù)據(jù)集來評(píng)價(jià)5個(gè)算法.兩個(gè)文本數(shù)據(jù)集Reuters和20Newsgroups.其中,在Reuters數(shù)據(jù)集中,選擇10類2900個(gè)樣本,它們的維數(shù)是1000維;在20Newsgroups數(shù)據(jù)集里,選擇10類7500個(gè)樣本,它們的維數(shù)是4000維.兩個(gè)圖像數(shù)據(jù)集是USPS數(shù)字圖像和ORL人臉圖像.在USPS中,選擇10類7000個(gè)樣本,維數(shù)是256維;在ORL中,圖像大小是32×32像素,是256級(jí)灰度圖像,選擇40個(gè)人400個(gè)人臉圖像.實(shí)驗(yàn)結(jié)果如表3和圖2所示.從表3和圖2能夠觀察到,SSRL在20Newsgroups,USPS和ORL上聚類性能最好.在Reuters數(shù)據(jù)集上,SSDR執(zhí)行的最好.類似于UCI數(shù)據(jù)集,DisKmeans在所有算法中聚類性能最差.總體上,SSRL的性能要優(yōu)于其它四個(gè)算法.不過,也應(yīng)該看到,在Solar和Reuters數(shù)據(jù)集上,盡管SSRL的聚類性能不是最優(yōu),但SSRL的聚類性能接近SSDR的結(jié)果.根據(jù)上述實(shí)驗(yàn)結(jié)