基于核稀疏保持投影的典型相關(guān)分析算法*

張 榮 孫權(quán)森

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京，210094)

基于核稀疏保持投影的典型相關(guān)分析算法*

張 榮 孫權(quán)森

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京，210094)

模式識(shí)別的技術(shù)核心就是特征提取，而特征融合則是對特征提取方法的強(qiáng)力補(bǔ)充，對于提高特征的識(shí)別效率具有重要作用。本文基于稀疏表示方法，將稀疏表示方法用到高維度空間，并利用核方法在高維度空間進(jìn)行稀疏表示，用其計(jì)算核稀疏表示系數(shù)，同時(shí)研究了核稀疏保持投影算法(Kernel sparsity preserve projection,KSPP)。將KSPP引入到典型相關(guān)分析算法(Canonical correlation analysis,CCA)，研究了基于核稀疏保持投影的典型相關(guān)分析算法(Kernel sparsity preserve canonical correlation analysis,K-SPCCA)。在多特征手寫體數(shù)據(jù)庫和人臉圖像數(shù)據(jù)庫上分別證實(shí)了本文提出方法的可靠性和有效性。

特征提取;核稀疏表示;核稀疏保持投影;典型相關(guān)分析

引 言

隨著壓縮感知理論的迅速發(fā)展，在20世紀(jì)90年代，稀疏表示理論應(yīng)運(yùn)而生，稀疏表示理論就是從原始的高維樣本數(shù)據(jù)中提取低維空間的特征，使得這個(gè)投影滿足稀疏性，使得這個(gè)表示系數(shù)的非0個(gè)數(shù)最少。通常使用過完備字典[1]的設(shè)計(jì)來求解稀疏表示系數(shù)，其原理是：字典中的所有元素選取全部的原始高維樣本數(shù)據(jù)，然后在字典中盡量選擇最少的基本元素來表示原始高維的樣本數(shù)據(jù)，從而使這個(gè)表示系數(shù)里不是0的個(gè)數(shù)越少越好。Qiao[2]等提出了一種基于稀疏表示的特征提取的方法——稀疏保持投影(Sparsity preserve projection,SPP)，而最近侯書東等[3,4]受稀疏算法的啟發(fā)，將SPP引入到典型相關(guān)分析(Canonical correlation analysis,CCA)中，提出了基于稀疏保持的典型相關(guān)分析(Sparsity preserve canonical correlation analysis， SPCCA)，這種算法不僅約束了樣本之間的稀疏重構(gòu)性，同時(shí)實(shí)現(xiàn)了兩組不同特征之間的特征融合，從而增強(qiáng)了該特征提取方法的識(shí)別率。Sun通過原始樣本數(shù)據(jù)提取兩種不同的特征，以這兩組不同的特征作為典型相關(guān)分析的兩組輸入數(shù)據(jù)，在CCA準(zhǔn)則下最大化這兩組特征的相關(guān)性，得到兩組投影矢量，通過不同的策略，融合這兩組投影矢量，對原始樣本數(shù)據(jù)進(jìn)行新特征提取工作，用于樣本數(shù)據(jù)的分類。CCA是一種線性的特征提取模型，其計(jì)算能力有限。一般而言，現(xiàn)實(shí)世界中很多復(fù)雜的應(yīng)用問題，比如Shen[5]等提出了正交化CCA，還有核的CCA[6]都是比線性函數(shù)更富有表達(dá)能力的假設(shè)空間。核方法的原理是：通過某種未知的非線性映射關(guān)系，將原始樣本數(shù)據(jù)映射到高維特征空間或者無窮維的特征空間，然后在新的空間中進(jìn)行線性形式的操作。盡管通過這種非線性的映射，存在以下問題：非線性映射函數(shù)形式的不確定和函數(shù)的某些參數(shù)不確定等，但是這些問題都可以通過核函數(shù)技術(shù)的內(nèi)積運(yùn)算加以解決。20世紀(jì)90年代以來，隨著核方法在支持向量機(jī)(SVM)[7,8]中的成功應(yīng)用，一大批核化的算法相繼被提出，核技術(shù)在模式識(shí)別領(lǐng)域得到了很大擴(kuò)展和成功運(yùn)用，主要包括兩方面：新方法主要用于支持向量機(jī)中，但是這里使得SVM結(jié)構(gòu)風(fēng)險(xiǎn)最小；傳統(tǒng)方法改造提出了很多有效地穩(wěn)定的算法，主要包括核主元分析(Kernel PCA，KPCA)[9]、核主元回歸(Kernel PCR，KPCR)、核部分最小二乘法(Kernel PLS，KPLS)、核Fisher判別分析(Kernel fisher discriminator，KFD)[10,11]以及核獨(dú)立主元分析(Kernel independent component analysis，KICA)，這些不同的方法在模式識(shí)別中都取得了不錯(cuò)的、甚至意想不到的結(jié)果。這些核方法在處理非線性問題時(shí)都獲得了成功。根據(jù)Cover T的模式可分性定理，當(dāng)模式分類問題映射到高維空間時(shí)，會(huì)比在低維度空間更加容易可識(shí)別或者說可分[12]。受該定理的啟發(fā)，本文運(yùn)用核方法(所謂“核技巧”[8,13]，就是在算法中出現(xiàn)樣本內(nèi)積時(shí)進(jìn)行核函數(shù)代入)，將線性的SPCCA推廣到高維特征空間，提出了核化的SPCCA(Kernelized SPCCA，KSPCCA)。最后利用優(yōu)化策略將它們引入CCA理論。

