楊國亮，羅 璐，豐義琴，梁禮明

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000）

基于低秩稀疏圖的結(jié)構(gòu)保持投影算法*

楊國亮，羅 璐，豐義琴，梁禮明

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000）

在圖嵌入理論框架下，能夠較好地揭示數(shù)據(jù)本質(zhì)特性的圖在一些維數(shù)約簡方法中起到關(guān)鍵性的作用。基于稀疏表示和低秩表示方法，構(gòu)建了一種低秩稀疏圖，能夠同時(shí)揭示數(shù)據(jù)的局部結(jié)構(gòu)信息和全局結(jié)構(gòu)信息。然后，利用圖嵌入理論方法使這些特性在線性投影的過程中得以保持不變，從而學(xué)習(xí)出高維數(shù)據(jù)有效的低維嵌入。在標(biāo)準(zhǔn)的人臉和手寫數(shù)字?jǐn)?shù)據(jù)集（ORL，Yale，PIE，MNIST）上進(jìn)行實(shí)驗(yàn)，同傳統(tǒng)的圖嵌入方法比較，結(jié)果表明了算法的有效性。

圖嵌入；稀疏表示；低秩表示；低秩稀疏圖；線性投影

1 引言

現(xiàn)今，學(xué)習(xí)高維空間的低維投影這一維數(shù)約簡技術(shù)被廣泛地應(yīng)用在計(jì)算機(jī)視覺和模式識別領(lǐng)域中。投影技術(shù)的主要步驟是采用某種學(xué)習(xí)算法學(xué)習(xí)出數(shù)據(jù)的轉(zhuǎn)換矩陣A，然后通過yi=ATxi將高維空間中的數(shù)據(jù)xi投影到低維子空間中。

圖嵌入理論［1］為高維空間的低維投影技術(shù)提供了一個(gè)統(tǒng)一的學(xué)習(xí)框架。在這個(gè)框架中，不同的投影算法可以用同一個(gè)數(shù)學(xué)表達(dá)式來表示，式中具有圖結(jié)構(gòu)屬性的相似度矩陣是區(qū)別各種算法的關(guān)鍵所在，不同的學(xué)習(xí)算法構(gòu)建反映不同結(jié)構(gòu)特性的圖。圖嵌入理論就是通過在學(xué)習(xí)低維投影的過程中保持這些圖特性不變，從而達(dá)到數(shù)據(jù)降維的目的。典型的局部保持投影LPP（Locality Preserving Projections）［2］和鄰域保持嵌入NPE（Neighborhood Preserving Embedding）［3］算法在圖嵌入理論框架下的形式是通過構(gòu)建反映數(shù)據(jù)局部鄰域結(jié)構(gòu)信息的k鄰域圖或ε鄰域圖來學(xué)習(xí)高維空間的低維投影。但是，k鄰域圖和ε鄰域圖存在如下兩個(gè)缺點(diǎn)：（1）算法效果受鄰域參數(shù)k和ε的影響很大，目前又沒有一種很好的方法用于對鄰域參數(shù)k和ε的選擇進(jìn)行指導(dǎo)，往往是人們通過經(jīng)驗(yàn)設(shè)定，所以算法在數(shù)據(jù)類型上的可移植性不強(qiáng)。（2）k鄰域圖和ε鄰域圖反映的是數(shù)據(jù)局部結(jié)構(gòu)信息，這種結(jié)構(gòu)極易受到噪聲數(shù)據(jù)的干擾。

為了克服鄰域圖存在的缺點(diǎn)，文獻(xiàn)［4］提出了用稀疏表示［5］構(gòu)建稀疏圖反映數(shù)據(jù)的局部結(jié)構(gòu)信息。基于稀疏表示的稀疏圖利用除本身數(shù)據(jù)外的所有樣本進(jìn)行編碼，可以自動(dòng)地為每一個(gè)數(shù)據(jù)選擇最優(yōu)的鄰域，通過求解l1優(yōu)化問題獲得鄰域關(guān)系和相應(yīng)的連接權(quán)值。與傳統(tǒng)的基于k近鄰或ε近鄰數(shù)據(jù)編碼的近鄰圖不同，稀疏圖把這種近鄰關(guān)系從局部結(jié)構(gòu)拓展到半局部結(jié)構(gòu)，在整個(gè)建圖過程中不需要人為選擇參數(shù)，能夠很好地描述數(shù)據(jù)集的局部結(jié)構(gòu)關(guān)系。可是稀疏表示是獨(dú)立地對每個(gè)樣本點(diǎn)進(jìn)行稀疏編碼，在稀疏圖的構(gòu)建中缺少全局約束，不能反映數(shù)據(jù)的全局結(jié)構(gòu)特性，當(dāng)數(shù)據(jù)點(diǎn)存在較大噪聲干擾時(shí)，將稀疏圖用于圖嵌入理論框架中學(xué)習(xí)的投影表現(xiàn)性能不佳。數(shù)據(jù)的全局信息不僅對揭示數(shù)據(jù)屬性具有一定的魯棒性，而且在分類任務(wù)中有一定的積極作用。為了學(xué)習(xí)數(shù)據(jù)的全局結(jié)構(gòu)信息，文獻(xiàn)［6］采用低秩表示［7］構(gòu)建了一種能夠反映數(shù)據(jù)結(jié)構(gòu)特性的低秩圖用于圖像的半監(jiān)督學(xué)習(xí)任務(wù)中。低秩圖是在全局低秩約束下對數(shù)據(jù)進(jìn)行聯(lián)合線性表示獲得的，可以很好地揭示數(shù)據(jù)的全局結(jié)構(gòu)，還能夠反映出相同類別數(shù)據(jù)之間的近似關(guān)系，具有一定的鑒別能力。

