聯(lián)合核主成分分析

王 喆,孟 蕓

(華東理工大學(xué) 計算機科學(xué)與工程系,上海 200237)

聯(lián)合核主成分分析

王 喆,孟 蕓

(華東理工大學(xué) 計算機科學(xué)與工程系,上海 200237)

提出了KPCA的一種稱為聯(lián)合核主成分分析(Joint Kernel Principle Component Analysis,JKPCA)的變型,能夠從輸入和輸出空間引出先驗信息用于特征提取.首次將聯(lián)合核映射應(yīng)用于特征提取領(lǐng)域,而且在圖像數(shù)據(jù)集上的實驗結(jié)果表明,JKPCA是可行并有效的.

核主成分分析(KPCA); 聯(lián)合核映射; 特征提取; 核方法

特征提取是模式識別中一個重要的研究方向.一個模式識別系統(tǒng)的成敗,首先取決于所利用的特征是否較好地反映了將要研究的分類問題.對于已獲得的特征,一方面,有很多與分類問題不相關(guān),在分類器設(shè)計中會影響分類器的性能;另一方面,特征過多會帶來計算量大和推廣能力差等問題[1].因此,人們希望在保證分類效果的前提下使用盡可能少的特征,特征提取就是一種被廣泛采用的方法.

在特征提取中,主成分分析(PCA)[2-3]是一種經(jīng)典的用于從原始數(shù)據(jù)中提取緊密結(jié)構(gòu)的特征提取方法.選擇較少的主成分來表示數(shù)據(jù),不但可以用作特征的降維,還可以用來消除數(shù)據(jù)中的噪聲.但是主成分分析并不總是對分類有好處,如果相比于類別之間的差別來說噪聲很大,那么主成分分析將找到噪聲的主方向而不是人們所期望的信號的主方向[1].因此,對特征提取方法的改進是十分必要的,它直接影響到后續(xù)分類器的設(shè)計和模式識別系統(tǒng)的總體性能.

基于以上描述,本文首次將聯(lián)合核映射(JKM)應(yīng)用于特征提取領(lǐng)域,提出了一種新型的基于核的特征提取方法,稱作聯(lián)合核主成分分析(JKPCA).由于方法中采用的JKM是基于輸入和輸出空間的聯(lián)合數(shù)據(jù)表示,JKPCA相比其他方法能夠引入更多的先驗信息.實驗結(jié)果表明,JKPCA在由圖像表示的輸出數(shù)據(jù)上不僅其分類性能優(yōu)于兩個典型特征提取方法,即基于核的主成分分析(KPCA)和核Fisher判別分析(KFDA)[4],而且和對比算法相比,計算復(fù)雜度相當(dāng).

1 相關(guān)工作

主成分分析(PCA)投射原始數(shù)據(jù)至可以用特征值問題解決的主成分,即使用規(guī)模很小的主成分,也足夠表達原始數(shù)據(jù)的主要結(jié)構(gòu).PCA是一種數(shù)學(xué)變換方法,把給定的一組相關(guān)變量通過線性變換轉(zhuǎn)成另一組不相關(guān)的變量,在數(shù)學(xué)變換中保持變量的總方差不變,使具有最大方差的第一變量為第一主成分,第二變量的方差次大,并且和第一變量不相關(guān)為第二主成分,依此類推[5].因為PCA是一種線性方法,而且只能用于原始數(shù)據(jù)空間,所以Sch?lkopf等將PCA推廣到非線性形式的核主成分分析(KPCA).實驗證明,因為KPCA能夠通過選擇不同的核函數(shù)處理特征空間中的任意維度,它比PCA更有效且有更好的適應(yīng)性[6-7].核方法之所以性能優(yōu)異是因為采用了核函數(shù),核函數(shù)即在特征空間F上的內(nèi)積,它能夠?qū)⒃驾斎肟臻g的x∈F映射到特征空間,有Φ(x)∈F:

(1)

所以,k(xi,xj)=[φ(xi)·φ(xj)],其中,核函數(shù)k能夠從原始輸入空間引入先驗信息.在一些文獻中提到只有具有0-1損失函數(shù)形式的映射可以從輸入空間為輸出空間Y提供足夠的信息[8-10].但同時Y可以由很多復(fù)雜的結(jié)構(gòu)如圖像、字符串、樹或者序列等表示,只在輸入空間定義核函數(shù)k會導(dǎo)致輸出空間的信息不能得到有效利用而不能很有效地解決問題.為了能夠處理以上提到的復(fù)雜輸出,有些文獻提出新型的核映射,稱作聯(lián)合核映射(JKM)[11-14].

