一種半監(jiān)督稀疏保持近鄰判別嵌入算法

李世銀，王 飛，彭 超

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

一種半監(jiān)督稀疏保持近鄰判別嵌入算法

李世銀，王 飛，彭 超

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

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

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

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

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

1 保持近鄰嵌入算法

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

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

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

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

式中:kn是xi的近鄰個數(shù)。

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

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

2 基于半監(jiān)督的保持近鄰判別嵌入算法

2.1 數(shù)據(jù)預(yù)處理

2.1.1 小波變換

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

2.1.2 Isomap 選擇合適的維數(shù)

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

圖1 小波分解

2.2 稀疏重構(gòu)權(quán)值

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

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

同類樣本離散度矩陣為

異類樣本離散度矩陣為

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

目標函數(shù)定義為

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

2.3 SNPDE 具體過程

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

3 實驗與分析

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

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

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

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

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

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

圖2 剩余方差和維數(shù)關(guān)系圖

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

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

圖3 實驗結(jié)果

4 小結(jié)

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

:

［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］劉志宇.一種半監(jiān)督判別鄰域嵌入算法［J］.計算機工程與應(yīng)用，2011，47（19）:173－175.

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

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

［10］劉倩，潘晨.新的局部線性嵌入下的人臉識別方法［J］.計算機工程與應(yīng)用，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

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

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

責任編輯:時 雯

2012－07－15