基于矩陣模式的局部子域最大間距判別分析

黃麗莉

(1.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001; 2.鹽城工學(xué)院 信息學(xué)院，江蘇 鹽城 224051)

智能識別領(lǐng)域存在著大量需要處理的高維數(shù)據(jù)樣本，為了便于從中找出我們最需要的信息，就需要進行特征降維，將一些冗余的信息進行處理。特征提取作為一種數(shù)據(jù)預(yù)處理方法得到了廣泛的運用[1]。一般經(jīng)典的特征提取方法，如：PCA[2,3]，LDA[4,5]方法都是在高維向量空間上進行特征提取。然而，在現(xiàn)實的空間中，將圖像矩陣樣本轉(zhuǎn)換為向量的過程中，破壞了圖像矩陣樣本原有的幾何結(jié)構(gòu)，導(dǎo)致一些有用信息的損失。

近年來基于矩陣模式的特征提取算法(如文獻[6-8])由于能有效地提高識別率、節(jié)省計算時間，被廣泛的研究。如文獻[6]提出的矩陣模式的Fisher線性判別準則(MatFLDA)、矩陣模式的主成份分析方法(MatPCA)不但在處理圖像數(shù)據(jù)時使用矩陣模式，盡可能地保留原始的數(shù)據(jù)信息，而且，提出一種將矢量數(shù)據(jù)轉(zhuǎn)換成矩陣模式的方法，大大擴展了矩陣模式的應(yīng)用范圍。

矩陣模式的Fisher線性判別準則(MatFLDA) 雖然避免了基于向量方法的缺點，具有較好的特征提取能力，然而，MatFLDA方法作為全局判別準則，算法中使用總體均值來替代方差，對于那些具有明顯局部流形的數(shù)據(jù)，比如人臉數(shù)據(jù)、高維文本數(shù)據(jù)等等，MatFLDA方法一定程度上缺乏適應(yīng)性。為了確保樣本數(shù)據(jù)的局部信息，我們在本文的方法構(gòu)造中引入局部保持投影(Locality Preserving Projections, LPP)[9]流形學(xué)習(xí)方法中通過嵌入樣本的最近鄰圖，提取樣本空間的局部結(jié)構(gòu)信息這一思想。

本文在MatFLDA基礎(chǔ)上，引入局部加權(quán)均值(Local Weighted Mean,LWM)[10]的概念，提出一種具有局部學(xué)習(xí)能力的特征提取方法：基于矩陣模式的局部子域最大間距判別分析(Local Sub-domains Maximum Margin Criterion Based Matrix Pattern,Mat-LSMMC)。該方法具有如下優(yōu)勢：(1)Mat-LSMMC方法運用了矩陣模式，提高了特征提取能力，大大降低了空間復(fù)雜度，同時消除了一般行(列)向量所帶來的限制；(2)Mat-LSMMC方法使用了最大間距準則(Maximum Margin Criterion,MMC)[11,12]，避免小樣本問題[13]；(3)Mat-LSMMC方法中用LWM替代標準均值，一定程度上較好地反映不同樣本在保持內(nèi)在局部結(jié)構(gòu)方面的貢獻程度大小，實現(xiàn)了局部保持。

在實驗中，通過測試傳統(tǒng)的UCI數(shù)據(jù)集和人臉識別數(shù)據(jù)集，表明本文的Mat-LSMMC方法具有上述優(yōu)勢。

1 相關(guān)工作

為了便于描述，我們在本節(jié)簡單回顧一下LWM、MatFLDA方法的概念。

1.1 局部加權(quán)均值:LWM

從定義1可以看出，LWM是通過給在局部子域中的樣本分配不同權(quán)值來表示不同樣本在保持內(nèi)在局部結(jié)構(gòu)所反映的貢獻程度的不同。

1.2 矩陣線性判別分析 MatFLDA

定義2 (MatFLDA)：假設(shè)有n個樣本組成的樣本集A={A1,…,An}，Ai(i=1,2,…,n)均是矩陣模式，分別屬于C個不同的類，第c類大小為nc，給定分類決策平面的法向量ω。則MatFLDA的類內(nèi)、類間散度矩陣和目標函數(shù)為：

2 基于矩陣模式的局部子域最大間距判別分析：Mat-LSMMC

在矩陣模式的基礎(chǔ)上，結(jié)合局部加權(quán)子域的概念，本文提出了一種新的算法Mat-LSMMC，見圖1。我們用文獻[6]的方法將每個矢量數(shù)據(jù)轉(zhuǎn)換為矩陣模式，在樣本數(shù)據(jù)中結(jié)合1.1節(jié)中局部加權(quán)均值LWM的概念，運用流形學(xué)習(xí)算法中的局部保存思想將數(shù)據(jù)有效劃分為各個局部加權(quán)子域，尋找每個局部加權(quán)子域的類內(nèi)最近鄰局部子域(Within-class Nearest Neighbor Local Sub-domains,WNNLSD)和類間最近鄰局部子域(Between-class Nearest Neighbor Local Sub-domains,BNNLSD)，構(gòu)造對應(yīng)的具有明顯幾何含義的矩陣模式類內(nèi)散度和類間散度。