假設(shè)輸入空間中x∈F以及任意獨立的輸出空間y∈Y,JKM的形式如下:

(2)

式中,Ψ表示輸入和輸出空間中一些特征表示組合之間的映射.更進一步地,利用聯(lián)合特征表示的內(nèi)積,一個聯(lián)合核函數(shù)可以如下定義:

(3)

JKM已經(jīng)被證明能夠很好地處理由多個獨立變量構(gòu)成的輸出.

KPCA采用了式(1)中表示的常規(guī)核映射,因此,KPCA繼承了式(1)中在處理復(fù)雜輸出方面的缺點.為了克服這個缺點,本文將類似于式(2)中的JKM應(yīng)用到KPCA,提出了基于核的特征提取方法,稱作聯(lián)合核主成分分析(JKPCA).

2 聯(lián)合核主成分分析

2.1 特征提取

給定一組訓(xùn)練集(x1,y1),…,(xN,yN)∈X×Y,其中,輸入空間X和輸出空間Y都可以用向量、圖像或者樹型結(jié)構(gòu)來表示.通過式(2)描述的JKM,能夠映射輸入和輸出空間的聯(lián)合表示(x,y)至φ(x,y)∈F,其中,φ(x,y)是一個向量且屬于生成的聯(lián)合特征空間F.因此,在聯(lián)合特征空間F中,試圖找到一個線性變換向量ω∈F,使得投影φ(x,y)在ω有

(4)

為了找到一個較好的轉(zhuǎn)換向量ω,使投影范圍r能夠在ω方向上表示φ(x,y)的主要結(jié)構(gòu),本文引入投影樣本的總散度來衡量ω,其準則函數(shù)是:

(5)

函數(shù)(5)中提到的S表示投影樣本的協(xié)方差矩陣,其中,tr(S)是S的跡.準則函數(shù)(5)可以保證投影r能夠保持原始樣本φ(x,y)在轉(zhuǎn)換向量ω方向上的主要結(jié)構(gòu).投影樣本的協(xié)方差矩陣S可以由訓(xùn)練樣本直接計算得到:

(6)

定義樣本協(xié)方差矩陣C有如下式所示的形式:

(7)

把式(7)代入式(5)可以得到:

(8)

進一步地,最大化式(8)相當(dāng)于解決了如下特征值問題:

(9)

(10)

所以,針對所有的訓(xùn)練樣本φ(xk,yk)(k=1,…,N),式(9)能夠變換為

(11)

把式(7)和式(10)代入式(11)可以得到

(12)

定義一個聯(lián)合核矩陣K[11-12]:

(13)

則式(12)可以寫成

(14)

式中,αvec是一個列向量,αvec=[α1,…,αN]T.求解式(14)又相當(dāng)于求解如下特征值問題:

(15)

(16)

假設(shè)一組測試數(shù)據(jù)(z,y)能夠映射到聯(lián)合特征空間F的φ(z,y),按如下方式將φ(z,y)投影到第k個轉(zhuǎn)換方向ωk:

(17)

利用W=[ω1,…,ωp],則從φ(z,y)提取的特征可以表示為

(18)

2.2 分類算法

通常情況下,測試數(shù)據(jù)(z,y)中的輸出值y是未知的,但是在特征提取式(18)的過程中,對給定樣本z對應(yīng)的y的估計是十分必要的.本文通過如下式子得到z的輸出y:

(19)

式中,Y為訓(xùn)練集輸出(y1,…,yN)的集合.進一步地,假設(shè)對于(xi,yi)和(xj,yj),如果存在yi=yj,那么φ(xi,yi)和φ(xj,yj)投影之間的距離也是很小的;否則它們之間的距離會很大.另外要注意的是,在使用JKPCA投影的過程中,對于一個給定的測試樣本,它的輸出y也是可以得到的.

JKPCA的算法設(shè)計總結(jié)如下:

(1) 通過式(13)計算矩陣K;

(2) 計算式(15)的特征值;

(3) 通過式(16)正規(guī)化步驟(2)得到的特征值;

(4) 通過式(18)從測試數(shù)據(jù)(z,y)提取特征,同時,通過式(19)從z里獲取輸出y.

2.3 非集中型樣本

上節(jié)中認為訓(xùn)練樣本(x1,y1),…,(xN,yN)在聯(lián)合特征空間F中是集中的,本節(jié)討論一般情況即不集中的樣本.假設(shè)一個訓(xùn)練樣本集(x1,y1),…,(xN,yN)∈X×Y能夠用式(2)表示的JKM映射到一個聯(lián)合特征空間F,將樣本依據(jù)下式進行集中:

(20)

(21)

(22)

(23)

2.4 JKPCA、KPCA和KFDA的聯(lián)系

下面從理論上討論JKPCA、KPCA和KFDA三者之間的關(guān)系.若式(15)中的K采用常規(guī)映射(1),則很容易發(fā)現(xiàn)KPCA是JKPCA 的一個特例.對于給定的訓(xùn)練樣本,假設(shè)有l(wèi)個類別,第k類有nk個樣本,并且設(shè)定1=[1,…,1]T∈Rnk,定義如下矩陣:

這樣,KFDA面向的是如下廣義特征值問題:

(24)

代入定義的矩陣,式(24)可以轉(zhuǎn)化成

(25)

若使式(15)中的JKPCA的K為K-TD-1CK,則JKPCA就會退化成KFDA.所以不難看出,KPCA和KFDA都是JKPCA的特例.

3 實 驗

與文獻[12-13,16]的工作類似,本文中JKPCA中的聯(lián)合核定義為兩個核映射的張量積,并設(shè)定兩個核函數(shù)為同一形式以方便計算,即J((xi,yi),(xj,yj))=[φ(xi,xj)][φ(yi,yj)].根據(jù)核函數(shù)的性質(zhì)有φ(xi,xj)=φ(xi)·φ(xj),則JKM有如下形式:[φ(xi,yi)·φ(xj,yj)]=[φ(xi)·φ(xj)][φ(yi)·φ(yj)].

因此,式(13)中聯(lián)合核矩陣具有如下形式:

Kij=[φ(xi)·φ(xj)][φ(yi)·φ(yj)]=KxijKyij.

(26)

式中,Kxij=φ(xi)·φ(xj),Kyij=φ(yi)·φ(yj),并分別把線性核、RBF核和多項式核用于Kxij和Kyij.

3.1 在ORL上的實驗

ORL數(shù)據(jù)集總共是來自40個人的圖像,每個人有10張不同的姿勢和不同的表情變化且尺寸為28×23的圖像.圖1展示了ORL數(shù)據(jù)集中來自同一個人的十張圖像.針對ORL數(shù)據(jù)集的實驗設(shè)置中,使用每個人也就是每一類別中的前5張圖作訓(xùn)練,其余的作測試.KPCA和KFDA使用離散的類標號{0,1,2,…}來表示輸出空間,很明顯,這兩個算法關(guān)于輸出空間的這一設(shè)定并不能反映出輸出空間的實際結(jié)構(gòu).而相反地,JKPCA能夠在特征提取的過程中考慮到輸出空間的結(jié)構(gòu),因此它比KPCA 和KFDA 得到了更多的先驗信息.

圖1 ORL數(shù)據(jù)集示例一個人的10張圖像Fig.1 Ten images of one person on ORL data set

在本文的實驗中,所有的輸入數(shù)據(jù)xi都來自同一類別,它們有相同的輸出y.更具體地,ORL中每個人的第一張圖像用作相應(yīng)的輸出.以圖1中的人像為例,第一行的5張圖用來訓(xùn)練,第二行的用作測試.所有這10張圖有共同的輸出y,即第一行最左邊的圖,這樣做是因為通常每個圖像數(shù)據(jù)集每一類都會有1或2張標準圖像.圖2展示了KPCA,KFDA和JKPCA在ORL數(shù)據(jù)集上變化提取特征維度時的分類正確率.這里要說明的是,基于使用的核不同,共給出了JKPCA的兩種形式.圖2中,“JKPCA” 表示的是使用了相同的Kxij和Kyij,另一個“JKPCA2”則表示使用了不同的Kxij和Kyij.由圖2可以觀察到:①JKPCA2在提取特征維度從1到12變化過程中一直保持著比其他算法更高的分類正確率;②JKPCA與KPCA和KFDA相比沒有明顯的優(yōu)勢,尤其是在低維度上的分類正確率甚至低于二者,與預(yù)估不符,出現(xiàn)這種現(xiàn)象可能是由于JKPCA使用相同的Kxij和Kyij造成的.輸入空間和輸出空間在通常情況下是很不相同的,所以它們對應(yīng)的映射也不盡相同.而JKPCA2則對輸入和輸出空間使用了不同的核以與前面描述的情況一致,所以展現(xiàn)出了很好的分類性能.

圖2 KPCA,KFDA和JKPCA在ORL數(shù)據(jù)集上變化提取特征維度時的分類正確率

