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

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

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