支持向量描述鑒別分析及在人臉識別中的應用

摘 要:數據降維是模式識別的重要組成部分。支持向量鑒別分析(support vector discriminant analysis， SVDA)依最優超平面法線方向投影對數據進行降維，克服了傳統方法中假設數據滿足高斯分布時，導致無法反映超平面單側中多類數據間投影距離差異并影響了算法有效性的缺點。提出一種支持向量描述鑒別分析(support vector description discriminant analysis， SVDDA)算法，首先利用支持向量機最優超平面獲取樣本的類屬信息，然后通過SVDD的超球面法線作為投影軸取得樣本的投影距離，取兩信息的組合作為樣本的特征映射。算法利用SVDD的一類緊致超球特性，彌補支持向量鑒別分析的不足。通過人臉識別實驗，驗證了該算法的有效性。

關鍵詞:特征降維; 支持向量鑒別分析; 支持向量數據描述; 支持向量描述鑒別分析; 人臉識別

中圖分類號:TP391.41

文獻標志碼:A

文章編號:1001-3695(2010)02-0488-03

doi:10.3969/j.issn.1001-3695.2010.02.022

Support vector description discriminant analysis andits application to face recognition

CHEN Chang-jun， ZHAN Yong-zhao， WEN Chuan-jun

(School of Computer Science Communication Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China)

Abstract:Dimension reduction of data is one of the most important components for pattern recognition. SVDA projected data according to the normal direction of SVM’s optimal separating hyperplane. SVDA could overcome the shortcomings of that traditional dimension reduction methods always assumes data meets Gaussian distribution. But the differences of some classes in the same side of SVM hyperplane could not be reflected by normal direction projection. This paper proposed a new dimension reduction method named as support vector description discriminant analysis. Obtained class information through SVM hyperplane and extracted projection distances through SVDD hypersphere projection normal， set the combination of class information and projection distance of sample data as corresponding feature component. And applied the algorithm to the feature extraction in face recognition. The results show the effectiveness of this algorithm.

Key words:feature dimension reduction; SVDA; SVDD; SVDDA; face recognition

0 引言

在統計模式識別問題中，原始觀察數據維數很高，存在大量的冗余信息，會導致算法復雜度過高、計算量太大、降低分類的性能，因此需要對原始數據降維[1，2]。傳統的降維方法主要有主元分析(PCA)[3]、Fisher線性鑒別分解(LDA)[4]、獨立分量分析(ICA)[5]、奇異值分解(SVD)[3]等。核化算法[6]將原始數據通過非線性變換映射到高維特征空間進行降維變換，很好地表達了原始數據的非線性特性。對傳統方法應用核化算法可以得到KPCA、GDA、KICA等。這些降維方法需要假設數據服從確定的概率分布(正態分布)，利用有限樣本對均值和方差的估計，代替正態分布的均值和方差，當分布在原始空間或高維投影空間中的實際數據不服從假設要求或樣本參數估計不準確時，投影降維后的數據就不能夠進行正確的分類。支持向量鑒別分析(SVDA)[7]利用支持向量機(SVM)尋找有限樣本下最大間隔的最優超平面，以對應的法線作為投影軸，對數據降維，可以克服因預先假定數據分布而帶來的弊端，在小樣本條件下尋求類間最大可能差異。但由于SVM二分類的特點，投影軸只能有效地反映兩大類之間的差異，當某一大類為多個小類所組成時，這些小類之間的差異性則忽略了。支持向量數據描述(SVDD)是由Tax等人[8]為了解決一類分類問題而提出的分類方法，僅需一類樣本建立緊致的超球面，其他類的樣本對于超球的建立無影響，對于超球面而言，其余類的樣本將保留原有類別間的統計差異。基于以上分析，本文提出了一種支持向量描述鑒別分析(SVDDA)方法，分別建立SVM和SVDD模型，利用SVM提取樣本的類別信息;樣本距離SVDD超球心的距離作為投影距離;借助超球半徑，對投影軸的量綱進行尺度歸一化;組合類別信息和歸一化投影距離，即可得到樣本的壓縮特征。