3.2 在Coil-20上的實驗

Coil-20是一個從哥倫比亞大學(xué)物體圖像數(shù)據(jù)庫獲取到的實體圖像數(shù)據(jù)集,它包含來自20個實體大小為32×32共1 440張圖像.環(huán)繞每個實體每5°獲取一張圖像,共得到72張.圖3展示了Coil-20中呈現(xiàn)不同形態(tài)的一個實體的圖像.針對Coil-20數(shù)據(jù)集,本文共設(shè)計了兩個實驗.第一個實驗是在相同訓(xùn)練集規(guī)模下提取不同維度的特征,

其中每個實體選取12張圖用來訓(xùn)練,其余的用作測試.第二個實驗是從不同規(guī)模的訓(xùn)練集中提取固定數(shù)目的特征,其中,每個實體用作訓(xùn)練的數(shù)量分別是{12,24,36,48,60}.圖4給出了相應(yīng)的實驗結(jié)果.由圖4可以觀察到以下兩點:①兩種情況即不同特征維度和不同訓(xùn)練集規(guī)模下,JKPCA2總是比KPCA,KFDA和JKPCA的分類正確率高;②JKPCA2和JKPCA相比于KPCA和KFDA都需要較少或至多相當(dāng)?shù)挠?xùn)練時間.實驗證明了提出的JKPCA不僅提高了分類正確率,并在一定程度上減少了分類器的訓(xùn)練時間,是一種可行的且值得推廣的算法.

圖3 Coil-20數(shù)據(jù)集示例一個實體的10張圖像Fig.3 Ten images of one object on Coil-20 data set

圖4 實驗結(jié)果Fig.4 Experimental result

3.3 在AR上的實驗

AR人臉數(shù)據(jù)集[15]包含126個人超過3 200張的正臉圖像.本文使用的是AR的一個子集,包含100個人,每個人20張圖,共計2 000張人臉圖像.每張圖像的尺寸是66×48,分別涉及時間、表情、穿著和光照變化.圖5顯示了AR數(shù)據(jù)集中一個人的20張圖像,具體的圖像細節(jié)是:第一行從左數(shù)依次為自然表情,微笑,生氣,尖叫,戴墨鏡,戴墨鏡且左側(cè)有光照,戴墨鏡且右側(cè)有光照,戴圍巾,戴圍巾且左側(cè)有光照,戴圍巾且右側(cè)有光照.第二行的圖像和第一行的情景狀況一樣,區(qū)別是獲取圖像的時間不同.

圖5 AR數(shù)據(jù)集示例一個人的20張圖像Fig.5 Twenty images of one person on AR data set

針對AR數(shù)據(jù)集,本文總共設(shè)計了三個實驗.第一個實驗針對面部表情的變化,以每個人的第一張圖像(如圖5中的(a)(k)所示)作訓(xùn)練,其余涉及面部表情的作測試(如圖5中的(b)(c)(d)(l)(m)(n)所示).第二個實驗針對不同的穿戴,以每個人的第一張圖像(如圖5中的(a)(k)所示)作訓(xùn)練,有墨鏡和圍巾的圖像(如圖5中的(e)(h)(o)(r)所示)作測試.第三個實驗針對不同的光照,以每個人的第一張圖像(如圖5中的(a)(k)所示)作訓(xùn)練,涉及光照的圖像(如圖5中的(e)(j)(o)(t)所示)作測試.對所有的實驗,選擇每個人的第一張圖像(如圖5a所示)表示輸出空間y.圖6給出了KPCA,KFDA,JKPCA和JKPCA2在變換面部表情、穿著和光照三種訓(xùn)練測試集時不同特征維度下的分類正確率.由圖6可以看出,JKPCA和JKPCA2相較于KPCA和KFDA并沒有展現(xiàn)出一個很明顯的優(yōu)勢,在高維情況下保持了與KPCA,KFDA相當(dāng)?shù)姆诸愓_率,但同時它提供了一個可以在特征提取過程中同時引入輸入和輸出空間的新概念.

圖6 KPCA,KFDA,JKPCA和JKPCA2在變換面部表情、穿著和光照三種訓(xùn)練測試集時不同特征維度下的分類正確率Fig.6 Classification accuracy of KPCA,KFDA,JKPCA and JKPCA2 with varying dimension of the extracted feature vectors on the variation of facial expressions,cover,and both cover and light

4 結(jié) 語