基于上述描述，我們提出利用權(quán)值融合方法將數(shù)據(jù)的稀疏圖和低秩圖進(jìn)行加權(quán)線性組合，構(gòu)建一種能夠同時(shí)揭示數(shù)據(jù)局部結(jié)構(gòu)信息和全局結(jié)構(gòu)信息、且具有一定鑒別能力的低秩稀疏圖，代替原始LPP算法和NPE算法中的鄰域圖，完成高維數(shù)據(jù)的低維子空間學(xué)習(xí)任務(wù)。由于低秩稀疏圖中既利用稀疏圖描述數(shù)據(jù)集局部結(jié)構(gòu)也利用了低秩圖描述數(shù)據(jù)集的全局結(jié)構(gòu)關(guān)系，因此在投影過程中將這些數(shù)據(jù)特性進(jìn)行保持，學(xué)習(xí)出的子空間將更加準(zhǔn)確地表示高維數(shù)據(jù)。

2 低秩稀疏圖

假設(shè)有高維圖像數(shù)據(jù)集X=［x1，x2，…，xn］，其中xi表示一張被排成列向量的圖像數(shù)據(jù)點(diǎn)。先利用數(shù)據(jù)集X構(gòu)建一個(gè)無向圖G=（V，E）和對應(yīng)的權(quán)值矩陣W=｛wij｝，這里V=｛vi｝是節(jié)點(diǎn)集，每一個(gè)vi對應(yīng)于數(shù)據(jù)集中的一個(gè)xi，E=｛eij｝是一個(gè)連接邊界集，每一條邊界eij對應(yīng)于數(shù)據(jù)點(diǎn)xi與xj之間的權(quán)值wij。由于節(jié)點(diǎn)集V是給定的，所以構(gòu)建數(shù)據(jù)圖結(jié)構(gòu)就只需要學(xué)習(xí)數(shù)據(jù)間的連接權(quán)值矩陣W。鄰域圖通過利用數(shù)據(jù)與k鄰域中的數(shù)據(jù)點(diǎn)間的歐氏距離來決定數(shù)據(jù)之間的連接權(quán)值。在壓縮感知領(lǐng)域中，認(rèn)為數(shù)據(jù)點(diǎn)可以由其他相應(yīng)的 數(shù) 據(jù) 對其進(jìn) 行 線 性 重 構(gòu) 表示，即 xi=。由 于 這 樣的 線 性 組合 有 多 種可 能性，因此需要引入一定的條件進(jìn)行約束，得到最優(yōu)的線性組合系數(shù)，這些系數(shù)也能夠反映數(shù)據(jù)點(diǎn)間的連接權(quán)值關(guān)系。本節(jié)將分別介紹在稀疏和低秩條件約束下，求解數(shù)據(jù)的連接權(quán)值 wij，構(gòu)建數(shù)據(jù)的稀疏圖和低秩圖。然后介紹如何通過這兩種組合系數(shù)構(gòu)建反映數(shù)據(jù)全局結(jié)構(gòu)信息和局部信息的低秩稀疏圖。

2.1 稀疏圖

數(shù)據(jù)集X=［x1，x2，…，xn］∈Rm×n來自k個(gè)獨(dú)立的子空間，且k?n，基于來自同一子空間的樣本點(diǎn)具有相同屬性這一假設(shè)可知，來自同一子空間的數(shù)據(jù)間具有較高的相似性；來自不同子空間數(shù)據(jù)之間的相似性較弱，在重構(gòu)表示過程中發(fā)揮的作用不大。為此，樣本點(diǎn)的線性重構(gòu)表示系數(shù)具有稀疏特性，所以在線性重構(gòu)表示的基礎(chǔ)上對表示系數(shù)引入稀疏性約束，通過求解如下的優(yōu)化問題構(gòu)建數(shù)據(jù)的連接權(quán)值：

