宋昱,孫文赟,陳昌盛

(1.深圳大學(xué)電子與信息工程學(xué)院,518060,廣東深圳;2.深圳大學(xué)深圳市媒體信息內(nèi)容安全重點實驗室,518060,廣東深圳;3.深圳大學(xué)廣東省智能信號處理重點實驗室,518060,廣東深圳)

主成分分析(PCA)[1]是一種線性變換算法,在圖像處理和機器學(xué)習(xí)中有很多重要的應(yīng)用。PCA將高維數(shù)據(jù)投影至低維空間,可以有效地表示高維數(shù)據(jù)。然而,PCA也有一些缺點。因為PCA采用l2范數(shù)的平方衡量原樣本與重構(gòu)樣本的誤差,所以當數(shù)據(jù)中有些樣本明顯遠離其他樣本,即數(shù)據(jù)中含有異常樣本時,這些異常樣本會對PCA的目標函數(shù)造成顯著的影響[2-5],從而導(dǎo)致標準PCA不能很好地處理含有異常樣本的數(shù)據(jù)。

為了減小異常樣本帶來的負面效果,研究者提出了很多魯棒PCA算法。文獻[6]和文獻[7]通過對樣本進行最大似然估計,得到了基于l1范數(shù)的PCA算法。文獻[6]采用啟發(fā)式的估計算法檢測異常樣本,文獻[7]采用凸優(yōu)化算法檢測異常樣本。文獻[8]采用非凸M估計算子作為目標函數(shù),學(xué)習(xí)得到彩色圖像的表示。盡管這些算法具有對異常樣本的魯棒性,但是有一個共同的缺點,即不具有旋轉(zhuǎn)不變性,而旋轉(zhuǎn)不變性是學(xué)習(xí)算法應(yīng)具有的一個重要性質(zhì)[9]。為了保留標準PCA算法的旋轉(zhuǎn)不變性,研究者提出了一些魯棒的旋轉(zhuǎn)不變PCA算法[3-4,10-13]。文獻[10]提出了PCA-L1,采用貪婪算法最大化投影后樣本的l1范數(shù)。文獻[11]提出了一種非貪婪算法,以此求解PCA-L1的目標函數(shù),可以同時求解所有的投影方向。為了擴展PCA-L1算法,文獻[12]提出了PCA-Lp算法,該算法最大化投影后樣本的lp范數(shù)。PCA-L1或者PCA-Lp并沒有最小化重構(gòu)誤差,而是最大化投影后樣本的l1或者lp范數(shù),其目標函數(shù)與標準PCA的目標函數(shù)有本質(zhì)不同。文獻[3]和文獻[4]提出了R1-PCA,其目標函數(shù)中使用了2種范數(shù),在樣本空間維度上使用了l2范數(shù),在樣本間使用了l1范數(shù)。文獻[13]提出了Φ-PCA,其目標函數(shù)是一個二階可導(dǎo)的凸函數(shù),可以采用牛頓迭代法求解。然而,R1-PCA和Φ-PCA假設(shè)數(shù)據(jù)是均值的,該假設(shè)在實際中有一定的限制[14]。為了估計樣本均值,文獻[15]提出了基于最大相關(guān)熵的PCA。為了進一步擴展R1-PCA,文獻[16]提出了基于l2,p范數(shù)的PCA。該算法采用l2,p范數(shù)衡量原樣本與重構(gòu)樣本的誤差,當p=1時,該算法與R1-PCA算法等價。

盡管研究者已經(jīng)提出了眾多的魯棒PCA算法,但是這些算法在處理含有異常樣本的數(shù)據(jù)時依然有一些不足。以基于l2,p范數(shù)的PCA算法為例,不能在理論上保證該算法的目標函數(shù)值小于標準PCA算法的,從而其處理異常樣本的性能不能得到保證。為了改進現(xiàn)有的魯棒PCA算法,本文提出了一種基于對數(shù)變換的魯棒PCA算法,可以在理論上證明所提算法的目標函數(shù)值小于標準PCA算法的,從而提高現(xiàn)有魯棒PCA算法處理含有異常樣本數(shù)據(jù)的能力。所提算法保留了標準PCA算法的性質(zhì),即具有旋轉(zhuǎn)不變性,且投影矩陣與數(shù)據(jù)協(xié)方差矩陣相關(guān)。實際數(shù)據(jù)集上的實驗結(jié)果證明了所提算法的有效性。

