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

王 飛，劉玉英，彭 超

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

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

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

1 線性判別分析(LDA)

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

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

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

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

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

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

2.1 類內緊湊

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

2.2 類間遠離

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

2.3 構造投影矩陣

通過前兩節圖的構造以及優化后的公式，最終得到求解以下的優化問題

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

具體算法如下:

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

2)構造如圖1所示的類內和類間圖求出最優化向量wopt。

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

3 實驗分析

3.1 可視化分析

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

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

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

3.2 公共數據集測試

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

表1 各個數據集實驗參數

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

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

3.3 人臉數據集測試

3.3.1 BioID 數據庫

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

圖4 BioID人臉庫的部分圖像

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

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

3.3.2 JAFFE 數據庫

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

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

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

4 結論

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

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

[2]王飛.圖上的半監督學習算法研究[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]李白燕，李平，陳慶虎.基于改進的監督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]申中華，潘永惠，王士同.有監督的局部保留投影降維算法[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.