其中，αi是稀疏權(quán)值向量，αij表示 樣本點(diǎn)xj對樣本點(diǎn)xi的稀疏表示權(quán)值。式（1）是一個(gè)非凸優(yōu)化問題，在壓縮感知中往往用l1范數(shù)代替l0將其轉(zhuǎn)化為一個(gè)存在最優(yōu)解的凸優(yōu)化問題?？紤]到實(shí)際運(yùn)用中數(shù)據(jù)往往存在一定的噪聲干擾，為此將式（1）中的等式約束松弛為如下的形式：

其中，ε是一個(gè)給定的正數(shù)公差。利用式（2）對數(shù)據(jù)集中的每一個(gè)樣本點(diǎn)進(jìn)行線性重構(gòu)，得到n個(gè)稀疏權(quán)值向量，組成稀疏表示系數(shù)矩陣α。稀疏表示的詳細(xì)介紹和求解可以參考文獻(xiàn)［8］。由于數(shù)據(jù)圖結(jié)構(gòu)中的連接權(quán)值矩陣滿足對稱性，因此在得到數(shù)據(jù)的稀疏表示系數(shù)之后通過式（3）使稀疏圖連接權(quán)矩陣WSR滿足對稱性。

2.2 低秩圖

低秩表示的目的是尋求數(shù)據(jù)集中每一個(gè)獨(dú)立的數(shù)據(jù)向量作為數(shù)據(jù)集中所有數(shù)據(jù)向量的線性組合表示，同時(shí)這種線性組合系數(shù)滿足低秩性特性。通過求解如下的優(yōu)化問題得到數(shù)據(jù)的低秩表示系數(shù)，用來組成低秩圖中的連接權(quán)值矩陣W：

其中，X同稀疏表示中定義的X一樣，Z=［z1，z2，…，zn］是線性組合表示系數(shù)矩陣，zi代表xi在所有數(shù)據(jù)集下的線性表示系數(shù)。上式中最優(yōu)解Z*稱之為數(shù)據(jù)X的低秩表示系數(shù)。式（4）同樣是一個(gè)非凸優(yōu)化問題，很難得到最優(yōu)解，在凸優(yōu)化理論中可以用矩陣的核范數(shù)*代替矩陣的秩，使得優(yōu)化問題存在最優(yōu)解。因此，問題（4）可以變成如下的凸優(yōu)化問題：

構(gòu)造上述優(yōu)化問題的增廣拉格朗日函數(shù)：

采用交替迭代更新策略對上式中的每一個(gè)參數(shù)進(jìn)行更新，更新其中的一個(gè)參數(shù)時(shí)，保持其他所有參數(shù)不變，直到滿足停止迭代的條件時(shí)停止更新。

對參數(shù)J進(jìn)行更新：

對參數(shù)Z進(jìn)行更新：

對參數(shù)E進(jìn)行更新：E*=arg min

Eλ

對拉格朗日乘子Y1、Y2進(jìn)行更新：

對參數(shù)u進(jìn)行更新：u*=max（ηu），η、為設(shè)定數(shù)值。

更新步驟中的設(shè)定參數(shù)值參照文獻(xiàn)［7］，在對參數(shù)J和E更新步驟中的［M］算子和［M］可參考文獻(xiàn)［9］中的定義求解。得到數(shù)據(jù)的低秩表示系數(shù)后按低秩圖構(gòu)建的方法構(gòu)建低秩圖。

由于低秩表示得到的低秩表示系數(shù)中存在一些非常接近零的數(shù)值，這些數(shù)值會(huì)給圖連接帶來不必要的錯(cuò)誤連接關(guān)系，所以通過下式對低秩表示系數(shù)進(jìn)行預(yù)處理：

同時(shí)，利用式（14）使得連接權(quán)值矩陣WLR滿足對稱性：

2.3 構(gòu)建低秩稀疏圖

