一種可鑒別的稀疏保局投影算法

茍建平，詹永照，張建明，沈項軍

（江蘇大學計算機科學與通信工程學院，江蘇鎮(zhèn)江212013）

一種可鑒別的稀疏保局投影算法

茍建平，詹永照，張建明，沈項軍

（江蘇大學計算機科學與通信工程學院，江蘇鎮(zhèn)江212013）

為了增強高維數(shù)據(jù)在低維子空間中的模式識別能力，假設任意2個類別相同的相似樣本其稀疏表示也相似，并基于SPP和LPP思想，提出一種可鑒別稀疏保局投影降維新方法DSLPP.該方法通過稀疏表示學習和保局部投影，使得在投影子空間中不僅能夠保持稀疏表示對數(shù)據(jù)很好的表達能力，而且較好地獲取高維數(shù)據(jù)所蘊含的本質(zhì)局部流形結(jié)構(gòu)和自然判別信息，從而增強高維數(shù)據(jù)在子空間中的表示能力和可鑒別能力.在3個典型的人臉數(shù)據(jù)集Yale，ORL和PIE29上，將所提出方法DSLPP與PCA，LPP，NPE和SPP進行對比試驗.結(jié)果表明DSLPP是一種有效的降維方法，能夠較好地改善高維數(shù)據(jù)在低維子空間中的分類效果.

可鑒別稀疏保局投影；稀疏保持投影；保局部投影；稀疏表示；降維；模式分類

doi∶10.3969/j.issn.1671-7775.2015.06.013

近年來，稀疏表示已成為模式識別與計算機視覺領域廣泛關注的熱門話題之一.稀疏表示的基本假設是輸入信號在一個過完備系統(tǒng)中求解一個最稀疏或者接近稀疏的表示，在信號壓縮與編碼［1］、圖像恢復［2］方面取得了顯著的成果.由于稀疏表示具有較好的數(shù)據(jù)表達能力和自然判別能力，其在人臉識別［3-4］、圖像分類［5］、視頻語義分析［6］等模式分類問題中得到了廣泛應用，并取得了較好的分類效果.

在模式分類問題中，降維技術是的一個重要的處理過程.目前，降維技術主要包括線性和非線性2類方法.線性方法主要有主成分分析（PrinciPal com-Ponent analysis，PCA）、線性判別分析（linear discriminant analysis，LDA）和保局部投影（locality Preserving Projections，LPP）［7］等，非線性方法主要有基于核的KPCA，KLDA，KLPP等方法和基于流形的等距特征映射（isometric feature maPPing，ISOMAP）、拉普拉斯特征映射（LaPlacian eigenmaP，LE）、局部線性嵌入（locally linear embedding，LLE）等方法.這些典型的降維方法幾乎都可以統(tǒng)一在圖嵌入框架下，稱為基于圖的降維方法［S］.其中，最為典型的圖嵌入方法是LPP和保近鄰嵌入（neighborhood Preserving embedding，NPE）［9］，2者的主要思想都是基于近鄰構(gòu)圖方式，構(gòu)造一個局部鄰接圖，通過投影轉(zhuǎn)化，將高維數(shù)據(jù)的這種局部結(jié)構(gòu)保持在低維子空間中.LPP和NPE本質(zhì)上是線性的流形學習方法，LPP是LE的線性擴展，NPE是LEE的線性擴展.

鑒于稀疏表示對數(shù)據(jù)具有很好的表達能力和自然判別能力，它在降維技術中的應用取得了成功.稀疏保持投影（sParsity Preserving Projections，SPP）就是一種典型的基于稀疏表示的無監(jiān)督降維方法［10］.針對在LLE，LPP等一些圖嵌入學習算法中，依靠局部的K-近鄰構(gòu)圖的局限性，SPP采用稀疏表示構(gòu)圖，自動選擇樣本的近鄰個數(shù)，并且定義類似于NPE的目標函數(shù)，獲得一個低維的子空間投影.該投影在保持數(shù)據(jù)的旋轉(zhuǎn)、尺度和平移不變的內(nèi)蘊特征的同時，還具有自然的判別能力.基于SPP的主要思想，一些研究者在SPP的基礎上，提出了一些其他的稀疏降維方法［11-12］，這些方法主要將樣本的類別信息加入到稀疏表示學習中，從而增強了數(shù)據(jù)降維后模式之間的判別能力.