1 支持向量描述鑒別分析(SVDDA)

1.1 支持向量機(SVM)

基于結構風險最小化原理的支持向量機[9]通過尋找有限訓練樣本情況下的最優分類面，使得分類間隔達到最大。設{xi，yi}(i=1，…，n)，為n個訓練樣本，xi∈Rd，yi∈{-1，1}為樣本i的類別屬性，為了使得算法對于測試樣本具有良好的推廣能力，所選擇的最優分類面H應盡可能地遠離訓練樣本。設分類面H方程H:xTw+b=0，則對于所有樣本，滿足約束方程yi(xiTw+b)≥1，超平面H距離樣本的距離和為2/‖w‖，最大化間隔距離2/‖w‖對應于最小化目標函數(1/2)‖w‖2。若訓練樣本為近似可分，則引入松弛變量ξi(>0)，條件約束方程變為yi(xiTw+b)≥1-ξi，目標函數加上錯分樣本的懲罰變為1/2‖w‖2+C∑iξi。通過求解目標函數對應的對偶問題，并通過核函數非線性映射，得到判決輸出函數為

f(x)=sign(∑iyiαiK(xi，x)+b)(1)

常用的核函數主要有線性核函數、多項式核函數、高斯徑向基核函數、Sigmoid核函數。

1.2 支持向量數據描述(SVDD)

SVDD通過尋找包含盡可能多一類數據的最小體積的超球體來實現對數據的描述，對于奇異的數據點，引入松弛變量進行約束(即允許存在少量樣本位于超球外)。對于最小超球體的計算可以轉換為如下二次規劃問題:

min L=R2+C∑iξi(2)

約束條件為‖xi-a‖2=(xi-a)T(xi-a)≤R2+ξi，ξi≥0。其中:a為超球球心;R為超球半徑;C為懲罰因子。上面的優化問題通過拉格朗日乘子法轉換為其對偶問題，并引入核函數映射取代非線性映射內積運算，得到在高維空間的對偶形式，其目的是為了讓原始數據經過映射后呈現球狀分布。得到

max LD=∑iαiK(xi，xi)-∑i.jαiαjK(xi，xj)(3)

s.t. ∑iαi=1 0≤αi≤C i

同時也可得到a=∑iαixi∑iαi=∑iαixi，即超球體的球心為數據樣本的線性組合。當‖xi-a‖2

R2=‖xk-a‖2=K(xk，xk)-2∑iαiK(xk，xi)+

∑jαiαjK(xi，xj)(4)

其中:xk為某一支持向量，即xk∈{xsv}。

對于任意樣本x基于超球球心距離的平方為

D2(x，a)=‖x-a‖2=K(x，x)-2∑iαiK(x，xi)+

∑jαiαjK(xi，xj)(5)

1.3 支持向量描述鑒別分析(SVDDA)

SVDDA構造方法如下所述:

a)設存在C類樣本集{xc，i}，其中1≤c≤C，1≤i≤Nc。Nc表示第c類的樣本數，選擇第j類數據{xj，i}(1≤j≤C，1≤i≤Nj)作為第一類，剩下的其他類別數據作為第二類，訓練第j個SVM模型，建立最優超平面πj，其法線投影軸為wj。

b)對于任意樣本x，以超平面πj法線作為投影軸wj進行投影。投影計算式為

zj=wTjx+bj=∑iαjiyjiK(xji，x)+bj(6)

其中:xji、yji、αji、bj為第j個SVM模型所對應的支持向量、類標簽、Lagrange乘子以及偏移。樣本x關于第j個SVM模型的投影坐標為zj，sgn(zj)表示了樣本x關于第j個SVM模型的類別信息。

c)利用第j類數據{xj，i}，1≤j≤C，1≤i≤Nj，利用SVDD建立第j個最優超球面Sj，相應得到最優超球Sj的球心aj和半徑Rj。

d)對于任意樣本x，由式(4)計算得到x距離第j個最優超球球心的距離為

