王 飛，劉玉英，彭 超

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

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

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

1 線性判別分析(LDA)

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

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

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

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

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

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

2.1 類內(nèi)緊湊

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

2.2 類間遠(yuǎn)離

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

2.3 構(gòu)造投影矩陣

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

當(dāng)Sc非奇異時(shí)，最佳投影矩陣wopt的列向量為廣義特征方程Spα=λScα的d個(gè)最大的特征值所對應(yīng)的特征向量。

具體算法如下:

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

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

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

3 實(shí)驗(yàn)分析

3.1 可視化分析

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

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

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

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

選取UCI中Wine數(shù)據(jù)集、Sonar數(shù)據(jù)集、Abalone數(shù)據(jù)集和Diabetes數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)，表1列出了每個(gè)數(shù)據(jù)集的實(shí)驗(yàn)參數(shù)。為達(dá)到對比的效果，本文降維后的分類器均選擇1－NN分類，實(shí)驗(yàn)結(jié)果如圖3所示，縱坐標(biāo)表示降維之后采用1－NN分類的正確率，橫坐標(biāo)表示所降到的維數(shù)，實(shí)驗(yàn)?zāi)康氖潜容^3種算法在不同數(shù)據(jù)集降維后的分類正確率。

表1 各個(gè)數(shù)據(jù)集實(shí)驗(yàn)參數(shù)

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

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

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

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

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

圖4 BioID人臉庫的部分圖像

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

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

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

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

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

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

4 結(jié)論

針對LDA在處理邊緣點(diǎn)上存在的問題，本文提出了一種新的基于圖的線性判別分析方法。該方法基于圖學(xué)習(xí)的思想，重新構(gòu)造圖，使同類樣本盡量緊湊的同時(shí)，避免了不同類之間邊緣點(diǎn)的誤分。實(shí)驗(yàn)中可以看出，新方法在降維過程中的分類正確率以及穩(wěn)定性較好，與LDA方法相比有一定提高;不足之處在于K的選擇上，本文實(shí)驗(yàn)K的選擇是在從大量實(shí)驗(yàn)中得出的經(jīng)驗(yàn)值。如何有效選擇K值達(dá)到更好的效果是接下來要研究的內(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)督學(xué)習(xí)算法研究[D].北京:清華大學(xué)，2008.

[3]喬立山.基于圖的降維技術(shù)研究及應(yīng)用[D].南京:南京航天航空大學(xué)，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]李白燕，李平，陳慶虎.基于改進(jìn)的監(jiān)督LLE人臉識(shí)別算法[J].電視技術(shù)，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]邊肇祺，張學(xué)工.模式識(shí)別[M].北京:清華大學(xué)出版社，2000.

[9]申中華，潘永惠，王士同.有監(jiān)督的局部保留投影降維算法[J].模式識(shí)別與人工智能，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加密流量識(shí)別中的研究與應(yīng)用[J].電視技術(shù)，2012，36(3):62－65.