第5章非線性特征提取5.1核方法5.2流形學(xué)習(xí)方法

5.1核方法

5.1.1核方法原理

核函數(shù)是一種非線性投影方法,通過引入核函數(shù),原空間中非線性的算法可以在一個高維的空間中用一般的線性算法來實現(xiàn)。高維特征空間中所有的運算都是通過原空間中的內(nèi)積核函數(shù)來實現(xiàn)的。

即任何(線性)只用到向量內(nèi)積的算法都可以通過一個核函數(shù)在特征空間中隱含地進(jìn)行運算。利用此思想在高維特征空間中用一般的線性算法實現(xiàn)相對于原空間來說是非線性的算法,將會大大地提高學(xué)習(xí)算法的效率,還可以改進(jìn)現(xiàn)有算法,提高各類識別任務(wù)的識別率。

對于核函數(shù)與非線性映射φ之間的關(guān)系,根據(jù)Mercer理論可知:一個正定積分算子的任何核都可以按它的特征函數(shù)φi

(λi>0,NH≤∞)進(jìn)行展開,即

這時

對于線性不可分的兩類數(shù)據(jù),通過一個非線性映射φ將原空間的數(shù)據(jù)映射到某個(由內(nèi)積核函數(shù)決定的)高維特征空間中,在高維空間中,數(shù)據(jù)變得線性可分,如圖5-1所示。圖5-1φ將原空間的數(shù)據(jù)映射到某個高維特征空間

構(gòu)造如上映射的方法:

目前常用的滿足Mercer條件的核函數(shù)只有幾種,一般分為兩大類:點積型核函數(shù)和轉(zhuǎn)移不變型核函數(shù)。

(1)多項式內(nèi)積核函數(shù):

式中,核參數(shù)q為多項式的階次,取自然數(shù),屬于點積型核函數(shù)。

(2)徑向基內(nèi)積核函數(shù):

式中,核參數(shù)σ控制核函數(shù)的寬度,屬于轉(zhuǎn)移不變型核函數(shù)。

(3)Sigmoid內(nèi)積核函數(shù):

式中,核參數(shù)k、θ分別控制核函數(shù)的斜率和偏移量,屬于點積型核函數(shù)。

還有一些其他的核函數(shù),如全子集核、高斯核、ANOVA核、集合核、隨機核、最大最小值核等。而根據(jù)核函數(shù)的運算規(guī)則又可以演變出各種形式的組合。要根據(jù)每個核函數(shù)的特點和應(yīng)用范圍及實際情況選擇合適的核函數(shù),這樣既能簡化運算,又可以有效地解決問題。

5.1.2核主成分分析

核主成分分析(KPCA)通過非線性映射,將原始數(shù)據(jù)從數(shù)據(jù)空間變換到特征空間,然后在特征空間中利用統(tǒng)計主元分析求出最佳投影方向,從而獲得非線性特征。

KPCA的基本思想如圖5-2所示。圖5-2KPCA的基本思想

在高維特征空間F進(jìn)行線性PCA變換(見圖5-2(b)),就好像PCA在輸入空間(見圖5-2(a)):因為特征空間F相對于輸入空間是非線性的,因此在輸入空間投影到主本征向量上就稱為非線性。對于KPCA,重要的是實際上并沒有向F空間進(jìn)行映射,而是在輸入空間進(jìn)行了核函數(shù)K的計算。

假定X=(x1,x2,…,xm)是輸入空間的數(shù)據(jù)集,其中xi(i=1,2,…,m)是d維向量,m是數(shù)據(jù)集中的總樣本數(shù)。存在一個函數(shù)φ把數(shù)據(jù)映射到高維(甚至無限維)的再生核希爾伯特空間(RKHS)。

使用這個映射函數(shù)φ,我們可以得到特征空間的數(shù)據(jù)集Φ(X)=(φ(x1),φ(x2),…,φ(xm

)),這樣在映射的特征空間協(xié)方差定義為

它符合特征方程:

式中,v和λ分別對應(yīng)協(xié)方差矩陣的特征向量和特征值。因為一般情況下映射函數(shù)并不知道,而且映射的空間是高維甚至是無限維,因此在特征空間中計算協(xié)方差是最難以處理的,正如前面所介紹的那樣,利用核技巧,采用核函數(shù)可以不用顯式地知道映射函數(shù),也不用考慮具體特征空間的維數(shù),而實現(xiàn)數(shù)據(jù)的高維特征空間的嵌入。在特征空間中一個核函數(shù)被用于計算這些映射數(shù)據(jù)樣本之間的內(nèi)積,這個核函數(shù)定義為k(.,.)=k(xi,xj)=φ(xi)Tφ(xj

)。

則歸一化的特征向量為

這樣得到特征向量α后,可以使用式(5-15)計算核主成分v。

對于任何一個測試樣本x,其非線性特征為

特征提取過程可以用圖5-3表示。圖5-3非線性特征提取結(jié)構(gòu)

概括起來,計算核主成分的步驟如下:

(1)計算核矩陣K=Φ(

X)T·Φ(X);

(2)對核矩陣特征K分解,得到相應(yīng)的特征值λ和特征向量α;

(3)歸一化特征向量v;

(4)對測試樣本,計算其在特征向量v上的投影。

5.1.3核線性判別分析

核線性判別分析(KFDA)是將核學(xué)習(xí)方法的思想與FDA算法相結(jié)合的產(chǎn)物。KFDA算法的思路是:首先通過一個非線性映射,將輸入數(shù)據(jù)映射到一個高維的特征空間中,然后,在這個高維特征空間中再進(jìn)行線性Fisher判別分析,從而實現(xiàn)相對于原空間為非線性判別分析。

在進(jìn)行KFDA時,首先通過一個非線性映射φ將輸入數(shù)據(jù)映射到一個高維的特征空間中,即

這時輸入的訓(xùn)練樣本由原來的x變?yōu)棣?x),然后在這個特征空間F中進(jìn)行線性FDA。KFDA就是在F空間中求解以下問題

假定在F空間中,所有的樣本都是去均值的

則類間散度矩陣為

以上就是KDA算法的推導(dǎo)過程,它是在線性鑒別分析的基礎(chǔ)上通過分別對類內(nèi)散度矩陣和類間散度矩陣進(jìn)行推導(dǎo)的。由于Fisher準(zhǔn)則在計算過程中存在矩陣奇異的情況,因此KDA同樣具有小樣本問題,本章我們就不再贅述對于小樣本問題的解決方法,具體方法留待后續(xù)算法進(jìn)行解決。

5.1.4核局部線性判別分析

5.2流形學(xué)習(xí)方法

5.2.1流形學(xué)習(xí)方法的概念1.流形學(xué)習(xí)方法的基本思想流形(Manifold)在局部具有歐氏空間性質(zhì),是歐氏空間中曲線、曲面等概念的推廣,歐氏空間就是最簡單的流形的實例。

我們存在的三維空間就是典型的歐式空間,像地球表面這樣的球面就是一個典型流形:歷史上人類曾經(jīng)認(rèn)為地球是平面的,因為人相對于地球來講只是球面上的一個點,一個點在球面上只能做二維運動,所以人平常看到的只是一個局部的二維空間,即在局部具有二維歐式空間性質(zhì);當(dāng)人乘坐航空器離開地表,就看到地球是個三維空間的球形,就像足球一樣。一個理想的球面在局部足夠小的區(qū)域上可近似為一個平面,即在局部具有歐式空間性質(zhì),這就表明它是一個流形。但是從整體全局看,球面和平面具有本質(zhì)區(qū)別,球面上一個點沿著直線運動會回到起點,但在平面上這個點可以無限向前移動而不會回到起點。

