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

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

?

基于隨機(jī)投影的正交判別流形學(xué)習(xí)算法

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

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

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

關(guān)鍵詞：流形學(xué)習(xí)算法； 鄰域選擇； 流形距離； 正交判別； 局部線性嵌入； 隨機(jī)投影

0引言

在當(dāng)今的信息社會(huì)中，人們獲得數(shù)據(jù)和信息的能力越來越強(qiáng).而這些數(shù)據(jù)信息呈現(xiàn)出的特性是高維數(shù)、大規(guī)模和結(jié)構(gòu)復(fù)雜等.那么如何從這些繁雜的數(shù)據(jù)中迅速提取有價(jià)值的信息，引起了人們的關(guān)注和研究.因此，數(shù)據(jù)的維數(shù)約簡(jiǎn)就顯得尤為重要了.數(shù)據(jù)降維，一方面可以解決“維數(shù)災(zāi)難”，緩解“數(shù)據(jù)爆炸但知識(shí)貧乏”的現(xiàn)狀[1]，降低復(fù)雜度；另一方面可以更好地認(rèn)識(shí)和利用數(shù)據(jù).

流形學(xué)習(xí)用于數(shù)據(jù)維數(shù)約簡(jiǎn)，已成為數(shù)據(jù)挖掘的研究熱點(diǎn).假設(shè)數(shù)據(jù)是均勻采樣于一個(gè)高維觀測(cè)空間中的低維流形，流形學(xué)習(xí)就是從高維采樣數(shù)據(jù)中恢復(fù)這個(gè)低維流形結(jié)構(gòu)[2]，并求出相應(yīng)的低維嵌入映射，以實(shí)現(xiàn)數(shù)據(jù)降維或數(shù)據(jù)可視化.它是從觀測(cè)到的現(xiàn)象中去尋找事物的本質(zhì)，找到復(fù)雜數(shù)據(jù)的內(nèi)在規(guī)律.近年來，流形學(xué)習(xí)鄰域已取得了大量的研究成果.經(jīng)典的非線性流形學(xué)習(xí)算法有等距特征映射算法(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]和黎曼流形學(xué)習(xí)算法(Riemannian manifold learning)等.現(xiàn)有的流形學(xué)習(xí)算法根據(jù)所保持幾何特性的不同，可分為局部特性保持算法和全局特性保持算法.局部特性保持算法主要是保持流形的局部幾何結(jié)構(gòu)特性，通過映射建立高維觀測(cè)空間與低維流形之間的聯(lián)系，在低維流形空間中保持近鄰域所具有的局部結(jié)構(gòu).全局特性保持算法主要是保持低維流形的全局幾何結(jié)構(gòu)，構(gòu)造所有數(shù)據(jù)點(diǎn)對(duì)之間的全局度量矩陣，再將度量矩陣轉(zhuǎn)化為內(nèi)積矩陣并求解其特征向量，即可獲得數(shù)據(jù)集的內(nèi)在低維結(jié)構(gòu).目前，很多研究者對(duì)上述經(jīng)典算法進(jìn)行改進(jìn)，如有監(jiān)督的流形學(xué)習(xí)算法[3]、增量式流形學(xué)習(xí)算法等[6—7]，顯著提高了原始算法的性能.

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

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

1局部線性嵌入算法

局部線性嵌入算法[2]是一種局部特性保持方法，核心是保持降維前后近鄰之間的線性結(jié)構(gòu)不變.其前提假設(shè)是高維數(shù)據(jù)所在的低維流形是局部線性的，即每個(gè)樣本點(diǎn)可以用其近鄰點(diǎn)線性表示.算法的主要思想是通過在低維嵌入空間中保持每個(gè)數(shù)據(jù)點(diǎn)的近鄰重構(gòu)系數(shù)來保持整個(gè)數(shù)據(jù)的流形結(jié)構(gòu)，即以重構(gòu)權(quán)值矩陣作為高維觀測(cè)空間與低維嵌入空間的聯(lián)系橋梁：高維觀測(cè)空間的每個(gè)數(shù)據(jù)點(diǎn)用其近鄰點(diǎn)線性表示的權(quán)重與它們?cè)诘途S嵌入空間中線性表示的權(quán)重保持一致.由于流形上的局部可以認(rèn)為是一個(gè)局部歐式空間，因此每個(gè)樣本點(diǎn)與其近鄰樣本之間是線性關(guān)系，從而一個(gè)樣本可以用其近鄰樣本的線性組合來重構(gòu).

LLE算法包含以下3個(gè)基本步驟：

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

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

其中:權(quán)值wij反映了樣本點(diǎn)xj對(duì)xi重構(gòu)的貢獻(xiàn).

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

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

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

2.1流形距離

由于數(shù)據(jù)集的低維流形分布，用歐氏距離來選擇最近鄰域時(shí)，這些選擇的近鄰點(diǎn)不能準(zhǔn)確地表征流形上的真正鄰域結(jié)構(gòu).為了解決流形上數(shù)據(jù)的最近鄰點(diǎn)的選擇，提出一種新的相似度度量來計(jì)算數(shù)據(jù)點(diǎn)間的最短距離.

定義1流形上兩點(diǎn)xi,xj的線段長(zhǎng)度定義為：

(1)

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

(2)

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

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

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

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

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

兩個(gè)數(shù)據(jù)點(diǎn)間的距離越小，它們的相似度越高.因此，定義xi,xj間的相似度為：

(3)

