半監(jiān)督判別分析

半監(jiān)督判別分析摘要線性判別分析（LDA）已經(jīng)成為特征提取的常用方法，此方法可保存類可分性。通常投影向量通過最大化類間協(xié)方差，同時最大限度地減少類內(nèi)協(xié)方差的方式獲得的。在實踐中，當沒有足夠的訓練樣本，每個類的協(xié)方差矩陣的估計可能不準確。在本文中，我們提出了一種新的方法，稱為半監(jiān)督判別分析（SDA）,這種方法既使用的標記樣本有使用未標記的樣本。標記的數(shù)據(jù)點是用來最大化不同類別之間的可分性，而未標記的數(shù)據(jù)點用來估計數(shù)據(jù)的內(nèi)在的幾何結(jié)構。具體來說,我們的目標是學習的一個判別函數(shù)，使其盡可能平穩(wěn)地表示數(shù)據(jù)流形。單訓練圖像的人臉識別和相關反饋圖像檢索的實驗結(jié)果可以證明我們算法的有效性。介紹在許多可視化分析應用中，如圖像檢索、人臉識別等，它們都會遭遇高維數(shù)據(jù)的問題。然而，有理由懷疑，自然產(chǎn)生的高維數(shù)據(jù)可能駐留在一個低維流形。這導致我們?nèi)タ紤]降維方法，這種方法允許高維數(shù)據(jù)代表一個較低維空間中的數(shù)據(jù)。要達到此目的，有兩個最流行的方法，分別是是主成分分析（PCA）和線性判別分析（LDA）。主成分分析法是一種無監(jiān)督的方法。該方法是通過將原來的N維數(shù)據(jù)投影到高維的線性子空間的方式來實現(xiàn)降維，而線性子空間通過數(shù)據(jù)的協(xié)方差矩陣的主要特征向量來跨越。它的目標是找到一組相互正交的基函數(shù)，用于捕獲數(shù)據(jù)中最大方差的方向，因此，成對的歐氏距離可以最好地保存。如果數(shù)據(jù)被嵌入在一個線性子空間，主成分分析可以保證挖掘出子空間的維數(shù)，并產(chǎn)生一個簡潔的表示。LDA是一種有監(jiān)督的方法。它搜索項目軸，在該軸上，不同類別的數(shù)據(jù)點相距很遠，同時要求同一類的數(shù)據(jù)點彼此接近。當標簽信息可獲得時，例如，用于分類任務,LDA可以實現(xiàn)的性能優(yōu)于PCA。然而，當相對于維度數(shù)量沒有足夠的訓練樣本的時，每個類的協(xié)方差矩陣的估計可能不準確。在這種情況下，測試樣品的泛化能力不能得到保證。一個可行的解決方案可以應對培訓（標記）樣本不足的情況，該方法既學習標記得數(shù)據(jù)又未標記的數(shù)據(jù)（半監(jiān)督和直推式學習）。這種方法既時自然的也是合理的，因為在現(xiàn)實中，我們通常只有一部分的輸入數(shù)據(jù)被標記，以及大量的未標記的數(shù)據(jù)。在過去的幾十年中，半監(jiān)督學習（或直推式學習）吸引了越來越多的關注。兩個眾所周知的算法分別是直推式支持向量機（TSVM）和協(xié)同訓練。最近，基于半監(jiān)督學習算法的圖像分析有相當大的興趣和成功，這種方法考慮將所有的樣本的圖形作為前提來指導決策。所有這些算法考慮的都是分類問題，要么直推法，要么歸納法。在本文中，我們的目標是在半監(jiān)督的情況下的降維。我們提出了一種半監(jiān)督降維算法，稱為半監(jiān)督判別分析（SDA）。SDA的目的是找到一個投影，這個投影代表從標記的數(shù)據(jù)點中推斷出的判別結(jié)構，以及代表從標記和未標記的數(shù)據(jù)點中推斷出的固有的幾何結(jié)構。具體而言，這些結(jié)合未標記的數(shù)據(jù)點標記的數(shù)據(jù)點，被用于建立一個包含數(shù)據(jù)集鄰域信息的圖。該圖提供了一個相對于數(shù)據(jù)流形局部幾何的離散的近似值。利用拉普拉斯圖的概念，圖上的一個平滑可以納入目標函數(shù)。這樣，我們的SDA算法可以優(yōu)化保留流形結(jié)構。本文的其余部分組織如下。在第2節(jié)中，我們提供LDA簡要回顧。在第三部分中，我們介紹我們的半監(jiān)督判別分析（SDA）的降維算法。在第4節(jié)，稱述實驗結(jié)果。最后在第5節(jié)，我們總結(jié)本文，并為今后的工作提供建議。LDA的圖視角線性判別分析（LDA）尋求某種方向，再次方向上的不同類別的數(shù)據(jù)點相距很遠，同時要求同一類的數(shù)據(jù)點彼此接近。假設我們有一組L樣本XXXRn，屬于C類。LDA的目標1,2,l