流形在微分幾何中用于描述形體,它的可微性為研究幾何形體提供了平臺和工具。從拓?fù)浣Y(jié)構(gòu)看,流形是柔軟的,因為所有變形(同胚)會保持拓?fù)浣Y(jié)構(gòu)不變;而從解析幾何看,流形是硬的,因為流形局部的數(shù)據(jù)結(jié)構(gòu)是固定的。所以這種局部是硬的,而整體可以流動的幾何形體就稱之為流形。

拓?fù)淞餍问且环N最簡單的流形,它由局部普通的歐氏空間Rn組成,形式化地講,一個拓?fù)淞餍问且粋€局部同胚于一個歐氏空間的拓?fù)淇臻g。這表示每個點有一個鄰域,它有一個同胚(連續(xù)雙射,其逆也連續(xù))將它映射到Rn,這些同胚是流形的坐標(biāo)圖。拓?fù)淞餍尉褪且粋€集合,上面賦予了拓?fù)浣Y(jié)構(gòu),拓?fù)淇臻g之間可以定義連續(xù)映射。

拓?fù)淇臻gM在滿足以下條件時,稱M為m維流形。

(1)M為豪斯多夫空間。豪斯多夫空間是數(shù)學(xué)拓?fù)鋵W(xué)中的一個分離空間,滿足分離定理:對于拓?fù)淇臻gM中任意2個不同的點x和y,存在x的鄰域U和y的鄰域V,滿足U∩V=Φ。

(2)對于任意一點p∈M,存在包含p的m維坐標(biāo)鄰域(U,Φ),坐標(biāo)鄰域是拓?fù)淇臻g中的開集與其在歐幾里德空間中的映射Φ的有序?qū)Α?/p>

2.形學(xué)習(xí)概念

對于給定的數(shù)據(jù)集X={xi,i=1,…,n}∈RD,并假設(shè)X中的數(shù)據(jù)樣本是由低維空間中的數(shù)據(jù)集Y={yi,i=1,…,n}∈Rd經(jīng)過系列的非線性數(shù)學(xué)變換f而生成為xi=f(yi)+εi,這里的,d?D,f:Rd→RD是C∞嵌入映射。流形學(xué)習(xí)就是在給定觀察樣本集{xi}的條件下重構(gòu)f和{yi}。

5.2.2流形學(xué)習(xí)方法的分類

根據(jù)流形學(xué)習(xí)方法的實質(zhì),可將其分為兩類,第一類是構(gòu)建關(guān)系矩陣方法,主要包括等距映射、局部線性嵌入等;第二類是基于局部模型的全局坐標(biāo)對齊,主要有局部切空間排列、黎曼流形等。

流形學(xué)習(xí)如果按照算法對樣本涵蓋范圍來分,可以分為兩類,如圖5-4所示。圖5-4流形學(xué)習(xí)方法的分類

(1)全局方法是從全局角度出發(fā),在降維時流形上臨近的點映射到低維空間時保持臨近,但這種方法條件較為苛刻,算法復(fù)雜度很高;

(2)局部方法則只要求在一個局部范圍內(nèi)映射到低維空間的臨近關(guān)系保持不變即可。

如果按照樣本的特征變換方式來分,還可分為線性和非線性兩大類。

5.2.3等距映射算法

等距映射(ISOMAP)算法實際上是MDS算法的推廣。在MDS思想中,約簡后低維空間中任意兩點間的距離應(yīng)該與它們在原高維空間中的距離是相同的,所以對距離度量是算法的關(guān)鍵,很顯然當(dāng)數(shù)據(jù)為線性結(jié)構(gòu)時歐氏距離度量是有效的,但當(dāng)樣本數(shù)據(jù)是在流形曲面上采樣時,歐氏距離就不再反映數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)。基于以上的問題,在ISOMAP算法可以得到有效解決。

ISOMAP的計算步驟如下:

(1)確定鄰域,構(gòu)造鄰近圖G。計算每個點的近鄰點,可以使用ε鄰域法或k鄰域法,這兩種鄰域選取方式均是以樣本點間的歐式距離為基礎(chǔ),對這兩種鄰域法進(jìn)行定義。

