重加權稀疏主成分分析算法及其在人臉識別中的應用

李東博，黃鋁文

（西北農林科技大學信息工程學院，陜西楊凌712100）

（*通信作者電子郵箱huanglvwen@nwsuaf.edu.cn）

0 引言

隨著現(xiàn)代科學技術的不斷發(fā)展，尤其是互聯(lián)網(wǎng)技術的飛速發(fā)展，生物特征數(shù)據(jù)［1］、基因表達數(shù)據(jù)［2］、多媒體數(shù)據(jù)［3］等數(shù)據(jù)的維數(shù)越來越高，海量數(shù)據(jù)的產(chǎn)生為生活帶來了諸多便利，但是也為如何處理海量數(shù)據(jù)，挖掘其中的主要信息，尋找數(shù)據(jù)的主要特征帶來了困難［4］。主成分分析（Principal Component Analysis，PCA）算法是處理高維數(shù)據(jù)，提取其主要特征的一個重要方法，該算法通過使用特征值分解、保留原始數(shù)據(jù)最大方差的方式實現(xiàn)原始數(shù)據(jù)的維度降低，從而達到提取原始數(shù)據(jù)特征的目的［5］。但是主成分分析算法存在一個重要的問題:主成分分析算法所得到的主成分不夠稀疏，擁有較多的非零元，主成分向量可以保留原始高維數(shù)據(jù)中的主要特征，但是所提取的主成分向量通常是稠密的，即大部分分量是非零值［6］。在最優(yōu)化領域之中，Xu等［7］提出了一個重加權?1最優(yōu)化框架，此框架使用重加權方法處理?1最優(yōu)化問題，其與傳統(tǒng)?1最優(yōu)化框架相比，可以獲得更加稀疏的解，有著更好的性能效果，證明了重加權方法的有效性。

本文針對主成分分析算法所獲得的主成分不夠稀疏的問題，將重加權方法引入到主成分分析問題的解決之中，對主成分分析算法進行優(yōu)化，得到了一個新的提取高維數(shù)據(jù)特征的方法，即重加權稀疏主成分分析算法，本文提出的方法有以下幾項創(chuàng)新:

1）通過將重加權的思想引入主成分分析算法的處理之中，通過使用交替最小化算法、奇異值分解算法、最小角回歸算法等方式實現(xiàn)了對所提出方法的求解，以實現(xiàn)提取高維數(shù)據(jù)特征時可以獲取更多的稀疏解。

2）本文通過使用基于K折交叉驗證的人臉檢測實驗比較了主成分分析算法和重加權稀疏主成分分析算法性能差異，并針對手寫數(shù)字識別這一問題使用本文方法進行求解，獲得了良好的實驗效果，證明了該方法的優(yōu)異性。

1 相關工作

主成分分析是一個高效、便捷的高維數(shù)據(jù)降維算法，為得到更加稀疏的解，國內外學者都進行了廣泛的研究。Jolliffe等［8］引入了稀疏主成分分析算法，并提供了一個簡單的基于LASSO（Least Absolute Shrinkage and Selection Operator）的方法來獲得稀疏向量。Zou 等［9］在2006 年將稀疏主成分分析（Sparse Principal Component Analysis，SPCA）作為一個回歸問題并與Elastic Net 回歸模型相結合，然后對之進行了求解。然而，這兩種方法都涉及直接求解非凸問題，因此遭遇到局部最小值問題。Moghaddam等［10］采用組合方法求解SPCA問題，同時采用貪婪策略獲得稀疏解。D'Aspremont 等［11］提出了稀疏PCA 問題的半定規(guī)劃（Semi-Definite Programming，SDP）松弛，由于稀疏主成分分析是一個難以解決的非凸優(yōu)化問題，因此難以有效的求解。

Jolliffe使用LASSO算法對PCA算法進一步優(yōu)化，提出了主成分分析算法的一個優(yōu)化算法，即SCoTLASSO（Simplified Component Technique LASSO）算法，在該算法中增加?1約束來提高稀疏性。但是SCoTLASSO是非凸的，Jolliffe等［8］提出了一種簡單的投影梯度下降方法來解決這個問題，即將“?1約束”作為懲罰函數(shù)移入目標。盡管SCoTLASSO 成功找到稀疏向量，但就其解釋的方差量而言，其性能已經(jīng)被發(fā)現(xiàn)比其他方法差。