本文提出了一種新型的基于核的特征提取方法JKPCA,也是第一次將JKM應(yīng)用在特征提取過程中.通過與傳統(tǒng)的基于核的特征提取方法KPCA和KFDA對比,JKPCA從輸入和輸出空間引入了更多先驗信息.在圖像數(shù)據(jù)集上的實驗證明,JKPCA是一種可行有效的方法,它比KPCA和KFDA有更優(yōu)或者至少相當(dāng)?shù)姆诸愋阅?同時,計算代價也是相當(dāng)?shù)?今后應(yīng)進一步探索JKPCA在更復(fù)雜輸出空間如相互依賴的變量上的有效性.

[1] 張學(xué)工.模式識別[M].北京:清華大學(xué)出版社,2010.

(Zhang Xuegong.Pattern Recognition[M].Beijing: Tsinghua University Press,2010.)

[2] Jolliffe I T.Principal Component Analysis[M].New York: John Wiley & Sons Ltd.,2005.

[3] Kirby M,Sirovich L.Application of the Karhunen-Loeve Procedure for the Characterization of Human Faces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(1):103-108.

[4] Baudat G,Anouar F.Generalized Discriminant Analysis Using a Kernel Approach[J].Neural Computation,2000,12(10):2385-2404.

[5] 張曉飛,萬福才,劉朋.主元分析法(PCA)在圖像顏色特征提取中的應(yīng)用[J].沈陽大學(xué)學(xué)報,2006,18(5):93-95.

(Zhang Xiaofei,Wan Fucai,Liu Peng.Application of Principal Component Analysis (PCA) Color-Based Feature Extraction of Image[J].Journal of Shenyang University,2006,18(5):93-95.)

[6] Rosipal R,Girolami M.An Expectation-Maximization Approach to Nonlinear Component Analysis[J].Neural Computation,2001,13(3):505-510.

[7] Sch?lkopf B,Smola A,Müller K R.Nonlinear Component Analysis as a Kernel Eigenvalue Problem[J].Neural Computation,1998,10(5):1299-1319.

[8] Cristianini N,Shawe-Taylor J.An Introduction to Support Vector Machines and other Kernel-Based Learning Methods[M].Cambridge: Cambridge University Press,2000.

[9] Sch?lkopf B,Smola A.Learning with Kernels[J].Cambridge: The MIT Press,2002:110-146.

[10] Vapnik V.The Nature of Statistical Learning Theory[M].2nd Edition.New York: Springer-Verlag,2000.

[11] Collins M,Duffy N.Convolution Kernels for Natural Language[C]∥ Advances in Neural Information Processing Systems,2001(14):625-632.

[12] Hofmann T,Tsochantaridis I,Altun Y.Learning over Discrete Output Spaces via Joint Kernel Functions[C]∥Advances in Neural Information Processing Systems,Workshop on Kernel Methods,2002.

[13] Tsochantaridis I,Hofmann T,Joachims T,et al.Support Vector Machine Learning for Interdependent and Structured Output Spaces[C]∥Proceedings of the Twenty-first International Conference on Machine Learning.New York: ACM Press,2004:85-103.

[14] Weston J,Chapelle O,Elisseeff A,et al.Kernel Dependency Estimation[C]∥Becker S,Obermayer K.Advances in Neural Information Processing Systems.Cambridge: The MIT Press,2003:873-880.

[15] Martinez A M,Benavente R.The AR Face Database[R].Barcelona: Computer Vision Center (CVC) Technical Report 24,1998.

[16] Weston J,Sch?lkopf B,Bousquet O,et al.Joint Kernel Maps[C]∥Cabestany J,Prieto A,Sandoval D F.Computational Intelligence and Bioinspired Systems: Eighth International Work-Conference on Artificial Neural Networks,Lecture Notes in Computer Science.Berlin,Heidelberg: Springer-Verlag,2005:176-191.

【責(zé)任編輯: 李 艷】

Joint Kernel Principle Component Analysis

WangZhe,MengYun

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

A variant of KPCA called joint kernel principal component analysis (JKPCA) is proposed,which is able to obtain the prior information from both the input and output spaces for the feature extraction processing.Moreover,the joint kernel mapping is applied into feature extraction for the first time.The experimental results validate the feasibility and effectiveness of the proposed JKPCA on image datasets.

kernel principal component analysis (KPCA); joint kernel mapping; feature extraction; kernel-based method

2015-01-14

國家自然科學(xué)基金資助項目(61272198).

王 喆(1981-),男,江蘇淮安人,華東理工大學(xué)副教授,博士.

2095-5456(2015)04-0306-07

TP 181

A