基于兩階段流形學習的半監督維數約簡算法

徐金成，李曉東，劉 輝

(1.廣東司法警官職業學院 信息管理系，廣東 廣州 510520； 2.國家計算機網絡應急技術處理協調中心廣東分中心， 廣東 廣州 510665)

0 引 言

維數約減算法的目的是在保持數據的本質信息的前提下減少數據的復雜度。目前有大量半監督維數約簡算法提及：半監督維數約減算法能夠同時利用有標簽和無標簽訓練樣本進行綜合考慮。

一些研究者定義新的優化目標。Jincheng Xu[1]提出了一種對稱局部保持的半監督維數約減(SLPSDR)算法，該方法主要是針對自然界較多圖像具有對稱的特點以及數據分布大多呈一定的流行結構情況。Yi Yang等[4]提出一種排序學習的半監督維數約減算法，使用局部預測誤差表示樣本之間的流形結構，該方法假設的流形結構與多媒體數據有較好的一致性，但是該方法沒有處理全局流形結構。Jia Wei等[3]提出一種結合局部和全局拓撲結構的半監督維數約簡算法，該方法通過最小化類內距離和類間距離來突出分類結構，局部拓撲結構通過最小化局部重構誤差實現，全局拓撲結構通過最大化不在鄰域的樣本之間的距離實現。

一些研究者定義新的流形結構。Tingjin Luo等[8]提出一種判別正交彈性投影保持方法(DOEPP)，該方法使用EPP中的方法構建局部圖和全局圖，使用最大間距準則中的方法提取判別信息和正交信息。Puhua Chen等[5]提出一種基于稀疏圖的半監督維數約簡方法，該方法首先利用鄰域對無標簽樣本賦予偽標簽，然后根據標簽建立類內和類間稀疏表示圖，最后使用特征分解方法得到映射矩陣。蘭遠東等[6]通過最小化樣本到其所屬類別的中心點之間的距離，得出其鄰域的拓撲結構；再通過最大化不同類別邊緣間的距離，在投影子空間中就可以增強類別間的分離度。王憲保等[7]提出了一種半監督等距映射算法，該方法使用訓練樣本的標簽樣本構建K連通圖，得到近似樣本間測地線距離，并把它作為矢量特征代替原始數據點；然后通過測地線距離計算核矩陣，用半監督正則化方法代替多維尺度分析算法處理矢量特征；最后利用正則化回歸模型構建目標函數，得到低維表示的顯式映射。Xianglei Xing等[9]通過融合多種局部集合信息來獲得可信度更高的流形結構。ShengHuang等[10]提出一種全局局部保持的維數約簡算法，該方法使用薄板樣條和核徑向基核擬合數據的流形結構，能夠捕獲到步態中動態和靜態特征。

上述方法在建立數據流形結構時，直接使用高維數據。但是高維數據在樣本空間非常稀疏，流形結構可能不明顯，并且流形結構也容易受到噪聲的影響，導致保持該流形結構對分類的意義減小。為了克服上述問題，本文提出先利用原始數據建立數據的流形結構，并在該流形結構的基礎上，將訓練數據映射到低維空間。然后在低維空間中，建立新的數據流形結構，并在該流形結構的基礎上，得到最終的映射矩陣。顯然，在低維空間建立流形結構有3個好處：①低維空間由根據整個訓練數據學習到的映射矩陣獲得，能夠過濾掉噪聲的影響；②低維空間獲得時，還考慮了有標簽訓練數據，建立的流形結構考慮了類別結構；③在低維空間中數據維度更低，流形結構更明顯。

1 算法基礎

TSMSDR算法是在線性判別分析和局部嵌入的基礎上研究得到，所以本節對這兩種算法進行簡單介紹。

1.1 線性判別分析(LDA)

(1)計算樣本的類內距離Sw和類間距離Sb

(1)

(2)

其中，C為類的個數，ui為第i類樣本的均值，ni為第i類樣本的個數。

(2)計算Sw=λSb的特征值，并將特征值從大到小排序，選取前k個特征值對應的特征向量w1,w2,…,wk構成m×k的映射矩陣W。

(3)可使用Y=WTX將數據從高維空間映射到低維空間。

1.2 局部與全局保持的半監督維數約減(LGSSDR)

(3)

(4)

Sw定義如下

(5)

Sb定義如下

(6)

Sf定義如下

(7)

1.3 判別正交彈性投影保持方法(DOEPP)

(8)

(9)

(10)

2 兩階段流形學習半監督維數約簡算法(TSMSDR)

本節將給出本文提出的對稱局部保持半監督維數約簡算法，首先給出視覺信息處理中的對稱現象及其保持方法，然后給出TSMSDR的目標函數及其優化方法，最后給出本文提出的TSMSDR算法。

2.1 TSMSDR的目標函數及其優化

(11)

其中，Lb與Lw的定義與式(3)中的Lb與Lw相同，Lg′=Dg′-Sg′,Sg′定義如下

