基于隨機投影的正交判別流形學習算法

馬　麗，　董唯光，　梁金平，　張曉東

(蘭州交通大學 自動化與電氣工程學院　甘肅 蘭州 730070)

?

基于隨機投影的正交判別流形學習算法

馬麗，董唯光，梁金平，張曉東

(蘭州交通大學 自動化與電氣工程學院甘肅 蘭州 730070)

摘要：提出一種基于流形距離的局部線性嵌入算法，以流形距離測度數據間的相似度，選擇各樣本點的近鄰域，解決了歐氏距離作為相似性度量時對鄰域參數的敏感性.在MDLLE算法中引入最大邊緣準則(maximum margin criterion,MMC)來構建最優平移縮放模型，使得算法在保持LLE局部幾何結構的同時，具有MMC準則判別能力.通過正交化低維特征向量可消除降維過程中的噪聲影響，進而提高算法的監督判別能力.由實驗結果得到,所提出的方法具有良好的降維效果，能有效避免局部降維算法對鄰域參數的敏感.隨機投影獨立于原始高維數據，將高維數據映射到一個行單位化的隨機變換矩陣的低維空間中，維持映射與原始數據的緊密關系，從理論上分析證明了在流形學習算法中采用隨機投影可以高概率保證在低維空間保持高維數據信息.

關鍵詞：流形學習算法； 鄰域選擇； 流形距離； 正交判別； 局部線性嵌入； 隨機投影

0引言

在當今的信息社會中，人們獲得數據和信息的能力越來越強.而這些數據信息呈現出的特性是高維數、大規模和結構復雜等.那么如何從這些繁雜的數據中迅速提取有價值的信息，引起了人們的關注和研究.因此，數據的維數約簡就顯得尤為重要了.數據降維，一方面可以解決“維數災難”，緩解“數據爆炸但知識貧乏”的現狀[1]，降低復雜度；另一方面可以更好地認識和利用數據.

流形學習用于數據維數約簡，已成為數據挖掘的研究熱點.假設數據是均勻采樣于一個高維觀測空間中的低維流形，流形學習就是從高維采樣數據中恢復這個低維流形結構[2]，并求出相應的低維嵌入映射，以實現數據降維或數據可視化.它是從觀測到的現象中去尋找事物的本質，找到復雜數據的內在規律.近年來，流形學習鄰域已取得了大量的研究成果.經典的非線性流形學習算法有等距特征映射算法(isometric map, isomap)[1]、局部線性嵌入算法(locally linear embedding, LLE)[2]、Laplacian 特征映射算法(Laplacian eigenmaps, LE)[3]、Hessian 特征映射算法(Hessian-based locally linear embedding, HLLE)[4]、局部切空間排列算法(local tangent space alignment, LTSA)[5]和黎曼流形學習算法(Riemannian manifold learning)等.現有的流形學習算法根據所保持幾何特性的不同，可分為局部特性保持算法和全局特性保持算法.局部特性保持算法主要是保持流形的局部幾何結構特性，通過映射建立高維觀測空間與低維流形之間的聯系，在低維流形空間中保持近鄰域所具有的局部結構.全局特性保持算法主要是保持低維流形的全局幾何結構，構造所有數據點對之間的全局度量矩陣，再將度量矩陣轉化為內積矩陣并求解其特征向量，即可獲得數據集的內在低維結構.目前，很多研究者對上述經典算法進行改進，如有監督的流形學習算法[3]、增量式流形學習算法等[6—7]，顯著提高了原始算法的性能.

針對局部降維算法中近鄰參數K的選取問題，很多研究者提出了自適應選擇近鄰算法[8—11].文獻[12]通過分析數據集中任意樣本所在局部區域的線性重構誤差，確定該局部區域的近似線性塊，然后根據位于此局部線性塊上的樣本數來自適應地選擇局部線性嵌入的近鄰參數K.文獻[13]提出的鄰域參數動態變化的局部線性嵌入算法，根據測地距離與歐氏距離的關系動態確定數據點的鄰域.該方法能獲得較好的效果，但計算復雜度較高，在處理非均勻分布的數據流形時，歐氏距離作為相似性度量無法反映樣本的全局一致性，而流形距離[14]能有效反映樣本固有的全局一致性信息.故本文提出一種基于流形距離的局部線性嵌入算法(locally linear embedding algorithms based on manifold distance, MDLLE)，通過流形距離作為樣本間相似性度量的測度，對空間分布復雜的流形結構的數據具有更好的性能.