SCoTLASSO 算法還有一個缺點就是可能會陷入局部最佳狀態(tài)，這將會導致需要重新計算以獲得更適合的解決方案。為獲取更加優(yōu)異的解，Zou 等［12］首次將PCA 表示為回歸類型問題，然后可以通過適當?shù)?1懲罰來獲取稀疏解，提出了一種新的解決算法，即稀疏主成分分析（Sparse Principal Component Analysis，SPCA）算 法。SPCA 的 目 標 函 數(shù) 比SCoTLASSO 更加復雜，但其結果也更加稀疏，因此SPCA 算法被認為比SCoTLASSO 算法更加有效。在Pitprops 數(shù)據(jù)集中，SPCA 得到的最終結果比SCoTLASSO 更稀疏（總共分別為18個非零解和47 個非零解），并且在更大數(shù)據(jù)集中的方差超過了SCoTLASSO的方差（分別為75.8%和69.3%）。

SPCA 算法中存在的一個問題是其所提取的主成分對初始參數(shù)及主成分的個數(shù)敏感，且主成分之間存在線性相關關系。因此，Moghaddam 等［10］采用組合方法來處理稀疏PCA，并提出了一種新的算法GSPCA（Greedy Sparse PCA）。該算法采用貪婪策略來獲取稀疏解，貪婪策略獲得的解決方案可能不是全局最優(yōu)的，但將是局部最優(yōu)的，即對于其支持集合最優(yōu)。

D'Aspremont 等［11］提出了一個通過SDP 方法的凸松弛來獲取稀疏解，其稀疏性比SPCA 算法和SCoTLASSO 好，但是其存在一個明顯的缺點，即該算法只能解決維數(shù)小于100 的情況。從經(jīng)驗上看，該方法被認為比SPCA 表現(xiàn)更好，可以與GSPCA 相媲美。在Pitprops 數(shù)據(jù)集上，它產(chǎn)生的解決方案比SPCA 更稀疏（分別總共有12 個非零解和18 個非零解），并且其數(shù)據(jù)的變化略大于SPCA的數(shù)據(jù)變化。

SPCA算法中通常使用?2范數(shù)實現(xiàn)方差最大化，但卻很少有學者特意研究該算法的魯棒性問題。因此，Meng等［13］將傳統(tǒng)SPCA算法之中的?2范數(shù)用?1范數(shù)進行替換，對SPCA算法進行優(yōu)化處理，以期獲得更加稀疏的解。該算法從理論上證實了與傳統(tǒng)的一些稀疏主成分分析算法相比，該算法的運行速度更快，更易于實現(xiàn)并且可以實現(xiàn)局部最優(yōu)收斂的效果。通過使用人工合成數(shù)據(jù)與人臉重建實驗驗證了新算法對原始數(shù)據(jù)中存在的異常值和噪聲數(shù)據(jù)的魯棒性，從而證明了該算法的有效性。但是該算法仍存在一個較大的缺點，即該算法的解只是近似最優(yōu)解而非嚴格的最優(yōu)解，因此該算法還需要進一步完善。

2013 年，Luss 等［14］對常見的稀疏主成分分析算法進行歸納總結，按所采用優(yōu)化方法的不同將之分為五種形式:基于?1約束的PCA 優(yōu)化問題；基于?0懲罰的PCA 優(yōu)化問題；基于?1懲罰的PCA 優(yōu)化問題；基于?0懲罰近似的PCA 優(yōu)化問題；凸松弛問題。這五種形式又都可轉化為凸函數(shù)最大化問題，根據(jù)這些性質Luss 等提出了一個名為ConGradU（Conditional Gradient Union）的算法框架，該框架統(tǒng)一了各種不同的算法，并且可以使用其推導出新的算法。在具體的實驗中使用了美國國情咨文數(shù)據(jù)驗證該算法，實驗結果表明該算法可以通過數(shù)據(jù)內容來辨別出不同的總統(tǒng)并可提取出相應的關鍵詞［15］。

Papailiopoulos 等［16］在不完全-秩矩陣的稀疏主成分研究的基礎之上提出了通過低秩近似的新的稀疏主成分分析算法，即通過使用掃描協(xié)方差矩陣的低維特征子空間的方法來提取主成分。該算法首先計算原始數(shù)據(jù)矩陣的特征向量，然后在其子空間中尋找前k級具有最大解釋方差的稀疏向量。該算法的一大特點是若矩陣特征值衰減的速度越快，則算法的效果越好；若實驗中的協(xié)方差矩陣特征值根據(jù)冪律衰減，則可在多項式時間內使用近似算法實現(xiàn)任意精度的實驗結果。

