第6章圖方法6.1圖的基本概念6.2相似性計算6.3圖嵌入框架6.4圖嵌入的線性擴展6.5圖嵌入的核化擴展6.6

圖嵌入的張量擴展6.7圖嵌入面臨的挑戰(zhàn)

6.1圖的基本概念

1.圖的定義

由若干給定的頂點及連接兩頂點的邊(線)所構(gòu)成的圖形即為圖論中圖的定義。圖6-1描述了一個簡單的圖,圖中用點表示頂點,用點之間的連線表示邊。同時,圖是一種拓撲圖形。一般地,這種圖形中的頂點代表事物,連接兩點的邊代表與兩個頂點相應(yīng)的兩個事物間的某種關(guān)系,這樣,可以用圖來描述某些事物之間的某種特定關(guān)系。圖6-1簡單的圖

總的來說,一個圖包括頂點集合和邊,具體如下:

(1)頂點集合V。頂點代表圖中相互關(guān)聯(lián)的事物或個體,是圖的基本元素。圖6-1中可以用vi、vj來分別表示第i、j個頂點。同時,令V(G)={v1,v2,…,vn}表示頂點的集合V。

(2)邊E。圖中連接兩個頂點的連線稱為邊。圖6-1中eij={vi,vj}為連接第i、j個頂點的邊,即為i、j兩個頂點之間的聯(lián)系。同時,令E(G)={e1,e2,…,em}表示邊的集合E。另外,邊又分為有向邊和無向邊,當(dāng)圖6-1中邊eij={vi,vj}為有向邊時,則vi為起點,vj為終點。一般情況下,圖G表示為G=<V,E>,每條邊對應(yīng)著一對頂點,即E?V×V。一系列的頂點V和連接這些頂點的邊E的集合為數(shù)學(xué)上對圖G的定義。

2.鄰接結(jié)點和鄰接邊

圖6-1中由一條邊連接的兩個結(jié)點稱為鄰接結(jié)點,由同一個結(jié)點連接的兩個邊稱為鄰接邊。

3.圖的矩陣表示

可以用矩陣來表示圖的頂點與邊之間的關(guān)聯(lián)性質(zhì),圖的矩陣表示的優(yōu)勢主要有:

(1)給出了圖的一種表示方法;

(2)可以借助對圖的矩陣的研究結(jié)論,得出圖的有關(guān)性質(zhì);

(3)由于矩陣的計算更便于計算機處理,運算和操作圖可以直接轉(zhuǎn)為對圖的矩陣的處理。

一般選擇鄰接矩陣表示圖。頂點與頂點之間的鄰接關(guān)系即為鄰接矩陣。圖的鄰接矩陣的定義如下:

頂點V={v1,v2,…,vn},邊E={e1,e2,…,em},圖G=<V,E>,可以用一個n×n的矩陣A(G)表示圖G=<V,E>,其中,矩陣A(G)中第i行、第j列的元素為

從矩陣的定義中可以看出鄰接矩陣為對稱陣。

圖6-2給出了有向圖和無向圖以及它們分別用鄰接矩陣表示的例子。圖6-2圖及其鄰接矩陣的表示

如果圖G=<V,E>中的邊帶有權(quán)值(weight),則可用一個n×n的矩陣W來表示,矩陣中第i行、第j列的元素定義為

同樣地,權(quán)值矩陣W為對稱陣,即wij=wji。

常用的兩種建立圖形的方法有k鄰域圖和ε鄰域圖。對于一個訓(xùn)練樣本集X={x1,x2,…,xn},設(shè)N(xi)表示為xi

的近鄰點表示的集合,則X上的無向鄰域圖G=<V,E>定義如下:頂點集V=X,當(dāng)且僅當(dāng)xj∈N(xi

)或xi∈N(xj),存在xi

和xj相連接的邊,按照上述定義得到的無向鄰域圖稱為k鄰域圖。若N(xi

)={xj|dij<ε},其中dij定義為xi

和xj之間的距離,ε是一個參數(shù),按照上述準(zhǔn)則建立的無向鄰域圖稱為ε鄰域圖?？捎脠D6-3直觀表示k鄰域圖和ε鄰域圖的具體建立方法。圖6-3兩種圖形建立方法

1.高斯核