盡管SPP及其他稀疏降維方法在低維空間中保持了高維數(shù)據(jù)的一些內(nèi)在幾何特性和自然判別信息，并取得了良好的分類效果，但是由于未充分考察數(shù)據(jù)的局部幾何特性，數(shù)據(jù)隱含的本質(zhì)流形結(jié)構(gòu)以及潛在的判別能力沒有得到充分的獲取，這在一定程度上降低了識別的性能.

文中基于LPP的保持數(shù)據(jù)局部結(jié)構(gòu)特點，并借鑒SPP和LPP思想，提出一種可鑒別的稀疏保局投影算法（discriminative sParsity locality Preserving Projections，DSLPP）.在DSLPP算法中，首先通過稀疏學習，獲得每個訓練樣本優(yōu)化后的稀疏表達.其中，稀疏表示系數(shù)矩陣具有在一定程度上反映了數(shù)據(jù)的內(nèi)在幾何屬性和潛在自然判別能力特點.根據(jù)文獻［13］可知，稀疏表示學習獨立的對每個特征樣本進行編碼，由于過完備和足夠的字典，相似的特征可能得到完全不同的稀疏編碼去表達，這將導致數(shù)據(jù)局部信息的損失.為了保持這種局部信息，以及充分利用稀疏矩陣所具有的特性，DSLPP基于LPP保局部的思想，假定類別相同的2個相似樣本在稀疏表達后也相似，且投影在低維的子空間中也應盡可能地保持相似，從而使得高維數(shù)據(jù)的局部幾何結(jié)構(gòu)較好地保持在子空間中，并增強高維數(shù)據(jù)在子空間中的判別能力.為了驗證所提DSLPP算法的有效性，文中在3個典型的人臉數(shù)據(jù)庫上進行對比試驗.

1 相關的工作簡介

1.1保局部投影算法LPP

保局部投影算法LPP［7］是一種保持數(shù)據(jù)局部結(jié)構(gòu)的線性降維方法.LPP主要是通過構(gòu)造高維數(shù)據(jù)的局部鄰接圖，并在圖嵌入學習過程中保持這種局部的近鄰關系，其算法實現(xiàn)過程如下.

1）近鄰構(gòu)圖.采用K-近鄰方式構(gòu)建數(shù)據(jù)的鄰接圖.當樣本點xj是點xi的k個近鄰點或者點xi是點xj的k個近鄰點，頂點i和j之間用邊連接起來.近鄰邊權(quán)重W通常采用高斯核函數(shù)計算，即

式中∶Nk（xi）或者Nk（xj）代表點xi或xj的k個近鄰點集；參數(shù)t為正的調(diào)整因子.

2）特征映射.優(yōu)化的目標函數(shù)定義為

通過簡單的運算，式（2）可以轉(zhuǎn)化為求解一般的特征值問題，即為

式中∶I為單位矩陣；P為投影矩陣；L=D-W為拉普拉斯矩陣；D為對角矩陣，它的每一個元素是矩陣W的列之和，即的最優(yōu)解P*=［P1， P2，…，Pr］是求解式（3）的前r個最小特征值所對應的特征向量組成的映射矩陣.

1.2稀疏保持投影算法SPP

稀疏保持投影［10］主要包括稀疏構(gòu)圖和特征映射2個步驟.稀疏構(gòu)圖是通過稀疏學習，使得每個訓練樣本都可以用其他訓練樣本來合理的稀疏表達，并學習得到所有訓練樣本的稀疏表示系數(shù)所組成的稀疏系數(shù)矩陣.特征映射主要借鑒NPE思想［9］，利用訓練樣本的稀疏系數(shù)矩陣，通過特征學習，使得原始樣本與其相應的稀疏表示后的樣本投影到子空間中，且2者差異最小化.