1 標準PCA算法和魯棒PCA算法

(1)

式中Ik是k×k的單位矩陣。通過代數(shù)運算,可以得出目標函數(shù)式(1)等價于

(2)

從目標函數(shù)式(1)可以看出,PCA在平方的意義上最小化重構(gòu)誤差,使得目標函數(shù)對于異常樣本非常敏感[3-5]。異常樣本重構(gòu)誤差的平方非常大,對于目標函數(shù)有顯著影響,會影響得到的投影矩陣。為此,研究者提出了很多魯棒PCA算法,例如基于l1范數(shù)的PCA算法[11-12],該算法的目標函數(shù)為

(3)

基于l1范數(shù)的PCA算法通過求解目標函數(shù)式(3)得到投影矩陣。目標函數(shù)式(3)的解與協(xié)方差矩陣的關(guān)系并不清楚,而且因為‖xi-WWTxi‖1+‖WTxi‖1≠‖xi‖1,目標函數(shù)式(3)并沒有最小化重構(gòu)誤差。PCA算法的目標函數(shù)最小化了重構(gòu)誤差,這說明目標函數(shù)式(3)與PCA算法的目標函數(shù)有本質(zhì)不同。目標函數(shù)式(3)的解不等價于

(4)

目標函數(shù)式(4)直接考慮了數(shù)據(jù)的重構(gòu)誤差,并且對異常樣本具有一定的魯棒性。然而,目標函數(shù)式(4)不容易求解,其求解算法的計算量很大[3],而且目標函數(shù)式(4)不具有旋轉(zhuǎn)不變性。為了改進基于l1范數(shù)的PCA算法,文獻[16]中提出了基于l2,p范數(shù)的PCA算法,其目標函數(shù)為

(5)

式中0

2 對數(shù)變換的PCA算法

2.1 目標函數(shù)建立

為了從理論上保證所提算法的目標函數(shù)值小于目標函數(shù)式(1)的,采用對數(shù)形式。當x≥0時,有

x≥ln(x+1)

(6)

(7)

進一步得到

(8)

這樣就從理論上保證了重構(gòu)誤差的減小,而不等式(8)的右側(cè)即為本文采用的目標函數(shù),即

(9)

2.2 目標函數(shù)求解

通過代數(shù)運算,可以得到

(10)

(11)

(12)

式中D是一個對角矩陣,其對角線上的元素是di。根據(jù)矩陣理論,目標函數(shù)式(12)中W*的列向量應(yīng)是對應(yīng)于矩陣XDXT最大的k個特征值的特征向量。求解出矩陣W后,再更新di。重復(fù)上述迭代過程直至收斂,收斂條件為

(13)

式中:Ot和Ot-1分別表示在第t次和第t+1次目標函數(shù)式(9)的取值;ε是一個小的常數(shù),取為10-3。

求解目標函數(shù)式(9)的優(yōu)化算法為對數(shù)變換的PCA,即算法1,偽代碼如下。

輸入:X=[x1,…,xN]∈Rd×N,k

while 不收斂 do

1.計算對角矩陣D,其對角線上的元素為

2.計算加權(quán)協(xié)方差矩陣XDXT

4.t=t+1

end while

輸出:Wt∈Rd×k

2.3 收斂性分析

定理1在算法1的每一次迭代中,有

(14)

證明根據(jù)算法1,在第t+1次迭代時,有

(15)

(16)

(17)

(18)

(19)

(20)

對數(shù)函數(shù)ln(·)是凹函數(shù),滿足式(20),即

(21)

(22)

結(jié)合不等式(19),可以得到不等式(22)的右側(cè)小于0,所以可得

(23)