(2)估計點對間測地距離dM(xi,xj

)。用鄰近圖G上xi和xj之間的最短路徑dM(xi,xj

)近似流行M上的測地距離,得到距離矩陣DM。最短路徑dM(xi,xj

)的計算方法如下:當(dāng)G中存在邊(i,j)時,存在最短路徑dM(xi,xj

)=dE(xi,xj

),否則dM(xi,xj

)=∞;對于p=1,2,…,n,dM(xi,xj

)=min{dM(xi,xj

),dM(xi,xj

)+dM(xi,xj

)}最短路徑矩陣可表示為

(3)應(yīng)用MDS算法計算低維嵌入。計算對稱矩陣:

式中,I為n階單位矩陣;l是矩陣內(nèi)全部元素為1的n維列向量。

通過式(5-43)~式(5-45)可以總結(jié)出ISOMAP的特點:

(1)計算點對間的最短路徑比較耗時,當(dāng)樣本數(shù)和鄰域取值較大,全局計算量將會非常巨大。

(2)因為數(shù)據(jù)所在的低維流形與歐式空間的一個子集整體等距,該歐式空間的子集是一個凸集,如果當(dāng)這個低維子集非凸時,流形上樣本點間的最短路徑計算會產(chǎn)生較大的偏差,從而導(dǎo)致嵌入結(jié)果產(chǎn)生較為明顯的變形,所以,該算法只適用于學(xué)習(xí)內(nèi)部平坦的低維流形,不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。

(3)當(dāng)樣本點采樣稀疏,或數(shù)據(jù)集變形或扭曲,測地線距離的計算就會出現(xiàn)較大的誤差,使得嵌入結(jié)果產(chǎn)生變形。

(4)當(dāng)進(jìn)行等距計算時,會要求在高維數(shù)據(jù)空間向低維參數(shù)空間存在等距映射時,鄰圖上樣本點間最短路徑逼近的測地線距離,是無法描述數(shù)據(jù)集的內(nèi)在低維幾何結(jié)構(gòu),而導(dǎo)致錯誤嵌入結(jié)果。

5.2.4局部線性嵌入算法

局部線性嵌入算法(LLE)是Roweis在2000年的《Science》上提出的,并引起了轟動,因為LLE算法與ISOMAP算法相比,其局部線性更優(yōu),更具有研究價值。LLE算法是假設(shè)采樣數(shù)據(jù)所在的低維流形在局部是線性的,而且每個采樣點均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示。

LLE算法的基本思想:對于一組具有嵌套流形的數(shù)據(jù)集,在嵌套空間與內(nèi)在低維空間局部鄰域間的點的關(guān)系應(yīng)該不變。即在嵌套空間每個采樣點可以用它的近鄰點線性表示,在低維空間中保持每個鄰域中的權(quán)值不變,重構(gòu)原數(shù)據(jù)點,使重構(gòu)誤差最小。

LLE算法包括三個步驟,如圖5-5所示:

(1)選擇鄰近樣本;

(2)利用線性權(quán)值重構(gòu)矩陣W;

(3)利用矩陣W計算映射到低維空間。圖5-5-LLE算法步驟示意圖

LLE算法具體如下:

(1)設(shè)d維空間中有n個數(shù)據(jù)屬于同一流形,記作:Xi=(xi1,xi2,…,xi1),i=1,2,…,n。假設(shè)有足夠的數(shù)據(jù)點,并且認(rèn)為空間中的每一個數(shù)據(jù)點可以用它的k個近鄰線性表示。求近鄰點,一般采用k鄰域法或ε鄰域法。

(2)計算權(quán)值短陣W,代價函數(shù)為

并且權(quán)值要滿足兩個約束條件:

①每一個數(shù)據(jù)點Xi都只能由它的鄰近點來表示,若Xj不是鄰近點,則wij=0;

②權(quán)值矩陣的每一行的和為1,即:

這樣,求最優(yōu)權(quán)值就是對于式(5-46)在兩個約束條件下求解最小二乘問題。權(quán)值體現(xiàn)了數(shù)據(jù)間內(nèi)在的幾何關(guān)系:

利用Lagrangemultiplier對式(5-47)求解得重構(gòu)權(quán)值的矩陣W。

(3)保持權(quán)值不變,在低維空間dd?D()中對原數(shù)據(jù)點重構(gòu)。設(shè)低維空間的數(shù)據(jù)點為Yi,可以通過求最小的代價函數(shù)式(5-46)求得:

式(5-48)中的最優(yōu)解需要滿足下面的約束條件:

LLE算法的優(yōu)點:

(1)算法適用于各種的低維流形學(xué)習(xí);

(2)算法只需確定鄰域參數(shù)和維度參數(shù)即可,相比ISOMAP待定參數(shù)較少;

(3)算法中每個點的近鄰權(quán)值在平移、旋轉(zhuǎn)、伸縮變換下是保持不變的;

(4)算法通過最小二乘可以求得整體最優(yōu)解,而且不需重復(fù)步驟,計算簡單。

LLE算法的缺點:

(1)對所學(xué)習(xí)的流形假設(shè)是不閉合的,而且是局部線性的;

(2)要求在流形上進(jìn)行稠密的采樣;

(3)對樣本中的噪音很敏感;

(4)對于新樣本的映射過程則需要重新計算。

5.2.5-拉普拉斯特征映射算法

拉普拉斯特征映射算法[8](LE)來源于圖譜理論,假設(shè)有N個數(shù)據(jù)樣本,則由N個數(shù)據(jù)樣本及相鄰樣本間的邊構(gòu)成一個拉普拉斯圖,嵌入映射可通過求解拉普拉斯映射的特征向量得到,算法過程如下:

1.構(gòu)造鄰域圖

構(gòu)造鄰域圖,主要是構(gòu)造邊系數(shù),即如果兩個數(shù)據(jù)樣本點間是“接近的”,就在這兩個數(shù)據(jù)樣本間設(shè)置一條邊,否則兩個數(shù)據(jù)樣本間就不存在邊,判斷兩個數(shù)據(jù)樣本間是否“接近”,可以用兩種方法:

(2)k鄰域法,如果節(jié)點i是節(jié)點j的k個最近鄰之一,或者節(jié)點j是節(jié)點i的k個最近鄰之一,則認(rèn)為節(jié)點i與節(jié)點j之間存在一條邊。注意上述條件滿足之一則兩個節(jié)點間就存在一條邊,所以關(guān)系式是對稱的。此種方法優(yōu)勢在于容易選擇,而且不容易出現(xiàn)不連通的圖;缺點是缺少直觀幾何意義。

2.計算拉普拉斯圖的邊系數(shù)

計算拉普拉斯圖的邊系數(shù),可以使用以下兩種方法:

(1)使用熱核方程計算邊的系數(shù),即如果節(jié)點i與節(jié)點j之間存在一條邊,則該邊的系數(shù)為

否則Wij=0。式中t為熱核參數(shù)。

(2)簡化的方式計算邊系數(shù),即如果節(jié)點i與節(jié)點j之間存在一條邊,則Wij=1,否則Wij=0。

3.重構(gòu)樣本數(shù)據(jù)

在d維空間用各個樣本的近鄰重構(gòu)該樣本數(shù)據(jù),其思想可描述為:使任意Xi的近鄰在降維后仍然盡可能靠近Xi,即所有點與其近鄰的距離和最小,因此有如下代價函數(shù)

拉普拉斯特征映射算法其實與LLE算法類似。都是保持投影后點關(guān)系特征,也是分三個步驟。該算法主要思想是設(shè)在高維空間中樣本點之間的相關(guān)性投影到低維空間中點的相關(guān)性保持不變,并通過使用兩點間的加權(quán)距離作為目標(biāo)函數(shù),可求得相應(yīng)的約簡結(jié)果。相應(yīng)的損失函數(shù)為

矩陣D是流形頂點的一種自然測度,Dij越大,說明這個頂點越重要,LE算法的三個步驟中,對于流行描述是通過鄰域圖去近似的。描述如下:

(1)構(gòu)造鄰域圖——從樣本點構(gòu)建一個近鄰圖,圖的頂點為樣本點,離得最近兩點用邊相連,這里可以繼續(xù)采用ε鄰域法或k鄰域法計算。

(2)構(gòu)造權(quán)值矩陣——給每條邊賦予權(quán)值,如果點i和點j為非鄰域點時,Wij=0;如果點i和點j為鄰域點相連時,則有以下兩種方法:

①兩點間的權(quán)值為

式中,t為熱核參數(shù)。

②采用簡單權(quán)值法,兩點間的權(quán)值Wij直接設(shè)為1。

(3)計算d維嵌入———計算圖拉普拉斯算子的廣義特征向量,求得低維嵌入。設(shè)式(5-54)中D為對角矩陣,Dii=∑jWji,L=D-W,L是近鄰圖上的拉普拉斯算子,求解廣義特征值問題Lf=λDf,這里最小特征值為對應(yīng)的特征向量。

與LLE算法相比LE算法具有如下優(yōu)點:

(1)LE算法的思想較簡單,是局部非線性方法,主要目的是保留流形的局部近鄰信息,使原空間中離得很近的點在低維空間也離得很近,可以用于聚類。

(2)計算復(fù)雜度較低。LE算法只考慮局部鄰域直接的關(guān)系,其求解過程為稀疏矩陣的特征值,求出整體最優(yōu)解,效率非常高,能有效反映數(shù)據(jù)集所在低維流形上局部的內(nèi)在幾何信息。

LE算法的缺點:

(1)對算法參數(shù)和數(shù)據(jù)采樣密度較敏感。

(2)不能有效保持流形的全局幾何結(jié)構(gòu)。

5.2.6海賽局部線性嵌入算法

海賽局部線性嵌入算法(HLLE)也稱為Hessian特征映射,是由Donoho和Grimes提出來的。

HLLE與LE的理論架構(gòu)很類似,所不同的是,HLLE是用二階海賽算子替代拉普拉斯算子映射

HLLE的優(yōu)點是:無需要求流形所對應(yīng)的低維空間為凸;計算復(fù)雜度比LE更為簡單。缺點是:HLLE恢復(fù)低維流形坐標(biāo)時需要知道流形的維度D;對噪音分布不均勻會有較大誤差;對于計算高維數(shù)據(jù)局部鄰域內(nèi)的二階導(dǎo)相對比較困難。

5.2.7局部切空間排列算法

局部切空間排列算法(LTSA)是由張振躍等人于2004年提出的。其基本思想是:每個局部鄰域由局部切空間近似表示,每個樣本點通過局部切坐標(biāo)來表示,LTSA認(rèn)為全局低維坐標(biāo)可以通過局部切坐標(biāo)的仿射變換得到。對于大多數(shù)的非線性流形來說,LTSA可以通過局部線性信息,來整合發(fā)現(xiàn)它的全局非線性結(jié)構(gòu)。

同樣LTSA也分為三個步驟:

(1)用k鄰域法或者ε鄰域法求出樣本點的鄰域;

(2)求鄰域的局部坐標(biāo);

(3)求出局部坐標(biāo)的全局排列。

LTSA的優(yōu)點:計算比較簡單;無需要求流形所對應(yīng)的低維空間為凸;能很好地恢復(fù)出流形等距的低維空間的子集。缺點:算法中特征值分解的矩陣階數(shù)等于樣本數(shù),如果樣本大,則難以計算高階矩陣;與之前LLE一樣,對于新樣本還是無法有效處理;另外對流形樣本點的曲率和密度都比較敏感。

5.2.8流形學(xué)習(xí)方法在應(yīng)用中遇到的主要問題

1.本征維數(shù)估計

本征維數(shù)估計是流形學(xué)習(xí)方法中的一個重點和難點,同時也是特征提取中的一個棘手問題。通常認(rèn)為本征維數(shù)