大間距無監督正交特征提取算法*

林玉娥，李敬兆，梁興柱，林玉榮

(1.安徽理工大學計算機科學與工程學院，安徽淮南232001;2.哈爾濱工業大學航天學院，黑龍江哈爾濱150001)

0 引言

主成分分析(principal component analysis，PCA)［1］以投影矩陣能夠使得投影后的圖像達到最小重構誤差為目標，是一種全局的無監督特征提取算法，PCA所有的樣本數據點采取相同的處理方式，目的是使高維的樣本數據在投影空間中都被盡可能地分開，目前該算法已得到廣泛的應用.但是從識別的角度來講，比較靠近的數據樣本有可能是同一類，因此，降維后也應保持近鄰關系，局部保持投影［2，3］(locality preserving projection，LPP)就是基于這一思想的一種特征提取算法，其目的是使得投影后的圖像樣本在低維空間保持原有的近鄰結構，人臉庫上的實驗結果表明了該算法的有效性.能否將二者結合起來使得所求取的投影矩陣更為有效，對此本文進行了研究，提出了一種大間距無監督正交特征提取算法(maximum margin unsupervised orthogonal feature extraction algorithm，MMUOFEA)，該算法以PCA和LPP為理論基礎，其目標函數同時考慮全局與局部信息，其意義是盡可能重構原樣本的同時保持投影后的樣本原有的近鄰關系，并且由于目標函數采用了大間距的鑒別準則［4～6］，避免了矩陣求逆，因此，解決了人臉識別中的小樣本問題，同時為了增強算法的識別性能對鑒別矢量集進行了正交性的限制。仿真實驗表明:本文方法不但是有效的，而且適應性更強。

1 主成分分析與保局投影

在模式識別中特征提取就是要找到一個投影矩陣W，然后對高維樣本xi進行投影

式中 yi為圖像xi的投影特征系數向量，W是按照某種準則求得的最佳投影矩陣，W 應能夠使得投影后的圖像具有較低的維數和較好的可分性。下面將簡要地介紹2個與本文討論密切相關的目標函數。

主成份分析的目的是要求所求取投影矩陣能夠使得投影后的圖像達到最小重構誤差或最小均方意義下的最優表達，其準則函數為

式中 St稱之為總體散布矩陣，St的定義為

其中，mi為第i類樣本的均值向量，m為樣本的總體均值向量。

對于上式中的W求解，實際上就是求解下式廣義線性方程特征值與特征向量的問題

假設把求得的特征值按升序排列，選擇對應前d(通常d＜l)個最大的特征值所對應的特征向量 w1，w2，…，wd，即是所求的最優投影方向矩陣W。

LPP以保持樣本固有的局部流形結構為目標，其目標函數為

約束條件為

式(7)中的sij可按下式求得

式中 L=D－S為拉普拉斯矩陣，S是由sij構成表示位置相似矩陣，D為對角陣，其對角元素dii=，ε 是一個較小的正數。通過代數運算，式(7)可以轉換成下面的特征值求解問題，即

假設把求得的特征值按降序排列λi≤λi+1，選擇對應前d(通常d＜l)個最小特征值所對應的特征向量w1，w2，…，wd即是所求的最優投影方向矩陣W。

2 大間距無監督正交特征提取算法

PCA是一種全局算法，而LPP則是一種局部算法，2種算法基于不同的幾何思想，因此，只可以發現數據集某一方面的特性。為了使算法能夠在揭示數據集全局結構的同時又可以有效保持它的局部結構，本文將二者聯系起來，提出MMUOFEA。其目標函數同時考慮全局與局部信息，其意義是盡可能重構原樣本的同時要保證在低維空間保持原有樣本的近鄰結構。因此，MMUOFEA的目標函數應同時滿足下面二式，即

上面二式可轉化為一式，在這里為了避免了矩陣求逆，采用大間距的鑒別準則，同時加上正交約束條件，故MMUOFEA的目標函數定義為

對于上式的求解，根據Lagrange乘子法構造函數

對 wi求偏導并，可以得到式(10)的求解實際上就是下面廣義特征值問題

最后選擇對應前d(通常d＜l)個最大特征值所對應的特征向量 w1，w2，…，wd即是所求的正交投影矩陣。MMUMFA的具體實現步驟總結如下:

1)分別根據式(2)和式(7)分別求出St和S;

2)再根據L=D－S計算出L;

3)對式(11)進行特征值分解，選前d個最大特征值所對應的特征向量w1，w2，…，wd即求出W。

3 實驗結果與討論

本文為了驗證提出MMUOFEA的性能，在ORL人臉庫上進行了實驗，采用簡單的最近鄰方法進行分類。ORL人臉庫有40個人，每人10幅，共400幅圖像，每幅圖像的分辨率為112×92.對MMUOFEA與LPP及PCA的識別性能進行了比較，分別選擇ORL人臉庫前5幅圖像作為訓練樣本，剩余作為測試樣本，對MMUOFEA與LPP及PCA在提取不同特征數目時的識別性能進行了比較，實驗結果如圖1所示。圖2為選用前3—8幅圖像作為訓練樣本數目時，后7—2幅作為測試樣本，2種算法識別率的比較。終都優于其他2種算法的識別率，當提取到大于40個特征時，MMUOFEA穩定在最高識別率92.5%，而且隨著特征個數的增加算法的識別率一直穩定在92.5%;從圖2可看出:無論訓練樣本如何變化，MMUOFEA都優于LPP和PCA的識別率，這也說明了本文的目標函數提取出的特征更加有利于分類，這是因為本文算法綜合了LPP和PCA二者的優點，不但能夠發現數據樣本的全局結構更能有效地保持樣本原有的近鄰結構，因此，能夠取得更好的識別效果。

圖1 ORL人臉庫識別率隨維數變化的結果Fig 1 Change of recognition rate of ORL face database with different dimension

圖2 訓練樣本個數變化時3種方法的性能比較Fig 2 Performance comparison of three methods while number of training samples change

4 結論

本文提出一種新的特征提取算法—MMUOFEA，其目標函數同時考慮數據樣本的全局與局部信息，因此，MMUOFEA獲得了更好的識別效果。MMUOFEA利用矩陣之差作為準則函數，解決了小樣本問題，在人臉庫上的實驗結果驗證了本文算法的正確性和有效性。

［1］Turk M，Pentland A.Eigenfaces for recognition［J］.Journal of Cognitive Neuroscience，1991，3(1):71－86.

［2］He X F，Yan SC，Hu Y，et al.Face recognition using Laplacianfaces［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(3):328－340.

［3］He X，Niyogi F.Locality preserving projections［C］∥Proceedings of Advances in Neural Information Processing Systems，Cambridge，MA，2004:153－160.

［4］Li H F，Jiang T，Zhang K S.Efficient and robust feature extraction by maximum margin criterion［J］.IEEE Transactions on Neura1 Networks，2006，17(1):1157－1165.

［5］林克正，王慧鑫，卜雪娜，等.基于局部保持投影的鑒別最大間距準則［J］.模式識別與人工智能，2010，23(2):178－185.

［6］Lu G F，Lin Z，Jin Z.Face recognition using discriminant locality preserving projections based on maximum margin criterion［J］.Pattern Recognition，2010，43(3):3572－3579.