王化喆，劉 佳，，王 勝

（1.商丘職業(yè)技術(shù)學(xué)院，河南 商丘 476000；2.南京理工大學(xué)，江蘇 南京 210000）

1 圖的定義

一個圖G就是一個有序的三元組（V（G），E（G），ΨG），其中V（G）是非空的頂點集，內(nèi)部元素稱為圖G的頂點，E（G）是不相交的邊集，內(nèi)部的元素稱為圖G的邊.ΨG稱為關(guān)聯(lián)函數(shù)，它使G的每條邊對應(yīng)于G的無序頂點對.如圖1所示：

圖1 圖G的結(jié)構(gòu)

2 圖嵌入

G＝｛X，W｝是一個圖，其中X為頂點集，W 為相似度矩陣，W ∈RN×N.Wij度量數(shù)據(jù)點Xi與Xj的相似度，如果Wij＝0就認(rèn)為點xi，xj的相似度為0.W 可以依據(jù)不同的準(zhǔn)則來定義.圖G的對角矩陣D和拉普拉斯（Laplacian）矩陣L定義如下：

該文的圖嵌入定義如下：

設(shè)向量x∈RD，y∈Rd，（d?D），x→y，并且數(shù)據(jù)集Y能夠很好地保持原來數(shù)據(jù)集X相似關(guān)系（即圖G）.假設(shè)數(shù)據(jù)集X的本質(zhì)圖為G，懲罰圖為Gp.圖結(jié)構(gòu)保持準(zhǔn)則定義如下：

其中L定義如公式（1），限制條件yTBy＝d用來獲得最優(yōu)的數(shù)據(jù).

B的定義如下：若只有本質(zhì)圖時B＝D，此時B作為一個圖歸一化矩陣；當(dāng)有懲罰圖時B＝LP＝DPWP，DP定義如公式（2），此時B作為一個懲罰項.圖結(jié)構(gòu)保持含義如下：原始數(shù)據(jù)相似度較小的點相似度變小，原始數(shù)據(jù)相似度較高的點映射之后相似度變大.

由于上述圖結(jié)構(gòu)保持準(zhǔn)則只計算出訓(xùn)練樣本的低維嵌入，而不是全體樣本的.因此，下面介紹一種線性化的嵌入映射［1］2323－2325.

設(shè)向量x∈RD，y∈Rd，（d?D），x→y＝，P為映射變換向量。此時公式（2）可變化為下式：

歸一化后的映射變換向量P，即為映射變換的方向?？梢酝ㄟ^核化來計算非線性映射變換向量，通過張量化來計算映射變換矩陣.

3 基于圖嵌入的算法分析

3.1 主成分分析

主成分分析（Principal Components Analysis，PCA），本質(zhì)上是數(shù)學(xué)統(tǒng)計的特征分析算法，基于PCA算法抽取出的人臉特征——特征臉.基于特征臉的人臉識別算法是較為經(jīng)典的識別算法之一，成為鑒別新算法優(yōu)劣的基準(zhǔn)算法之一［2］40.其基本原理如下：

設(shè)樣本數(shù)據(jù)集X ＝ （x1，x2，…，xN），其中xi∈RD，i＝1，2，…，N.樣本xi的類別標(biāo)簽為ci∈ ｛1，2，…，Nc｝，其中Nc為樣本數(shù)據(jù)集類別數(shù)，第i類的樣本的總數(shù)為ni.PCA尋找最優(yōu)的映射變換矩陣P，將iD空間的數(shù)據(jù)映射到一個相對低維的特征空間id（（d?D））中.

樣本數(shù)據(jù)集的平均值為：

則其協(xié)方差矩陣如下：

其目標(biāo)函數(shù)為：

協(xié)方差矩陣可以推導(dǎo)如下：

3.2 線性鑒別分析

線性鑒別分析（LDA）的主要思想是：計算使得Fisher準(zhǔn)則函數(shù)得到最大值的向量作為映射向量.即使類間散度矩陣和類內(nèi)散度矩陣之商獲得最大值的向量，因此該向量可以通過計算類間散度矩陣和類內(nèi)散度矩陣的廣義特征向量獲得.

最佳鑒別矢量投影矩陣的計算，利用矩陣論相關(guān)知識使該投影矩陣投影后保證有最大類間距和最小類內(nèi)距，即具有最大的可分離性［3］67.因此，它是一種有效的特征抽取方法.其基本原理如下：

設(shè)樣本數(shù)據(jù)集X ＝ （x1，x2，…，xN），其中xi∈RD，i＝1，2，…，N.樣本xi的類別標(biāo)簽為ci∈ ｛1，2，…，Nc｝，其中Nc為樣本數(shù)據(jù)集類別數(shù)，第i類的樣本的總數(shù)為ni.LDA尋找最優(yōu)的映射變換矩陣P，將iD空間的數(shù)據(jù)映射到一個相對低維的特征空間id（d?D）中［4］100.令映射函數(shù)為：

i類樣本均值計算如下：

總體樣本均值：

根據(jù)類間離散度矩陣和類內(nèi)離散度矩陣定義，可以得到如下式子：

與LDA類似，MFA的目標(biāo)函數(shù)如下：

類間離散度矩陣可以變換為：

類內(nèi)離散度矩陣可以變換為：

故LDA的目標(biāo)函數(shù)可以變換為：

由公式（16）可以看出LDA也可以看做一種圖嵌入.

3.3 L1圖及其嵌入

設(shè)數(shù)據(jù)集X＝ （x1，x2，…，xN），其中xi∈RD，i＝1，2，…，N..L1圖的目的是利用訓(xùn)練樣本表示每一個訓(xùn)練樣本，同時要求用來表示每一個測試樣本的訓(xùn)練樣本盡可能的稀疏.

L1計算方法如下：

其中ai∈RN－1；

利用NPE類似的方法可以實現(xiàn)L1圖的嵌入。同時，嵌入映射變換矩陣P可以通過計算下面最小化問題得到：

約束條件為PTXXTP＝1.其中tr表示矩陣的跡，M的定義如下：

4 結(jié)論

通過對PCA，LDA，L1等經(jīng)典算法的代數(shù)推導(dǎo)及對比可以得出，這些經(jīng)典算法都可以利用圖嵌入框架理論來解釋并統(tǒng)一到此種框架中.由此，得出特征提取算法的核心是樣本的圖構(gòu)造，對于降低特征提取算法的計算復(fù)雜度和提高算法的效率有較好的效果［5］189－201.

［1］T.Roweis，L.K.Saul.Nonlinear Dimensionality Reduction by Loeally Linear Embedding［J］.Seienee，2000，290（5500）.

［2］C.Yan，D.Xu，B.Y.Zhang.Graph embedding andextensions：ageneral framework for dimensional－ity reduetion.IEEE Tran［J］.s.on Pattern Analysis and Maehine Intelligenc，2007，29（1）.

［3］黃 鴻.圖嵌入框架下流形學(xué)習(xí)理論及應(yīng)用研究［D］.重慶：重慶大學(xué)，2008.

［4］邊肇棋，張學(xué)工.模式識別（第二版）［M］.北京：清華大學(xué)出版社，2000.

［5］X.F.He，D.Cai.Learning a Maximum Margin SubsPa－ce for Image Retrieval［J］.IEEE Trans.on Knowledge and Data Engineering，2008，20（2）.