基于主成分分析的自適應特征選擇算法研究

張 鑫，刁麓弘，南 東，王永利，劉 陽

?

基于主成分分析的自適應特征選擇算法研究

張 鑫，刁麓弘，南 東，王永利，劉 陽

(北京工業大學應用數理學院，北京 100124)

提出了一種自適應性的特征提取方法。首先通過主成分分析求出樣本全局投影空間，然后基于最大化投影構建優化目標函數，最后通過該函數求出自適應于個體樣本的投影空間。該方法很好地考慮了樣本集合中每個樣本的分布特點。為了使得算法可應用于識別分類問題中，給出了計算存在于不同投影空間的個體樣本間相似性的方法，相比于歐式度量，該方法被證明得到的相似性能夠更好地表征樣本間的測地距離關系，使其能夠有效地對流型結構數據進行學習。通過在不同數據庫上進行分類及重構的對比實驗，實驗結果表明，該方法能夠更好地提取數據特征，且對離群點具有魯棒性。

特征提取；主成分分析；自適應特征提取；人臉識別

隨著數據采集硬件水平的提升，越來越多的實驗數據被成功地采集。數據包含的信息更加復雜，維數同時隨之增加，對于降維方法的研究變得越來越重要，其中主成分分析(principal component analysis，PCA)作為一種線性降維算法，被成功地應用到了模式識別中的許多領域[1-6]。

PCA方法以投影后數據均方誤差最小作為目標函數，通過構造一個低維投影空間進行降維。傳統PCA的目標函數是基于L2范數的[7]。其對于樣本中的噪聲與異常點較為敏感，因此近年來更多的研究者著手于提升PCA魯棒性的算法研究。因為L1范數對于噪聲與異常點的不敏感，基于L1范數的PCA算法相繼被提出。其中，BACCINI等[8]利用極大似然估計，提出了一種啟發式Gini-PCA近似估計L1范數下的主成分，KE和KANADE[9]提出了一種利用交錯迭代方法求解L1范數下低維空間的算法，雖然該算法提升了對異常點魯棒性，但計算量極大，且不具有旋轉不變性。KWAK[10]以基于L1范數下最大化方差為目標函數，提出了一種兼具魯棒性與旋轉不變性的PCA-L1算法，并且利用快速貪婪算法逐步計算主成分，實驗結果表明該算法能夠很好地應用于人臉識別、人臉重建等模式識別中。除了采用L1范數作為目標函數外，DING等[11]定義了另一種新的R1范數，將傳統PCA中的L2范數替換為R1進行求解，實驗證明該算法能夠很好地處理異常點，缺點仍為計算量過大。為了解決計算量的問題，研究者們提出了一些近似算法[12-13]，其中文獻[10]算法在計算效率和性能上都取得了很好的結果。CANDES等[14]提出了RPCA算法，引入稀疏噪聲矩陣，通過構造噪聲矩陣與低秩矩陣的目標函數，從而恢復低秩矩陣實現了降維，并且對于噪聲具有很好的魯棒性。SHAHID等[15]對RPCA進行改進，加入了平滑度正則化，在保證對異常點魯棒性前提下，在聚類以及低秩矩陣恢復應用上取得了很好的效果。

為了能使得PCA算法更加適應樣本數據，一些自適應特征提取算法也被相繼提出。WANG和WU[16]提出了一種基于L2范數的WPCA算法，通過向投影空間添加權重，使得投影后的數據協方差為單位陣。TAN和CHEN[17]提出了一種用于人臉識別的自適應加權子模式PCA，該算法增強了對不同面部表情和照明條件的魯棒性。

以上對于PCA算法的研究，使得改進的PCA算法魯棒性得到提高，并且能夠很好的適應于樣本數據，但計算出的投影空間卻是唯一的，滿足的目標函數是適應于整體樣本的。為了對數據更好地比對和識別，本文提出了一種能夠適應于單個樣本的特征選擇算法，該方法在PCA-L2的基礎上，基于最大化投影為每個樣本自適應地選擇特征，從而很好地考慮了樣本集合中每個樣本的分布特點。

1 PCA算法理論

(1) 最小化投影誤差

(2) 最大化投影后方差

2 基于PCA自適應特征選擇算法

2.1 算法描述

自適應目標函數為

自適應特征選擇算法如下：

輸入：訓練樣本與測試樣本。

投影空間中投影向量的數量取決于提取樣本特征的個數，篩選投影向量的順序在式(3)的約束下進行，優先選取數據投影后絕對值較大的投影向量。

2.2 性能分析