函數(shù)如下：函數(shù)如下：aTSaa二argmaxb-optaaTSaW，(1)，（2）S=才lC(k)_卩人^)一，（2）k=1=1l任C)-4)X(k)-4))iiTOC\o"1-5"\h\zk=1Ji=1丿,(3)卩l(xiāng)卩?）x（）ki其中，是總樣本的均值向量，是k類樣本數(shù)，是第k個類的平均向量，是SS在第k個類的第i個樣本。我們稱w為類內(nèi)散布矩陣，稱b為類間散布矩陣。S=21（X-卩）（-卩》S=S+S確定的總散射矩陣ti=1ii,我們有twb，那么公式（1）中的線性判別分析的目標函數(shù)就等于，（4）aTSaa=argmaxioptaaTSa，（4）t最佳的a是與本征問題的非零特征值對應的特征向量:Sa二九Sabt，（5）Sb由于的階是由CT限制，所以最多的有CT個非零特征值對應的特征向量。卩=01無一般性損失，我們假設。我們有bkkbkk=1=21=211丄ILx(k)k(iik=1ki=1k=1讓數(shù)據(jù)矩陣X=LG,...,X（）］并且定義一個1x1的矩陣J為其中，W財是一個i讓數(shù)據(jù)矩陣X=LG,...,X（）］并且定義一個1x1的矩陣J為_W(1)0...0"w=lxl0w(2)...0(6)_00...W(c)_我們有s=￡xawa)Q=xwxt(7)blxlk=1因此，在方程式(4)中線性判別分析的目標函數(shù)可以改寫為aTSaaTxwxTaa=argmaxi=argmax陽(8)optaaTSaaaTxxTatLDA目標函數(shù)的公式將對發(fā)展我們的算法是非常有幫助的。他第一次被介紹在14半監(jiān)督判別分析LDA考慮者正尋求完全基于訓練集的最優(yōu)預測。在現(xiàn)實中，獲得一個大規(guī)模未標記的數(shù)據(jù)集是有可能的。在這部分中，我們試圖擴展LDA模型去涵蓋由未標記的數(shù)據(jù)表示的流形結(jié)構。3.1.目標函數(shù)LDA的目的是找到一個投影向量a，以至于aTSa和aTSa之間的比例最大化。當沒有足夠bt的訓練樣本時，過擬合將發(fā)生。一個防止過擬合的E典型方法來是加強規(guī)范化。LDA的規(guī)范化版本的優(yōu)化問題可以寫成如下：maxaamaxaaTSa

aTS+aJ(a)t9)其中，J(a)控制假設群的學習復雜度，而系數(shù)a控制模型復雜度與實驗誤差之間的平衡。一個最流行的正則化是Tiknonov正則化［21］J(a)=|^|2帶有Tikhonov正則化的LDA模型通常被稱為正則化判別分析(RDA)［8］。正則化項J(a)為我們提供了一定的靈活性，幫助我們吸收特定應用的先驗知識。當可獲得一組未標記樣本時，我們的目標是建立一個結(jié)合的流形結(jié)構的JC)。半監(jiān)督學習算法的關鍵是一致性的先驗假設。對于分類，它意味著附近的點有可能有相同的標簽［26］。對于降維，它可以解釋為附近的點將有類似的嵌入(低維表示)。給出一組例子＜h，我們可以ii=1用一個p最鄰近的圖G模擬附近的數(shù)據(jù)點之間的關系。具體來說，如果xi和xj是“關閉”我們在節(jié)點i和j之間設置一個界限，換言之，xi和xj是近鄰之間的相互。讓相應的權重矩陣為S,定義為「1,ifxeN(xIrxeN(x)S=<iPjjPi(10)ij10,otherwise其中，N(x)表示P最近鄰的集合。在一般情況下，映射函數(shù)在圖上應該是盡可能光滑的。pi具體來說，如果兩個數(shù)據(jù)點是由一個邊緣連接的，它們很可能是在同一個類中的。此外，那些與子圖緊密聯(lián)系的子圖可能有相同的(標簽。因此，)一個自然的正交化矩陣可以定義如下J0=1(itx-aTx)S(11)ijijij這一公式由光譜數(shù)據(jù)降維［2，13］引出，它也在譜聚類算法［17］和多種的基于半監(jiān)督學習算法［3，6，20］圖表中起著關鍵的作用。讓X=lx,xx］，我們有12J(a)=Z(aTx-aTx)2Sijij=2工aTxDxTa-aTxSxTaiiiiiijj=2aTX(D-S)XTa=2aTXLXTa其中，D是一個對角矩陣；其條目是S的列(或行，因為S是對稱的)的總和，D=工S，iijijL=D-S是拉普拉斯矩陣［7］這個數(shù)據(jù)依賴于的正規(guī)化矩陣，我們得到半監(jiān)督判別分析的目標函數(shù)aTSamax一(b)(12)aaT^S+aXlXt丿at最大化目標函數(shù)的的投影向量a由解決廣義特征值問題的最大特征值求得:Sa=X+aXLXt丿a（13）bt3.2算法給定一個屬于c類的標記集€y力和一個為標記集(x}m。第k類有1個樣品,i,ii=1ii=l+1k工cl二l。不失一般性，我們假設在?…,x^中的數(shù)據(jù)點根據(jù)自己的標簽來排序。k=1ki,1半監(jiān)督判別分析的算法程序如下：1?構造鄰接圖：構建P的近鄰圖矩陣S,正如公式(10)所示，計算該圖的拉普拉斯矩陣L=DS.2?構建標記圖：為標記圖構建權重矩陣X-E，如下:W1x100其中，性1W辰m矩陣就是在公式6中所定義的，即定義

其中，丨是大小為lXl的恒等矩陣3.本征問題：計算廣義特征向量問題的特征向量以及對應的非零特征值。（?\XWXTa=XX+aLXtq,（14）k1丿其中，X二Lxx...x]1,l,l+1,m檢查W是否是C級是很簡單的，我們將將計算C的特征向量以及相對應的非零特征值］。我們用a...a來表示。1,c4.SDA的嵌入：讓A二Laa1A是一個nxc的變換矩陣。通過XtZ二ATX,1,2,c樣品可以嵌入到C維子空間。讓X=Lx〕表示標記數(shù)據(jù)矩陣。易得，XWXt二XWXt二S以及1,lllxllbX?Xt=XXt=SIllt因此，公式14中的特征問題和公式13中的特征問題一樣。（?）為了得到一個穩(wěn)定解決公式14中的本征問題的方案、矩陣X/+aLIXt必須是非奇異的,當特征數(shù)大于樣本數(shù)時，該矩陣不正確。在次問題中，我們可以應用吉洪諾夫正則化思想作為正則化判別分析的方法。因此，我們的廣義特征問題出現(xiàn)了：XWXta二XWXta二九（（~）x+alTXt+pIa（15）kkI丿丿（對于B>0,矩陣X_+alXt+pI肯定是非奇異。我們也可以使用光譜譜回歸技術來kI丿丿解決這個奇異性問題，請參閱［5］。3.3核心半監(jiān)督判別分析算法上面描述的算法是一個線性方法。當數(shù)據(jù)流形具有高度非線性時，它可能無法發(fā)現(xiàn)內(nèi)在的幾何結(jié)構。在這一部分，我們將討論如何用（RKHS）執(zhí)行SDA算法，該算法對SDA有很大的提升。這里所使用的方法基本上與13相似。我們認為，功能空間F中的問題是由一些非線性映射引起。選擇合適的內(nèi)積0，它可以在F上定義，F(xiàn)創(chuàng)造一個所謂的再生核