圖1 Mat-LSMMC原理圖Fig.1 The schematic diagram of Mat-LSMMC

下面定義本文Mat-LSMMC方法的類內(nèi)散度矩陣和類間散度矩陣。

(1)

(2)

則本文Mat-LSMMC方法的目標函數(shù)為：

(3)

為了提高本文Mat-LSMMC方法求解目標函數(shù)的效率，我們對式(1)、式(2)進行改寫和簡化，由此，我們得到如下定理。

定理1 根據(jù)定義3，式(1)、式(2)分別可以簡化為：

(4)

(5)

其中：

則式(1)可以表示為：

則式(4)成立。

算法：基于矩陣模式的局部子域最大間距判別分析。

Algorithm：Mat-LSMMC

Input:數(shù)據(jù)集X，并給kc，h賦初值；

Output:變換矢量ω；

Step1:對矢量表示的樣本根據(jù)文獻[6]的方法轉(zhuǎn)換成矩陣模式；

Step2:根據(jù)給定的kc，將數(shù)據(jù)集A劃分成若干個局部子域；

Step4:根據(jù)定義3，構(gòu)造相應(yīng)的類內(nèi)散度矩陣和類間散度矩陣；

Step5:根據(jù)定理1，求解式(3)，得到滿足式(3)最大特征值對應(yīng)的矢量ω。

3 實驗

通過測試4個UCI數(shù)據(jù)子集(即：IRIS、Ionosphere、Wine、Glass)、兩個人臉識別數(shù)據(jù)集(ORL、Yale)來說明Mat-LSMMC方法具有較好的特征提取能力。在實驗過程中都使用最近鄰分類器。

3.1 測試UCI數(shù)據(jù)集

通過測試4個UCI數(shù)據(jù)子集(見表1)來說明Mat-LSMMC方法具有較好的特征提取能力，并將Mat-LSMMC方法同MatPCA、MatFLDA、MatMMC 3種特征提取方法進行比較。測試過程中Mat-LSMMC的參數(shù)：K∈[2,5]，h∈2t，t∈(-500,500),γ∈(0,1)，使用10-折交叉驗證。測試結(jié)果見表2。

表1 Ionosphere、IRIS、Wine、Glass數(shù)據(jù)集
Table1IonosphereIRIS,Wine,Glass,datasets

DatasetsThe Number of Training SamplesThe Number of Test SamplesThe Number ofFeaturesThe Number of SubjectsMatrix ModelIonosphere23011733211×3IRIS10050432×2Wine1186012310×6Glass14272963×3

從表2，我們可以得到以下結(jié)論：

(1)Mat-LSMMC同其他3種方法相比,其精度較大。說明Mat-LSMMC方法具有較好的特征提取。Mat-LSMMC方法中運用了局部流形學(xué)習(xí)方法中構(gòu)造近鄰拉普拉斯圖的方法，實現(xiàn)了局部保持，提高了特征提取效果和分類精度。

(2)Mat-LSMMC由于是基于矩陣模式下的特征提取方法，空間復(fù)雜度較低。

(3)Mat-LSMMC方法由于使用了最大間距準則，避免了matFLDA方法的小樣本問題。

3.2 測試人臉數(shù)據(jù)

人臉圖像數(shù)據(jù)集蘊含著內(nèi)在的非線性流形結(jié)構(gòu)。通過測試ORL(32×32)(40個類，每類10個樣本)和Yale(32×32)(15個類，每類11個樣本)兩個人臉圖像數(shù)據(jù)集來表明Mat-LSMMC方法在一定程度上能解決小樣本問題，具有較好的特征提取能力。

在測試過程中,為了有效說明Mat-LSMMC方法的優(yōu)勢，我們使用PCA、MatPCA、MatFLDA、MatMMC 4種方法來對比測試，Mat-LSMMC參數(shù)的設(shè)定同3.1。測試結(jié)果見表3。

表2對Ionosphere 、IRIS、Wine、Glass數(shù)據(jù)集的識別效果比較
Table2ReoognitionperformancecomprisononIonosphereIRIS,Wine,Glassdatasets

DatasetsAlgorithmMatPCAMatFLDAMatMMCMat-LSMMCIonosphereAccuracy0.906 00.863 20.897 40.9316(K=3;h=25;γ=0.3)IRISAccuracy0.940.940.961(K=5;h=2-3;γ=0.5)WineAccuracy0.716 70.733 30.766 70.8(K=5;h=2-10;γ=0.25)GlassAccuracy0.833 330.805 60.847 20.875(K=3;h=2-5;γ=0.1)

表3對ORL、Yale數(shù)據(jù)集識別效果比較
Table3ThecomparisonofORL,Yaledatasetrecognitioneffect