隨機投影[15—17]是維數約簡中出現的一種新方法，尤其Johnson-Lindenstrauss (JL)引理[16]給出了一個重要的結論，利用隨機投影可將N維歐氏空間中包含任意n個點的集合映射到K維的歐氏空間(K?N)，并且能以較高的概率保持原空間中任意兩點間距離變化極小.也就是說，可以隨機選擇一個適當的高維子空間(需比原始空間維度小)，原始空間兩點間的距離投影到這個子空間，能高概率地保持這種距離關系.本文用理論證明了隨機投影保持原始數據信息的有效性，在LLE算法中采用隨機投影實現從高維空間到低維空間的映射，以較高的概率保證投影后數據點之間的距離信息變化不大.

1局部線性嵌入算法

局部線性嵌入算法[2]是一種局部特性保持方法，核心是保持降維前后近鄰之間的線性結構不變.其前提假設是高維數據所在的低維流形是局部線性的，即每個樣本點可以用其近鄰點線性表示.算法的主要思想是通過在低維嵌入空間中保持每個數據點的近鄰重構系數來保持整個數據的流形結構，即以重構權值矩陣作為高維觀測空間與低維嵌入空間的聯系橋梁：高維觀測空間的每個數據點用其近鄰點線性表示的權重與它們在低維嵌入空間中線性表示的權重保持一致.由于流形上的局部可以認為是一個局部歐式空間，因此每個樣本點與其近鄰樣本之間是線性關系，從而一個樣本可以用其近鄰樣本的線性組合來重構.

LLE算法包含以下3個基本步驟：

1) 構造近鄰域.對于給定的數據集X=[x1,x2,…,xn]∈RD×n，在高維數據空間，通過歐氏距離尋找與每個樣本點最近的k個近鄰，xi的k個近鄰集合為N(xi)={xi1,xi2,…,xik}.

2) 計算高維空間中的局部線性表示.權值矩陣W 對于每個樣本點xi及其近鄰集N(xi)={xi1,xi2,…,xik},是通過最小二乘法極小化每個樣本點的重構誤差得到，即：

其中:權值wij反映了樣本點xj對xi重構的貢獻.

3) 求低維嵌入Y.在低維空間用各個樣本點的近鄰重構其本身，即求Y=[y1,y2,…,yN]，使得重構誤差最小，設置誤差函數為：

圖1　LLE算法的降維效果Fig.1　Reduction-dimensional effect of LLE

2基于流形距離的局部線性嵌入

2.1流形距離

由于數據集的低維流形分布，用歐氏距離來選擇最近鄰域時，這些選擇的近鄰點不能準確地表征流形上的真正鄰域結構.為了解決流形上數據的最近鄰點的選擇，提出一種新的相似度度量來計算數據點間的最短距離.

定義1流形上兩點xi,xj的線段長度定義為：

(1)

其中：d(xi,xj)表示xi,xj之間的歐氏距離，τ是可調參數.

(2)

其中：L(a,b)表示兩點間流形上的線段長度.流形距離滿足以下4個條件：

1) 對稱性：MD(xi,xj)=MD(xj,xi)；

2) 非負性：MD(xi,xj)≥0；

3) 三角不等式：對任意的xi,xj,xk，有MD(xi,xj)≤MD(xi,xk)+MD(xk,xj)；

4) 自反性：MD(xi,xj)=0，當且僅當xi=xj.

兩個數據點間的距離越小，它們的相似度越高.因此，定義xi,xj間的相似度為：

(3)

需說明的是，本文定義樣本自身的相似度為0，即當i=j時，σij=0.

2.2基于流形距離的鄰域選擇

