一種半監督稀疏保持近鄰判別嵌入算法

李世銀，王 飛，彭 超

（中國礦業大學信息與電氣工程學院，江蘇徐州 221116）

一種半監督稀疏保持近鄰判別嵌入算法

李世銀，王 飛，彭 超

（中國礦業大學信息與電氣工程學院，江蘇徐州 221116）

保持近鄰嵌入（NPE）算法對局部線性嵌入（LLE）算法進行了改進，克服了新來樣本問題，但在處理分類問題上表現不足。基于此提出一種半監督稀疏保持近鄰判別嵌入算法，該方法首先采用小波變換對數據進行預處理，然后執行等距離映射（Isomap）算法選擇合適的低維嵌入維數，最后結合稀疏表示理論、NPE和線性判別分析（LDA）的思想，重構鄰域圖，并在建立目標函數時使得已標簽信息中同類樣本點之間相互靠近，異類樣本點之間相互遠離，未標簽信息鄰域信息得以保持。這樣，既得到了高維映射函數，又提高了分類正確率。通過在人臉數據庫上實驗，并與其他半監督算法作比較，該算法在識別率上表現較好。

保持近鄰嵌入;稀疏表示;線性判別分析;半監督

目前，在較為典型的降維方法中線性降維的方法主要有主成分分析（PCA）［1］、線性判別分析（LDA）［2］等，這些方法在處理具有線性結構的數據時表現出較好的優越性，但是在處理具有非線性數據結構時表現較差。后來出現的較為典型的流形降維方法，如等距離映射（Isomap）［3］、局部線性嵌入（LLE）［4］、Laplace 特征嵌入（Laplacian Eigenmaps）［5］等在處理非線性結構數據時表現較好，但是它們同時又都具有無法處理外來樣本的缺點。為克服這些方法的缺點，文獻［6］提出了保持近鄰嵌入（NPE）算法，該方法能有效地處理外來樣本的問題，但是該方法在處理分類問題時表現不足，因為它在線性重構時并沒有對鄰域的類別進行判斷。文獻［7］結合LDA思想，使得同類樣本點分布盡可能密集，不同樣本點分離，提出了一種新的半監督降維方法——半監督判別鄰域嵌入（SSDNE），提高了識別率，但是該方法在選擇鄰域時依賴K值的選擇，不能動態地反映數據之間的變化信息;文獻［8］提出一種基于稀疏表示的半監督降維方法（SpSSDR），該方法結合稀疏表示和LDA思想，通過稀疏重構系數來同時定義圖上邊連接性及邊權重，再結合邊約束信息進行降維，但是容易忽略局部數據信息。綜合上述文獻的優點，本文結合稀疏表示思想、NPE和LDA算法，提出了一種基于半監督的保持近鄰判別嵌入算法（SNPDE）。

小波變換是一種新的變換分析方法，它繼承和發展了短時傅里葉變換局部化的思想，是進行信號時域分析的理想工具，在信號處理領域得到廣泛的應用。在圖像處理上，通過小波變換可將圖像分解成不同尺度的低頻分量和高頻分量，低頻分量保持圖像的輪廓，高頻分量保持圖像的細節［9］。保留圖像低頻信息，適當去掉高頻部分信息可以減少數據冗余，能很大程度地消除數據間的高頻相關性，文獻［10］把小波變換引入有監督增量式局部線性嵌入算法，提出了一種新的局部線性嵌入算法，用于人臉識別，提高了識別精度;而文獻［11］把小波變換引入線性判別分析，提出了一種將人臉圖像的小波分解和線性判別分析結合的人臉識別方法，提高了識別率。鑒于此思想，本文在數據預處理階段引入小波變換思想，提取低頻分量，然后再將處理后的數據應用到本文提出的算法中。

1 保持近鄰嵌入算法

保持近鄰嵌入算法（NPE）是局部線性嵌入（LLE）的線性逼近，能在降維后得到一個高維映射函數，彌補了LLE無法處理新來樣本問題上的不足［6］。

設X={x1，x2，…，xn}∈Rm×n為訓練樣本，Y={y1，y2，…，yn}∈Rd×n為降維后訓練樣本的低維嵌入，n為樣本數，m為樣本維數，d為嵌入維數。NPE能在降維過程中得到一個投影矩陣W，將高維數據映射到一個低維d的特征空間中，即Y=WTX。NPE算法的具體步驟為:

首先，構造近鄰圖。與LLE類似，假定每個局部近鄰是線性的，因此可以通過線性組合來描述局部的幾何特征，選擇每個樣本點的K個近鄰的構成近鄰圖。

然后，計算重建權值。近鄰圖中每一個訓練樣本xi用它的K近鄰點xj線性重構，wij通過重建代價函數計算，公式為

式中:kn是xi的近鄰個數。

最后，通過求解式（2）的廣義特征向量得到線性映射關系

式中:M=（I-W）T（I-W），M是半正定矩陣。