定理2算法1近似收斂于目標函數(shù)式(9)的最優(yōu)解處。

證明目標函數(shù)式(9)是約束優(yōu)化問題。采用拉格朗日乘子法,將其轉(zhuǎn)換為非約束優(yōu)化問題。目標函數(shù)式(9)對應(yīng)的拉格朗日函數(shù)為

tr(ΛT(WTW-I))

(24)

式中Λ是拉格朗日乘子。為了滿足約束條件WTW=Ik,Λ應(yīng)設(shè)為對角矩陣。根據(jù)KKT條件,在最優(yōu)解處有dL=0。對式(24)取微分,可得

tr(WΛT(dW)T)

(25)

為了使得dL=0,應(yīng)滿足

(26)

目標函數(shù)式(12)的最優(yōu)解在算法1的第3步得到,所以算法1收斂時的解滿足目標函數(shù)式(12)的KKT條件。目標函數(shù)式(12)的拉格朗日函數(shù)為

(27)

對L2取微分,并令其微分為0,可得

(28)

2.4 旋轉(zhuǎn)不變性分析

旋轉(zhuǎn)不變性意味著投影結(jié)果,即高維數(shù)據(jù)的低維表示,在樣本空間經(jīng)過旋轉(zhuǎn)后保持不變。

定理3算法1的解具有旋轉(zhuǎn)不變性。

證明任意給定一個旋轉(zhuǎn)矩陣Γ(ΓTΓ=I),投影矩陣W和樣本xi的旋轉(zhuǎn)變換表示為

(29)

因為ΓTΓ=I,從而可得

(30)

將式(29)和式(30)進行結(jié)合,算法1的目標函數(shù)可以表示為

(31)

(32)

樣本xi的低維表示在旋轉(zhuǎn)變換下并不改變。證畢。

圖1 重構(gòu)誤差與目標函數(shù)值的關(guān)系

與現(xiàn)有的PCA-L1算法相比,所提的基于對數(shù)變換的PCA算法最小化重構(gòu)誤差,與PCA算法的目標一致。與目標函數(shù)式(4)對應(yīng)的算法相比,所提算法保留了PCA算法的旋轉(zhuǎn)不變性。與基于l2,p范數(shù)的PCA算法相比,在理論上所提算法的目標函數(shù)值小于PCA算法的,避免了l2,p范數(shù)放大較小重構(gòu)誤差的缺點。所提算法具有良好的收斂性。

3 實驗結(jié)果與分析

為了驗證所提算法的有效性,在AR、Extended Yale B和CMU PIE共3個人臉數(shù)據(jù)集及MNIST共1個手寫字符數(shù)據(jù)集上進行了實驗,和標準PCA算法[1]、貪婪求解的基于l1范數(shù)的PCA算法[10](記為貪婪PCA-L1算法)、非貪婪求解的基于l1范數(shù)的PCA算法[11](記為非貪婪PCA-L1算法)、基于最大相關(guān)熵的PCA算法[15](記為HQPCA算法)以及基于l2,p范數(shù)的PCA算法[16](記為PCA-l2,p)進行了比較。設(shè)置PCA-l2,p算法的p=1。使用最近鄰算法對降維后的數(shù)據(jù)進行分類,近鄰數(shù)取為1。投影向量數(shù)k從10取到200。重構(gòu)誤差為

(33)

3.1 在AR數(shù)據(jù)集上的實驗

AR數(shù)據(jù)集[17]包含126人的超過4 000幅彩色正面人臉圖像,實驗中轉(zhuǎn)為灰度圖像。實驗選擇其中119人(65名男性和54名女性)的3 094幅圖像作為數(shù)據(jù)集。這些圖像在2個時段拍攝(相隔2周)。每個時段包含13幅圖像,6幅圖像有眼鏡或圍巾遮擋,7幅圖像有不同表情和光照。從每幅圖像中選出人臉區(qū)域,并將圖像大小調(diào)整為50×40像素[18]。圖2是AR數(shù)據(jù)集中的某人圖像,圖像a～m來自第1個時段,圖像n～z來自第2個時段。