DatasetsORLYaleNumber of Train Samples4646AlorightmAccuracyAccuracyAccuracyAccuracyPCA0.854 170.887 50.638 10.666 67MatPCA0.8750.90.66670.7067MatFLDA0.908 30.90.676 20.773 3MatMMC0.912 50.931 30.695 20.786 7Mat-LSMMC0.9208(K=5;h=2300;γ=0.25)0.9437(K=3;h=2500;γ=0.875)0.7048(K=5;h=2200;γ=0.1)0.8133(K=5;h=2200;γ=0.875)

為了提高測試結(jié)果的有效性，在測試過程中分別對ORL、Yale數(shù)據(jù)集選取4個、6個樣本作為訓(xùn)練樣本來測試上述4種方法，并分別使用4-折交叉驗證和6-折交叉驗證。

根據(jù)上述結(jié)果，我們可以得到如下結(jié)論：

(1)Mat-LSMMC方法在處理人臉數(shù)據(jù)時，比其他方法具有更好的特征提取效果和分類精度,說明此方法由于引入了LWM來替代標準均值，較好地反映了不同樣本在保持樣本內(nèi)在局部結(jié)構(gòu)方面的貢獻程度的差異，更好地保持樣本內(nèi)在蘊含的幾何結(jié)構(gòu)。

(2)Mat-LSMMC方法處理32×32圖像數(shù)據(jù)集時，直接使用矩陣模式，如果用矢量形式表示，則需要存儲1 024×1 024的散度矩陣，而本文的方法則只需要存儲32×32散度矩陣，所占空間只是原方法的1/1 024，大大降低了空間復(fù)雜度。

(3)Mat-LSMMC方法使用了最大間距判別分析，不存在小樣本問題。

4 總結(jié)

本文在矩陣模式的基礎(chǔ)上，提出了具有一定局部學(xué)習(xí)能力的Mat-LSMMC方法。該方法結(jié)合局部加權(quán)均值概念，使用流形學(xué)習(xí)理論對原樣本空間進行有效劃分，一定程度上提高了算法的局部學(xué)習(xí)能力。同時，由于采用矩陣模式使得算法空間復(fù)雜度大大的降低。最后通過測試人造、真實數(shù)據(jù)集來表明本文Mat-LSMMC方法具有較強的特征提取能力。當(dāng)然，Mat-LSMMC方法也存在著一定的不足，比如如何更好地確定近鄰參數(shù)和熱核參數(shù)，更有效地提高該方法的執(zhí)行效率，將是我們以后研究的方向。

參考文獻：

[1] Bian Z Q, Zhang X G. Pattern Recognition[M].Beijing: TsingHua University Press, 2001.

[2] Jolliffe I T. Principal Component Analysis[M].New York: Springer-Verlag, 1986.

[3] Todorov, Valentin, Filzmoser, et al. Comparing classical and robust sparse PCA[C].Advances in Intelligent Systems and Computing. Berlin:Springer Verlag, 2013:1 283-1 291.

[4] Li Ronghua, Liang Shuang, Baciu George, et al. Equivalence between LDA/QR and direct LDA[J].International Journal of Cognitive Informatics and Natural Intelligence,2011,5(1):94-112.

[5] Dhir Chandra Shekhar, Lee Sooyoung. Discriminant independent component analysis[J].IEEE Transactions on Neural Networks,2011,22(6):845-857.

[6] Chen S C, Zhu Y L, Zhang D Q, et al. Feature extraction approaches based on m atrix pattern: matPCA and matFLDA[J].Pattern Recognition Letters, 2005,26(8):1 157-1 167.

[7] He Xiaofei, Cai Deng, Niyogi Partha.Tensor Subspace Analysis[C].Advances in Neural Information Processing Systems. 2005 Annual Conference on Neural Information Processing Systems. Canada: Neural information processing system foundation, 2005:499-506.

[8] Jun Gao, Chung Fulai, Wang Shitong. Matrix pattern based minimum within-class scatter support vector machines.Applied Soft Computing Journal,2011,11(8):5 602-5 610.

[9] Wong W K, Zhao H T. Supervised optimal locality preserving projection[J].Pattern Recognition, 2012,45(1):186-197.

[10] Atkeson, Christopher G, Moore, et al. Locally weighted learning[J].Artificial Intelligence Review, 1997,11(1-5):75-113.

[11] Yang Wankou, Sun Changyin, Du Helen S, et al. Feature extraction using Laplacian Maximum Margin Criterion[J].Neural Processing Letters, 2011,33(1):99-110.

[12] Cui Yan, Fan Liya. Feature extraction using fuzzy maximum margin criterion[J].Neurocomputing, 2012,86(1):52-58.

[13] Deng Weihong, Liu Yebin, Hu Jiani, et al. The small sample size problem of ICA: A comparative study and analysis[J].Pattern Recognition, 2012,45(12):4 438-4 450.