基于稀疏表示構(gòu)建的稀疏圖利用較少的連接權(quán)值表示數(shù)據(jù)間的相似度關(guān)系，能夠揭示數(shù)據(jù)的局部結(jié)構(gòu)信息，同時(shí)還體現(xiàn)出數(shù)據(jù)在高維空間中重構(gòu)系數(shù)的稀疏特性。基于低秩表示構(gòu)建的低秩圖反映了數(shù)據(jù)聯(lián)合線性表示的組合系數(shù)，利用這種系數(shù)代表低秩圖中的連接權(quán)值，具有揭示數(shù)據(jù)全局結(jié)構(gòu)信息的能力和一定的數(shù)據(jù)鑒別能力。為了可以在數(shù)據(jù)的一個(gè)圖中同時(shí)揭示數(shù)據(jù)的局部結(jié)構(gòu)信息和全局結(jié)構(gòu)信息，同時(shí)圖結(jié)構(gòu)還具有一定的鑒別能力，我們對低秩圖和稀疏圖進(jìn)行權(quán)值組合構(gòu)建一個(gè)新的圖，稱之為低秩稀疏圖。在對稀疏圖和低秩圖進(jìn)行組合前分別對其進(jìn)行歸一化處理，對權(quán)值矩陣W中的每一列進(jìn)行w'i=wi/max（wi）操作。低秩稀疏圖連接權(quán)矩陣WLRS的構(gòu)建表達(dá)式如下：

其中，β是平衡參數(shù)，取值范圍在0～1，權(quán)衡低秩稀疏圖中揭示數(shù)據(jù)局部結(jié)構(gòu)特性和全局結(jié)構(gòu)特性的比重。通過式（15）可以發(fā)現(xiàn)，當(dāng)β為0時(shí)WLRS圖只反映數(shù)據(jù)的全局結(jié)構(gòu)信息，等同于數(shù)據(jù)的低秩圖；當(dāng)β為1時(shí)WLRS圖只反映數(shù)據(jù)的局部結(jié)構(gòu)信息，等同于數(shù)據(jù)的稀疏圖。

求解低秩稀疏圖時(shí)，首先利用同倫方法［10］求解凸優(yōu)化函數(shù)（2）得到數(shù)據(jù)集中數(shù)據(jù)樣本xi（1≤i≤n）的稀疏表示系數(shù)αi，將n個(gè)數(shù)據(jù)的稀疏表示系數(shù)向量組成稀疏表示系數(shù)矩陣α=［α1，α2，…，αn］，然后通過式（3）求解數(shù)據(jù)的稀疏圖。對于低秩圖中的連接權(quán)值，我們采用非精確的增廣拉格朗日方法求解優(yōu)化問題（6）。最后，根據(jù)式（14）構(gòu)建低秩稀疏圖。低秩稀疏圖的求解步驟見算法1。

算法1 低秩稀疏圖的構(gòu)建

輸入：高維數(shù)據(jù)集X，參數(shù)β；

輸出：數(shù)據(jù)的低秩稀疏圖。

步驟1 歸一化數(shù)據(jù)集X；

步驟2 求解優(yōu)化問題（2），通過式（3）求解稀疏權(quán)值矩陣WSR；

步驟3 求解優(yōu)化問題（6），根據(jù)式（14）求解低秩權(quán)值矩陣WLR；

步驟4 對稀疏權(quán)值矩陣和低秩權(quán)值矩陣進(jìn)行歸一化處理；

步驟5 通過式（15）構(gòu)建低秩稀疏權(quán)值矩陣WLRS，得到數(shù)據(jù)的低秩稀疏圖。

3 基于低秩稀疏圖的結(jié)構(gòu)保持投影

在高維圖像識別任務(wù)中，假設(shè)存在一些來自C個(gè)類別、帶有類別標(biāo)簽信息的訓(xùn)練圖像 ｛xi，li｝，xi∈RM代表 一 張 被 表 示為列 向 量 的 二 維 圖像，li∈｛1，…，C｝ 表示圖像xi的類別信息。稀疏低秩特性保持的目標(biāo)是尋求一映射矩陣A，通過線性投影yi=ATxi將高維空間M中的數(shù)據(jù)用低維空間D（D?M）表示，同時(shí)在低維空間D中保持?jǐn)?shù)據(jù)在高維空間中所具有的稀疏低秩特性。LPP算法和NPE算法都是基于數(shù)據(jù)鄰域圖的投影算法，目的是在數(shù)據(jù)投影的過程中保持空間鄰域中數(shù)據(jù)點(diǎn)間結(jié)構(gòu)關(guān)系不變。算法有三個(gè)步驟：（1）構(gòu)建k鄰域或ε鄰域；（2）計(jì)算鄰域數(shù)據(jù)間的距離度量；（3）計(jì)算特征映射。在圖嵌入理論框架下，算法的前兩步被視為揭示數(shù)據(jù)結(jié)構(gòu)特性的求解過程，目的是得到反映數(shù)據(jù)某種特性的圖。第（3）步是通過在投影的過程中保持圖所揭示的數(shù)據(jù)特性不變，完成數(shù)據(jù)降維的目的。

