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

（江西理工大學電氣工程與自動化學院，江西 贛州 341000）

基于低秩稀疏圖的結構保持投影算法*

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

（江西理工大學電氣工程與自動化學院，江西 贛州 341000）

在圖嵌入理論框架下，能夠較好地揭示數(shù)據(jù)本質特性的圖在一些維數(shù)約簡方法中起到關鍵性的作用?；谙∈璞硎竞偷椭缺硎痉椒ǎ瑯嫿艘环N低秩稀疏圖，能夠同時揭示數(shù)據(jù)的局部結構信息和全局結構信息。然后，利用圖嵌入理論方法使這些特性在線性投影的過程中得以保持不變，從而學習出高維數(shù)據(jù)有效的低維嵌入。在標準的人臉和手寫數(shù)字數(shù)據(jù)集（ORL，Yale，PIE，MNIST）上進行實驗，同傳統(tǒng)的圖嵌入方法比較，結果表明了算法的有效性。

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

1 引言

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

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

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

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

2 低秩稀疏圖

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

2.1 稀疏圖

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

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

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

2.2 低秩圖

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

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

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

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

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

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

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

Eλ

對拉格朗日乘子Y1、Y2進行更新：

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

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

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

同時，利用式（14）使得連接權值矩陣WLR滿足對稱性：

2.3 構建低秩稀疏圖

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

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

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

算法1 低秩稀疏圖的構建

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

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

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

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

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

步驟4 對稀疏權值矩陣和低秩權值矩陣進行歸一化處理；

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

3 基于低秩稀疏圖的結構保持投影

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

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

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

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

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

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

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

4 實驗與結果分析

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

4.1 實驗數(shù)據(jù)集

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

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

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

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

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

4.2 算法結果分析

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

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

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

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

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

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

5 結束語

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

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

［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），男，江西豐城人，博士，副教授，研究方向為智能控制、圖像處理與模式識別。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

國家自然科學基金資助項目（51365017，61305019）；江西省科技廳青年科學基金資助項目（20132bab211032）

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

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

341000，Jiangxi，P.R.China