當數據集不滿足全局線性結構時，用歐氏距離度量數據間的相似度，選取近鄰點是不合理的.而流形距離測度滿足上述的自反性、非負性、對稱性及三角不等性，故使用流形距離可以反映空間分布復雜的流形數據[18].如圖所示，圖2是用歐氏距離作為測度所選的近鄰點，圖3是用流形距離作為測度所選的近鄰點，圖中黑色實心點X、Y為樣本點，以X、Y為中心的近鄰域由虛線圓畫出.相同流形上兩點間的距離較短，不同流形上兩點間的距離較長，從圖上可以觀察到以流形距離為測度給樣本點X、Y選出的近鄰點更合理.圖4中S型曲線上有兩點M、N分別用流形距離和歐氏距離選出其近鄰域，如圖所示以流形距離作為測度所選的近鄰域用實線畫出，以歐氏距離作為測度所選的近鄰域用虛線畫出，當曲率較大時采用歐氏距離選出的近鄰域不能反映流形的局部結構，而基于流形距離的近鄰域選擇可以很好地反映流形的局部結構.

圖2　以歐氏距離所選的近鄰點Fig.2　Neighbors selected by Euclidean

圖3　以流形距離所選的近鄰點Fig.3　Neighbors selected by manifold

圖4　S型曲線上樣本點的近鄰選擇Fig.4　Neighbors selected on the S curve

根據上述定義，可以計算數據集中任意兩點間的流形距離，然后選擇合適的鄰域.算法流程如下.

步驟1利用K最近鄰算法的思想，由式(1)構建線段長度矩陣L；

步驟2利用式(2)計算數據點對之間最短的路徑，得到流形距離，并根據式(3)計算數據點對間的相似度.

步驟3根據步驟2 計算出的點對間的相似度選擇樣本點xi的最近鄰點得到近鄰點數.

2.3基于流形距離的局部線性嵌入算法

用流形距離代替歐氏距離計算.假設數據樣本集X=[x1,x2,…,xn]∈RD×n，根據2.2節描述的算法計算線段長度矩陣L，進而求出流形距離MD.使用流形距離作為相似度度量構造算法的目標函數，并求出各個樣本點xi的K個近鄰點xi1,xi2,…,xik.對任意樣本點xi，用其近鄰點的線性組合重構xi，使得誤差函數在流形距離度量下最小.在低維空間用各個樣本點的近鄰重構其本身，即求Y=[y1,y2,…,yN]，使得重構誤差最小.

用流形距離表示權值矩陣W：

根據歐氏距離下定義的權值系數，可得：

故可將流形距離下的權值矩陣表示為：

在低維空間中用流形距離表示的權值矩陣計算低維嵌入Y，使其重構誤差最小，則重構誤差函數為：

構造目標函數，如下：

(4)

約束條件：ATXMXTA=I.

由于隨機投影在降維后能很好地保持原高維數據的主要特性，因此在MDLLE算法從高維到低維映射的過程中采用隨機投影，建立足夠多的隨機映射算子，保證在降維過程中高概率地保持原始數據信息.

3隨機映射定理

這個定理說明，對于任意一個樣本大小為m的集合，如果通過隨機投影將其維度降到一個合適的范圍內，那么將以較高的概率保證投影后數據點之間的距離信息變化不大.因此，在LLE算法中用隨機投影將流形距離投影到低維空間，保證了投影后數據點間的距離信息不發生太大變化.在MDLLE算法中要保持不變的是近鄰點之間的流形距離，通過隨機映射算子Φ:RN→RM，將流形距離高概率地投影到M維的隨機子空間中，這樣就使得高維觀測空間中流形數據的局部結構在低維空間得到保持.

從定理1可以得到:

即隨機投影后高概率保持近鄰點之間的流形距離.

(5)

(6)

隨機投影的思想來源于Johnson-Lindenstrauss (JL)[19—21]引理,假如一個向量空間中的點被映射到一個適當高維的隨機子空間中，那么這種映射會近似地維持映射點之間的距離.相關的證明參見文獻[20—21].隨機投影之所以精確重建原始數據的關鍵在于隨機投影矩陣H滿足一定階數的限制等距條件(RIP)：

隨機映射算子Φ:RN→RM要滿足K階的限制等距條件RIP，K