本節(jié)將介紹同時(shí)保持?jǐn)?shù)據(jù)局部和全局特性的兩種方法，利用上節(jié)的數(shù)據(jù)低秩稀疏圖代替算法LPP和NPE中的鄰域圖，分別構(gòu)建低秩稀疏保持投影LRSPP（Low Rank Sparse Preserving Projections）和低秩稀疏保持嵌入LRSPE（Low Rank Sparse Preserving Embedding）。算法的主要步驟流程如圖1所示。

低秩稀疏保持投影LRSPP算法通過利用上一節(jié)中介紹的低秩稀疏圖代替LPP算法中的鄰域圖，使得數(shù)據(jù)的全局和局部特性在進(jìn)行特征提取的過程中得到保持。LRSPP中特征投影的步驟類似于LPP的方法，都是求解如下廣義特征向量問題的特征向量和特征值：

其中，D是一個(gè)對角矩陣，每一個(gè)對角項(xiàng)是低秩稀疏圖的連接權(quán)值矩陣WLRS中對應(yīng)列所有項(xiàng)的總和，Dii=∑jWji。L=D—W是拉普拉斯矩陣，X為圖像訓(xùn)練集，X矩陣的第i列是一張圖像xi。求解式（16）得到P個(gè)特征值λi，i∈｛1，…，P｝，和相應(yīng)的特征列向量ai，i∈｛1，…，P｝，根據(jù)特征值大小升序排列，選擇前d個(gè)特征值對應(yīng)的特征向量組成映射矩陣A=［a1，a2，…，ad］，線性投影如下，式中yi表示數(shù)據(jù)點(diǎn)xi在d維空間中的表示。

Figure 1 Framework of the proposed algorithm圖1 基于低秩稀疏圖投影算法步驟

低秩稀疏保持嵌入（LRSPE）改進(jìn)思路類似于LRSPP算法，通過利用上一節(jié)中介紹的低秩稀疏圖代替NPE算法中的鄰域圖，使得數(shù)據(jù)低秩稀疏特性在進(jìn)行圖嵌入的過程中得到保持。通過求解下面廣義特征向量問題完成圖嵌入的過程：

其中，M=（I—W）T（I—W），I=diag（1，…，1），M是對稱的半正定矩陣，W為低秩稀疏圖中的連接權(quán)值矩陣WLRS。X為圖像訓(xùn)練集，X矩陣的第i列是一張圖像xi。特征列向量ai，i∈｛1，…，P｝，是式（18）的特征值λi，i∈｛1，…，P｝，對應(yīng)的特征向量，將特征值按升序排列，選擇前d個(gè)特征值對應(yīng)的特征向量組成嵌入轉(zhuǎn)換矩陣A=［a1，a2，…，ad］，低秩稀疏特性嵌入如式（17）所示，式中yi表示數(shù)據(jù)點(diǎn)xi在d維空間中的表示。

4 實(shí)驗(yàn)與結(jié)果分析

在數(shù)字圖像識別任務(wù)中，學(xué)習(xí)高維數(shù)據(jù)的低維子空間是一個(gè)重要的步驟，該步驟可以極大地降低圖像的數(shù)據(jù)維數(shù)，增強(qiáng)后續(xù)分類器識別的能力和速度。本文將基于低秩稀疏圖提出的LRSPP算法和LRSPE算法用于數(shù)字圖像識別任務(wù)中的降維步驟，同基于鄰域圖的OLPP算法、NPE算法和基于稀疏圖的SPE算法、OSPP算法進(jìn)行比較，分析圖在數(shù)字圖像分類中的有效性。實(shí)驗(yàn)中圖像的分類使用最近鄰分類器完成。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中，用了三個(gè)標(biāo)準(zhǔn)的人臉圖像數(shù)據(jù)集和一個(gè)手寫體圖像數(shù)據(jù)集進(jìn)行算法性能的比較。實(shí)驗(yàn)中用到的所有數(shù)字圖像尺寸都被調(diào)整為32×32像素大小，因此在圖像空間中，每一張圖像看成為1 024維的數(shù)據(jù)向量。

ORL人臉數(shù)據(jù)庫包含了40個(gè)類別的人臉數(shù)據(jù)，每個(gè)類別含有10幅在不同條件下獲取的人臉圖像。每幅圖像的臉部表情和外部特征都各不相同，這些圖像之間存在不同程度的傾斜，角度偏移量在20°以內(nèi)。在每個(gè)類別中隨機(jī)選取5幅圖像共200幅圖像作為實(shí)驗(yàn)訓(xùn)練集，剩下的為測試集。