D2(x，aj)=‖x-aj‖2=K(x，x)-2∑kαjkK(x，xjk)+

∑k，lαjkαjlK(xjk，xjl)(7)

其中:xjk、αjk為最優超球Sj的支持向量和Lagrange乘子。

e)對于任意樣本x，結合x的類別信息和超球距離，得到第j個特征投影映射為

yj=sgn(zj)D2(x，aj)Rj2(8)

從而得到任意樣本x的C維特征投影(y1，…，yC)T。

推廣:在C類樣本中任選k(1≤k≤[C/2])類，其中[]為取整運算，以所選k類為第一類，仿式(1)進行特征降維，即式(1)為k=1時的特殊情況，令k≤[C/2]，采用這樣的方式可以降維到(kC)維。對于不同的k，得到不同的降維方式，也可以對不同的k所產生的降維方式進行組合使用。

2 算法性能分析

本文所提出的基于SVDD的支持向量描述鑒別存在如下優勢:

a)算法的投影正負類信息，是利用SVM的最優超平面確定的，基于核函數高維空間非線性映射的SVM，在高維線性可分的兩大類樣本間通過最大幾何間隔確定最優超平面。設δ為幾何間隔，R為空間中一個能完全包含樣本數據的球的半徑，則誤分次數≤(2R/δ)2，因此最優超平面為分類信息(即投影正負)提供了精確的描述和良好的推廣保證。

b)算法的投影距離，采用超球面的法線作為投影軸，而超球面的建立僅僅利用了第一類樣本，而剩余類的樣本與超球面間不存在約束關系，即剩余各類樣本之間的分類信息不會因為超球面的建立而受到破壞，剩余各類樣本互無干擾分布于超球外。SVDA投影軸需要將剩余類作為第二類參與確定，對SVDA投影軸而言，剩余類的樣本被看做是一個類而不是多個類，因而無法反映這些剩余類之間的分類特性。

c)設ω2、ω3為剩余類中兩類，x1、x2分別為這兩類的兩個樣本，即有x1∈ω2，x2∈ω3，顯然有x1≠x2。經SVDA投影映射后得到對應分量y1、y2，經本文算法投影映射后得到投影分量為z1、z2。

P(y1=y2)=∑tP(y1=t)P(y2=t|y1=t)

P(z1=z2)=∑tP(z1=t)P(z2=t|z1=t)

在無法對分布P(y1=t)、P(z1=t)進行準確估計的情況下，假設P(y1=t)=P(z1=t)。以二維空間為例，事件(y2=t|y1=t)等價于x2基于SVDA的取值范圍為一條直線，而基于本文算法為一個圓，從而有P(y2=t|y1=t)≥P(z2=t|z1=t)，則P(y1=y2)≥P(z1=z2)，這說明了該降維算法投影映射后，導致不同類樣本混淆的可能性較低。

d)算法投影距離并不是一個絕對的距離概念，而是相對于超球半徑平方的比值。因為超球的大小是與第一類樣本的數量相關的，不同的第一類樣本所確定的超球大小是不一致的，利用相對比值距離作為投影距離，可以避免因為超球訓練樣本數量上的不同而帶來的對投影距離的干擾，即對投影距離進行了歸一化處理。這樣處理的目的，可以使得對于任意樣本x的每一維分量，在量綱上達到統一。

3 SVDDA在人臉識別中應用

3.1 仿真應用

人臉識別是生物識別研究的重要內容之一，是生理學、心理學、圖像處理、模式識別和機器視覺等領域一個極富挑戰性的交叉課題。它的應用領域包括安全領域、智能機器人研制、人際交互、計算機游戲、精神分析、醫療輔助等[10]。

將基于SVDD的SVDDA算法用于人臉識別工作，以此驗證算法的有效性。實驗數據采用ORL人臉數據庫。ORL人臉庫存在一定的光照、表情(微笑、睜眼、閉眼等)、飾物的變化(眼鏡)，共由40個人組成，每個人10幅圖像。