需說明的是，本文定義樣本自身的相似度為0，即當(dāng)i=j時(shí)，σij=0.

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

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

圖2　以歐氏距離所選的近鄰點(diǎn)Fig.2　Neighbors selected by Euclidean

圖3　以流形距離所選的近鄰點(diǎn)Fig.3　Neighbors selected by manifold

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

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

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

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

步驟3根據(jù)步驟2 計(jì)算出的點(diǎn)對(duì)間的相似度選擇樣本點(diǎn)xi的最近鄰點(diǎn)得到近鄰點(diǎn)數(shù).

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

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

用流形距離表示權(quán)值矩陣W：

根據(jù)歐氏距離下定義的權(quán)值系數(shù)，可得：

故可將流形距離下的權(quán)值矩陣表示為：

在低維空間中用流形距離表示的權(quán)值矩陣計(jì)算低維嵌入Y，使其重構(gòu)誤差最小，則重構(gòu)誤差函數(shù)為：

構(gòu)造目標(biāo)函數(shù)，如下：

(4)

約束條件：ATXMXTA=I.

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

3隨機(jī)映射定理

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

從定理1可以得到:

即隨機(jī)投影后高概率保持近鄰點(diǎn)之間的流形距離.

(5)

(6)

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

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

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

(7)

(8)

根據(jù)式(6)～(7)可以推導(dǎo)：

(9)

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

4正交判別

4.1引入監(jiān)督

MMC是通過最大化類間平均邊緣求取最優(yōu)線性子空間[22].MMC算法的目標(biāo)函數(shù)可以表示為：

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

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

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

(10)

對(duì)式(10)進(jìn)行線性變換：

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

運(yùn)用Lagrangian算子求解上述優(yōu)化問題，得：

上式的求解就轉(zhuǎn)化為如下廣義特征值的求解：

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

(11)

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

4.2特征向量正交化

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

(12)

運(yùn)用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}就是最小特征值λ所對(duì)應(yīng)的特征向量.所求的正交基向量可完全避免約簡(jiǎn)后的低維局部子空間的結(jié)構(gòu)失真，具有穩(wěn)定的局部分類判別力，故引入正交后比LLE有更好的分類精度.

基于隨機(jī)投影的正交判別流形學(xué)習(xí)算法步驟.

步驟1生成隨機(jī)投影變換矩陣H：各行均是單位化的獨(dú)立同分布零均值正態(tài)變量的標(biāo)準(zhǔn)正交矩陣.

步驟2構(gòu)建M個(gè)隨機(jī)映射算子Φ:RN→RM.

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

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

5實(shí)驗(yàn)仿真

1) 為了驗(yàn)證MDLLE算法的性能，本文采用經(jīng)典實(shí)驗(yàn)數(shù)據(jù)集Swiss roll和Swiss hold來說明本文提出的算法能夠有效地處理非線性流形數(shù)據(jù)集.數(shù)據(jù)集的采樣點(diǎn)數(shù)N=2 000，分別選取鄰域參數(shù)k=14、k=16、k=18.圖1所示為L(zhǎng)LE算法對(duì)數(shù)據(jù)集Swiss roll的降維，從圖中可以看出當(dāng)鄰域參數(shù)k不同時(shí)，LLE算法的降維效果表現(xiàn)出不穩(wěn)定性，即LLE算法無法正確揭示原始數(shù)據(jù)的低維結(jié)構(gòu)，降維后的低維結(jié)果發(fā)生嚴(yán)重變形.圖5所示為MDLLE算法對(duì)數(shù)據(jù)集Swiss roll和Swiss hold的降維，從圖中可以看出當(dāng)鄰域參數(shù)k不同時(shí)，MDLLE算法所揭示的低維結(jié)構(gòu)可以良好地展現(xiàn)原始數(shù)據(jù)集的本質(zhì)低維結(jié)構(gòu)，即在一定的范圍內(nèi)，MDLLE算法對(duì)鄰域參數(shù)不敏感，改善了原始算法的降維效果.

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

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

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

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

6結(jié)論

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

參考文獻(xiàn)：

[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]孟德宇, 徐宗本, 戴明偉. 一種新的有監(jiān)督流形學(xué)習(xí)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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]李峰, 田大慶, 王家序. 基于有監(jiān)督增量式局部線性嵌入的故障辨識(shí)[J]. 振動(dòng)與沖擊，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]侯越先, 吳靜怡. 基于局域主方向重構(gòu)的適應(yīng)性非線性維數(shù)約簡(jiǎn)[J]. 計(jì)算機(jī)應(yīng)用，2006, 26(4): 895—897.

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

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

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

[13] 文貴華, 江麗君, 文軍. 鄰域參數(shù)動(dòng)態(tài)變化的局部線性嵌入[J]. 軟件學(xué)報(bào), 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]魏萊, 王守覺. 基于流形距離的半監(jiān)督判別分析[J]. 軟件學(xué)報(bào), 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的監(jiān)督流形學(xué)習(xí)算法[J]. 自動(dòng)化學(xué)報(bào), 2013, 39(12): 2077—2089.

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

(責(zé)任編輯：王浩毅)

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

基金項(xiàng)目:甘肅省科技支撐基金資助項(xiàng)目(1204GKCA038)；甘肅省財(cái)政廳基本科研業(yè)務(wù)費(fèi)資助項(xiàng)目(213063).

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

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

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

DOI:10.3969/j.issn.1671-6841.201508008

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