Qi 等［17］通過使用?1范數(shù)與?2范數(shù)的凸組合來代替?zhèn)鹘y(tǒng)特征提取方法中的?2范數(shù)，構建了一個迭代算法框架來處理優(yōu)化問題。該算法可以成功地獲取原始數(shù)據(jù)中的不相關的主成分，并可以提取相互正交的載荷，最終可實現(xiàn)使用較為稀疏的主成分獲得高解釋方差的目標。實驗中使用Pitprops 數(shù)據(jù)集與美國國立癌癥研究所（National Cancer Institute，NCI）細胞系數(shù)據(jù)集，并與常見的SPCA 算法、SCoTLASSO 算法以及sPCA-rSVD（sparse PCA via regularized SVD）等稀疏PCA 算法的實驗效果進行了對比分析，實驗結果表明新算法的性能與其他算法相比有所提高。

2 重加權稀疏主成分分析算法

2.1 重加權?1最優(yōu)化框架

?1最優(yōu)化問題的使用最早可以追溯到1973 年［18］，其在反射地震學、信號恢復和圖像處理等領域中都有著廣泛的應用。?1最優(yōu)化問題起源于?0最優(yōu)化問題，?0最優(yōu)化問題可表述為:假設給定一個m×n矩陣A和一個非零向量b，其中m≤n，求解Ax=b的最稀疏解，其數(shù)學形式如下所示:

步驟1 首先根據(jù)式（4）所示主成分分析算法模型使用奇異值分解方法計算矩陣X的前d個主成分向量[α1，α2，…，αk]，X為原始數(shù)據(jù)所構成的矩陣，d為求解時所設置的一個常量值。

步驟2 將矩陣P初始化為步驟1 中所計算出來的主成分向量，P=[α1，α2，…，αk]。

步驟3 根據(jù)所給定的矩陣P，使用LARS-EN 算法求解式（11），得到矩陣P=[β1，β2，…，βk]。

步驟4 根據(jù)計算出的矩陣Q=[α1，α2，…，αk]，根據(jù)式（12）使用奇異值分解更新矩陣P。

步驟5 重復步驟3、4直至終止條件滿足，將最終得到的結果。

3 實驗設計與分析

3.1 人臉識別

本次實驗中使用的人臉數(shù)據(jù)集為OLR（Olivetti Research Laboratory）數(shù)據(jù)集，該數(shù)據(jù)集由劍橋大學計算機實驗室所采集，共包含40個不同的人臉，每人有10張不同的圖像，圖像大小為92×112像素，共400張圖像。數(shù)據(jù)集包含不同時間段、不同光照、不同面部表情（開/閉眼，微笑/不微笑）和不同面部細節(jié)（眼鏡/沒有眼鏡）下的人臉圖像。實驗中使用K 折交叉驗證進行實驗，將每個人的10 張圖像劃分為五組，每組數(shù)據(jù)分別做一次測試集，其余四組作為訓練集，使用所獲得的五組數(shù)據(jù)的平均值最終的結果，劃分示意圖如圖1所示。

主成分分析算法遵循最大方差理論，將方差作為衡量降維后數(shù)據(jù)蘊含原始信息量多少的指標，本文算法同樣遵循該理論，因此為測試本文所提出算法和主成分分析算法之間的性能差異，研究稀疏優(yōu)化后算法的性能變化，實驗中以識別準確率和降維后數(shù)據(jù)總方差作為觀測指標，使用控制變量法分別控制零元的個數(shù)和降維維數(shù)，以此觀測不同條件下識別準確率和方差的變化情況。

圖1 K折交叉驗證示意圖Fig. 1 K-fold cross-validation diagram

實驗中首先選取每個人物的8張照片作為匹配集，匹配集中共320張圖片，將匹配集中的圖片使用重加權稀疏主成分算法和主成分分析算法進行降維處理，并獲取數(shù)據(jù)降維之后的方差，之后選取需要識別的人臉照片，將待識別照片使用同樣的方法進行降維，最后將降維后的照片在匹配集中通過最小距離法進行匹配，從而實現(xiàn)人臉識別的目的。其中識別準確率按照測試集中所有被正確識別的圖片數(shù)目占比進行計算，實驗中分別將圖片維數(shù)控制在10，20，30，40，50，60，70，80，90和100，在每一維度下分別控制零元的個數(shù)為0，10，20，30，40，50，100，150，以此觀察對應的識別準確率和總方差，如表1和表2所示。