Yale人臉庫包含15個(gè)類別共165幅人臉圖像，每個(gè)類別有11幅圖片，主要在臉部表情上存在較大的變化，另外采集圖像的光照條件也存在微小的差異。實(shí)驗(yàn)中，在每類中隨機(jī)選取6幅圖像共90幅圖像作為訓(xùn)練集，其余則為實(shí)驗(yàn)中的測試集。

PIE人臉數(shù)據(jù)集中收集了68個(gè)人的41 368幅人臉數(shù)據(jù)，包含每個(gè)人在不同光照、表情和姿態(tài)條件下的數(shù)據(jù)，來自卡內(nèi)基梅隆人臉表情數(shù)據(jù)庫。在本文的實(shí)驗(yàn)中，保持人臉的表情和姿態(tài)條件不變，選取其中20個(gè)類別，每類別的21幅不同光照下的人臉數(shù)據(jù)組成實(shí)驗(yàn)數(shù)據(jù)集。實(shí)驗(yàn)中隨機(jī)選取每個(gè)類別的3幅圖像作為訓(xùn)練集，其余為測試集。

MNIST數(shù)據(jù)集包含0～9十個(gè)數(shù)字的手寫體圖像，其中在訓(xùn)練集中有6 000幅手寫體圖像，測試集中包含1 000幅手寫體圖像。在實(shí)驗(yàn)中我們在每個(gè)數(shù)字的手寫體圖像中選取10幅共100幅圖像作為訓(xùn)練集，用同樣方法尋求100幅作為測試集。

4.2 算法結(jié)果分析

由于LRSPP算法和LRSPE算法分別是在LPP和NPE算法上改進(jìn)提出的。因此，實(shí)驗(yàn)中，在不同圖像數(shù)據(jù)集上，分別將LRSPP算法與LPP算法、LRSPE算法與NPE算法進(jìn)行分類實(shí)驗(yàn)的比較，同時(shí)還引入了SPE算法和SPP算法進(jìn)行比較。NPE算法和LPP算法中的鄰域參數(shù)K設(shè)置為5，LRSPP算法和LRSPE算法中衡量低秩稀疏特性參數(shù)β設(shè)置為0.5。因?yàn)檎齽t化可以提高算法的表現(xiàn)，在LPP和SPP算法進(jìn)行實(shí)驗(yàn)時(shí)采用其正則化版本OLPP和OSPP算法。表1中顯示的是不同算法在幾個(gè)圖像數(shù)據(jù)集上取得的最佳識別率和相應(yīng)的子空間維數(shù)，括號中給出的是取得最佳識別效果的子空間維數(shù)。

從結(jié)果中可以看出：（1）在四個(gè)數(shù)據(jù)集上，相比于保持?jǐn)?shù)據(jù)局部鄰域距離結(jié)構(gòu)的OLPP、OSPP算法，利用投影技術(shù)保持?jǐn)?shù)據(jù)局部和全局結(jié)構(gòu)特性的LRSPP算法取得了更好的分類表現(xiàn)；同樣，相比于保持?jǐn)?shù)據(jù)局部鄰域結(jié)構(gòu)重構(gòu)關(guān)系的NPE、SPE算法，利用投影技術(shù)保持?jǐn)?shù)據(jù)局部和全局結(jié)構(gòu)特性的LRSPE算法也獲得了更優(yōu)的表現(xiàn)。這表明了所提算法的有效性。在LPP和NPE算法中，分類性能和鄰域參數(shù)K的正確選擇有關(guān)，目前還不存在較好的方法對鄰域參數(shù)進(jìn)行優(yōu)化選擇，往往是人為設(shè)定的，這使得算法的穩(wěn)定性不高。而在本文提出的LRSPP和LRSPE算法中，反映數(shù)據(jù)局部和全局結(jié)構(gòu)特性的連接權(quán)值矩陣WLRS不存在類似參數(shù)優(yōu)化選擇的問題。（2）同NPE、SPE算法和OLPP、OSPP算法比較，本文的LRSPP和LRSPE算法取得最佳識別效果所需的子空間維數(shù)更低。在PIE數(shù)據(jù)集上LRSPP算法僅僅只需要11維。在流形學(xué)習(xí)理論中，研究者發(fā)現(xiàn)人臉圖像分布在嵌入于高維空間中的低維流形上，本征維數(shù)只有9維。這表明本文學(xué)習(xí)得到的能夠同時(shí)揭示數(shù)據(jù)局部和全局結(jié)構(gòu)信息的低秩稀疏圖相比于僅僅揭示數(shù)據(jù)局部結(jié)構(gòu)信息的鄰域圖對圖像分類具有更好的幫助。（3）從實(shí)驗(yàn)結(jié)果中發(fā)現(xiàn)，在PIE數(shù)據(jù)集上取得的識別率較好，導(dǎo)致這一現(xiàn)象的原因是我們實(shí)驗(yàn)選擇的人臉數(shù)據(jù)主要在光照強(qiáng)弱上存在變化，數(shù)據(jù)集的低秩特性良好，且分布的流形結(jié)構(gòu)緊密，幾種算法能夠在降維的過程中很好地保持這些特性，使得分類效果較理想。