在光滑K維子流形μ?RN上，存在隨機映射算子Φ:RN→RM，(K

(7)

(8)

根據式(6)～(7)可以推導：

(9)

由此證明了隨機投影降維后在低維空間能保留高維觀測空間中的數據信息.即用隨機映射變換可以在低維空間維持高維數據近鄰之間的流形距離.

4正交判別

4.1引入監督

MMC是通過最大化類間平均邊緣求取最優線性子空間[22].MMC算法的目標函數可以表示為：

J(W)=tr{WT(Sb-Sw)W},

式中Sw和Sb分別表示樣本的類內散度矩陣和類間散度矩陣.

在MDLLE算法中引入MMC來構建最優平移縮放模型，使得算法在保持LLE局部幾何結構的同時，具有MMC判別能力.通過正交化低維特征向量可消除降維過程中的噪聲影響，進而提高算法的監督判別能力.故提出一種有監督的MDLLE算法.因此，上述目標函數(4)可描述成如下優化問題：

(10)

對式(10)進行線性變換：

min tr{AT(XMXT-(Sb-SW))A}s.t.ATXXTA=I.

運用Lagrangian算子求解上述優化問題，得：

上式的求解就轉化為如下廣義特征值的求解：

(XMXT-(Sb-Sw))a=λXXTa，

(11)

式中:λ是廣義特征方程(11)的特征值，a是其特征值對應的特征向量.由廣義特征方程(11)可知，當線性變換矩陣A是由廣義特征對{(XMXT-(Sb-Sw)),XXT}的前d個最小特征值對應的特征向量組成時，目標函數將取得最小值.

4.2特征向量正交化

由于所求解的特征向量是非正交的，因此需將特征向量正交化，以消除噪聲影響,最終將所要求解的低維度特征向量轉化為矩陣特征值的求解問題[23].這里采用一種新的正交化方法.令Q=XMXT-(Sb-Sw)，算法的目標是要尋找一組正交基向量a1,a2,…,ad.極小化如下目標函數，并獲取第k個正交基向量：

(12)

運用Lagrangian算子求解式(12)，得：

則有：

2Qak-2λXXTak-η1a1-…-ηk-1ak-1=0.

(13)

將式(13)左乘(XXT)-1，得：

2(XXT)-1Qak-2λXXTak-η1(XXT)-1a1-…-ηk-1(XXT)-1ak-1=0,

即所求的正交基向量{a1,a2,…,ad}就是最小特征值λ所對應的特征向量.所求的正交基向量可完全避免約簡后的低維局部子空間的結構失真，具有穩定的局部分類判別力，故引入正交后比LLE有更好的分類精度.

基于隨機投影的正交判別流形學習算法步驟.

步驟1生成隨機投影變換矩陣H：各行均是單位化的獨立同分布零均值正態變量的標準正交矩陣.

步驟2構建M個隨機映射算子Φ:RN→RM.

步驟4用隨機映射算子Φ:RN→RM，將權值矩陣高概率地投影到低維空間.

步驟5在低維空間中用正交化的低維特征向量進行優化判別：求解方程(XMXT-(Sb-Sw))a=λXXTa的特征值λ及其特征向量a1,a2,…,ad.

5實驗仿真

1) 為了驗證MDLLE算法的性能，本文采用經典實驗數據集Swiss roll和Swiss hold來說明本文提出的算法能夠有效地處理非線性流形數據集.數據集的采樣點數N=2 000，分別選取鄰域參數k=14、k=16、k=18.圖1所示為LLE算法對數據集Swiss roll的降維，從圖中可以看出當鄰域參數k不同時，LLE算法的降維效果表現出不穩定性，即LLE算法無法正確揭示原始數據的低維結構，降維后的低維結果發生嚴重變形.圖5所示為MDLLE算法對數據集Swiss roll和Swiss hold的降維，從圖中可以看出當鄰域參數k不同時，MDLLE算法所揭示的低維結構可以良好地展現原始數據集的本質低維結構，即在一定的范圍內，MDLLE算法對鄰域參數不敏感，改善了原始算法的降維效果.

