一種基于圖的線性判別分析方法

王 飛，劉玉英，彭 超

(中國礦業(yè)大學信電學院，江蘇 徐州 221116)

隨著信息時代的發(fā)展，大量信息的涌入使得人們獲得豐富的數(shù)據(jù)。如果僅從這些數(shù)據(jù)本身出發(fā)來尋找我們想要的信息，已經(jīng)超出了人類以及計算機的能力范圍。因而如何有效而合理地收集、組織以及分析這些數(shù)據(jù)是現(xiàn)代人們亟待解決的問題。基于圖學習的方法就是解決這一問題的一類非常重要的方法。研究表明，很多降維方法最終可歸結(jié)于圖的構造和低維嵌入方式[1]。這類方法通常將整個數(shù)據(jù)集建模成為一張圖，圖上的結(jié)點G就是樣本數(shù)據(jù)，S邊表示數(shù)據(jù)之間的關系，通常用(G，S)表示。這樣，數(shù)據(jù)的分析問題就轉(zhuǎn)換成為圖上的分析問題，因為圖可以看作是流形的離散化形式，圖上的結(jié)點是從數(shù)據(jù)流形上采樣得到的，而圖上的邊則反映了某些數(shù)據(jù)流形的結(jié)構信息。這些方法的目標就是要學習一個更低維的數(shù)據(jù)嵌入并且保持原數(shù)據(jù)圖的某些信息[2－3]，一些流行的降維方法如:等距離映射(Isomap)[4]主要保持數(shù)據(jù)點之間的測地距離，局部線性嵌(LLE)[5－6]主要保持數(shù)據(jù)的領域關系，Laplace特征嵌入(LE)[7]主要保持數(shù)據(jù)流行的光滑性。

同樣，線性判別分析(LDA)[8]作為經(jīng)典的降維方法，也可歸結(jié)于圖的構造方法范疇。LDA的核心思想是樣本從高維映射到低維空間保證投影后，使得模式樣本在新的空間中有最小的類內(nèi)距離和最大的類間距離，從圖構造的角度分析，LDA可理解為:首先構造類內(nèi)樣本圖，使得類內(nèi)所有樣本點向該類中心靠攏;然后構造類間圖，使得各類中心與總樣本中心遠離。然而LDA方法作為全局性降維方法，在處理類間樣本分類時，只考慮總體樣本中心點與各類樣本點的分離的全局特性，忽略了樣本間的邊緣點的局部特性，從而可能導致類間邊緣樣本點的誤分。本文從圖構造的角度重新構造類間圖，針對該問題提出了一種新的降維方法——K－邊緣判別分析方法(KMDA)。從可視化分析和降維后分類效果兩個方面分別對新提出的方法和LDA進行對比實驗，數(shù)據(jù)庫選擇UCI上的公共數(shù)據(jù)集和人臉數(shù)據(jù)集，實驗證明，該方法在分類正確率方面表現(xiàn)較好。

1 線性判別分析(LDA)

線性判別式分析(Linear Discriminant Analysis，LDA)，也叫做Fisher線性判別分析(FDA)，是模式識別的經(jīng)典算法，基本思想是將高維的模式樣本投影到低維的最佳鑒別矢量空間，以達到抽取分類信息和壓縮特征空間維數(shù)的效果，投影后盡量使同一類別的樣本緊湊，而使不同類別的樣本遠離。因此，它是一種有效的特征抽取方法。使用這種方法能夠使投影后模式樣本的類間散布矩陣最大，并且同時類內(nèi)散布矩陣最小。也就是說，它能夠保證投影后模式樣本在新的空間中有最小的類內(nèi)距離和最大的類間距離。具體算法如下:

設有C個模式類別，X=(x1，x2，…，xm)是N個m維的訓練樣本，類間離散度矩陣Sb和類內(nèi)離散度矩陣Sw定義[7]

式中:ui是第i類樣本的均值;u0是總體樣本的均值;ni是屬于i類的樣本個數(shù)。當Sw非奇異時，F(xiàn)isher準則最終的投影函數(shù)可定義為[8]

2 K－邊緣判別分析方法(KMDA)

這里介紹一種新的方法——K－邊緣判別分析方法(KMDA)，來控制邊緣部分的點，重新建圖，類似LDA構圖思想，本方法首先使得樣本類內(nèi)緊湊，同時類間選擇一類的中心，并求其他類中與這類中心的K個近鄰點，最大化它們之間的距離，圖1為該方法的基本思想。首先使得同類中所有點向該類中心靠攏;同時，使得該類中心與其他類的K個邊緣點遠離。

圖1 K－邊緣判別分析方法(KMDA)基本思想

2.1 類內(nèi)緊湊