式中,t為高斯核參數(shù),它可以控制權(quán)值的大小,當(dāng)t→∞時,高斯核就會簡化為一個二值圖,也就是

2.歐氏距離的倒數(shù)

xi和xj之間的距離越大,兩者之間的權(quán)值越小;當(dāng)距離趨近于無窮大時,兩者之間的權(quán)值為0;當(dāng)兩者之間的距離趨于0時,得到的兩者之間的權(quán)值大小趨近于無窮大。

3.局部線性重構(gòu)系數(shù)

Roweis和Saul于2000年提出LLE算法,該算法能夠找到嵌入在高維數(shù)據(jù)空間中的低維光滑流形,它主要利用局部線性來逼近全局非線性,通過相互重疊的局部鄰域來提供整體的信息,從而保持整體的幾何性質(zhì)。利用歐氏距離作為測度,尋找每個高維數(shù)據(jù)點xi

的k最近鄰數(shù)據(jù)點,其組成的集合用N(xi

)表示。

LLE算法是基于假設(shè)每個樣本點都可由近鄰的樣本點線性表示,因此可用重構(gòu)誤差作為成本函數(shù)來衡量,可表示為

式中,每個數(shù)據(jù)點只能通過它鄰域內(nèi)的數(shù)據(jù)點來構(gòu)造,當(dāng)某個數(shù)據(jù)點不屬于此鄰域內(nèi)時,Wij=0。此外,還約束權(quán)值矩陣每一行的所有元素之和等于1。

6.2相似性計算

除了確定構(gòu)建什么類型的圖,還需要確定如何計算圖中連接各個頂點之間的邊的權(quán)值,也就是構(gòu)建權(quán)值矩陣。權(quán)值矩陣中的權(quán)值是樣本之間相似性的具體反映,而在計算樣本之間的相似性時,通常使用第3章有關(guān)的歐氏、明氏、馬氏等方法,還可以使用以下方法:

(1)負指數(shù)法或RBF核函數(shù)法:任意兩個數(shù)據(jù)點xi、xj之間的相似性定義為

式中,α為常量。

(2)正切值法:任意兩個數(shù)據(jù)點xi、xj之間的相似性定義為

式中,α1、α2為常量。

除了上述幾種相似性計算方法外,還有不少研究者提出應(yīng)該根據(jù)數(shù)據(jù)流形或密度等特性來衡量數(shù)據(jù)點之間的相似性。如Chapelle提出一種基于密度的距離,他指出兩個數(shù)據(jù)點之間的距離應(yīng)該是連接它們的所有路徑中的最短路徑距離,這種方法得出的距離可以看成是一種體現(xiàn)數(shù)據(jù)流形的距離,同時也隱含實現(xiàn)了流形假設(shè)。

6.3圖嵌入框架

圖譜理論主要研究圖的鄰接矩陣和拉普拉斯矩陣的特征值與特征向量,圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形,這種圖形通常用來描述某些事物之間的某種特定關(guān)系,用點代表事物,用連接兩點的線表示相應(yīng)兩個事物間具有的某種關(guān)系。

圖嵌入通過定義兩個不同的圖:用來描述數(shù)據(jù)集的某些需要凸顯的統(tǒng)計或幾何性質(zhì)的本征圖(IntrinsicGraph)G(V,W)和用來描述需要保持或者抑制的部分統(tǒng)計或幾何性質(zhì)的懲罰圖(PenaltyGraph)Gp

(V,Wp)來考慮樣本間的關(guān)系。本征圖和懲罰圖具有相同的頂點,但圖的邊權(quán)重矩陣不同。

通過定義不同的本征圖和懲罰圖及其相應(yīng)的邊權(quán)重矩陣,目前常見的降維算法,如PCA、LDA、ISOMAP、LLE、LE等均可統(tǒng)一到圖嵌入框架下。

式(6-10)給出了圖嵌入算法的最基本形式,相應(yīng)地,圖嵌入算法也有多種擴展,如線性化、核化及張量化。圖6-4給出了圖嵌入算法的統(tǒng)一框架及可能的擴展方向。圖6-4圖嵌入算法的統(tǒng)一框架