首先對所截取的人臉圖像通過灰度均衡和尺度歸一化為30×30像素大小，即每個圖像所提供的樣本數據為1×900維。ORL庫中，每人選擇4幅圖像加入訓練樣本集，即有40類樣本，每類樣本4個訓練樣本;ORL庫剩余的圖像集中，每人6個樣本，共有240個樣本構成測試樣本集。進行5輪試驗，最后結果是5輪的平均。

3.2 測試結果

實驗對人臉圖像進行LBP[11]特征提取，經過SVDDA算法對原始高維LBP特征投影壓縮后，利用KNN算法進行分類識別。表1給出了實驗結果。第一行表示分類器及其對應的參數，如KNN(K=3)，近鄰參數K=3，K=5;第一列表示降維算法，原始單樣本高維特征將被降維至1×40維，所有的核函數都采用徑向基核函數，σ=3。行與列相交處的百分數是使用對應的特征提取方法和分類方法所取得的平均識別率。

表1 降維方法與KNN組合得到的人臉識別率

降維算法KNN(3)/%KNN(5)/%

SVDA96.596.9

SVDDA97.0497.84

由表1可以看出，SVDDA對于不同參數的KNN分類器都有良好的分類效果，對分類工作提供了很好的魯棒支持。

4 結束語

對原始數據進行降維可以降低噪聲干擾、消除數據冗余、減少計算量、提高識別的穩健性，是模式識別工作的研究重點。本文提出了一種支持向量描述鑒別分析數據降維方法。首先利用SVM最優超平面最大分類間隔的特性獲取數據投影的正負極信息，再借助SVDD一類數據所構造的超球面法線做投影軸得到數據極坐標距離投影，盡可能保留基于SVM超平面中多類組成的剩余類之間的分類統計信息，并將投影距離與超球半徑相比的方式進行歸一化，從而消除了訓練樣本量對投影的干擾。所選取的組合投影方式是可輪換對稱的，保證了對于數據的盲處理過程。將算法應用在人臉識別上，取得了良好的分類效果，證明了算法的有效性。

致謝:感謝ORL人臉圖像庫、DD_Tools、Stprtools、Prtools的免費提供使用。

參考文獻:

[1]宋楓溪，高秀梅，劉樹海，等. 統計模式識別中的維數消減與低損降維[J].計算機學報，2005，28(11):1915-1922.

[2]劉海峰，王元元，張學仁，等. 基于散度差準則的文本特征降維研究[J].計算機應用研究，2008，25(7):1971-1973.

[3]吳春國，梁艷春，孫延風，等. 關于SVD與PCA等價性的研究[J]. 計算機學報， 2004， 27(2):286-288.

[4]陳伏兵，張生亮，高秀梅，等. 小樣本情況下Fisher線性鑒別分析的理論及其驗證[J]. 中國圖象圖形學報， 2005，10(8):984-991.

[5]谷雨，徐宗本，孫劍，等. 基于PCA與ICA特征提取的入侵檢測集成分類系統[J]. 計算機研究與發展，2006，43(4):633-638.

[6]王泳，胡包鋼. 應用統計方法綜合評估核函數分類能力的研究[J]. 計算機學報， 2008， 31(6):942-951.

[7]應自爐，唐京海，李景文，等. 支持向量鑒別分析及在人臉表情識別中的應用[J]. 電子學報， 2008， 36(4):725-730.

[8]TAX D M J， DULIN R P W. Support vector domain description [J]. Pattern Recognition Letters， 1999， 20(11-13):1191-1199.

[9]CORTES C， VAPNIK V. Support-vector networks [J]. Machine Learning， 1995， 20(3):273-297.

[10]CHELLAPPA R， WILSON C， SIROHEY S. Human and machine recognition of faces: a survey [J]. Proceedings of the IEEE， 1995， 83(5):705-740.

[11]AHONEN T， HADID A， PIETIKAINEN M. Face recognition with local binary patterns[C]//Proc of the European Conference on Compu-ter Vision. Prague:Springer-Verlag， 2004:469-481.