abcdefghijklm

在AR數(shù)據(jù)集上,進行3組實驗,實驗1是眼鏡遮擋實驗,實驗2是圍巾遮擋實驗,實驗3是眼鏡和圍巾遮擋實驗。在實驗1中,選擇每人10幅圖像,即圖像a～j作為訓(xùn)練樣本,圖像n～w作為測試樣本,其中被眼鏡遮擋的圖像是異常樣本。在實驗2中,選擇每人10幅圖像,即圖像a～g和k～m作為訓(xùn)練樣本,圖像n～t和x～z作為測試樣本,其中被圍巾遮擋的圖像是異常樣本。在實驗3中,選擇每人13幅圖像,包括第1個時段的13幅圖像a～m作為訓(xùn)練樣本,其他圖像作為測試樣本,被眼鏡或者圍巾遮擋的圖像是異常樣本。

圖3是AR數(shù)據(jù)集上的平均重構(gòu)誤差和最高識別率。從圖3a可以看出:在實驗1和2中,所提算法的重構(gòu)誤差與PCA-l2,p算法的接近,2種算法的重構(gòu)誤差小于其他4種算法的;在實驗3中,所提算法的重構(gòu)誤差最小,優(yōu)于其他算法的;在所有實驗中,HQPCA算法的重構(gòu)誤差明顯高于其他算法的。從圖3b可以看出,所提算法和HQPCA算法以及PCA-l2,p算法的識別率接近,高于其他3種算法的。

(a)平均重構(gòu)誤差

(b)最高識別率圖3 AR數(shù)據(jù)集上的平均重構(gòu)誤差和最高識別率

圖4是AR數(shù)據(jù)集上的性能比較。從圖4a可以看出,當投影向量數(shù)在100～180時,各算法取得最高的識別率,由此表明投影向量數(shù)在100～180變化時,對各算法有重要影響。從圖4b中可以看出,當投影向量數(shù)在100～180時:所提算法取得了最小重構(gòu)誤差;PCA-l2,p算法取得了較小的重構(gòu)誤差;HQPCA算法的重構(gòu)誤差較大。對于AR數(shù)據(jù)集上的3類實驗,在第1、2類實驗中分別加入了被眼鏡遮擋的樣本和被圍巾遮擋的樣本作為異常樣本,異常樣本數(shù)量占的比例較小。實驗1和實驗2不能充分體現(xiàn)魯棒PCA算法處理含有異常樣本數(shù)據(jù)集的優(yōu)越性。實驗3中加入了被眼鏡和圍巾遮擋的樣本作為異常樣本,異常樣本占比明顯高于實驗1和實驗2的。實驗3上的結(jié)果更能體現(xiàn)魯棒PCA算法的優(yōu)越性。綜合可知,所提算法在實驗3上取得了最小的重構(gòu)誤差,且取得了較高的識別率。

(a)取得最高識別率時對應(yīng)的投影向量數(shù)

(b)實驗3的重構(gòu)誤差圖4 AR數(shù)據(jù)集上的性能比較

3.2 在Extended Yale B數(shù)據(jù)集上的實驗

Extended Yale B數(shù)據(jù)集[19]包含了來自38人的2 144幅在不同光照下的圖像。在該實驗中,將人臉圖像的大小調(diào)整為32×32像素[18]。從每個人的圖像中隨機選取14幅圖像,然后隨機選取圖像的一部分,將這部分替換為含有椒鹽噪聲的圖像塊。該圖像塊只包含像素值為0和255的點,大小取為12×12像素。圖5是Extended Yale B數(shù)據(jù)集中的部分正常圖像和含噪圖像。對于每一個人,隨機選取25幅正常圖像和7幅含噪圖像作為訓(xùn)練樣本,該人的其他圖像作為測試樣本。實驗重復(fù)10次。

(a)正常圖像

(b)含噪圖像圖5 Extended Yale B數(shù)據(jù)集中的部分圖像