Table 1 The maximal recognition rates of NPE，SPE，LRSPE，OLPP，OSPP and LRSPP，and the corresponding dimensions表1 幾種算法的最大識別率和相應(yīng)的維數(shù) %

圖2顯示了幾種算法在 ORL人臉庫和MNIST手寫體數(shù)字庫上不同維數(shù)子空間下的分類結(jié)果。在ORL數(shù)據(jù)集上的實(shí)驗(yàn)表明，LRSPP算法在不同的維數(shù)子空間下都取得了較OLPP和OSPP算法更好的效果；LRSPE算法在不同的維數(shù)子空間下也同樣取得了較NPE和SPE算法更好的識別效果。但是，在MNIST數(shù)據(jù)集上的實(shí)驗(yàn)中，在某些維數(shù)子空間中，LRSPE算法稍稍低于NPE和SPE算法的分類效果。這是因?yàn)長RSPP 和LRSPE算法的思路是利用低秩性和稀疏性約束揭示數(shù)據(jù)的全局結(jié)構(gòu)信息和局部結(jié)構(gòu)信息在投影過程中保持不變，而MNIST數(shù)據(jù)集是手寫體數(shù)字?jǐn)?shù)據(jù)，由于不同的人具有不同的手寫風(fēng)格，使得手寫圖像的低秩性不是非常強(qiáng)，低秩模型揭示的全局結(jié)構(gòu)信息不是很強(qiáng)。ORL是人臉數(shù)據(jù)集，人臉圖像僅在光照和姿態(tài)上發(fā)生較小的改變，所以低秩性很好，能夠較全面地揭示數(shù)據(jù)的全局結(jié)構(gòu)信息，因此LRSPP和LRSPE算法較傳統(tǒng)幾種算法取得的效果更加明顯。

Figure 2 Recognition rates of different algorithms in subspace with different numbers of dimensionality圖2 幾種算法在不同維數(shù)子空間中的識別率

在本文提出的算法中存在一個(gè)權(quán)衡數(shù)據(jù)低秩特性和稀疏特性的平衡參數(shù)β，我們在0～1的范圍內(nèi)人為地選取不同的數(shù)值設(shè)定為參數(shù)β的值，使得低秩稀疏圖揭示的全局結(jié)構(gòu)信息和局部結(jié)構(gòu)信息的比重不同，觀察參數(shù)β對識別結(jié)果的影響。當(dāng)參數(shù)為0時(shí)，數(shù)據(jù)低秩稀疏圖只反映數(shù)據(jù)的全局結(jié)構(gòu)信息；當(dāng)參數(shù)為1時(shí)，數(shù)據(jù)低秩稀疏圖僅揭示數(shù)據(jù)的局部結(jié)構(gòu)信息。圖3顯示的是參數(shù)β取不同值時(shí)的最佳識別率。從結(jié)果中發(fā)現(xiàn)，在 ORL和Yale數(shù)據(jù)集上，當(dāng)β=0.3～0.5，低秩稀疏圖中同時(shí)含有數(shù)據(jù)的局部特性和全局特性的情況下，識別效果較好；在 MNIST數(shù)據(jù)集上的結(jié)果顯示，當(dāng)β 為1時(shí)，取得的識別效果最好，這是因?yàn)镸NIST數(shù)據(jù)集中包含的手寫數(shù)字0～9，數(shù)字書寫的角度和形式變化多樣，數(shù)據(jù)集本身的低秩特性不強(qiáng)。

5 結(jié)束語