2.1節中所提出的方法是線性降維方法。大多數真實世界的數據存在于高維的非線性流形中，線性降維方法本質在于利用低維的線性空間去表示高維的復雜流形，從而可以利用歐式距離代表原復雜流形的測地距離。一般情況下，歐式距離往往不能真正衡量數據間真實距離，如圖1所示。

圖1 瑞士卷結構上的歐式距離與測地距離

通過好的降維方法進行降維以后，其數據點歐式距離能夠更好保持原本的測地距離結構。目前，基于PCA的方法均是假設數據都分布在同一線性空間中，事實上樣本數據有時會分布在不同的子空間中，而常用的LDA方法即針對這一問題提出的，但是LDA方法也存在一些問題，如降維后的空間受樣本數量限制等。本文所提的方法則可基于PCA對這一問題進行解決。

表1 5種不同PCA算法計算所得與值結果

3 實驗結果

為了對本文算法的有效性進行驗證，特給出了在實際數據庫上的對比實驗。6種的降維算法應用到3個不同的數據庫上，通過正確識別率以及平均重建誤差來評估算法性能。其中，分類過程采用了基于歐式空間距離的最近鄰分類器，正確識別率為識別正確的測試樣本數量與總測試樣本數量的比值。重建過程則為計算原數據與噪聲數據重建后數值的差。所有實驗中，每一種特征數下的識別率均做了10倍交叉檢驗，即隨機生成10次訓練集與測試集并計算平均識別率。

3.1 UCI數據集

5種PCA算法首先應用在UCI數據集[19]中進行分類實驗。UCI數據庫是加州大學歐文分校提出的用于機器學習的數據庫，這個數據庫目前共有378個數據集，是一個常用的標準機器學習測試數據集。

實驗選取常用的Balance等6個數據集[10-11]進行測試，其變量數量、類別以及樣本數量見表2。

表2 UCI數據集屬性

訓練前，每個數據集都被歸一化至均值為0，在十倍交叉檢驗中，隨機將數據集40%作為訓練集，剩余數據作為測試集。實驗中，首先算法通過計算訓練集的協方差矩陣特征值，得到了基于L2范數的投影空間。在自適應特征選擇過程中，采用本文提出的PCA-L2/ASF算法，分別挑選出適應于每張測試圖片的投影向量進而組成自適應投影空間，之后使用歐氏空間下的最小距離分類器進行分類。對比實驗的識別率結果如圖2所示。

對于傳統PCA-L2算法，本文算法明顯可以得到更高的識別率，尤其當提取特征數較小時，優勢更為明顯。相比于PCA-L1算法，本文算法在圖2(a)、(f)中，在提取特征較高時結果更優。在圖2(a)、(e)、(f)中提取特征較低時PCA-L1算法更優；特征較高時結果基本持平；在圖2(d)中提取特征較低時本文算法識別率更高。對于較高樣本量及特征量的數據集圖2(c)中，本文算法取得了很好的結果，在不同維度下識別率優于所有算法。WPCA在圖2(b)、(e)、(f)中在低維上識別率較高，但隨著提取特征數增加，本文算法明顯好于WPCA算法。在圖2(a)中本文算法基本與WPCA保持持平，當維度為3時本文算法更優。而在圖2(d)中WPCA在中段維度識別率較為突出，但本文算法在低維與高維空間識別率結果均優于WPCA。

3.2 Yale圖像數據庫

第二個對比實驗所采用的是耶魯人臉庫。該數據庫采集了15個人共計165張灰度人臉圖像，每個人的圖像中包含了人臉表情、光照條件不同的11幅圖像。實驗前，每幅圖像被轉化為了一個10 000維的向量，并且所有數據被歸一化至均值為0。在十倍交叉檢驗中，隨機抽取每個人5幅圖片共計75張圖片作為訓練集，剩余數據作為訓練集。

實驗引入棧式自編碼網絡[20](stacked autoencoder, SAE)，輸入單元10 000個(每張圖像10 000維)，輸出單元15個(圖像共15類)，代碼來自文獻[21]，除輸入與輸出單元個數，網絡結構參數設置與文獻[21]相同。識別結果如圖3所示。

從圖3中可以看到，本文算法對于人臉識別的效果要遠遠優于傳統PCA-L2算法效果。與PCA-L1與WPCA算法相比，在提取特征數量較低的區域內，本文算法在識別率優勢較為明顯，較高區域與L1算法的識別率基本持平，WPCA的識別率最好。由于樣本量較少，SAE在提取特征數量較低時，識別率均偏低，出現了目標函數不收斂情況。在提取特征較高時，目標函數可以收斂，相對應的測試集進行測試時結果卻在64.44%~80.00%之間。因此，PCA算法在小樣本數據集上的識別率要優于SAE神經網絡。