圖嵌入算法的相似度保留特性可以從以下兩個方面來解釋:一方面如果兩個點之間的相似度很大,為了使圖嵌入算法的目標(biāo)函數(shù)最小化,兩個點之間的距離就應(yīng)該更小;另一方面,如果兩個點之間的相似度很小甚至是負值,只有當(dāng)兩個點之間的距離很大的時候才能使得圖嵌入算法的目標(biāo)函數(shù)更小。

6.4圖嵌入的線性擴展

為了得到測試點的低維嵌入,圖嵌入框架給出了線性化、核化及張量化的擴展。先看圖嵌入的線性擴展:假定圖嵌入中的映射是線性的,即

則可以推導(dǎo)出線性圖嵌入算法。把式(6-11)給出的線性映射代入到式(6-10),則可得到線性圖嵌入算法的目標(biāo)函數(shù)

或者

其可轉(zhuǎn)化為最小化問題

由拉格朗日乘數(shù)法,上式可轉(zhuǎn)化為廣義特征值問題:

6.4.1主成分分析

主成分分析(PCA)是最為經(jīng)典、應(yīng)用最為廣泛的線性特征提取方法之一。其主要思想是在全局最小重構(gòu)誤差的意義下把高維觀測數(shù)據(jù)投影到低維主子空間上,高維觀測數(shù)據(jù)在子空間上的投影坐標(biāo)就是對應(yīng)的低維表示。

設(shè)觀測數(shù)據(jù)集為{xi=f(yi

)}?RD,共有n個樣本,采樣自d維嵌入流形,Y={yi}是包含在歐氏空間Rd的在嵌入流形上對應(yīng)的低維坐標(biāo),y=XTa,a為投影向量。則PCA算法就是尋找d個正交單位投影向量{a1,a2,…,an}=A,作為低維空間的正交基,使得從低維空間重構(gòu)高維數(shù)據(jù)的重構(gòu)誤差平方和最小,也就是最大化整體方差,PCA算法的目標(biāo)函數(shù)為

設(shè)數(shù)據(jù)集的均值為m,令St為數(shù)據(jù)集的總體散度矩陣,其定義為

則數(shù)據(jù)集的協(xié)方差矩陣C可表示為

由拉格朗日乘數(shù)法,式(6-16)的解等價于

由式(6-27)可見,當(dāng)圖的邊權(quán)重矩陣定義如式(6-25)時,數(shù)據(jù)集的協(xié)方差矩陣可以由圖的拉普拉斯矩陣表示。PCA尋求能夠使得方差最大的投影方向,而圖嵌入算法尋求數(shù)據(jù)集相似性,因此PCA中的最大化問題可以轉(zhuǎn)換為去除圖嵌入算法的相似性的最小化問題,投影向量可按照特征值由大到小的順序排列最小化問題的特征向量求得。

6.4.2線性判別分析

在線性映射中,投影非常關(guān)鍵,相同的樣本在向不同方向作投影時,產(chǎn)生的結(jié)構(gòu)的可分性會有顯著的不同。圖6-5給出了在二維空間上的示例。圖6-5樣本在二維空間投影示例

設(shè)觀測數(shù)據(jù)集為{xi=f(yi

)}?RD

,共有n個樣本,分屬于c個類別,采樣自d維嵌入流形,Y={yi}是包含在歐氏空間R＋在嵌入流形上對應(yīng)的低維坐標(biāo),y=XTw,w為投影向量。

既然不同的投影方向會產(chǎn)生不同的分類效果,如何確定這樣最佳的投影方向w就是我們關(guān)注的焦點。一個可以用來衡量投影結(jié)果可分性程度的標(biāo)準(zhǔn)是不同類樣本的差。

設(shè)mi表示第i類的樣本均值

當(dāng)樣本投影到特征空間后,該類數(shù)據(jù)的樣本均值也是原樣本均值mi的投影

從而得到投影到特征空間后數(shù)據(jù)集中兩類樣本的均值差

可見當(dāng)投影向量的幅值一定時,投影后的兩類樣本之間的均值差從一定程度上反映了數(shù)據(jù)的可分性,其數(shù)值越大說明兩類相距越遠。但是這個均值差不但受到投影向量的幅值影響,而且與數(shù)據(jù)的分布有關(guān)。

LDA算法定義了三個散度矩陣:類內(nèi)散度矩陣、類間散度矩陣及總體散度矩陣。

(1)類內(nèi)散度矩陣(WithinclassScatterMatrix)定義:

式中,mi為每類的均值。

(2)類間散度矩陣(Between-classScatterMatrix)定義:

式中,m為總體均值。

LDA算法的目標(biāo)函數(shù)可以表示為

(3)總體散度矩陣等于類內(nèi)散度和類間散度的和,即

從而LDA算法的目標(biāo)函數(shù)等價于

由拉格朗日乘數(shù)法,上述優(yōu)化問題可通過求解如下廣義特征值問題獲得

6.4.3邊界費舍爾分析

MFA中定義的本征圖把每個樣本點和與其同類別的近鄰點連接起來,表示類內(nèi)的緊致度;而懲罰圖把每個樣本點與其不同類別的近鄰點連接起來,表示類間的可分性。MFA算法的目的就是利用樣本的局部關(guān)系,使得類間可分性增加的同時保持類內(nèi)的緊致度。

因此可得MFA算法的目標(biāo)函數(shù):

MFA是基于局部數(shù)據(jù)關(guān)系的監(jiān)督鑒別方法,它有兩個最近鄰近點數(shù)量的參數(shù)k1和k2

要調(diào)整,相比LDA增加了算法的復(fù)雜性。

6.5圖嵌入的核化擴展

根據(jù)模式識別理論,低維空間線性不可分的模式通過非線性映射到高維特征空間則可能實現(xiàn)線性可分或者近似線性可分,如圖6-6所示。設(shè)K是Gram矩陣,則圖6-6-數(shù)據(jù)在原始空間中線性不可分,映射到核空間后線性可分

當(dāng)數(shù)據(jù)集在原始空間是線性不可分時,通過一個非線性映射到更高維的特征空間,在更高維的特征空間中線性可分或者近似線性可分,設(shè)圖嵌入的核函數(shù)擴展中的Gram矩陣定義如式(6-50),在非線性映射后的高維空間中的投影向量為

則此時圖嵌入算法的目標(biāo)函數(shù)為

從而上式轉(zhuǎn)換為廣義特征值問題的求解:

6.6-圖嵌入的張量擴展

線性化與核擴展方式都是以提取的特征向量形式表征圖上頂點之間的聯(lián)系的,但是在實際應(yīng)用中,可能在目標(biāo)中提取的特征包含高階結(jié)構(gòu)信息。

如果B通過懲罰圖來計算,例如B=Lp=Dp-Wp,則

下面介紹2DLDA算法

設(shè)A為一個m×n像素的隨機圖像矩陣,x為一個待選定的n維列向量,代表n維的空間向量。A可以通過下式被投影到x上:

從而得到一個m維的向量y,稱其為圖像A的一個特征向量。

從而,2DLDA的目標(biāo)函數(shù)可以表示為

上述問題可轉(zhuǎn)化為廣義特征值問題

現(xiàn)在再來看圖嵌入框架的張量化擴展,張量化擴展把數(shù)據(jù)從向量形式擴展為任意階張量,圖的定義不變,對數(shù)據(jù)的運算引入了張量分析,既然LDA可以用線性圖嵌入框架解釋,那么2DLDA也同樣可以用圖嵌入的張量化擴展來解釋,2D只是張量的一個特定階數(shù)。

6.7圖嵌入面臨的挑戰(zhàn)

1.局部與類別的矛盾通常,局部型降維方法假設(shè)樣本位于或近似位于嵌入在高維空間的低維流形,并滿足光滑性假設(shè)。然而,這往往局限于理想情形或人工數(shù)據(jù)(如SwissRole),實際情況遠非如此。

2.揮之不去的維數(shù)災(zāi)難

多數(shù)局部型降維方法基于k近鄰準(zhǔn)則建圖,這將導(dǎo)致后續(xù)工作(降維、分類或聚類等)嚴(yán)重依賴于最近鄰準(zhǔn)則在原始空間的性能。通常,我們期望一個好的“近鄰圖”能潛在地使同類樣本相連,異類樣本不連。然而,不幸的是,最近鄰準(zhǔn)則往往需要大量訓(xùn)練樣本,并且在很多情形下不適合在原始高維空間工作。如此一來,雖然降維的目的之一是為了克服維數(shù)災(zāi)難,但局部型算法自身卻受維數(shù)災(zāi)難的困擾,