1）稀疏構(gòu)圖.給定訓練數(shù)據(jù)樣本集X=［x1，x2，…，xn］∈RdXn，且d＜n，稀疏表示就是用稀疏系數(shù)向量si將xi表示成X中各向量的線性組合xi=

式中∶si=［si，1，…，si，i-1，0，si，i+1，…，si，n］T∈Rn；l=［1，…，1，…，1］T∈Rn是分量全1的向量.值得注意的是，在si中的第i個元素為0表示從X中去掉xi.式（4）得到的每個最優(yōu)的稀疏系數(shù)向量～si本質(zhì)上代表了樣本xi與其他樣本點的近鄰關系及其鄰接權(quán)重大小.

2）特征映射.為了在投影子空間中保持稀疏系數(shù)矩陣所反映的數(shù)據(jù)內(nèi)蘊幾何特性和潛在判別信息，基于NPE思想，投影目標函數(shù)定義為

通過簡單的運算，式（5）可以等價轉(zhuǎn)化為求解一般的特征值問題，即為

2 可鑒別稀疏保局投影

受SPP和LPP的基本思想啟發(fā)，文中提出一種新的降維新方法∶可鑒別稀疏保局投影算法（discriminative sParsity locality Preserving Projections，DSLPP）.在DSLPP學習得到的低維嵌入空間中，不僅能保持稀疏系數(shù)矩陣S所具有的高維數(shù)據(jù)空間的內(nèi)在幾何屬性和自然的判別能力，還能保持數(shù)據(jù)的局部幾何信息.

2.1基本思想

在DSLPP中，為了保持稀疏系數(shù)所具有的數(shù)據(jù)內(nèi)在幾何特性和潛在判別信息，同樣采用式（4）進行稀疏學習得到稀疏系數(shù)重構(gòu)矩陣S，使得訓練樣本集中的每個樣本xi都可以通過其他訓練樣本進行合理的重構(gòu)表達，即是文獻［13］表明，通過稀疏學習后，2個原本相似的樣本其稀疏表達后可能完全不一樣，導致數(shù)據(jù)局部信息的損失.為了有效地保持數(shù)據(jù)的局部幾何信息，基于LPP的思想，在DSLPP算法中，可使類別相同的2個相似的樣本進行稀疏表示后也盡可能地保持其相似性，進而在低維的嵌入子空間中保持數(shù)據(jù)的本質(zhì)的局部流形結(jié)構(gòu)，進一步增強高維數(shù)據(jù)在低維子空間中的可鑒別能力.

為了使得稀疏表達后的每個樣本，在低維投影中保持原始高維數(shù)據(jù)的局部幾何關系，文中采用K-近鄰構(gòu)圖方式，在原始的樣本空間中構(gòu)造訓練樣本點之間的局部鄰接關系圖G并給每條近鄰邊賦予相應的權(quán)重.鄰接圖G的近鄰權(quán)重矩陣W定義［14］為

式中參數(shù)t是正的動態(tài)局部調(diào)整近鄰點之間權(quán)重的因子，定義為

為了保持這種近鄰局部關系，假定任意2個類別相同的樣本xi和xj稀疏表示后，即如果xi和xj很相似，為了保持原始樣本之間的相似性和之間也應盡可能保持相似，其對應的稀疏系數(shù)和也應該保持相似［13］.為了滿足在高維空間中類別相同的相似樣本xi和xj，其稀疏表示也相似的，在低維投影空間中也盡可能的保持相似，DSLPP的投影目標函數(shù)定義為

通過以下簡單的代數(shù)運算

式（8）可以改寫為

式中L=D-W為拉普拉斯矩陣，D為對角矩陣，它的每一個元素是矩陣W列之和由式（9）可知，所求解的投影矩陣P，不僅具有了稀疏學習后所具有的一些典型特征，而且還保持了數(shù)據(jù)所具有的局部幾何屬性.