圖2 UCI數據庫的識別率

圖3 Yale數據庫的識別率

因為在圖形上識別率曲線比較接近，表3列出了提取特征在10維之內的正確識別率結果。

表3 6種PCA算法的正確識別率結果

注：提取特征數小于10

3.3 ORL人臉數據庫

ORL人臉數據庫包含了40個人共計400張的灰度人臉圖像，其中每人10張圖像。每張圖像都是在不同人臉面部表情及光照強度的條件下采集的，像素大小為92×112。實驗前，將每張圖片轉換為一個10 304維的向量。

在識別率實驗中，隨機抽取每個人的5張圖像作為訓練集，剩余5張作為測試集。實驗結果如圖4所示。

實驗中棧式自編碼網絡輸入單元個數為10 304 (每張圖像10 304維)，輸出單元個數為40(圖像共40類)，除輸入與輸出單元個數，網絡結構參數設置與文獻[21]相同。

從圖4中可以明顯看出本文算法相比于傳統PCA-L2算法的優勢，相比于PCA-L1與WPCA算法，當提取特征數量較小時(小于20)，自適應算法能夠實現更高的識別率。因為在圖形上識別率曲線比較接近，表4列出了低于20維的正確識別率結果。當提取特征大于20時，PCA-L1在識別率上的表現略好于其他算法，本文算法與PCA-L1GBF相比基本持平。SAE算法在小樣本數據庫下仍然出現了不收斂及過擬合的狀況，識別率低于本文算法。

圖4 ORL數據庫的識別率

表4 6種PCA算法的正確識別率結果

注：提取特征數小于20

通過實驗對比，可知本論文提出的自適應方法在識別分類的模式識別問題上對于傳統PCA算法有很大的提升，因此降維后的子空間能夠更好地表示原數據。

為了檢驗本文算法對于離群點的魯棒性，重建誤差實驗被應用在了ORL數據庫上。實驗前，每張圖片都被歸一化至[0,1]區間中，并且均值為0。從每類人臉圖像中隨機抽取3張圖片加入位置隨機的，大小為45×25的黑白噪聲塊，如圖5(a)，最終得到120個噪聲圖像。對帶有噪聲圖像的400張ORL數據庫進行重建誤差實驗，將重建誤差定義為

其中，m為提取特征數量；n為圖片總數，在這里n=400；為未加入噪聲塊的原始圖像；為加入噪聲塊的數據。

本文算法與PCA-L2、PCA-L1、PCA-L1GBF算法的平均重建誤差結果如圖6所示。

圖6 ORL數據庫的平均重建誤差結果

隨著特征數的增加，4種算法都在不同程度地降低平均重建誤差。通過實驗對比可見，本文算法的平均重建誤差明顯小于其他算法，證實本文算法對于具有噪聲的數據集能夠實現更低的平均誤差值，對離群點具有較好的魯棒性。

為了將人臉重建效果可視化，圖5(b)~(e)分別展示了4種算法將帶有噪聲塊的人臉進行重建后的效果，實驗中提取特征數為70。從圖5中可以較清晰的看出本文算法相比于其他算法，能夠在降維時較好地保留原數據中的結構，并在圖像重構中獲得更為清晰的人臉輪廓。

4 結 論

本文提出了一種具有更高自適應性個體樣本的特征提取PCA方法。通過建立自適應目標函數，基于PCA算法求出自適應于個體樣本的投影空間并完成特征提取。由于所提取特征是與數據相關的，因此在進行分類時，數據點中的歐式空間并不完全一致。盡管如此，該算法在真實數據上的對比實驗仍然取得了較好的識別率，并在具有離群點的數據集中取得了更優的重建誤差。下一步主要工作是研究針對不同的空間進行更好的距離度量。