表1是Extended Yale B數(shù)據(jù)集上各算法的最低平均重構(gòu)誤差和對應(yīng)的識別率,表中以“量值±標準差”的形式表示。

表1 Extended Yale B數(shù)據(jù)集上各算法的最低平均誤差和對應(yīng)的識別率

圖6是Extended Yale B數(shù)據(jù)集上各算法的性能比較。從圖6和表1中可以看出:所提算法在數(shù)據(jù)重構(gòu)和分類上的性能明顯優(yōu)于其他5種算法的,性能僅次于所提算法的是HQPCA算法,再次是PCA-l2,p算法;HQPCA在投影向量數(shù)從190變?yōu)?00時,重構(gòu)誤差下降,而其他5種算法依然保持上升;PCA算法性能不佳,這是因為數(shù)據(jù)集中含有異常樣本,而異常樣本對PCA算法的重構(gòu)誤差有較大影響;貪婪和非貪婪PCA-L1算法由于沒有直接最小化重構(gòu)誤差,而是最大化投影后向量的l1范數(shù),所以性能也不佳;所提算法優(yōu)于PCA-l2,p算法,這是因為所提算法沒有放大小的重構(gòu)誤差,對于大的重構(gòu)誤差也有更大的抑制,所以所提算法取得了最優(yōu)的性能。在Extended Yale B數(shù)據(jù)集上實驗結(jié)果與理論分析一致,且與AR數(shù)據(jù)集上的實驗結(jié)果一致。

(a)重構(gòu)誤差和投影向量數(shù)的關(guān)系

(b)識別率和投影向量數(shù)的關(guān)系圖6 Extended Yale B數(shù)據(jù)集上各算法的性能比較

3.3 在CMU PIE數(shù)據(jù)集上的實驗

CMU PIE數(shù)據(jù)集[20]包含了來自68人的2 856幅正面人臉圖像。每人含有42幅在不同光照條件下拍攝的圖像。在該實驗中,將每幅圖像的大小調(diào)整為32×32像素[18],并且加入了類似于在Extended Yale B數(shù)據(jù)集的實驗中加入的噪聲。從每人的圖像中隨機選擇10幅圖像加入噪聲。圖7是部分CMU PIE數(shù)據(jù)集上的人臉圖像和含噪圖像。隨機選取每個人的21幅圖像(16幅正常圖像和5幅含噪圖像)作為訓(xùn)練樣本,其他圖像作為測試樣本。實驗重復(fù)10次。

(a)正常圖像

(b)含噪圖像圖7 CMU PIE數(shù)據(jù)集中的部分圖像

表2是CMU PIE數(shù)據(jù)集上各算法的平均最小重構(gòu)誤差和對應(yīng)的識別率。

表2 CMU PIE數(shù)據(jù)集上各算法的平均最小重構(gòu)誤差和對應(yīng)的識別率

圖8是CMU PIE數(shù)據(jù)集上各算法的性能比較。從表2和圖8可以看出:所提算法取得了最優(yōu)的性能,性能僅次于所提算法的是HQPCA算法;對于HQPCA算法,當投影向量數(shù)較小時,其性能與所提算法接近,隨著投影向量數(shù)的增加,其性能達到最優(yōu)后開始變差,而所提算法的性能隨著投影向量數(shù)的增加一直增加,并且優(yōu)于HQPCA算法的最優(yōu)性能。在CMU PIE數(shù)據(jù)集上的實驗結(jié)果與理論分析一致,并且與在AR數(shù)據(jù)集和Extended Yale B數(shù)據(jù)集上的實驗結(jié)果一致。

(a)重構(gòu)誤差和投影向量數(shù)的關(guān)系

(b)識別率和投影向量數(shù)量的關(guān)系圖8 CMU PIE數(shù)據(jù)集上各算法的性能比較

3.4 在MNIST數(shù)據(jù)集上的實驗