1 核稀疏保持投影的典型相關(guān)分析

1.1 稀疏表示理論[14]

(1)

(2)

所以如果測試樣本的類別不知道，就通過所有的原始樣本數(shù)據(jù)的線性組合，表示測試樣本y，即

(3)

圖1 稀疏表示的求解示意圖Fig.1 Schematic diagram of solving sparse representation

當(dāng)式(3)中字典X的基本元素較多時(shí)，即原始樣本數(shù)據(jù)很多，系數(shù)向量α就會(huì)只包含很少數(shù)的有用的系數(shù)，其他的大部分系數(shù)都為0，因而稀疏表示的最后就是要求出解稀疏系數(shù)向量α，滿足式(3)的解中選擇α最稀疏的解，也就是求解式(4)的約束條件的最小化問題，這里采用L1范數(shù)來加以限制

(4)

式(4)可以變?yōu)橄旅娴恼齽t化表現(xiàn)形式

(5)

圖1給出了只有兩組特征變量情況下在L1范數(shù)和L2范數(shù)限制下的優(yōu)化問題求解圖示，圖1中正方形虛線表示L1范數(shù)的優(yōu)化，圓形實(shí)線表示L2范數(shù)的優(yōu)化，從圖中可以很容易地看出，只有范數(shù)才能達(dá)到稀疏的目的。

1.2 稀疏保持投影算法

SPP算法較好地保持了全局樣本間的稀疏重構(gòu)性。文獻(xiàn)[4]中給出了SPP算法的優(yōu)化目標(biāo)函數(shù)，通過數(shù)學(xué)推導(dǎo)可得到廣義本征方程。

(6)

(7)

(8)

通過數(shù)學(xué)推導(dǎo)，可以將式(8)化簡為

其中ei表示第i個(gè)元素為1，其他均為0的列向量。在求解過程中為了避免出現(xiàn)退化的解，給定約束條件，wTXXTw=1，因此，最終SPP的廣義本征方程為

(9)

求解式(9)，取得d個(gè)最大特征值所對應(yīng)的投影向量wi(i=1,…,d)，即為所求的投影。

由于矩陣XXT一般都不可逆，因而式(9)一般不能直接求解，即常說的小樣本問題。為了解決小樣本問題，就要求在特征提取前對原始樣本數(shù)據(jù)進(jìn)行PCA操作，降低原始樣本數(shù)據(jù)的特征維數(shù)，從而避免XXT奇異。

1.3 核稀疏保持投影

通過核方法將原始的樣本數(shù)據(jù)映射到高維特征空間，改變了原始樣本的分布情況，從而將原始樣本數(shù)據(jù)中的非線性問題轉(zhuǎn)化為線性問題。因此，在高維特征空間中，針對新分布的樣本情況進(jìn)行稀疏表示的工作，就可以得到高維特征空間的核稀疏表示系數(shù)；利用得到的核稀疏表示系數(shù)，構(gòu)造高維特征空間中樣本數(shù)據(jù)的鄰接矩陣來提取數(shù)據(jù)特征，稱為核稀疏保持投影(KSPP)。