2 基于半監督的保持近鄰判別嵌入算法

2.1 數據預處理

2.1.1 小波變換

根據小波變換原理，低頻部分具有較高的頻率分辨力和較低的時間分辨力，在圖像處理中，高頻信號起到的作用非常微弱，而低頻部分是針對有意義的某種尺度信號，對進一步的研究具有很好的幫助［9］。在運行本文提出的算法之前，首先對訓練樣本進行小波分解，并提取低頻部分的數據作為人臉識別的特征矢量。圖1是對ORL數據庫中的一個圖像的低頻分量圖，從左到右依次為:原始圖像、進行小波1層分解和2層分解。原始圖像大小為112×92，1層分解后圖像大小為56×46，2層分解后圖像大小為28×23。

2.1.2 Isomap 選擇合適的維數

剩余方差描述的是低維特征空間中保持高維空間數據間幾何關系的程度，剩余方差越小，表示這種幾何關系保持的越好［3］。因此，本文在對高維數據降維前，并不是盲目選擇某一低維進行降維，而是對高維數據先執行Isomap算法，通過剩余方差與維數之間的關系圖來確定合適的低維嵌入維數。

圖1 小波分解

2.2 稀疏重構權值

式中:X=［xi，x2，…，xn］為基信號矩陣;C 是重建系數向量;‖C‖0表示C的偽l0范數，用于衡量C的稀疏性，為C中非零元素的個數。針對上式條件存在的非凸問題，研究表明，只要所求的理論最優解足夠稀釋，則l0和l1問題等價，式（1）描述的優化問題的解唯一，且可以通過式（4）優化問題求解

求解式（4）可以通過拉格朗日乘子法獲得，即求解

同類樣本離散度矩陣為

異類樣本離散度矩陣為

未標簽的樣本，定義其上的稀疏保持項為

目標函數定義為

把上式的特征值從大到小排序λ0≥λ1≥…≥λd-1，對應的特征向量A={a0，a1，…，ad-1}，得到低維嵌入 yi=ATxi。

2.3 SNPDE 具體過程

綜上所述，本文提出的具體算法步驟為:1）對訓練樣本進行小波分解，得到的數據運行Isomap選擇合適的低維嵌入維數;2）根據標簽信息和式（6）和式（7）分別計算同類樣本離散度矩陣和異類樣本離散度矩陣，根據式（8）計算未標簽樣本的稀疏保持項。

3 實驗與分析

ORL標準人臉庫是400個112×92灰度自然場景下的人臉圖像，由40個測試者提供。其中人臉部分表情和細節均有變化，例如笑與不笑、眼睛睜著或閉著、戴或不戴眼鏡等，人臉姿態也有變化，其深度旋轉和平面旋轉可達20°，人臉尺寸最多有10%的變化。在ORL人臉庫上做實驗，隨機選擇每個人5幅圖像做訓練樣本，然后隨機選擇5幅作為測試樣本，這樣訓練樣本和測試樣本總數均為200個。

另外，Jaffe人臉數據庫，是在人臉表情識別研究中應用最多的數據庫之一。包括216張人臉表情圖像數據，每人20幾幅分辨力為256×256的圖像組成。在Jaffe人臉庫上選10個人臉圖像做實驗，每個人均隨機選擇10幅圖像做訓練樣本，另外隨機選擇10幅為測試樣本，這樣訓練樣本和測試樣本總數均為100個。

首先，為驗證小波分解的有效性，本文用ORL數據庫分別對執行小波2層分解的NPE和未執行小波2層分解的NPE進行對比實驗，結果如表1所示。

表1 未執行小波分解的NPE 算法與執行小波分解的NPE 算法比較

表1中的時間是NPE僅訓練過程所用的時間，單位為s，可以看出執行小波分解和未執行小波分解的NPE算法中，最終的識別率相差不大，但時間上卻節省了大約0.9 s，所以本文提出的算法在實驗預處理上同樣先進行小波分解。

本文實驗對訓練樣本采用小波2層分解，對于ORL數據庫分解后訓練樣本大小由原來的112×92降到28×23，Jaffe數據庫分解后訓練樣本大小由原來的256×256降到64×64。然后分別對數據進行Isomap降維算法，得到剩余方差和維數關系圖，如圖2所示。對于ORL數據庫，當維數大于10時，剩余方差變化就非常小了，因此這里可以選取低維空間大于10的維數，對于Jaffe數據庫，選擇大于20的維數，然后再分別運行PCA+LDA，NPE，NPDE，SpSSDR和SNPDE算法降到各維，最后采用1－NN分類器進行分類。

圖2 剩余方差和維數關系圖

實驗中，近鄰數K統一設置為10，α設置為0.01，為達到對比效果，本文分別對兩個數據庫進行不同維度下降維結果對比，為避免實驗隨機性，實驗結果均為20次結果的平均值，實驗結果如圖3所示。圖3a和圖3b分別是ORL和Jaffe數據庫中選擇標簽120和60個訓練樣本時各種算法的識別率，圖3c和圖3d分別是ORL和Jaffe數據庫中選擇標簽80和40個訓練樣本時各種算法的識別率。