MNIST數(shù)據(jù)集[21]共包含了70 000幅手寫數(shù)字圖像,其中訓(xùn)練集有60 000幅圖像,測試集有10 000幅圖像。每幅圖像的大小是28×28像素,手寫數(shù)字位于圖像中間。在本實驗中,從測試集中選取5 000幅圖像,每個字符(即0～9)包含500幅圖像。從每個字符的圖像中隨機選取120幅圖像,然后隨機選取圖像的一部分,將這部分替換為含有椒鹽噪聲的圖像塊,圖像塊的大小取為10×10像素。對于每一個字符,隨機選取190幅正常圖像和60幅含噪圖像作為訓(xùn)練樣本,該字符的其他圖像為測試樣本。實驗重復(fù)10次。表3是MNIST數(shù)據(jù)集上各算法的平均最小重構(gòu)誤差和對應(yīng)的識別率。

表3 MNIST數(shù)據(jù)集上各算法的平均最小重構(gòu)誤差和對應(yīng)的識別率

圖9是MNIST數(shù)據(jù)集上是各算法的性能比較。從表4和圖9a可以看出:所提算法取得了最小的重構(gòu)誤差,HQPCA算法和PCA-l2,p算法也取得了較好的性能,它們的性能都優(yōu)于其他3類算法的;當投影向量數(shù)較小時,HQPCA算法的重構(gòu)誤差略小于所提算法的,而當投影向量數(shù)量增大時,所提算法的性能逐漸優(yōu)于HQPCA算法的。從圖9b可以看出:各算法的識別率非常接近,最高的識別率(PCA)與最低的識別率(HQPCA)之間的差距為0.16%,基本可以忽略;當投影向量數(shù)較少時,所提算法取得了最高的識別率。綜上可知,所提算法的特征提取性能優(yōu)于其他對比算法的。

(a)重構(gòu)誤差和投影向量數(shù)的關(guān)系

(b)識別率和投影向量數(shù)的關(guān)系圖9 MNIST數(shù)據(jù)集上各算法的性能比較

3.5 收斂性實驗

AR數(shù)據(jù)集上實驗3的目標函數(shù)值與迭代次數(shù)的關(guān)系曲線如圖10所示,投影向量數(shù)k=10。可以看出,所提算法的目標函數(shù)值迅速減小至收斂,大概在第5次迭代時即可達到收斂。圖10的結(jié)果與2.3小節(jié)中對于算法收斂性的理論分析一致,所提算法可以得到目標函數(shù)的最優(yōu)解。

圖10 所提算法目標函數(shù)值與迭代次數(shù)的關(guān)系曲線

4 結(jié) 論

本文提出了一種魯棒PCA算法——基于對數(shù)變換的PCA算法。從對數(shù)變換的性質(zhì)出發(fā),導(dǎo)出了所提算法使用的目標函數(shù)。所提算法的目標函數(shù)值和標準PCA算法的呈對數(shù)變換關(guān)系,從理論上保證了所提算法的目標函數(shù)值小于標準PCA算法的。因為對標準PCA算法的目標函數(shù)采用了對數(shù)變換,大幅降低了異常樣本對于目標函數(shù)值的影響,從而保證了所提算法的魯棒性。理論分析表明,所提算法的每次迭代可以近似降低目標函數(shù)值,并且可以近似收斂于目標函數(shù)的最優(yōu)解。

人臉數(shù)據(jù)集和手寫字符數(shù)據(jù)集上的實驗充分表明了所提算法的優(yōu)越性。與現(xiàn)有的魯棒PCA算法相比,所提算法對于異常樣本的魯棒性和處理能力有較大提升,取得了最低的重構(gòu)誤差并且取得了最高的識別率。與PCA-l2,p算法相比,所提算法的目標函數(shù)能夠降低較小的重構(gòu)誤差,同時對于較大的重構(gòu)誤差有更強的抑制。與PCA-L1算法相比,所提算法保留了PCA算法具有的旋轉(zhuǎn)不變性。實驗分析表明,所提算法的收斂性能較好,一般迭代數(shù)次即可收斂,與理論分析一致。

未來可將對數(shù)變換應(yīng)用于稀疏PCA算法,從而得到能更好地處理含有異常樣本的稀疏PCA算法。