1.3.1 核稀疏表示

(10)

由于Φ(X)和Φ(xi)均未知，所以式(10)不能直接求解。在約束條件的兩邊同時(shí)乘上Φ(X)T，即

(11)

在高維特征空間中的內(nèi)積，同樣也是通過核函數(shù)來求得，兩個(gè)樣本數(shù)據(jù)x1，x2，映射到高維特征空間后的內(nèi)積形式為：Φ(x1)TΦ(x2)=K(x1,x2)，則

(12)

并且

(13)

當(dāng)核函數(shù)K(x1,x2)給定時(shí)，Φ(X)TΦ(X)和Φ(X)TΦ(y)就可以根據(jù)式(12，13)求得，從而求解(11)的最優(yōu)化問題。

1.3.2 核稀疏保持投影

利用上一小節(jié)得到的高維特征空間中的核稀疏表示系數(shù)，建立樣本數(shù)據(jù)的鄰接矩陣，并用于特征提取工作。同樣地，通過某種未知的非線性映射φ，將原始的樣本數(shù)據(jù)xi∈Rp(i=1,…,N)映射到高維特征空間，得到映射后的樣本數(shù)據(jù)φ(xi)(i=1,…,N)。對于現(xiàn)在的高維特征空間任一個(gè)樣本數(shù)據(jù)φ(xi)(i=1,…,N)；也同樣地，在高維特征空間中用除自己以外的所有樣本數(shù)據(jù)求解自己的稀疏表示系數(shù)。其中p表示樣本的特征維數(shù)，N表示訓(xùn)練樣本數(shù)，則φ(X)=[φ(x1),…,φ(xN)]表示所有高維特征空間的樣本數(shù)據(jù)。仿照SPP理論的方法， 可以得到KSPP的優(yōu)化問題模型,即

(14)

(15)

利用核函數(shù)計(jì)算高維空間數(shù)據(jù)的內(nèi)積，可得

(16)

和

(17)

(18)

通過類似SPP的推導(dǎo)，可以得到

同樣地，給定約束條件wTΦ(X)Φ(X)Tw=1，這樣優(yōu)化準(zhǔn)則可以變成

(19)

等價(jià)于最大化準(zhǔn)則

(20)

最大化準(zhǔn)則可以轉(zhuǎn)化為求解廣義本征方程

(21)

w可以表示為

(22)

將式(22)代入式(21)，得到

(23)

式(23)等價(jià)于

(24)

從而，廣義本征方程可以化簡為

(25)

求解式(25)，取得d個(gè)最大特征值所對應(yīng)的投影向量αi(i=1,…,d)。為了歸一化KSPP的投影向量wi=Φ(X)αi(i=1,…,d)，就要使得

(26)

則

(27)

高維特征空間樣本Φ(x)，經(jīng)過KSPP投影后的第i個(gè)新特征為

(28)

綜上所述，KSPP算法可歸納為如下步驟：

(2) 求解廣義本征方程(25)對應(yīng)的前d個(gè)最大本征值所對應(yīng)的本征向量αi(i=1,…,d)。

1.4 核稀疏保持典型相關(guān)分析(KSPCCA)

典型相關(guān)分析(CCA)[6]的優(yōu)化準(zhǔn)則函數(shù)為

(29)

式中：Sxx,Syy分別表示x,y兩組隨機(jī)變量組內(nèi)的協(xié)方差矩陣，Sxy表示x,y兩組隨機(jī)變量之間協(xié)方差矩陣，則CCA可表述為如下優(yōu)化問題的解，即

(30)

(31)

則目標(biāo)函數(shù)可改為

(32)

相應(yīng)地，由CCA的約束條件可得KSPCCA的約束條件αTKx(I-RT-R+RTR)Kxα=1，βTKy(I-ST-S+STS)Kyβ=1，因此，KSPCCA的約束優(yōu)化問題可表示為

(33)

利用Lagrange乘子法，不難得到如下關(guān)于α,β的廣義本征特征值問題

(34)

因此只需利用式(34)，即可求解得α,β，之后取d個(gè)最大特征值所對應(yīng)的特征向量αi(i=1,…,d)和βi(i=1,…,d)。KSPCCA算法可歸納為如下步驟