(12)

Lm′分成兩階段定義，第一階段Lm′的定義與式(3)中的Lm定義相同。第二階段Lm′的定義如下

Lm′=(I-A′)T(I-A′)

(13)

其中，A′使用下式優化得到

(14)

可以看到優化式(11)是一個廣義瑞利商的問題[3]，如果Lw+aLm′非奇異，那么式(11)的優化可通過求解下式的特征值和特征向量完成

X(Lb+aLg′)XTw=λ(Lw+aLm′)w

(15)

將特征值從大到小排序，選取前k個特征值對應的特征向量w1,w2,…,wK構成m×K的映射矩陣W。

2.2 TSMSDR算法

根據前面一節的描述，TSMSDR可總結成如下算法：

算法TSMSDR:

輸出：映射矩陣W

(1)在輸入數據的基礎上。根據式(5)和式(6)計算Lb和Lw。根據式(12)計算Lg′。根據式(13)計算第一階段的Lm′。

(5)使用Lb,Lw,Lg′和第二階段的Lm′，根據式(11)計算第二階段的映射矩陣W。

2.3 TSMSDR算法的理論依據

本小節依次分析式(11)中各個組成部分的原理與作用。

Lb,Lw的定義與式(3)中的Lb,Lw一樣。其中最大化WTXLbXTW，可以最大化低維空間中類間樣本之間的距離；最小化WTXLbXTW，可以最小化低維空間中同類樣本之間的距離。達到使分類結構更突出的目的。

Lg′的定義根據式(10)改進而來。該式的功能與式(3)中Lf的功能相似，能夠保持數據的全局流形結構。但是式(3)中Lf有一定的缺點。首先式(7)在定義Lf時樣本對之間的權重相同，導致即使兩個樣本之間的距離非常大時，依舊有可能最大化這兩個樣本之間的距離。顯然，使兩個離得非常遠的樣本之間的距離離得更遠意義不大。其次，式(7)在定義Lf時，只定義鄰域之外的樣本對之間的關系，這會導致鄰域之外和鄰域之內的樣本之間的關系在優化時，賦予的職能會發生突然變化，影響樣本之間流形結構的保持。這對本文算法的影響較大，因為本文算法需要利用第一階段維數約減結果建立流形結構。

Lm′的計算公式與式(3)中Lm的計算公式相同，兩者的差別是Lm′分成兩階段計算得到。第一階段直接使用原始高維數據計算得到，第二階段使用第一階段獲得的低維數據計算得到。本文使用兩階段的方法計算Lm的原因是：在大部分實際應用中，訓練樣本的維度經常遠遠大于訓練樣本的個數，即容易出現高維度小樣本的問題。這會導致在原始高維數據上的流形結構不明顯，并且容易受到噪聲的影響。

使用兩階段的流形結構建立方法有如下好處：①本文使用式(12)定義一種漸變的全局流行結構定義方法，可以使第一階段獲得的低維空間中的流形結構并不會發生較大的變化，為第二階段流行結構的建立打下了基礎；②另外在第一階段獲得低維空間時，還考慮了類別結構，使第二階段建立的流形結構中蘊含分類信息；③第二階段建立流形結構的輸入數據維度更低，可以使流形結構更加明顯；④經過一次維數約簡之后建立的流行結構，對數據小的變化和噪聲有一定的克服能力。

3 實驗結果

3.1 對比算法與實驗設置

TSMSDR是一種維數約簡算法，其中維數約簡算法有無監督、有監督和半監督維數約簡算法，所以本文將與以下算法比較：①無監督維數約簡算法，包含主成分分析法(principal components analysis，PCA)；②有監督維數約簡算法，局部投影保持(locality preserving projection，LPP)[2]，包含線性判別分析(linear discriminant analysis，LDA)[2]，判別正交彈性投影保持方法(discriminative orthogonal elastic preserving projections，DOEPP)[8]；③半監督維數約簡算法，包含局部與全局拓撲結構保持半監督維數約簡算法(local and global structures for semi-supervised dimensionality reduction，LGSSDR)[3]，邊緣判別嵌入與局部保持的半監督維數約減算法(semisupervised marginal discriminant embedding and local preserving for dimensionality reduction，SSMDELPDR)[6]。其中LGSSDR，DOEPP，SSMDELPDR均需要設置平衡參數。其中LGSSDR需要設置全局保持和局部保持平衡參數，均設為0.1。DOEPP需要設置彈性保持能力平衡參數，設為0.1。SSMDELPDR需要設置邊緣嵌入平衡參數，設為0.1。

一般來說維數約簡的主要目的是分類，所以在維數約簡后使用分類器驗證各個半監督維數約簡的效果。支持向量機(support vector machine，SVM)[12]是一種非常經典的分類器，并且能取得較為穩定的結果。所以本文使用SVM作為分類器。另外因為維數約簡后，以及本文算法在人臉數據庫上驗證，在維數約簡之后，各個類的訓練數據均能較為密集的聚集在一起，所示SVM使用線性核函數。