從表1和表2中可以觀察出，本文所采用的方法在OLR人臉數(shù)據(jù)集中取得了不錯的實驗結果，最高識別率達到了95.6%，平均識別準確率達到95.1%，同時從表2中可以看出當維數(shù)控制在100維時，使用本文方法進行降維后的數(shù)據(jù)中總方差達到了90.2%左右，說明降維后的數(shù)據(jù)中已經(jīng)包含了原始數(shù)據(jù)中的大部分信息，從而也證明了本文方法的有效性。

表1 不同維度不同零元下識別準確率 單位：%Tab. 1 Recognition accuracy under different dimensions and different zero elements unit:%

表2 不同維度不同零元下降維方差 單位：%Tab. 2 Dimensionality reduction variance under different dimensions and different zero elements unit:%

為更加清晰地觀察本文算法，即重加權稀疏主成分分析（Reweighted Sparse Principal Component Analysis，RSPCA）算法與傳統(tǒng)主成分分析（PCA）算法的差別，分別選取了10 維、20 維、50 維、100 維四個維度下，重加權稀疏主成分分析算法和傳統(tǒng)主成分分析算法在不同零元個數(shù)下的識別準確率對比，如圖2所示。

圖2 不同維數(shù)下PCA算法與RSPCA算法識別準確率對比Fig. 2 Recognition accuracy comparison of PCA algorithm and RSPCA algorithm under different dimensions

從圖2 中可以觀察到，本文所使用的方法擁有著不弱于傳統(tǒng)方法的表現(xiàn)。如圖2（a）所示，當零元個數(shù)在200以內時，本文所使用方法在獲得了更稀疏解的基礎上仍然擁有著和傳統(tǒng)方法相近的識別效果，當零元個數(shù)超過400 時，識別效果開始慢慢下降，最差的識別效果也達到近80%的識別準確率。當維數(shù)逐漸上升時，如圖2（b），2（c），2（d）所示，零元的個數(shù)達到300甚至近400時仍有著與傳統(tǒng)方法相同的識別效果，總體識別效果也更加接近于傳統(tǒng)方法所得到的結果。

從實驗中可以看出，隨著數(shù)據(jù)稀疏性的提高，原始數(shù)據(jù)信息不斷損失，數(shù)據(jù)總方差無可避免地開始逐漸降低，其識別準確率也逐漸降低，但每一維度下使用重加權稀疏主成分分析算法與傳統(tǒng)PCA相比識別準確率相差較小，說明對數(shù)據(jù)進行稀疏化處理之后，降維后數(shù)據(jù)仍保持著原始數(shù)據(jù)獨有的特征。

3.2 對比實驗

為了進一步驗證本文算法的優(yōu)異性，對3.1 節(jié)中實驗進行拓展，使用人臉識別準確率、實驗耗時與GSPCA 算法［11］、ScotLASS算法［12］和sPCA-rSVD算法［16］進行對比分析。

實驗中使用三個人臉數(shù)據(jù)集，分別為ORL 人臉數(shù)據(jù)集、AR（A.M. Martinez-R. Benavente）人臉數(shù)據(jù)集、Yale B 人臉數(shù)據(jù)集（Yale Face Database B）。AR 人臉數(shù)據(jù)集中包含120 人，每人有14張不同的面部圖像，本文選取了每個人物的前10張照片作為數(shù)據(jù)集，共計1 200 張圖片，每張圖片的大小為40×50 像素。Yale B 人臉數(shù)據(jù)集中包含38 人，每人64 張照片，實驗中選取每個人物的前10 張照片作為數(shù)據(jù)集，共計380 張照片，每張圖片大小為168×192像素。

實驗中將三個人臉數(shù)據(jù)集按照1∶1比例分別劃分為匹配集和測試集，三個數(shù)據(jù)集匹配集與測試集中圖片數(shù)量分別為200 張、600 張、190 張。實驗中分別將維數(shù)控制在10 維、30維、50 維、100 維，比較四個算法的識別準確率和實驗耗時，識別準確率按照測試集中識別正確的圖片個數(shù)占據(jù)測試集比例計算，實驗結果如表3所示。