2) 為了驗證監督性MDLLE算法的性能，實驗將監督MDLLE、MDLLE及LLE進行比較.隨機選擇YALE人臉圖庫中的圖像作為訓練樣本，3種算法在相同訓練樣本和測試樣本下運行20次，取其平均識別結果作為每種算法的識別結果.YALE圖庫中有15個人，每人在不同表情和不同光照下有11張圖像，圖6為YALE圖庫中1個人的樣本圖像.隨機選擇3、6、9張圖像作為訓練樣本集，其余為測試樣本集.實驗結果如表1所示，顯示了20次重復實驗的最大平均識別率.從表中可以看出有監督的算法MDLLE具有更好的識別精度.隨著訓練次數的增多，算法LLE、MDLLE、監督型MDLLE對人臉圖像的識別精度也提高了.由于監督型MDLLE算法引入MMC構建最優平移縮放模型，使得算法在保持局部幾何結構信息的同時具有監督判別能力，因此算法對人臉圖像的分類識別精度得到了很大的提高.

圖5　MDLLE算法的降維效果Fig.5　Reduction-dimensional effect of MDLLE

圖6　YALE 人臉庫圖像示例Fig.6　Sample face images from the YALE database

表1　YALE人臉圖庫上算法性能比較

6結論

本文針對局部線性嵌入算法中鄰域參數選擇問題，提出了一種基于流形距離的局部線性嵌入算法(MDLLE)，該算法用流形距離代替傳統的歐氏距離作為相似性度量，利用流形距離測度合理地選取各個樣本的近鄰點，實現了高維數據的降維.實驗結果表明，本文提出的基于流形距離的近鄰選擇算法可以有效避免局部降維算法對選取近鄰參數K的不確定性.在MDLLE算法中引入最大邊緣準則，通過正交化低維特征向量消除降維過程中的噪聲影響，提高算法的監督判別能力，有監督的MDLLE算法在實驗中具有較好的降維性和穩定性，提高了圖像識別精度.從理論上證明了隨機投影能夠很好地保持流形數據上的主要特征，隨機投影在流形學習算法的降維中還有很大的研究空間.在后續的研究中將通過仿真實驗證明隨機投影在其他流形學習算法降維中的優勢，并討論隨機投影與流形本征維數之間的關系.

參考文獻：

[1]ROWEIS S, SAUL L. Nonlinear dimensionality reduction by locally linear embedding [J]. Science, 2000, 290(5500): 2323—2326.

[2]TENENBAUM J B, SILA A V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science, 2000, 290(5500): 2319—2323.

[3]孟德宇, 徐宗本, 戴明偉. 一種新的有監督流形學習方法[J]. 計算機研究與發展, 2007, 44(12): 2072—2077.

[4]DONOHO D L, GRIMES C. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data [J]. Proc eedings of the national academy of sciences of USA, 2003, 100(10): 5591—5596.

[5]ZHANG Z Y, ZHA H Y. Principal manifolds and nonlinear dimension reduction via local tangent space alignment [J]. SIAM journal： scientific computing, 2005, 26(1): 313—338.

[6]李峰, 田大慶, 王家序. 基于有監督增量式局部線性嵌入的故障辨識[J]. 振動與沖擊，2013, 32(23): 82—88.

[7]LAW M H C, JAIN A K. Incremental nonlinear dimensionality reduction by manifold learning [J]. IEEE transaction on pattern analysis and machine intelligence, 2006, 28(3): 377—391.

[8]ZHANG Z Y, WANG J, ZHA H Y. Adaptive manifold learning[J]. IEEE transaction on pattern analysis and machine intelligence, 2012, 34(2): 253—265.

[9]侯越先, 吳靜怡. 基于局域主方向重構的適應性非線性維數約簡[J]. 計算機應用，2006, 26(4): 895—897.

[10] 蒲玲. 自適應局部線性降維方法[J]. 計算機應用與軟件, 2013, 30(4): 255—257.

[11] 蒲玲. 自適應鄰域圖的流形學習方法[J]. 計算機應用與軟件, 2014, 31(2): 191—194.

[12] 惠康華, 肖柏華, 王春恒. 基于自適應近鄰參數的局部線性嵌入[J].模式識別與人工智能, 2010, 23(6): 842—846.