為了比較各種算法在不同目標維度下的性能，分別在ORL和Jaffe執行各算法，如圖3a和圖3b所示，本文提出的算法要優于其他算法，這是因為:人臉數據庫是一種非線性結構，LDA方法在處理這些數據時，容易忽略局部數據信息，所以效果最差;SSDNE算法融合了NPE和LDA的思想，降維過程中，重構目標函數，既保證了局部數據信息，又使得同類樣本點靠近，異類樣本點遠離，效果要好于NPE，但是在建鄰近圖時，K值的選擇是人為的，容易丟失整體樣本點之間隱藏的信息;SpSSDR引入了稀疏表示思想構建圖，基于稀疏重構系數構建的圖較其他算法構造的圖具有更好的區分性，從而易于獲得具有較好區分能力的判別子空間，其上的分類精度也較高，但是SpSSDR容易忽略數據間的局部信息;本文提出的算法SNPDE在重建圖時，既引入了稀疏表示，又結合NPE思想保證了局部信息得以保留，最后的目標函數又結合了LDA思想，易于分類，所以效果最佳。另外，本文重做以上實驗僅對三種半監督算法進行比較，但分別都減少了監督信息標簽，如圖3c和圖3d所示，結果驗證了本文算法的優越性，同時也可以看出，隨監督信息標簽減少，識別率也隨之降低。

圖3 實驗結果

4 小結

本文提出了一種新的半監督降維方法，數據預處理部分選擇小波分解，去掉了高頻部分信息，很大程度地消除數據間的高頻相關性，降低了維數，提高了算法的效率;通過執行Isomap算法選擇了合適的低維嵌入維數進行降維，避免了低維選擇的盲目性;新算法把稀疏表示理論引入到NPE算法中，重新構造了鄰域圖，保證了局部領域關系。同時，構建目標函數時又借助了LDA思想，既得到了映射函數，解決了新來樣本問題，又提高了識別率。

:

［1］TURK M，PENTLAND A.Eigenfaces for recognition［J］.Journal of Cognitive Neuroscience，1991，3（1）:71－86.

［2］邊肇祺，張學工.模式識別［M］.北京:清華大學出版社，2000.

［3］TENENBAUM J B，SILVA V D，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000（290）:2319－2322.

［4］ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000（290）:2323－2326.

［5］BELKIN M，NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003（15）:1373－1396.

［6］HE X F，CAI D，YAN S C，et al.Neighborhood preserving embedding［C］//Proc.ICCV 2005.Washington D C:IEEE Computer Society Press，2005:1208－1213.

［7］劉志宇.一種半監督判別鄰域嵌入算法［J］.計算機工程與應用，2011，47（19）:173－175.

［8］張春濤，郭皎，徐家良.基于稀疏表示的半監督降維方法［J］.計算機工程與應用，2011，47（20）:181－183.

［9］李春華，秦志英.圖像的超小波稀疏表示［J］.電視技術，2012，36（13）:44－47.

［10］劉倩，潘晨.新的局部線性嵌入下的人臉識別方法［J］.計算機工程與應用，2011，47（24）:171－173.

［11］鄧志國.基于小波變換和線性判別分析的人臉識別方法［J］.華東交通大學學報，2006（5）:102－104.

［12］MALLAT S G，ZHANG Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Trans.Signal Orocessing，1993，41（12）:3397－3415.

Semi－supervised Sparse Neighborhood Preserving Discriminant Embedding Algorithm

LI Shiyin，WANG Fei，PENG Chao

（School of Information and Electrical Engineering，China University of Mining and Technology，Jiangsu Xuzhou 221116，China）

Neighborhood preserving embedding（NPE）algorithm is improved on Locally Linear Embedding（LLE）algorithm，and it overcomes the new coming sample problem，but it is not good in dealing with the classification.A semi－supervised sparse neighborhood preserving discriminant embedding algorithm is presented，the method preprocesses the data by using the wavelet transform，and then it performs Isomap algorithm to select the appropriate low－dimensional embedding dimension，and the last it reconstructs the neighborhood graph which is based on the theroy of sparse representations，NPE and linear discriminant analysis（LDA），at the same times，it makes closer between the same class points and away from each other between different class points which have been labeled，maintains the information of points which have been unlabeled.So the new algorithm has both got the high－dimensional mapping function，and it improves the classification accuracy.Experiments on face databases，comparing with other semi－supervised algorithms，the proposed algorithm performes better on the recognition rate.

NPE;sparse representation;LDA;semi－supervised

TP391

A

【本文獻信息】李世銀，王飛，彭超.一種半監督稀疏保持近鄰判別嵌入算法［J］.電視技術，2013，37（3）.

徐州市科技計劃項目（XX10A001）

責任編輯:時 雯

2012－07－15