2.2目標函數(shù)優(yōu)化

為了在低維投影空間中，保持稀疏學習后所具有的數(shù)據(jù)內(nèi)在幾何的屬性、自然判別能力和數(shù)據(jù)的局部信息，根據(jù)式（9），DSLPP的最終目標函數(shù)定義為

式中PTP=I是正交化約束條件，保證投影矩陣的向量是相互正交的，使得投影矩陣P具有較好的保局部性和鑒別能力.采用拉格朗日乘數(shù)方法，式（10）經(jīng)過簡單的代數(shù)運算，可以轉(zhuǎn)化為求解如下一般特征值問題∶

通過求解式（11）中的一般特征值問題，DSLPP的最優(yōu)投影矩陣P*是該特征值問題的前r個最小特征值所對應的特征向量組成的矩陣，即λ1≤λ2≤…≤λr，P*=［P1，P2，…，Pr］.

在所提出的DSLLP算法中，使用其軟件包SLEP［15］來求解式（4）中稀疏學習的優(yōu)化問題.

2.3算法流程

根據(jù)2.1-2.2的分析，DSLPP算法主要實現(xiàn)過程總結(jié)如下∶①根據(jù)式（4）進行稀疏表示學習，得到每個訓練樣本的稀疏重構(gòu)矩陣S；②使用K-近鄰構(gòu)圖方式，構(gòu)造訓練樣本的局部鄰接圖G；③根據(jù)式（7），計算近鄰權(quán)重矩陣W；④求解投影矩陣∶根據(jù)式（11）的一般特征值問題求解特征值，從而得到最優(yōu)的投影矩陣P*；⑤特征提取∶根據(jù)最優(yōu)的投影矩陣P*，將所有原始高維空間的數(shù)據(jù)點映射到低維的子空間中，即Y=PTX；⑥模式分類∶選擇一定的分類器，文中采用最近鄰分類方法，對投影到低維子空間中的待測點進行分類.

3 試驗分析

為了驗證所提出DSLPP算法的有效性，在3個典型的人臉數(shù)據(jù)集Yale，ORL和PIE29上，與PCA，LPP，NPE和SPP方法進行對比試驗.從Yale，ORL和PIE29人臉數(shù)據(jù)庫的每類中隨機選取訓練樣本個數(shù)l分別為l=7，l=5，l=11組成訓練樣本集，剩余的做測試樣本集.在每個數(shù)據(jù)集上，做20次試驗，并根據(jù)95％的置信度對所有試驗結(jié)果做統(tǒng)計檢測，取其平均準確識別率（recognition rate）作為最終的分類結(jié)果.在試驗中，為了克服LPP，SPP和DSLPP中可能存在的奇異性問題，采用PCA作為預處理，以及構(gòu)造近鄰圖時所用到的近鄰選擇參數(shù)標記為Wk.為了保持對比試驗的公平性，LPP和DSLPP近鄰權(quán)重的調(diào)整參數(shù)t采用相同的方法設置，LPP和NPE中的Wk值設置為l-1.在試驗的模式分類階段，采用最近鄰分類方法.此外，試驗所用NPE和SPP代碼分別從httP∶//www.cad.zju.edu.cn/home/dengcai/和httP∶//idar.lcu.edu.cn/網(wǎng)站下載.

3.1數(shù)據(jù)集簡介

Yale人臉數(shù)據(jù)庫（httP∶//cvc.yale.edu/Projects/ yalefaces/yalefaces.html）是由15個人的165張人臉圖片組成，每人有11個樣本圖片.每個人的人臉圖片采集于不同光照和面部表情等條件，這些條件分別為∶中心光照、戴眼鏡、高興、左光照、無眼鏡、正常、右光照、悲哀、困倦、驚喜和眨眼.圖1a為其中一個人的樣本圖片示例.