[13] 文貴華, 江麗君, 文軍. 鄰域參數動態變化的局部線性嵌入[J]. 軟件學報, 2008, 19(7): 1666—1673.

[14]MA J J, GONG M G, JIAO L C. Evolutionary clustering algorithm based on mixed measures [J]. International journal of intelligent computing and cybernetics, 2011, 4(4): 511—526.

[15]SOOMIN LEE, ANGELIA N. Distributed random projection algorithm for convex optimization [J]. IEEE J Sel Topics Signal Processing, 2013, 7(2): 221—229.

[16]SANJOY D, ANUPAM G. An elementary proof of the JL lemma: technical report TR-99-006 [R]. University of California, Berkeley, 1990.

[17]HEGDE C, WAKIN M B, TENENBAUM J. Random projection for manifold learning proofs and analysis: technical report TREE 0710 [R]. Rice University,Houston,2007.

[18]魏萊, 王守覺. 基于流形距離的半監督判別分析[J]. 軟件學報, 2010, 21(10): 2445—2453.

[19]RICHARD G, BARANIUK, MICHAEL B W. Random projections of smooth manifold[J]. Foundations of computational mathematics, 2009, 9(1): 51—77.

[20]DASGUPTA S, GUPTA A. An elementary proof of the Johnson-Lindentrauss lemma: technical report TR-99-006 [R]. International Computer Science Institute, Berkeley, California, 1999.

[21]FRANKL P, MAEHARA H. The Johnoson-Lindenstrauss lemma and the sphericity of some graphs[J]. Journal of combinatorial theory: Ser. B, 1988, 44: 355—362.

[22]袁暋, 程雷, 朱然剛. 一種新的基于MMC和LSE的監督流形學習算法[J]. 自動化學報, 2013, 39(12): 2077—2089.

[23]張光耀，李鎮.一個n*n矩陣特征值問題的跡公式及其應用[J]. 鄭州大學學報(理學版)，2010，,4(4)：18—23.

(責任編輯：王浩毅)

Manifold Learning Algorithms of Orthogonal Discriminant Based on Random Projection

MA Li,DONG Weiguang, LIANG Jinping, ZHANG Xiaodong

(DepartmentofAutomationandElectricalEngineering,LanzhouJiaotongUniversity,Lanzhou730070,China)

Abstract:A kind of locally linear embedding algorithms based on manifold distance, MDLLE was proposed. The similarity between data can be could measured based on the manifold distance and the neighbor domain of the sample points can be selected. This could solve the neighborhood parameter sensitivity of the Euclidean distance in similarity measure. The maximum margin criterion(MMC) is introduced in the MDLLE algorithm for constructing the optimal translation and scaling model. Thus, the algorithm both can both maintain local geometric structure of LLE and have discriminant ability of Maximum margin criterion. The low-dimensional feature vector of orthogonalization can eliminate noise effects in the process of dimension reduction, and improve the supervision and discriminant ability of the algorithm. The experimental result showed that this method had good dimension reduction effect and can effectively avoid sensitivity. Random projection is independent of the original high-dimensional data, which mapped the high-dimensional data to a low-dimensional space of the random transformation matrix of line normalized. The theoretical analysis proved that the manifold learning algorithm of taking random projection could maintain high-dimensional data in low-dimensional space in high probability.

Key words:manifold learning； neighborhood selection； manifold distance； similarity measure； locally linear embedding； random projection

收稿日期:2015-08-21

基金項目:甘肅省科技支撐基金資助項目(1204GKCA038)；甘肅省財政廳基本科研業務費資助項目(213063).

作者簡介:馬麗(1990—)，女，甘肅蘭州人，碩士研究生，主要從事非線性數據降維研究,E-mail:mary15117221064@163.com.

中圖分類號：TP181

文獻標志碼：A

文章編號：1671-6841(2016)01-0102-08

DOI:10.3969/j.issn.1671-6841.201508008

引用本文：馬麗，董唯光，梁金平，等.基于隨機投影的正交判別流形學習算法[J].鄭州大學學報(理學版)，2016,48(1)：102—109