(2) 求解廣義本征方程(34)對應(yīng)的前d個(gè)最大特征值所對應(yīng)的特征向量αi(i=1,…,d)和βi(i=1,…,d)。

(35)

2 實(shí)驗(yàn)與分析

2.1 手寫體識(shí)別實(shí)驗(yàn)

本實(shí)驗(yàn)采用多特征手寫體數(shù)據(jù)庫(Multiple feature database)，該數(shù)據(jù)庫總共包括0～910個(gè)數(shù)字手寫體，總共包括6組不同的特征，每類200個(gè)樣本，共2 000個(gè)樣本。在實(shí)驗(yàn)中，對于每種特征組合，在每類數(shù)字手寫體中隨機(jī)選取100個(gè)樣本數(shù)字作為訓(xùn)練樣本，余下的100個(gè)樣本作為測試樣本，獨(dú)立隨機(jī)10次實(shí)驗(yàn)，這樣的隨機(jī)試驗(yàn)獨(dú)立進(jìn)行10次，記錄其平均識(shí)別率。實(shí)驗(yàn)中，對于KSPCCA中的核函數(shù)，選取了高斯核K(x,y)=exp(-‖x-y‖2/t)。這里選取的數(shù)據(jù)庫的特征維數(shù)是10，從而作為高斯核的參數(shù)t，即t=10。將KSPCCA與CCA[6],SPCCA[14]等算法做對比，其結(jié)果如表1所示。

實(shí)驗(yàn)結(jié)果表明，在不同的數(shù)據(jù)組合實(shí)驗(yàn)中，共有13次組合方式的識(shí)別率KSPCCA優(yōu)于SPCCA和CCA；相反，SPCCA只有2次表現(xiàn)最優(yōu)。這說明在多數(shù)情況下，KSPCCA的識(shí)別能力優(yōu)于SPCCA和CCA，同時(shí)，也說明核方法對于線性學(xué)習(xí)器的性能具有一定的提升作用。

表2 Yale數(shù)據(jù)集上的識(shí)別率

Tab．2 Rate of recognition on data set of Yale face

識(shí)別方法識(shí)別率CCA0.7230SPCCA0.8200KSPCCA0.8390

2.2 人臉識(shí)別實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證KSPCCA的識(shí)別性能， 在Yale人臉數(shù)據(jù)庫上進(jìn)行人臉識(shí)別實(shí)驗(yàn)。Yale人臉庫數(shù)據(jù)集主要反映了人臉的表情、光照的不同，該數(shù)據(jù)庫總共包含有15個(gè)人，每個(gè)人有11幅灰度，在每人11幅圖像中選取6幅作訓(xùn)練樣本，其余5幅作測試，這樣訓(xùn)練集的樣本數(shù)為90，測試集樣本數(shù)為75。表2列出了CCA，SPCCA和KSPCCA 3種方法在Yale數(shù)據(jù)集上的識(shí)別率。從實(shí)驗(yàn)結(jié)果來看，稀疏表示的方法明顯增加了人臉識(shí)別的性能，大大提高了人臉識(shí)別率；然而核方法的加入，雖然識(shí)別率有所提高，但是沒有明顯的提升，這就說明選取核與核參數(shù)是一個(gè)值得深入探討的問題，即如何根據(jù)樣本集的復(fù)雜程度(如樣本容量、特征維數(shù)以及類別數(shù)等)并結(jié)合數(shù)據(jù)集的先驗(yàn)知識(shí)(如人臉的表情、光照等)啟發(fā)式地選取合適的核與核參數(shù)，如果采用不適當(dāng)?shù)暮朔炊鴷?huì)造成過擬合而導(dǎo)致識(shí)別率下降。

3 結(jié)束語

本文中的KSPCCA的實(shí)驗(yàn)采用的是高斯核函數(shù)，實(shí)際上也可以使用其他形式的核函數(shù)，如多項(xiàng)式核、Sigmoid核等，核與核參數(shù)的選取是數(shù)據(jù)依賴的，與樣本集的復(fù)雜度以及數(shù)據(jù)集的先驗(yàn)知識(shí)有關(guān)。盡管已經(jīng)有很多這方面的探索，然而目前核與核參數(shù)的選取仍然是一個(gè)懸而未決的問題，因此還需進(jìn)一步思考和探索。