[1] TURK M A, PENTLAND A P. Face recognition using eigenfaces [C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 1991: 586-591

[2] FERRAZ A, ESPOSITO E, BRUNS R E, et al. The use of principal component analysis (PCA) for pattern recognition Eucalyptus grandis wood biodegradation experiments [J]. World Journal of Microbiology and Biotechnology, 1998, 14(4): 487-490.

[3] WASHIZAWA Y. Subset kernel PCA for pattern recognition [C]//Proceedings of the IEEE Conference on Computer Vision Workshops. New York: IEEE Press, 2009: 162-169.

[4] AGUIRRE J V, MESA A M á, SANTACOLOMA G D. Pattern recognition by dinamic feature analysis based on PCA Proceedings of the IEEE [J]. Tecno Lógicas, 2009(22): 29-42.

[5] 高艷霞. 基于Gabor+PCA特征與粒子群算法的部分遮擋人耳識別研究[J]. 圖學學報, 2014, 35(1): 100-104.

[6] 陳祥濤, 張前進, 張雙玲. 基于模糊理論決策的雙向二維PCA步態識別算法[J]. 圖學學報, 2012, 33(6): 103-109.

[7] JOLLIFFE I T, Principal component analysis [M]. New York: Springer, 1986.

[8] BACCINI A, BESSE P, DE FAGUEROLLES A. A L1-norm PCA and heuristic approach [C]//In Proceedings of the International Conference on Ordinal and Symbolic Data Analysis. State College: The Pennsylvania State University, 1996: 359-368.

[9] KE Q, KANADE T. Robust subspace computation using L1 norm [EB/OL]. [2016-12-20]. http://repository.cmu. edu/compsci/2191/.

[10] KWAK N. Principal component analysis based on L1-Norm maximization [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 30(9): 1672-1680.

[11] DING C, ZHOU D, HE X, et al. R1-PCA: rotational invariant L1-norm principal component analysis for robust subspace factorization [C]//International Conference on Machine Learning. New York: ACM Press, 2006: 281-288.

[12] MARKOPOULOS P P, KUNDU S, CHAMADIA S, et al. Efficient L1-norm principal-component analysis via bit flipping [J]. IEEE Transaltion on sigual Processing 2017, 65(16): 4252-4264.

[13] MARKOPOULOS P P, KARYSTINOS G N, PADOS D A. Optimal algorithms for L1-subspace signal processing [J]. IEEE Transactions on Signal Processing, 2014, 62(19): 5046-5058

[14] CANDES E J, LI X, MA Y, et al. Robust principal component analysis? [J]. Journal of ACM, 2009, 58(3): 11.

[15] SHAHID N, KALOFOLIAS V, BRESSON X, et al. Robust principal component analysis on graphs [C]// IEEE International Conference on Computer Vision. Los Alamitos: IEEE Computer Society, 2015: 2812-2820.

[16] WANG H Y, WU X J. Weighted PCA space and its application in face recognition [C]//International Conference on Machine Learning and Cybernetics. New York: IEEE Press, 2005: 4522-4527.

[17] TAN K, CHEN S. Adaptively weighted sub-pattern PCA for face recognition [J]. Neurocomputing, 2005, 64(1): 505-511.

[18] BRAHMA P P, WU D, SHE Y. Why deep learning works: a manifold disentanglement perspective [J]. IEEE Transactions on Neural Networks & Learning Systems, 2016, 27(10): 1997-2016.

[19] LICHMAN, M. UCI machine learning repository [EB/OL]. [2016-12-29]. http: //archive. ics. uci. edu/ml.

[20] VINCENT P, LAROCHELLE H, LAJOIE I, et al. Stacked denoising autoencoders: learning useful representations in a deep network with a local denoising criterion [J]. Journal of Machine Learning Research, 2010, 11(12): 3371-3408.

[21] ZHANG Y W. Toin github today [EB/OL]. [2016-11-30]. https: //github.com/Aewil-zz/Stacked_Autoencoder-Basic_ Version.

An Adaptive Feature Extraction Method Based on PCA

ZHANG Xin, DIAO Luhong, NAN Dong, WANG Yongli, LIU Yang

(College of Applied Sciences, Beijing University of Technology, Beijing 100124, China)

An adaptive features extraction method is proposed. It defines an adaptive objective function based on the projective space derived by using PCA method. Then the projection space of the individual sample is computed. The distribution characteristics of each sample are well considered. In order to make the algorithm applicable to the classification problem, a similarity measurement is proposed to calculate the similarity between individual samples in different projection spaces. Compared with the Euclidean metric, the proposed measurement is proved that can represent the geodesic distance relationship between the samples better, so that the proposed method can learn the manifold data effectually. The classification and reconstruction experiments on the different databases indicate that the new method can obtain features more effectively and robustly.

feature extraction; principal component analysis; adaptive feature extraction; face recognition

TP 391

10.11996/JG.j.2095-302X.2018030501

A

2095-302X(2018)03-0501-08

2017-09-04；

2017-10-07

張 鑫(1992-)，男，北京人，碩士研究生。主要研究方向為模式識別。E-mail：zxzx@emails.bjut.edu.cn

刁麓弘(1978-)，男，山東龍口人，副教授，博士。主要研究方向為計算機視覺與計算機圖形學。E-mail：diaoluhong@bjut.edu.cn