本文提出了在數(shù)據(jù)進(jìn)行投影和嵌入的過程中將數(shù)據(jù)的局部結(jié)構(gòu)特性和全局結(jié)構(gòu)特性同時(shí)進(jìn)行保持。在圖嵌入理論框架的思想下，首先基于低秩表示和稀疏表示構(gòu)建能夠同時(shí)反映數(shù)據(jù)局部結(jié)構(gòu)特性和全局結(jié)構(gòu)特性的低秩稀疏圖；然后分別利用LPP算法中的投影技術(shù)和NPE算法中的嵌入技術(shù)來保證數(shù)據(jù)的這些特性在降維過程中保持不變，從而提出了LRSPP算法和LRSPE算法。在實(shí)驗(yàn)中，同傳統(tǒng)的特征提取算法LPP和NPE進(jìn)行比較，將LRSPP算法和LRSPE算法用于圖像分類識別任務(wù)中的特征提取步驟，利用獲得的分類識別率高低來評價(jià)算法的有效性。實(shí)驗(yàn)結(jié)果顯示，提出的算法較傳統(tǒng)的方法取得了更理想的實(shí)驗(yàn)效果，表明了低秩稀疏圖在圖像分類中的有效性，較傳統(tǒng)的鄰域圖也更具有優(yōu)越性。但是，本文方法是對數(shù)據(jù)的低秩和稀疏特性分別通過低秩和稀疏模型進(jìn)行揭示的，與流形學(xué)習(xí)中傳統(tǒng)的構(gòu)圖方法比較，本文在構(gòu)圖過程中增加了求解低秩稀疏模型的工作，但慶幸的是整個(gè)構(gòu)圖過程可以離線進(jìn)行。當(dāng)然，如何提高求解低秩稀疏模型效率以降低構(gòu)圖的計(jì)算量，這是本文未來需要繼續(xù)討論的話題。

Figure 3 Impact of parameterβon experimental results圖3 參數(shù)β對實(shí)驗(yàn)結(jié)果的影響

［1］ Yan S，Xu D，Zhang B，et al.Graph embedding and extensions：A general framework for dimensionality reduction［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（1）：40-51.

［2］ Niyogi X.Locality preserving projections［C］∥Neural Information Processing Systems，2004：153.

［3］ He X，Cai D，Yan S，et al.Neighborhood preserving embedding［C］∥Proc of the 10th IEEE International Conference on Computer Vision（ICCV 2005），2005：1208-1213.

［4］ Cheng B，Yang J，Yan S，et al.Learning with l1-graph for image analysis［J］.IEEE Transactions on Image Processing，2010，19（4）：858-866.

［5］ Wright J，Yang A Y，Ganesh A，et al.Robust face recognition via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（2）：210-227.

［6］ Zhuang L，Gao H，Huang J，et al.Semi-supervised classification via low rank graph［C］∥Proc of the 6th International Conference on Image and Graphics（ICIG），2011：511-516.

［7］ Liu G，Lin Z，Yu Y.Robust subspace segmentation by low rank representation［C］∥Proc of the 27th International Conference on Machine Learning（ICML-10），2010：663-670.

［8］ Bruckstein A M，Donoho D L，Elad M.From sparse solutions of systems of equations to sparse modeling of signals and images［J］.SIAM Review，2009，51（1）：34-81.

［9］ Liu G，Lin Z，Yan S，et al.Robust recovery of subspace structures by low-rank representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35 （1）：171-184.

［10］ Donoho D L，Tsaig Y.Fast solution of l1-norm minimization problems when the solution may be sparse［J］.IEEE Transactions on Information Theory，2008，54（11）：4789-4812.

楊國亮（1973），男，江西豐城人，博士，副教授，研究方向?yàn)橹悄芸刂啤D像處理與模式識別。E-mail：ygliang30@126. com

YANG Guo-liang，born in 1973，PhD， associate professor，his research interests include intelligent controls，image processing，and pattern recognition.

Structure preserving projection algorithm based on low rank and sparse graph

YANG Guo-liang，LUO Lu，F(xiàn)ENG Yi-qin，LIANG Li-ming
（School of Electrical Engineering and Automation，Jiangxi University of Science and Technology，Ganzhou 341000，China）

In the unifying frameworks like graph embedding，constructing a good graph to represent data properties is critical for dimensionality reduction technology.In this paper，we construct a low rank and sparse graph to reveal local and global structure information of the data based on sparse representation and low rank representation.We first use graph embedding technology to preserve such properties during the linear projections，and then obtain the low-dimensional embedding of the original high-dimensional data.The effectiveness of the proposed method is compared with the state-of-the-art algorithms and is verified on face and handwritten digit databases（ORL，Yale，PIE，MNIST）.

graph embedding；sparse representation；low rank representation；low rank and sparse graph；linear projections

TP391.4

A

10.3969/j.issn.1007-130X.2015.08.025

1007-130X（2015）08-1584-07

2014-08-11；

2014-11-11

國家自然科學(xué)基金資助項(xiàng)目（51365017，61305019）；江西省科技廳青年科學(xué)基金資助項(xiàng)目（20132bab211032）

通信地址：341000江西省贛州市紅旗大道86號江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院

Address：School of Electrical Engineering and Automation，Jiangxi University of Science and Technology，86 Hongqi Avenue，Ganzhou

341000，Jiangxi，P.R.China