ORL人臉數(shù)據(jù)庫（httP∶//www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html）是由40個不同人的400張人臉圖片組成，每人有10張照片.每個人的人臉圖片采集于不同的時間、光照和表情變化（睜眼和閉眼、有笑容和沒有笑容）和人臉細部（帶眼鏡和不帶眼鏡）.圖1b為其中一個人的樣本圖片示例.

PIE人臉數(shù)據(jù)庫（httP∶//www.face-rec.org/databases/）是由6S個不同人的41 36S張人臉圖片組成.每個人的人臉圖片采集于13個不同的姿態(tài)變化，43個不同的光照變化和4種不同的表情變化.在本文試驗中，選擇該數(shù)據(jù)庫的一個子集PIE29，其中包括6S個人的1 632張圖片，每個人有24張樣本圖片.圖1c為其中一個人的樣本圖片示例.在整個試驗中，為了減少計算時間，將3個數(shù)據(jù)集中的每張圖片采樣至32 X32像素大小，灰度歸一化至單位區(qū)間，并拉伸成1 024維的列向量.

3.2試驗結(jié)果

圖2　DSLPP在各數(shù)據(jù)集上的識別率隨近鄰參數(shù)Wk變化結(jié)果

圖3　各方法的識別率隨投影維度的變化

表1　各方法在各數(shù)據(jù)集上的最大識別率及其標準偏差和維度

從表1中的分類結(jié)果可知，所提出的DSLPP方法與PCA，LPP，NPE和SPP相比，一致性地取得了最好的分類效果，而且DSLPP所取得的最大識別率所對應的維度相比其他4種方法要小很多.

通過以上對比試驗可知，所提出的DSLPP算法在高維的模式識別中取得了較好的分類效果，且所需維度較小，是一種行之有效的降維方法.這也充分證明了DSLPP能夠較好保持高維數(shù)據(jù)的局部性和稀疏學習得到的數(shù)據(jù)內(nèi)蘊特性，以及充分獲取判別信息的能力等優(yōu)點，在模式分類的高維降維中起著十分重要的作用.

4 結(jié) 論

1）在DSLPP學習得到的低維子空間中，DSLPP算法在保持稀疏學習所具有的數(shù)據(jù)的內(nèi)在幾何屬性和自然判別能力的同時，還較好地保持了數(shù)據(jù)的局部流形結(jié)構(gòu)信息，從而增強高維數(shù)據(jù)在低維子空間中可鑒別能力.

2）試驗結(jié)果表明，所提出的DSLPP算法是一種行之有效的降維方法，能較好地提高了高維數(shù)據(jù)在子空間中的分類效果.

3）在下一步工作中，筆者將研究稀疏表示和降維過程的統(tǒng)一學習.

（

）

［1］Wang Liangjun，Wu Xiaolin，Shi Guangming.Binned Progressive quantization for comPressive sensing［J］. IEEE Transactions on Image Processing，2012，21（6）∶29S0-2990.

［2］Mei Xue，Ling Haibin，Jacobs David W.Illumination recovery from image with cast shadows via sParse rePresentation［J］.IEEE Transactions on Image Processing，2011，20（S）∶2366-2377.

［3］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.

［4］DengWeihong，Hu Jiani，Guo Jun.Extended SRC∶undersamPled face recognition via intra-class variant dictionary［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（9）∶1S64-1S70.

［5］Yang Meng，Zhang Lei，F(xiàn)eng Xiangchu，et al.SParse rePresentation based fisher discrimination dictionary learning for image classification［J］.International Journal of Computer Vision，2014，109（3）∶209-232.

［6］詹永照，張珊珊，成科揚.基于非線性可鑒別的稀疏表示視頻語義分析方法［J］.江蘇大學學報∶自然科學版，2013，34（6）∶669-674. Zhan Yongzhao，Zhang Shanshan，Cheng Keyang. Video semantics analysis based on nonlinear identifiable sParse rePresentation［J］.Journal of Jiangsu Uniuersity∶Natural Science Edition，2013，34（6）∶669-674.（in Chinese）