從表3中可以觀察到三個數(shù)據(jù)集中使用RSPCA算法所獲得識別效果都要好于其他三種算法，在ORL 人臉數(shù)據(jù)集中最高識別率達到95.5%，而其余三種算法最高識別率僅為89.3%，識別準確率在原有基礎上提高了6.2 個百分點。在AR 數(shù)據(jù)集與Yale B 數(shù)據(jù)集中，人臉識別效果與其余三種算法相比有所提升。在表3 中可以觀察到RSPCA 的實驗耗時最少，在ORL 數(shù)據(jù)集中平均耗時為1.1 s，AR 數(shù)據(jù)集中平均耗時為1.45 s，Yale B 數(shù)據(jù)集中平均耗時為1.17 s，與其他三種算法相比，耗時均有所減少。

表3 三種算法識別準確率及耗時對比Tab. 3 Recognition accuracy and time consumption comparison of three algorithms

圖3 中展示了RSPCA 算法、GSPCA 算法、ScotLASS 算法和sPCA-rSVD 算法在ORL 人臉數(shù)據(jù)集、AR 人臉數(shù)據(jù)集和Yale B 人臉數(shù)據(jù)集上的平均識別準確率。從圖3 中可以清晰地觀察到RSPCA 算法在三個數(shù)據(jù)集中始終擁有著良好的識別準確率，在ORL 人臉數(shù)據(jù)集中的表現(xiàn)明顯好于其他三種算法，在AR 數(shù)據(jù)集高于其余三種算法中識別率最高的sPCArSVD算法，在Yale B數(shù)據(jù)集中與GSPCA算法相差無幾。

圖3 四種算法平均識別準確率Fig. 3 Average recognition accuracy of four algorithms

圖4 中展示了實驗中四種算法的平均耗時情況，從圖中可以發(fā)現(xiàn)RSPCA 算法耗時明顯少于其余三種算法，平均耗時僅為1.24 s，從算法效率方面來看要優(yōu)于其余三種算法。

圖4 四種算法實驗耗時Fig. 4 Average experimental time consumption of four algorithms

3.3 手寫數(shù)字識別

重加權稀疏主成分分析算法同樣可以應用于數(shù)字識別領域，數(shù)字識別在現(xiàn)實生活中有著許多重要的應用，如車牌檢測、手寫輸入等。實驗中使用重加權稀疏主成分分析算法+K近鄰算法的方式，首先對訓練集中的42 000 張圖片進行數(shù)據(jù)降維，訓練集中每張圖片大小為28×28 像素。之后輸入一張待識別圖片，使用重加權稀疏主成分分析算法進行數(shù)據(jù)降維，最后利用K近鄰算法尋找待識別圖片在特征空間中的k張最相似樣本中出現(xiàn)類別最多的類別，該類別即為待識別圖片所屬類別。實驗中使用100 張圖片作為測試集，并測試了在近鄰數(shù)目不同情況下識別準確率的變化情況，實驗中近鄰數(shù)目分布k=1，2，…，50，實驗結果如圖5所示。

圖5 不同近鄰數(shù)量對識別準確率的影響Fig.5 Influence of different neighbors on recognition accuracy

從實驗結果中可以發(fā)現(xiàn)，使用重加權稀疏主成分分析算法和K近鄰算法的數(shù)字識別準確率達到93%以上，平均識別率達96.4%，重加權主成分分析算法在數(shù)字識別實驗中獲得了良好的實驗效果。

4 結語

本文中針對主成分分析算法進行降維后獲取到的主成分稀疏性不強問題進行研究，通過使用重加權的方法對其進行稀疏處理，提出了一個新的稀疏優(yōu)化模型，即重加權稀疏主成分分析算法。文中使用數(shù)學方法對該算法進行了詳盡的理論證明，并給出了該算法的求解方法。實驗部分表明使用重加權稀疏主成分分析算法在進行人臉識別實驗中獲得了更加稀疏的結果且有著不弱于傳統(tǒng)主成分分析算法的實驗效果，數(shù)字識別實驗中重加權稀疏主成分分析算法更是有著平均識別率96.4%的良好實驗結果。本文所研究算法為解決主成分分析算法所得結果不夠稀疏的問題提供了一個新的解決方案，同時可以嘗試將此算法應用于更多的實驗場景中。