驗證半監督維數約簡算法需要3種數據：有標簽訓練數據，無標簽訓練數據，以及測試數據。本文采用兩種實驗設置驗證算法。第一種從每個類別中隨機選擇3個作為有標簽訓練數據，再從剩下的數據中再隨機選擇3個作為無標簽訓練數據，其它剩下的數據為測試數據。第二種從每個類別中隨機選擇6個作為有標簽訓練數據，再從剩下的數據中再隨機選擇3個作為無標簽訓練數據，其它剩下的數據為測試數據。這里使用不同的有標簽訓練數據的目的是為了說明本文算法對訓練數據的個數不敏感。為了減小樣本不一樣帶來實驗結果的差異，以上實驗重復執行50次，這50次實驗的均值作為最終實驗結果。另外，本文對比的大部分算法均能達到較高維度的維數約簡結果，本文將維數約簡之后的維度取值為20,40,60,80,100,120,140,160等，其目的是為了說明維數約簡之后的衛隊對對比算法的影響。實驗結果使用準確度(accuracy)評價。

3.2 分類結果

為了驗證TSMSDR，分別使用所有參與對比算法進行維數約簡，使用SVM作為分類器，根據分類結果評價TSMSDR。先給實驗策略1在4個人臉數據庫上的分類結果，實驗結果在表1中給出，在該實驗策略中有標簽訓練數據從每個類別隨機選取3個，無標簽訓練數據從每個類別剩余的數據中隨機選取3個，其它數據為測試樣本。從表1中可以看到，TSMSDR的實驗結果比第二好的實驗結果在4個數據庫中分別高1.08%，1.160%，0.78%，2.33%，驗證了TSMSDR的有效性。

表1 所有算法在4個數據庫的最大分類準確度(使用3個有標簽訓練樣本)

另外為了對比TSMSDR與其它對比的算法投影到不同維度時的實驗結果，將使用實驗策略1時，所有算法在4個數據庫上投影到不同維度時的準確度分別在圖1到圖4給出。從圖1到圖4可以看到，在4個數據庫上，TSMSDR能在較低維度上就能達到較高的分類準確度，這在對速度要求非常高的應用環境中，可以將數據投影到更低的維度，以加快算法的執行速度。另外從圖1到圖4還可以看到，TSMSDR能在較多的維度上取得較為穩定的準定度，對在實際應用中選擇合適的投影子空間的維度K更有利。

圖1 所有算法在PIE數據庫上投影到不同維度時的準確度

圖3 所有算法在ORL數據庫上投影到不同維度時的準確度

圖4 所有算法在AR數據庫上投影到不同維度時的準確度

同樣，在表2中給出實驗策略2在4個數據庫上的實驗結果，在該實驗策略中有標簽訓練數據從每個類別隨機選取6個，無標簽訓練數據從每個類別剩余的數據中隨機選取3個，其它數據為測試樣本。從表2中可以看到，TSMSDR的實驗結果比第二好的實驗結果在4個數據庫中分別高1.27%，1.79%，0.90%，0.70%，驗證了TSMSDR的有效性。

表2 對比算法在4個數據庫的最大分類準確度(使用6個有標簽訓練樣本)

同樣，為了對比TSMSDR與其它對比的算法投影到不同維度時的實驗結果，將使用實驗策略2時，所有算法在4個數據庫上投影到不同維度時的準確度分別在圖5到圖8給出。從圖5到圖8可以看到，TSMSDR能在較低維度上就能達到較高的分類準確度，能在較多的維度上取得較為穩定的準定度，以及在大部分維度上的識別均高于其它算法的識別率。

圖5 所有算法在PIE數據庫上投影到不同維度時的準確度

圖6 所有算法在YaleB數據庫上投影到不同維度時的準確度

圖7 所有算法在ORL數據庫上投影到不同維度時的準確度

圖8 所有算法在AR數據庫上投影到不同維度時的準確度

4 結束語

本文算法注意到在大部分實際應用中，在原始高維數據上建立的流形結構不穩定，不突出，提出一種兩階段的流形結構建立方法。第一階段在原始高維數據上建立流形結構，第二階段在第一階段獲取的低維空間中建立流形結構。另外為了使第一階段獲取的低維空間流形結構不發生較大的變化，本來還使用一種新的方法建立樣本的全局關系。

實驗結果表明，本文算法在人臉識別上能有較好的維數約簡的效果。但是，本文通過數據的全局結構保持，以減小第一階段獲得的低維空間的流形結構與原始數據的流形結構之間的差別，從而為兩階段的流形結構打下基礎。該方法可能在一定程度上使第二階段的流形結構并不完全正確。所以在將來研究一種更好的方法使建立的流形結構能夠克服高維小樣本的問題。