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

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

aTS+aJ(a)t9)其中，J(a)控制假設群的學習復雜度，而系數a控制模型復雜度與實驗誤差之間的平衡。一個最流行的正則化是Tiknonov正則化［21］J(a)=|^|2帶有Tikhonov正則化的LDA模型通常被稱為正則化判別分析(RDA)［8］。正則化項J(a)為我們提供了一定的靈活性，幫助我們吸收特定應用的先驗知識。當可獲得一組未標記樣本時，我們的目標是建立一個結合的流形結構的JC)。半監督學習算法的關鍵是一致性的先驗假設。對于分類，它意味著附近的點有可能有相同的標簽［26］。對于降維，它可以解釋為附近的點將有類似的嵌入(低維表示)。給出一組例子＜h，我們可以ii=1用一個p最鄰近的圖G模擬附近的數據點之間的關系。具體來說，如果xi和xj是“關閉”我們在節點i和j之間設置一個界限，換言之，xi和xj是近鄰之間的相互。讓相應的權重矩陣為S,定義為「1,ifxeN(xIrxeN(x)S=<iPjjPi(10)ij10,otherwise其中，N(x)表示P最近鄰的集合。在一般情況下，映射函數在圖上應該是盡可能光滑的。pi具體來說，如果兩個數據點是由一個邊緣連接的，它們很可能是在同一個類中的。此外，那些與子圖緊密聯系的子圖可能有相同的(標簽。因此，)一個自然的正交化矩陣可以定義如下J0=1(itx-aTx)S(11)ijijij這一公式由光譜數據降維［2，13］引出，它也在譜聚類算法［17］和多種的基于半監督學習算法［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］這個數據依賴于的正規化矩陣，我們得到半監督判別分析的目標函數aTSamax一(b)(12)aaT^S+aXlXt丿at最大化目標函數的的投影向量a由解決廣義特征值問題的最大特征值求得:Sa=X+aXLXt丿a（13）bt3.2算法給定一個屬于c類的標記集€y力和一個為標記集(x}m。第k類有1個樣品,i,ii=1ii=l+1k工cl二l。不失一般性，我們假設在?…,x^中的數據點根據自己的標簽來排序。k=1ki,1半監督判別分析的算法程序如下：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〕表示標記數據矩陣。易得，XWXt二XWXt二S以及1,lllxllbX?Xt=XXt=SIllt因此，公式14中的特征問題和公式13中的特征問題一樣。（?）為了得到一個穩定解決公式14中的本征問題的方案、矩陣X/+aLIXt必須是非奇異的,當特征數大于樣本數時，該矩陣不正確。在次問題中，我們可以應用吉洪諾夫正則化思想作為正則化判別分析的方法。因此，我們的廣義特征問題出現了：XWXta二XWXta二九（（~）x+alTXt+pIa（15）kkI丿丿（對于B>0,矩陣X_+alXt+pI肯定是非奇異。我們也可以使用光譜譜回歸技術來kI丿丿解決這個奇異性問題，請參閱［5］。3.3核心半監督判別分析算法上面描述的算法是一個線性方法。當數據流形具有高度非線性時，它可能無法發現內在的幾何結構。在這一部分，我們將討論如何用（RKHS）執行SDA算法，該算法對SDA有很大的提升。這里所使用的方法基本上與13相似。我們認為，功能空間F中的問題是由一些非線性映射引起。選擇合適的內積0，它可以在F上定義，F創造一個所謂的再生核