［7］He Xiaofei，Yan Shuicheng，Hu Yuxiao，et al.Face recognition using laPlacianfaces［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（3）∶32S-340.

［S］Yan Shuicheng，Xu Dong，Zhang Benyu，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.

［9］He Xiaofei，CaiDeng，Yan Shuicheng，etal.Neighborhood Preserving embedding［C］∥Proceedings of the 10th IEEE International Conference on Computer Vision. Beijing，China∶IEEE，2005∶120S-1213.

［10］Qiao Lishan，Chen Songcan，Tan Xiaoyang.SParsity Preserving Projections with aPPlications to face recognition［J］.Pattern Recognition，2010，43（1）∶331 -341.

［11］Wei Lai，Xu Feifei，Wu Aihua.Weighted discriminative sParsity Preserving embedding for face recognition［J］.Knowledge-Based Systems，2014，57∶136-145.

［12］Yang Wankou，Wang Zhenyu，Sun Changyin.A collaborative rePresentation based Projectionsmethod for feature extraction［J］.Pattern Recognition，2015，4S∶20-27.

［13］Gao S H，Tsang IW H，Chia L T.LaPlacian sParse coding，hyPergraPh laPlacian sParse coding，and aPPlications［J］.IEEE Transactionson Pattern Analysisand Machine Intelligence，2013，35（1）∶92-104.

［14］Gou JianPing，Yi Zhang.Locality-based discriminant neighborhood embedding［J］.The Computer Journal，2013，56（9）∶1063-10S2.

［15］Liu Jun，Ji Shuiwang，Ye JiePing.SLEP∶sParse learning with efficient Projections［CP/OL］.［2015-04-13］httP∶//www.Public.asu.edu/～jye02/Software/ SLEP.

（責任編輯 梁家峰）

A discrim inative sParsity locality Preserving Projectionsmethod

Gou Jianping，Zhan Yongzhao，Zhang Jianming，Shen Xiangjun
（School of ComPuter Science and Communication Engineering，Jiangsu University，Zhenjiang，Jiangsu 212013，China）

∶To imProve the Pattern recognition for high-dimensional data，assuming that any two similar samPles within the same class had similar sParse rePresentations，a novel dimensionality reductionmethod of discriminative sParsity locality Preserving Projections（DSLPP）was ProPosed based on SPP and LPP. Through sParse learning and locality Preserving Projections，the good sParse rePresentation was Preserved by the ProPosed DSLPP，and the Potential localmanifold structure and the discrimination information of high-dimensional datawere also bewell caPtured in the obtained subsPace.The exPression ability and the identifiability of high dimensional data were enhanced in the subsPace.The exPeriments were comPleted on Yale，ORL and PIE29 face databases to comPare DSLPPwith PCA，LPP，NPE and SPP.The results show that the ProPosed DSLPP is an effective dimensionality reduction algorithm，and it can well imProve the classification Performance for high-dimensional data in subsPace.

∶discriminative sParsity locality Preserving Projection；sParsity Preserving Projection；locality Preserving Projection；sParse rePresentation；dimensionality reduction；Pattern classification

TP391.9

A

1671-7775（2015）06-0691-06

茍建平，詹永照，張建明，等.一種可鑒別的稀疏保局投影算法［J］.江蘇大學學報∶自然科學版，2015，36（6）∶691-696.

2015-04-13

國家自然科學基金資助項目（6150220S，61170126）；中國博士后科學基金資助項目（2015M570411）；江蘇省自然科學基金資助項目（BK20150522）；江蘇省高校自然科學研究項目（14KJB520007）；江蘇大學高級專業(yè)人才科研啟動基金資助項目（14JDG037）

茍建平（19S2—），男，四川巴中人，講師（goujianPing@ujs.edu.cn），主要從事機器學習、模式識別研究.

詹永照（1962—），男，福建尤溪人，教授，博士生導師（yzzhan@ujs.edu.cn），主要從事多媒體與人機交互研究.