高維數(shù)據(jù)映射到低維應該保持類內(nèi)間距離更加緊湊[9]，基于LDA思想，本文構造類內(nèi)緊湊圖Gc，設X={x1，x2，…，xn}∈Rm×n為訓練樣本，Y={y1，y2，…，yn}∈Rd×n為降維后訓練樣本的低維嵌入，n為樣本數(shù)，m為樣本維數(shù)，d為嵌入維數(shù)。Gc={X，S}為無向有權圖，樣本xi為圖中一點，W為其相似度矩陣，Wij為樣本i和樣本j的相似度?？梢酝ㄟ^式(3)進行優(yōu)化

2.2 類間遠離

降維的目的一般是為了以后做數(shù)據(jù)的分類或回歸，前一節(jié)中盡量在降維的過程中保證類內(nèi)緊湊，這一節(jié)在降維過程中要使類與類之間盡量遠離，LDA算法通過求整體樣本的中心和各個類的中心，從而使得每一類的中心與整體樣本的中心遠離，但是對于比較分散的數(shù)據(jù)樣本，LDA算法容易導致邊緣點的誤分，根據(jù)MFA[10]思想，本文同樣構造一懲罰圖Gp，由于Gc已經(jīng)保證了降維過程中各訓練樣本向中心緊湊，所以在類間，另一類的邊緣可根據(jù)通過求與這類中心最近的K近鄰來確定，K的選擇一般根據(jù)訓練樣本的數(shù)量而定。優(yōu)化公式為

2.3 構造投影矩陣

通過前兩節(jié)圖的構造以及優(yōu)化后的公式，最終得到求解以下的優(yōu)化問題

當Sc非奇異時，最佳投影矩陣wopt的列向量為廣義特征方程Spα=λScα的d個最大的特征值所對應的特征向量。

具體算法如下:

1)首先檢驗樣本數(shù)和維數(shù)的大小，即Sc是否奇異，如果奇異先運行PCA[11－12]降維，使得樣本維數(shù)小于或等于樣本個數(shù)。

2)構造如圖1所示的類內(nèi)和類間圖求出最優(yōu)化向量wopt。

3)計算出低維表示:Y=XWopt。

3 實驗分析

3.1 可視化分析

Wine數(shù)據(jù)集是一個典型的機器學習標準數(shù)據(jù)集，本文首先選擇Wine數(shù)據(jù)前兩類進行分類實驗，共130個樣本，其中1～59為第一類，60～130為第二類，實驗測試訓練樣本選擇共66個，第一類和第二類分別33個，測試樣本共64個，第一類和第二類分別為29和35個，為達到可視化效果，本實驗分別運行LDA和KMDA分別把樣本降到二維空間并對測試樣本進行分類，結(jié)果如圖2所示。

圖2 分類結(jié)果對比(截圖)

可見，當運行LDA分類時，由于在處理不同類間遠離時，只注重全局性而忽略了邊緣的個別點，從而導致邊緣點的誤分;KMDA算法在映射過程中強制選擇不同類最近的K個點，使它們遠離本類的中心;圖2b為當邊緣近鄰值K=4時的KMDA分類結(jié)果，可以看出運行KMDA后，圖2a中被誤分的兩個點，在圖2b中得到正確的分類結(jié)果。

3.2 公共數(shù)據(jù)集測試

選取UCI中Wine數(shù)據(jù)集、Sonar數(shù)據(jù)集、Abalone數(shù)據(jù)集和Diabetes數(shù)據(jù)集進行對比實驗，表1列出了每個數(shù)據(jù)集的實驗參數(shù)。為達到對比的效果，本文降維后的分類器均選擇1－NN分類，實驗結(jié)果如圖3所示，縱坐標表示降維之后采用1－NN分類的正確率，橫坐標表示所降到的維數(shù)，實驗目的是比較3種算法在不同數(shù)據(jù)集降維后的分類正確率。

表1 各個數(shù)據(jù)集實驗參數(shù)

圖3 3種算法在不同數(shù)據(jù)集降維后的分類正確率比較

從圖中的曲線可以看出:就穩(wěn)定性而言，PCA降到各個低維空間比LDA好;LDA在降到特定的低維空間時分類正確率比PCA效果好;從總體看來，無論比較穩(wěn)定性還是最高分類正確率，KMDA效果最好。這是因為PCA在降維過程中，低維映射函數(shù)矩陣，選擇的是主成分映射，當降到不同維數(shù)時，PCA能選擇數(shù)據(jù)的主要特征，總體穩(wěn)定性較好;而LDA使同類緊湊，不同類遠離，注重分類效果;KMDA克服了LDA局部邊緣點存在的問題，總體效果最佳。

3.3 人臉數(shù)據(jù)集測試

3.3.1 BioID 數(shù)據(jù)庫