[1] Wright J, Yang A Y, Ganesh A,et al. Robust face recognition via sparse representation[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2009,31(2),210-227.

[2] Qiao L S, Chen S C,Tan X Y.Sparsity preserving projections with application to face recognition[J]. Pattern Recognition,2010,43(1):331-341.

[3] 侯書東,孫權(quán)森.稀疏保持典型相關(guān)分析及在特征融合中的應(yīng)用[J].自動(dòng)化學(xué)報(bào),2012,38(4):659-665.

Hou Shudong,Sun Quansen. Sparsity preserving canonical correlation analysis with application in feature fusion[J].Acta Automatica Sinica,2012,38(4):659-665.

[4] 侯書東.基于相關(guān)投影分析的特征提取研究及在圖像識(shí)別中的應(yīng)用[D].南京:南京理工大學(xué),2012.

Hou Shudong.Feature extraction based on correlation projection analysis and its application to image recognition[D].Nanjing:Nanjing University of Science and Technology,2012.

[5] Shen Xiaobo, Sun Quansen, Yuan Yunhao. Orthogonal canonical correlation analysis and its application in feature fusion[M]. Information Fusion (FUSION), 2013 16th International Conference on.[S.l.]:IEEE, 2013.

[6] Melzer T, Reiter M, Bischof H. Appearance models based on kernel canonical correlation analysis[J]． Pattern Recognition, 2003,36(9):1961-1971.

[7] Mairal J, Bach F, Ponce J, et al. Discriminative learned dictionaries for local image analysis[J].Proceedings of IEEE CVPR, 2008,413(2):1-8.

[8] Mairal J, Bach F, Ponce J, et al. Supervised dictionary learning[J].Proceddings of NIPS. 2009,21:1033-1040.

[9] Scholkopf B, Smola A, Muller K-R. Nonlinear component analysis as a kernel eigenvalue problem[J]． Neural Computation, 1998,10,1299-1319.

[10]Mika S, Ratsch G, Weston J, et al. Fisher discriminant analysis with kernels[J].IEEE Neural Networks for Signal Processing Workshop． 1999,9:41-48.

[11]Baudat G, Anouar F. Generalized discriminant analysis using a kernel approach[J].Neural Computation,2000, 12(10):2385-2404.

[12]Cover T M. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition[J]. IEEE Transactions on Electronic Computers, 1965, 14:326-334.

[13]Sch?lkopf B, Smola A, Müller K-R. Nonlinear component analysis as a kernel eigenvalue problem[J].Neural Computation, 1998, 10, 1299-1319.

[14]侯彬.基于稀疏表示的典型相關(guān)分析算法研究[D].南京:南京理工大學(xué),2013.

Hou bin. Canonical correlation analysis algorithm based on sparse representation[D].Nanjing:Nanjing University of Science and Technology,2013.

Canonical Correlation Analysis Algorithm Based on Kernel Sparsity Preserve Projection

Zhang Rong, Sun Quansen

(School of Computer Science and Engineering,Nanjing University of Science & Technology, Nanjing, 210094, China)

The key of pattern recognition is feature extraction. Fusion of feature is an important complement of feature extraction, and it has been proved to be important to improve discrimination. Here, the sparse representation method is studied by introducing sparse representation into a high dimensional feature space and utilizing kernel trick to make sparse representation in the space.The kernel sparse representation coefficients with kernel sparse representation are utilized, then kernel sparsity preserve projection (KSPP) subspace. Moreover KSPP is brought into canonical correlation analysis (CCA), then kernel sparsity preserve canonical correlation analysis (KSPCCA) is studied. The proposed algorithm is reliable and validated on the multiple feature database and face database.

feature extraction; kernel sparse representation; kernel sparsity preserve projection (KSPP); canonical correlation analysis (CCA)

國家自然科學(xué)基金(61273251)資助項(xiàng)目。

2014-09-02；

2015-01-13

TP751

A

張榮(1989-)，男，碩士研究生，研究方向：圖像處理與識(shí)別，E-mail: 15850564451@126.com。

孫權(quán)森(1963-)，男，教授，研究方向：模式識(shí)別理論與應(yīng)用、遙感信息系統(tǒng)理論與應(yīng)用、圖形圖像技術(shù)與應(yīng)用、多媒體信息處理技術(shù)以及醫(yī)學(xué)影像處理與分析。