BioID標準人臉庫是1521個384×286灰度自然場景下的人臉圖像，由23個測試者提供。還包含每個人臉的雙眼位置。圖4是BioID人臉庫中部分圖片。

圖4 BioID人臉庫的部分圖像

從BioID人臉庫選取兩個人共40幅圖像做實驗，以每人的前10幅圖像作為訓練樣本，后10幅作為測試樣本，這樣訓練樣本和測試樣本總數(shù)均為40。分別運行PCA，PCA+LDA，PCA+KMD算法降維，再分別選用1－NN分類器分類，最后得到識別率如表2所示。

表2 BioID數(shù)據(jù)庫采用各算法降維后的分類正確率

3.3.2 JAFFE 數(shù)據(jù)庫

JAFFE人臉數(shù)據(jù)庫是在人臉表情識別研究中應用最多的數(shù)據(jù)庫之一，從JAFFE人臉庫中選擇兩個人臉圖像做實驗，每個人均選擇前10幅圖像做訓練樣本，后10幅作為測試樣本，這樣訓練樣本和測試樣本總數(shù)均為20，先運行PCA算法，再分別運行LDA和KMDA算法，降到1～10維，最后采用1－NN分類器進行分類，分類正確率如表3所示。

表3 JAFFE數(shù)據(jù)庫采用各算法降維后的分類正確率

由表2和表3可見，在同一種分類器1－NN下，在各個維度上，KMDA方法識別結(jié)果明顯優(yōu)于經(jīng)典的LDA方法。其中的原因是，LDA方法在區(qū)分低維嵌入過程中，不同類間的分離是采用全局性嵌入，即在計算Sb時，用總體的均值減去每一類的均值，最后選取Sb的d個最大的特征值所對應的特征向量作為投影軸進行特征抽取，這樣處理的結(jié)果可以使不同類之間遠離的效果，但是容易忽略類間邊緣局部點的類間劃分，從而導致邊緣點的誤分;KMDA算法考慮到局部邊緣點，計算Sb過程，首先選擇最近的也是最容易誤分的這些邊緣點，使其遠離異類的中心，而從表可看出，這種鑒別信息的方法是有效的。另外，當降到某個維數(shù)時三種算法最后的分類效果較差，如JAFFE數(shù)據(jù)庫中，采用PCA+LDA，降到4維時分類正確率只有0.2，原因在于LDA和PCA都是全局性線性降維算法，而人臉數(shù)據(jù)庫是一種非線性結(jié)構，這些方法在處理這些數(shù)據(jù)時，容易忽略局部數(shù)據(jù)信息。從整體看來，本文提出的算法效果較好。

4 結(jié)論

針對LDA在處理邊緣點上存在的問題，本文提出了一種新的基于圖的線性判別分析方法。該方法基于圖學習的思想，重新構造圖，使同類樣本盡量緊湊的同時，避免了不同類之間邊緣點的誤分。實驗中可以看出，新方法在降維過程中的分類正確率以及穩(wěn)定性較好，與LDA方法相比有一定提高;不足之處在于K的選擇上，本文實驗K的選擇是在從大量實驗中得出的經(jīng)驗值。如何有效選擇K值達到更好的效果是接下來要研究的內(nèi)容。

[1]KOKIOPOULOU E，SAAD Y.Enhanced graph－based dimensionality reduction with repulsion Laplaceans[J].Pattern Recognition，2009，42(11):2392－2402.

[2]王飛.圖上的半監(jiān)督學習算法研究[D].北京:清華大學，2008.

[3]喬立山.基于圖的降維技術研究及應用[D].南京:南京航天航空大學，2009.

[4]TENENBAUM J B，SILVA V D，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290:2319－2322.

[5]ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290:2323－2326.

[6]李白燕，李平，陳慶虎.基于改進的監(jiān)督LLE人臉識別算法[J].電視技術，2011，35(19):105－108.

[7]BELKIN M，NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation，2003，15(6):1373－1396.

[8]邊肇祺，張學工.模式識別[M].北京:清華大學出版社，2000.

[9]申中華，潘永惠，王士同.有監(jiān)督的局部保留投影降維算法[J].模式識別與人工智能，2008，21(2):233－239.

[10]XU D，YAN S，TAO D，et al.Marginal fisher analysis and its variants for human gait recognition and content－based image retrieval[J].IEEE Trans.Image Processing，2007，16(11):2811－2821.

[11]ARTINEZ A M，KAK A C.PCA versus LDA[J].IEEE Trans.Pattern Analysis and Machine Intelligence，2001，23(2):228－233.

[12]羅丞，葉猛.PCA算法在P2P加密流量識別中的研究與應用[J].電視技術，2012，36(3):62－65.