高維數(shù)據(jù)的低維表示綜述(共30頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上高維數(shù)據(jù)的低維表示綜述一、研究背景在科學(xué)研究中，我們經(jīng)常要對數(shù)據(jù)進(jìn)行處理。而這些數(shù)據(jù)通常都位于維數(shù)較高的空間，例如，當(dāng)我們處理200個(gè)256*256的圖片序列時(shí)，通常我們將圖片拉成一個(gè)向量，這樣，我們得到了65536*200的數(shù)據(jù)，如果直接對這些數(shù)據(jù)進(jìn)行處理，會有以下問題：首先，會出現(xiàn)所謂的“位數(shù)災(zāi)難”問題，巨大的計(jì)算量將使我們無法忍受；其次，這些數(shù)據(jù)通常沒有反映出數(shù)據(jù)的本質(zhì)特征，如果直接對他們進(jìn)行處理，不會得到理想的結(jié)果。所以，通常我們需要首先對數(shù)據(jù)進(jìn)行降維，然后對降維后的數(shù)據(jù)進(jìn)行處理。降維的基本原理是把數(shù)據(jù)樣本從高維輸入空間通過線性或非線性映射投影到一個(gè)低維空間，

2、從而找出隱藏在高維觀測數(shù)據(jù)中有意義的低維結(jié)構(gòu)。（8）之所以能對高維數(shù)據(jù)進(jìn)行降維，是因?yàn)閿?shù)據(jù)的原始表示常常包含大量冗余：· 有些變量的變化比測量引入的噪聲還要小，因此可以看作是無關(guān)的 · 有些變量和其他的變量有很強(qiáng)的相關(guān)性(例如是其他變量的線性組合或是其他函數(shù)依賴關(guān)系)，可以找到一組新的不相關(guān)的變量。（3）從幾何的觀點(diǎn)來看，降維可以看成是挖掘嵌入在高維數(shù)據(jù)中的低維線性或非線性流形。這種嵌入保留了原始數(shù)據(jù)的幾何特性，即在高維空間中靠近的點(diǎn)在嵌入空間中也相互靠近。（12）數(shù)據(jù)降維是以犧牲一部分信息為代價(jià)的，把高維數(shù)據(jù)通過投影映射到低維空間中，勢必會造成一些原始信息的損失。所以在對

3、高維數(shù)據(jù)實(shí)施降維的過程中如何在最優(yōu)的保持原始數(shù)據(jù)的本質(zhì)的前提下，實(shí)現(xiàn)高維數(shù)據(jù)的低維表示，是研究的重點(diǎn)。（8）二、降維問題1定義定義1.1降維問題的模型為，其中維數(shù)據(jù)空間集合（一般為的一個(gè)子集），映射是空間集合（一般是，）的一個(gè)子集，我們稱是數(shù)據(jù)集（到）的降維。若為的線性函數(shù)，則稱為線性降維；否則，稱為非線性降維。定義1.2 稱映射為嵌入映射。（8）2分類針對降維問題的目的和待處理數(shù)據(jù)集合表象維數(shù)的多少，對其進(jìn)行初步的、粗略的分類如下：·硬降維問題：數(shù)據(jù)維數(shù)從幾千到幾萬甚至幾十萬的變化，此時(shí)需要對數(shù)據(jù)集進(jìn)行“嚴(yán)厲”的降維，以至于達(dá)到便于處理的大小，如圖像識別、分類問題以及語音識別問題等

4、。·軟降維問題：此時(shí)數(shù)據(jù)集合的維數(shù)不是太高，降維的需求不是非常的迫切。如社會科學(xué)、心理學(xué)以及多元統(tǒng)計(jì)分析領(lǐng)域皆屬于此類。·可視化問題：此時(shí)數(shù)據(jù)集合的絕對維數(shù)不是很高，但為了便于利用人們的直觀洞察力，即為了可視化，我們將其降到2或3維。雖然我們可以可視化更高維數(shù)的數(shù)據(jù)，但是它們通常難于理解，不能產(chǎn)生數(shù)據(jù)空間的合理形態(tài)。若我們還考慮時(shí)間變量的話可以對降維問題進(jìn)行更加進(jìn)一步的分類，靜態(tài)降維問題和動態(tài)降維問題。后者對于時(shí)間序列來講是有用的，如視頻序列、連續(xù)語音信號等的處理。（4）3方法介紹如何將高維數(shù)據(jù)表示在低維空間中，并由此發(fā)現(xiàn)其內(nèi)在結(jié)構(gòu)是高維信息處理研究的關(guān)鍵問題之一。實(shí)際處理

5、中，由于線性方法具有簡單性、易解釋性、可延展性等優(yōu)點(diǎn)，使得線性降維在高維數(shù)據(jù)處理中是一個(gè)主要研究方向。已有的線性維數(shù)約簡方法，主要包括主成分分析(Principal Component Analysis，PCA)16、獨(dú)立成分分析(Independent Component Analysis，ICA)、線性判別分析inear discriminant analysis(LDA) 17、Fisher 判別分析(Fisher Discriminant Analysis，F(xiàn)DA)、主曲線(Principal Curves)、投影尋蹤(Projection Pursuit, PP)、多維尺度方法(Mu

6、ltidimensional Scaling，MDS)等。這些方法實(shí)際是在不同優(yōu)化準(zhǔn)則之下，尋求最佳線性模型，這也是線性維數(shù)約簡方法的共性。（10）通過消除數(shù)據(jù)建模過程中的全局線性假設(shè)，Sammon提出了一種非線性映射，即Sammon映射(SM)，該算法能夠保持輸入樣本之間的相關(guān)距離；Hastie提出了principal curves(PC)，其定義為通過概率分布或數(shù)據(jù)中間的光滑曲線；Kohonen基于自組織神經(jīng)網(wǎng)絡(luò)提出了self-organizing map(SOM)用來保存數(shù)據(jù)空間的拓?fù)鋵傩?；Scholkopf等應(yīng)用Mercer核將PCA擴(kuò)展為Kernel PCA(KPCA)，該算法在高維

7、空間中計(jì)算主分量，而該高維空間由輸入空間經(jīng)某種非線性映射得到。Mika等采用相同的思想來非線性擴(kuò)展LDA，從而提出了kernel LDA（KLDA）；然而，基于核的方法其難點(diǎn)在于如何選擇一個(gè)合適的核函數(shù)， 一個(gè)好的核函數(shù)可以使數(shù)據(jù)在特征空間上線性可分或者近似線性可分，但并不是所選核函數(shù)對于每一種數(shù)據(jù)都適用。核函數(shù)的選擇反映了人們對問題的先驗(yàn)知識，在實(shí)際的應(yīng)用中往往是經(jīng)驗(yàn)地選擇某種核函數(shù)，比如徑向基函數(shù) (Radial Basis Function，RBF)。同時(shí)，在使用核函數(shù)時(shí)不必知道具體的特征空間，使得核函數(shù)方法缺乏物理直觀性，這也是核函數(shù)方法的一個(gè)缺點(diǎn)。（10）最近興起的流形學(xué)習(xí)算法也是用

8、來維數(shù)約減的非線性方法，并且依靠它們在探測嵌入在高維空間中低維流形的能力和靈活性而被廣泛應(yīng)用。具有代表性的流形學(xué)習(xí)算法包括等距映射 (Isometric Mapping，Isomap)、局部線性嵌入方法(Locally Linear Embedding，LLE)、Laplacian 特征映射(Laplacian Eigenmap，LE)、局部切空間排列方法( Local Tangent Space Alignment，LTSA)、Hessian等距映射(Hessian eigenmaps，HLLE)和最大方差展開(maximum variance unfolding，MVU)。其中，LLE運(yùn)用

9、線性系數(shù)，來表達(dá)局部幾何，該系數(shù)能夠重建一個(gè)給定的樣本點(diǎn)利用其近鄰點(diǎn)，然后尋找一個(gè)低維空間，在該空間中這些線性系數(shù)仍然可以用來重建相應(yīng)的點(diǎn)；ISOMAP作為MDS的變種，能夠保存點(diǎn)對之間的全局的測地線距離；LE通過對一個(gè)描述了點(diǎn)對之間鄰域關(guān)系的無向圖的操作，來保持?jǐn)?shù)據(jù)之間的近鄰關(guān)系。HLLE先通過估計(jì)鄰域上的Hessian而構(gòu)建一矩陣，然后在此矩陣上運(yùn)用特征值分解而得到最終的低維坐標(biāo)。LTSA運(yùn)用局部切信息作為局部幾何的表達(dá)，然后將這些切信息在全局中排列從而得到最終的全局坐標(biāo)。MVU不是一個(gè)絕對的局部方法而是一個(gè)介于局部和全局之間的方法，因?yàn)镸VU不僅保存近鄰點(diǎn)之間的幾何關(guān)系而且在它的目標(biāo)函數(shù)

10、中考慮了全局點(diǎn)對之間的距離。除了基于譜分析的流形學(xué)習(xí)的算法，基于概率參數(shù)模型，Rowels提出了global coordination(GC)；Teh和Roweis開發(fā)了locally linear coordination(LLC)；Brand提出了manifold charting(Charting)。這些方法也屬于流形學(xué)習(xí)的重要范疇。然而，這些非線性的算法卻不能夠?yàn)闃颖咎峁┮粋€(gè)外在的映射，也就是說，它們很難被應(yīng)用于識別問題。但是，一些基于譜分析的算法由于其具有特殊的特征分解機(jī)制而能夠較為容易的擴(kuò)展為線性算法，其線性化可以通過在解決優(yōu)化的過程中施加線性逼近來實(shí)現(xiàn)。Locality pres

11、erving projection(LPP)作為LE的線性化是其中最早提出的算法。后來提出的還包括neighborhood preserving embedding(NPE)，LLE的線性化擴(kuò)展，和orthogonal neighborhood preserving projections(ONPP)，LLE的正交線性化擴(kuò)展。這種線性化擴(kuò)展使流形學(xué)習(xí)的思想更能夠應(yīng)用到現(xiàn)實(shí)世界中。圖1.1給出了以上所提提及的降維算法的分類圖。在譜方法的線性化擴(kuò)展中，LPP可以被看作為基于圖結(jié)構(gòu)的最具代表性的算法，在接下來的幾年中，又不斷地有這種基于圖的算法被提出，從而進(jìn)一步完善了這種基于圖的框架。Cai等對LP

12、P算法分別對監(jiān)督設(shè)置和非監(jiān)督設(shè)置兩種情況作了系統(tǒng)的分析，并且將LDA用這種基于圖的框架重新公式化。Yan等提出了一種一般性的框架即“圖嵌入”，來統(tǒng)一各種各樣的降維算法?；诖朔N框架，一種新的線性算法，marginal fisher analysis（MFA）將開發(fā)出來。MFA不同于LPP其只用一個(gè)圖來描述數(shù)據(jù)的幾何結(jié)構(gòu)，該算法采用了兩個(gè)圖，其中一個(gè)為固有圖（intrinsic graph），它用來刻畫數(shù)據(jù)的類內(nèi)緊湊性；而另一個(gè)圖為懲罰圖（penalty graph），用來描述數(shù)據(jù)類間的分離性。因此，MFA比LPP更具有判別性。Chen等同時(shí)提出的local discriminant embed

13、ding（LDE）算法在本質(zhì)上與MFA的思想是相同的。（5）非線性降維方法與線性降維方法相比的一個(gè)顯著特點(diǎn)是，分析中的局部性(數(shù)據(jù)集合經(jīng)常滿足的一個(gè)簡單假設(shè))。原因在于對數(shù)據(jù)集合的內(nèi)蘊(yùn)結(jié)構(gòu)而言，有下列特性：·由泰勒定理，任何可微函數(shù)在一點(diǎn)的充分小的鄰域之內(nèi)滿足線性性。形象的來講，相當(dāng)于認(rèn)為曲面流形可由大小不一的局部線性塊拼接而成；·數(shù)據(jù)流形經(jīng)常是由許多可分割的子流形所組成；·數(shù)據(jù)流形的本征維數(shù)沿著流形不斷的發(fā)生變化，只有局部性才能抓住其根本特性。（4） 降維線性流行學(xué)習(xí)概率參數(shù)模型全局譜分析局部全局局部早期的非線性PCAMVUISOMAPChartingLLCKe

14、rnelPCSMSOMGCLDALPPNPELLELLTSAONPPLELTSAHLLE線性化三、常見降維方法（一）線性 1. 主成分分析(Principal Component Aanlysis PCA) 1PCA將方差的大小作為衡量信息量多少的標(biāo)準(zhǔn)，認(rèn)為方差越大提供的信息越多，反之提供的信息就越少。它是在損失很少的信息的前提下把多個(gè)指標(biāo)轉(zhuǎn)化為幾個(gè)綜合指標(biāo)的一種多元統(tǒng)計(jì)方法。它具有概念簡單，計(jì)算方便以及最優(yōu)線性重構(gòu)誤差等優(yōu)良的特性。PCA是一種全局算法，它可以較好地揭示具有線性結(jié)構(gòu)的高維數(shù)據(jù)集的全局分布。然而對于嵌入在高維空間中具有非線性流形結(jié)構(gòu)的數(shù)據(jù)，PCA很難學(xué)習(xí)出隱含在數(shù)據(jù)集中的低維流

15、形結(jié)構(gòu)。PCA假設(shè)數(shù)據(jù)之間的關(guān)系是線性的。它在保存原始高維數(shù)據(jù)協(xié)方差結(jié)構(gòu)的基礎(chǔ)上計(jì)算低維表達(dá)，也就是最大化總體方差。它的目標(biāo)函數(shù)可以寫為：其中，且為總體離散矩陣：。對轉(zhuǎn)換矩陣做尺度約束，其中為單位矩陣。則目標(biāo)函數(shù)可以寫為：，上式問題可以轉(zhuǎn)化為的標(biāo)準(zhǔn)的特征值問題：PCA的最優(yōu)轉(zhuǎn)換矩陣為的d個(gè)最大的特征值所對應(yīng)的d個(gè)m維特征向量。2.線性判別法(Linear Discriminant Analysis LDA) 2其基本思想是投影，首先找出特征向量，把這些數(shù)據(jù)投影到一個(gè)低維的方向，使得投影后不同的組之間盡可能的分開，而同一組內(nèi)的的樣本比較靠攏，然后在新空間中對樣本進(jìn)行分類。通過最小化類內(nèi)離散矩陣的

16、秩而最大化類間離散矩陣的秩，來尋找一個(gè)子空間來區(qū)分不同的類別。和分別定義如下：其中，是第i個(gè)類中樣本的個(gè)數(shù)；是第i個(gè)樣本中第j個(gè)樣本。為第i個(gè)類的質(zhì)心；用來表示所有樣本的質(zhì)心，C為樣本的類別數(shù)。LDA則有以下的優(yōu)化準(zhǔn)則： 上述的優(yōu)化可以轉(zhuǎn)化為求解一個(gè)廣義的特征分解問題：且最優(yōu)的解為d個(gè)特征向量其對應(yīng)于d個(gè)最大的非零特征值。3.投影尋蹤(Projection Pursuit PP) 3基本思想主要來源人們對低維空間幾何圖形的直觀理解，它包含倆個(gè)方面的含義：其一是投影(Projection)，把高維空間中數(shù)據(jù)投影到低維空間；其二是尋蹤(Pursuit)，利用低維空間投影數(shù)據(jù)的幾何分布形念，發(fā)現(xiàn)人們

17、感興趣的數(shù)據(jù)內(nèi)在特征和相應(yīng)的投影方向，同時(shí)排除與數(shù)據(jù)結(jié)構(gòu)和特征無關(guān)的或關(guān)系比較小的變量干擾。4. 多維尺度分析(Multidimensional Scalar ，MDS) 4主要思想是：根據(jù)數(shù)據(jù)點(diǎn)間的歐氏距離，構(gòu)造關(guān)系矩陣，為了盡可能地保持每對觀測數(shù)據(jù)點(diǎn)之間的歐氏距離，只需對此關(guān)系矩陣進(jìn)行特征分解，從而獲得每個(gè)數(shù)據(jù)在低維空間中的低維坐標(biāo)。算法步驟：1計(jì)算觀測空間中任意兩點(diǎn)歐式距離，構(gòu)造n階平方歐式距離矩陣A2將矩陣A進(jìn)行雙中心化計(jì)算，即計(jì)算。若設(shè)階矩陣（常稱之為中心化矩陣），將矩陣H左乘和右乘A的兩邊（常稱之為雙中心化）。3計(jì)算低維坐標(biāo)Y。即將B奇異值分解，設(shè)B的最大的d個(gè)特征值，對應(yīng)特征向量

18、，則d維坐標(biāo)為。（二）非線性流形學(xué)習(xí)旨在發(fā)現(xiàn)高維數(shù)據(jù)集分布的內(nèi)在規(guī)律性，其基本思想是：高維觀測空間中的點(diǎn)由少數(shù)獨(dú)立變量的共同作用在觀測空間張成一個(gè)流形，如果能有效地展開觀測空間卷曲的流形或發(fā)現(xiàn)內(nèi)在的主要變量，就可以對該數(shù)據(jù)集進(jìn)行降維。現(xiàn)在形式化地概括流形學(xué)習(xí)這一維數(shù)約簡過程：假設(shè)數(shù)據(jù)是均勻采樣于一個(gè)高維歐氏空間中的低維流形，流形學(xué)習(xí)就是從高維采樣數(shù)據(jù)中恢復(fù)低維流形結(jié)構(gòu)，即找到高維空間中的低維流形，并求出相應(yīng)的嵌入映射，以實(shí)現(xiàn)維數(shù)約簡或者數(shù)據(jù)可視化。它是從觀測到的現(xiàn)象中去尋找事物的本質(zhì)，找到產(chǎn)生數(shù)據(jù)的內(nèi)在規(guī)律。用數(shù)學(xué)語言可以這樣描述，令且是一個(gè)光滑的嵌套，流形學(xué)習(xí)的目標(biāo)是基于上的一個(gè)給定被觀測數(shù)

19、據(jù)集合去恢復(fù)和，在中隱藏的數(shù)據(jù)被隨機(jī)地產(chǎn)生，然后被映射到觀測空間，使得。（12）1.局部線性嵌入方法 LLE (Locally Linear Embedding) 5LLE在保存原始高維數(shù)據(jù)鄰域線性結(jié)構(gòu)的基礎(chǔ)上計(jì)算低維表達(dá)。（5）是一種局部方法，它試圖保持?jǐn)?shù)據(jù)的局部幾何特征，就本質(zhì)上來說，它是將流形上的近鄰點(diǎn)映射到低維空間的近鄰。（9）圖2 非線性降維實(shí)例 B是從 A中提取的樣本點(diǎn)（三維），通過非線性降維算法 LLE將數(shù)據(jù)映射到二維空間中（C），從C圖中的顏色可以看出通過 LLE算法處理后的數(shù)據(jù)能很好的保持原有數(shù)據(jù)的鄰域特性(引用文獻(xiàn)6)主要思想：對一組具有嵌套(流形)的數(shù)據(jù)集，在嵌套空問與內(nèi)

20、在低維空間局部鄰域問的關(guān)系應(yīng)該不變，即在嵌套空間中每個(gè)采樣點(diǎn)可以用它的近鄰點(diǎn)線性表示，在低維空間中保持每個(gè)鄰域中的權(quán)值不變，重構(gòu)原數(shù)據(jù)點(diǎn)，使重構(gòu)誤差最小。(8)LLE的實(shí)現(xiàn)過程步驟：LLE方法可以歸結(jié)為三步：(1) 尋找每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)；把相對于所求樣本點(diǎn)距離最近的k個(gè)樣本點(diǎn)規(guī)定為所求樣本點(diǎn)的k個(gè)鄰近點(diǎn)。k是一個(gè)預(yù)先給定值。距離的計(jì)算既可采用歐式距離也可采用Dijkstra距離。Dijkstra距離是一種測地距離，它能夠保持樣本點(diǎn)之間的曲面特性。(2)由每個(gè)樣本點(diǎn)的近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的局部重建權(quán)值矩陣；這里定義一個(gè)成本函數(shù)，如下式，來測量重建誤差：解得，時(shí)其中，和是的近鄰點(diǎn)；為了使重建

21、誤差最小化，權(quán)重服從一種重要的對稱性，即對所有特定數(shù)據(jù)點(diǎn)來說，它們和它們鄰居點(diǎn)之間經(jīng)過旋轉(zhuǎn)、重排、轉(zhuǎn)換等變換后，它們之間的對稱性是不變的。由此可見重建權(quán)重能夠描述每個(gè)鄰居本質(zhì)的幾何特性。因此可以認(rèn)為原始數(shù)據(jù)空間內(nèi)的局部幾何特征同在流形局部塊上的幾何特征是完全等效的。（3）由該樣本點(diǎn)的局部重建權(quán)值矩陣和其近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的輸出值。映射條件滿足如下成本函數(shù)：要使低維重構(gòu)誤差最小，計(jì)算得出，Y等價(jià)于求M的特征向量，其中在處理過程中，將M的特征值從小到大排列，第一個(gè)特征值幾乎接近于零，那么舍去第一個(gè)特征值。通常取第2到m+l之間的特征值所對應(yīng)的特征向量作為輸出結(jié)果。優(yōu)點(diǎn)：LLE算法可以學(xué)習(xí)任意維的

22、局部線性的低維流形，就是用局部性用局部的的線性來逼近全局的非線性，保持局部的幾何結(jié)構(gòu)不變，通過相互重疊的局部鄰域來提供整體的信息，從而保持整體的幾何性質(zhì)。LLE既有非線性的特點(diǎn)又具有線性方法的優(yōu)點(diǎn)。（8）同時(shí)由重構(gòu)成本函數(shù)最小化得到的最優(yōu)權(quán)值遵循對稱特性，每個(gè)點(diǎn)的近鄰權(quán)值在平移、旋轉(zhuǎn)、伸縮變換下是保持不變的LLE算法有解析的全局最優(yōu)解，不需迭代，低維嵌入的計(jì)算歸結(jié)為稀疏矩陣特征值的計(jì)算，這樣計(jì)算復(fù)雜度相對較小。缺點(diǎn)：LLE算法要求所學(xué)習(xí)的流形只能是不閉合的且在局部是線性的，還要求樣本在流形上是稠密采樣的。另外，該算法的參數(shù)選擇不確定，對樣本中的噪音很敏感。（12）此外，(1)對于一個(gè)新樣本點(diǎn)。

23、沒有顯式的方法把該點(diǎn)嵌入到低維空間中，這在檢索應(yīng)用中不適用。(2)新空間的維數(shù)沒有顯式準(zhǔn)則進(jìn)行確定，只有通過經(jīng)驗(yàn)的方法。(3)LLE沒有利用數(shù)據(jù)點(diǎn)的類信息。在分類問題中，對于有類標(biāo)號的樣本數(shù)據(jù)，LLE無能為力。SLLE算法7Dick和Robert提出一種針對有監(jiān)督的 LLE算法，即Supervised linear locally embedding (SLLE)傳統(tǒng)的LLE算法在第一步時(shí)是根據(jù)樣本點(diǎn)間的歐氏距離來尋找k個(gè)近鄰點(diǎn)，而SLLE在處理這一步時(shí)增加了樣本點(diǎn)的類別信息，SLLE算法的其余步驟同LLE算法是一致的。SLLE算法在計(jì)算點(diǎn)與點(diǎn)之間的距離時(shí)有兩種方法。SLLE1：第一種方法是采

24、用下式來修正點(diǎn)與點(diǎn)之間的距離公式如下所示其中：是計(jì)算后的距離D是最初采用的距離；max(D)是表示類與類之間的最大距離；取0或者1，當(dāng)兩點(diǎn)屬于同類時(shí)，取為0，否則取1；是控制點(diǎn)集之間的距離參數(shù)，是一個(gè)經(jīng)驗(yàn)參數(shù)。當(dāng)取為零時(shí)，此時(shí)的SLLE和 LLE 算法相同。這個(gè)方法引入了一個(gè)參數(shù)，它是一種經(jīng)驗(yàn)參數(shù)，對實(shí)驗(yàn)的結(jié)果有很大的影響，下面介紹一種非參數(shù)的方法。SLLE2：求解點(diǎn)與點(diǎn)之間的距離，目的在于是尋找樣本點(diǎn)的近鄰點(diǎn)。SLLE2的方法在尋找近鄰點(diǎn)時(shí)，不是在全局樣本中尋找近鄰點(diǎn)，而是在每個(gè)點(diǎn)所在類的樣本中尋找近鄰點(diǎn)，也就是說，在類內(nèi)中尋找樣本點(diǎn)的近鄰點(diǎn)。這個(gè)方法固然沒有采用參數(shù)的方法，但是如果某一類的

25、樣本個(gè)數(shù)小于k，那么這種方法必將失敗，則每個(gè)類的樣本個(gè)數(shù)在相當(dāng)多的情況下 可以采用這種方法。RLLE算法8當(dāng)在做聚類分析且采用LLE算法對數(shù)據(jù)進(jìn)行降維時(shí)，如果數(shù)據(jù)中存在著許多離異點(diǎn)的情況，那么降維后的結(jié)果將會發(fā)生變異，通常是第一維或者是第二維的數(shù)據(jù)發(fā)生跳躍式的變化，或者分布在某幾條直線上，這將會給聚類帶來很大的麻煩，其實(shí)當(dāng)離異點(diǎn)超過LLE算法中的k值時(shí)，這種現(xiàn)象將會發(fā)生。A.Hadid和M.Pietikäinen提出一種 Robust Locally Linear Embedding (RLLE)方法。它是針對存在有離異點(diǎn)的情況下，對樣本的一種無監(jiān)督的非線性降維方法。鄰域保持嵌入算法

26、NPE算法9NPE從本質(zhì)上說是局部線性嵌入(local linear embedding，LLE)的線性逼近。給定數(shù)據(jù)集X，采用與LLE相同的方法構(gòu)建數(shù)據(jù)集上的近鄰圖。NPE針對LLE算法的out-of-sample問題提出的，該算法通過最小化局部相似離散度尋找投影方向，有效的保持了數(shù)據(jù)間的相似幾何結(jié)構(gòu)，取得了不錯效果，已被廣泛地應(yīng)用到文檔分析、機(jī)器學(xué)習(xí)和模擬識別等領(lǐng)域。NPE假定每個(gè)局部近鄰都是線性的。算法步驟：1近鄰選擇，構(gòu)造鄰接圖G2計(jì)算近鄰重建權(quán)W3計(jì)算投影向量：a求低維坐標(biāo)對應(yīng)近鄰重建的目標(biāo)函數(shù)最小化，即b代入線性變換,得c 其中d求解下列廣義特征方程的d個(gè)最小特征值對應(yīng)的特征向量作

27、為d個(gè)投影向量：故由上述特征方程的d個(gè)最小特征值對應(yīng)特征向量，構(gòu)成保持近鄰重建特性的線性變換矩陣。缺點(diǎn)：NPE在保持?jǐn)?shù)據(jù)空間的局部相似信息時(shí)，不能較有效地保持差異信息，特別是高維非線性數(shù)據(jù)間的差異信息。如在人臉識別應(yīng)用中，人臉圖像的識別容易受光照、表情等非理想條件變化的影響，這些非理想情況會使得同一個(gè)人的不同圖像之間的差異大于不同人圖像之間的差異，從而導(dǎo)致識別錯誤。NPE算法通過式實(shí)現(xiàn)了數(shù)據(jù)到新空間的線性變換。顯然，這種線性變換實(shí)現(xiàn)的數(shù)據(jù)變換是一種顯式形式，這樣就解決了LLE算法沒有顯式映射函數(shù)的問題。LLE算法是非監(jiān)督的學(xué)習(xí)方法，沒有充分利用類別信息，為了提高算法的識別能力，于是有了LLE的

28、正交線性化擴(kuò)展，orthogonal neighborhood preserving projections(ONPP)10 11。 張長水等人12在LLE的基礎(chǔ)上提出一種從低維嵌入空間向高維空間映射的方法，并在多姿態(tài)人臉圖像的重構(gòu)實(shí)驗(yàn)中得到有效的驗(yàn)證，進(jìn)一步完善了非線性降維方法。 2. 等距映射法 ISOMAP (Isometric Map) 13ISOMAP認(rèn)為當(dāng)數(shù)據(jù)集具有嵌入流形結(jié)構(gòu)時(shí)，可以根據(jù)保距映射來獲得觀測空間數(shù)據(jù)集在低維結(jié)構(gòu)的對應(yīng)描述。基本思想：ISOMAP通過測地線距離來描述各點(diǎn)之間的相互關(guān)系，在全局意義下，通過尋找各點(diǎn)在圖意義下的最短路徑來獲得點(diǎn)與點(diǎn)之間的距離，然后利用經(jīng)典的

29、MDS算法得到低維的嵌入坐標(biāo)。因此ISOMAP可認(rèn)為是MDS算法的變種。（5）圖3 ISOMAP算法示意圖使用前提條件：高維數(shù)據(jù)所在的低維流形與歐氏空間的一個(gè)子集是整體等距的；與數(shù)據(jù)所在的流形等距的歐氏空問的子集是一個(gè)凸集。主要步驟：(1)構(gòu)造局部鄰域。首先對數(shù)據(jù)集，計(jì)算任意兩個(gè)樣本向量和的歐式距離，將每一個(gè)點(diǎn)與所有的點(diǎn)進(jìn)行比較，當(dāng)兩點(diǎn)之間的距離小于固定的半徑（或i是j的K-鄰域）時(shí)，我們就認(rèn)為它們是相鄰的，將其連接起來，該邊的長度,則得到鄰域圖G。(2)計(jì)算最短距離。在圖G中，設(shè)任意兩個(gè)樣本向量和之間的最短距離為。若和之間存在連線，的初始值為，否則令。對所有的k=1,2,n這樣得到矩陣，它是

30、圖G中所有點(diǎn)對的最短路徑組成的。(3)構(gòu)造d維嵌入。用MDS方法構(gòu)造一個(gè)保持本征幾何結(jié)構(gòu)的d維嵌入到空間Y。H是與同階的單位矩陣，對進(jìn)行特征分解，取最大的前d個(gè)特征值和對應(yīng)的特征向量，令為第p個(gè)特征向量的第i個(gè)成分，則對應(yīng)的數(shù)據(jù)低維表示為。優(yōu)點(diǎn)： 適用于學(xué)習(xí)內(nèi)部平坦的低維流形，ISOMAP結(jié)合了線性算法(如PCA和MDS)的主要特征計(jì)算的有效性、全局的優(yōu)化性和漸進(jìn)收斂性等。這種用測地距離來代替?zhèn)鹘y(tǒng)的歐氏距離的方法，可更有效的在低維空間來表達(dá)高維空間的數(shù)據(jù)，減少降維后損失的數(shù)據(jù)信息。缺點(diǎn)：不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。在噪聲干擾下，Isomap用于可視化會有不穩(wěn)定現(xiàn)象，取較大的鄰域會產(chǎn)生短路現(xiàn)

31、象，即低維流形中不同鄰域部分的點(diǎn)投影后出現(xiàn)明顯的混雜現(xiàn)象。選取較小的鄰域，雖然能夠保證整體結(jié)構(gòu)的穩(wěn)定，但低維投影結(jié)果會產(chǎn)生大量“空洞”，或使最短路徑算法重構(gòu)的圖不連通。降維維數(shù)的確定通常是在本質(zhì)維數(shù)未知的情況下進(jìn)行的，經(jīng)多次實(shí)驗(yàn)繪制殘差曲線觀察得到。Isomap算法計(jì)算圖上2點(diǎn)間的最短距離可采用Dijkstra算法，但執(zhí)行起來仍然比較慢。（12）(l)當(dāng)與高維流形等距的歐氏空間的子集不是凸型時(shí)，即當(dāng)高維空間存在“空洞”時(shí)，要計(jì)算高維觀測空間上任意樣本點(diǎn)之間的距離很有可能發(fā)生彎曲異常，如果這樣就會影響低維嵌入結(jié)果的表示。(2)等距特征映射算法在數(shù)據(jù)拓?fù)淇臻g有可能是不穩(wěn)定的。因?yàn)槿绻x擇的鄰域過小

32、，就會導(dǎo)致鄰域圖不連通，如果選擇的鄰域太大，又可能導(dǎo)致短路。(3)使用Isomap算法恢復(fù)非線性流形的幾何結(jié)構(gòu)的時(shí)候，所需的計(jì)算時(shí)間比較多，這主要是花在計(jì)算樣本點(diǎn)之間的最短路徑上。由于已有的流形學(xué)習(xí)算法對噪音和算法參數(shù)都比較敏感，詹德川、周志華14針對Isomap算法，提出了一種新方法，通過引入集成學(xué)習(xí)技術(shù)，擴(kuò)大了可以產(chǎn)生有效可視化結(jié)果的輸入?yún)?shù)范圍，并且降低了對噪音的敏感性。另外，趙連偉15等人完善了Isomap的理論基礎(chǔ)，給出了連續(xù)流形與其低維參數(shù)空間等距映射的存在性證明，并區(qū)分了嵌入空間維數(shù)、高維數(shù)據(jù)的固有維數(shù)與流形維數(shù)這些容易混淆的概念，證明如果高維數(shù)據(jù)空間存在環(huán)狀流形，流形維數(shù)則要小

33、于嵌入空間維數(shù)他們還給出一種有效的環(huán)狀流形發(fā)現(xiàn)算法，以得到正確的低維參數(shù)空間。特別地，周志華等16提出了一種方法，可以從放大因子和延伸方向兩方面顯示出觀測空間的高維數(shù)據(jù)與降維后的低維數(shù)據(jù)之間的聯(lián)系，并實(shí)驗(yàn)比較了2種著名流形學(xué)習(xí)算法(Isomap和LLE)的性能。文獻(xiàn)17中，作者提出了一種基于Isomap的監(jiān)督算法Weightedlso。在分類問題中，理想情況下屬于同一類的樣本在測量空間中應(yīng)離得近一些，反之，不同類的樣本則離得遠(yuǎn)一些。因此，作者在基本Isomap算法的第一步，計(jì)算各樣本點(diǎn)間的歐氏距離時(shí)引進(jìn)了一個(gè)常量參數(shù)，用來重新度量同一類樣本間的距離，使它們離得更近。Weightedlso算法雖

34、然在一定程度上克服了流形學(xué)習(xí)方法分類效果較差的缺點(diǎn)，但在引入常量參數(shù)重新度量同類樣本的距離時(shí)，由于噪聲的影響，破壞了樣本間的本質(zhì)結(jié)構(gòu)，使其可視化應(yīng)用效果下降。在分類問題中，權(quán)值w在很大程度上影響著分類的結(jié)果，如何選取w值得進(jìn)一步研究。由于Weightedlso的不足，Xin Geng,De Chuan Zhan等18提出了另一種基于Isomap的監(jiān)督算法SIsomap。該方法同樣是修改了Isomap算法的第一步，用已知的樣本所屬類別信息重新定義了樣本間的距離。3局部切空間排列算法 LTSA (local tangent space alignment)19LTSA是一種基于切空間的流形學(xué)習(xí)方法

35、，它通過逼近每一樣本點(diǎn)的切空間來構(gòu)建低維流形的局部幾何，然后利用局部切空間排列求出整體低維嵌入坐標(biāo)。主要思想：找出每個(gè)數(shù)據(jù)點(diǎn)的近鄰點(diǎn)，用鄰域中低維切空間的坐標(biāo)近似表示局部的非線性幾何特征，再通過變換矩陣將各數(shù)據(jù)點(diǎn)鄰域切空間的局部坐標(biāo)映射到一個(gè)同一的全局坐標(biāo)上，從而實(shí)現(xiàn)高維數(shù)據(jù)降維，即從n維數(shù)據(jù)中得到一個(gè)全局的d維坐標(biāo)。(8)算法步驟：第一步：構(gòu)造鄰域。對于每個(gè)數(shù)據(jù)點(diǎn)，找出它的包括它自身在內(nèi)的k個(gè)鄰域點(diǎn)，構(gòu)成矩陣。第二步：局部線性投影。對于每個(gè)樣本點(diǎn)的鄰域，計(jì)算中心化矩陣的最大d個(gè)奇異值對應(yīng)的左奇異向量，并將這d個(gè)左奇異向量組成矩陣。1由計(jì)算得出左奇異向量U，取出U的前d列構(gòu)成矩陣（即為點(diǎn)的切空

36、間的近似）；2計(jì)算各個(gè)鄰域點(diǎn)在該切空間的投影：第三步：局部坐標(biāo)系統(tǒng)的排列。對每個(gè)鄰域的局部切空間坐標(biāo)，構(gòu)造轉(zhuǎn)換矩陣。通過最小化的求解，最后化解可通過計(jì)算一個(gè)矩陣從第2小到第d+1小的特征值所對應(yīng)的特征向量。其中是的廣義Moor-Penrose逆。優(yōu)缺點(diǎn)：LTSA能夠有效地學(xué)習(xí)體現(xiàn)數(shù)據(jù)集低維流形結(jié)構(gòu)的整體嵌入坐標(biāo)，但它也存在兩方面的不足：一方面算法中用于特征值分解的矩陣的階數(shù)等于樣本數(shù)，樣本集較大時(shí)將無法處理；另一方面算法不能有效處理新來的樣本點(diǎn)。（12）對此，提出了一些相應(yīng)的改進(jìn)算法。但LTSA也面臨著同HLLE類似的一些問題：LTSA所反映的局部結(jié)構(gòu)是它的局部d維坐標(biāo)系統(tǒng)，因此，由于噪聲等因

37、素的影響，當(dāng)數(shù)據(jù)集的局部低維特征不明顯或者不是d維的時(shí)候，它的局部鄰域到局部切空間的投影距離往往并不小。此時(shí)，構(gòu)造的重建誤差也不會小，這樣LTSA可能就無法得到理想的嵌入結(jié)果。此外，LTSA對樣本點(diǎn)的密度和曲率的變化的影響比較敏感，樣本點(diǎn)的密度和曲率的變化使得樣本點(diǎn)到流形局部切空間的投影產(chǎn)生偏差，而LTSA構(gòu)造排列矩陣的模型并沒有將這種偏差計(jì)入考慮范圍。這使得對于樣本點(diǎn)密度和曲率變化較大的流形，LTSA的嵌入結(jié)果可能會出現(xiàn)扭曲現(xiàn)象。線性局部切空問排列(LLTSA)針對LTSA算法不能為新的測試樣本提供一個(gè)明確的從高維到低維的映射，也就是所謂的“Out of Sample”問題。提出了一個(gè)新的線

38、性算法，線性局部切空問排列(LLTSA)20。該算法運(yùn)用切信息作為數(shù)據(jù)的局部表達(dá)，然后將這些局部信息在可以用線性跌射得到的低維空間中排列。它先將每一個(gè)樣本點(diǎn)鄰域的切空間表示為流形的局部幾何，再經(jīng)線性映射實(shí)現(xiàn)樣本數(shù)據(jù)從高維空間降維到低維空間，最終將整體嵌入坐標(biāo)的求解問題轉(zhuǎn)化為矩陣的廣義特征值的求解問題。算法步驟：1近鄰選擇，構(gòu)造鄰接圖G2計(jì)算局部切坐標(biāo)3計(jì)算投影向量：a求低維坐標(biāo)對應(yīng)近鄰重建的目標(biāo)函數(shù)最小化，即 是k階中心化矩陣且。b代入線性變換，且由得c 其中,近鄰選擇矩陣使得，并且,且。d求解下列廣義特征方程的d個(gè)最小特征值對應(yīng)的特征向量作為d個(gè)投影向量：故由上述特征方程的d個(gè)最小特征值對應(yīng)

39、特征向量，構(gòu)成保持近鄰重建特性的線性變換矩陣。數(shù)據(jù)樣本的類別信息對于入臉識別是非常重要的資源，但是LLTSA算法是非監(jiān)督的學(xué)習(xí)方法，沒有充分利用類別信息。為了提高算法的識別能力，需要對LLTSA算法的目標(biāo)函數(shù)進(jìn)行修改，以增加有關(guān)判別信息的限定，使原來無監(jiān)督的學(xué)習(xí)方法發(fā)展為有監(jiān)督的學(xué)習(xí)方法。而且為了提高數(shù)據(jù)的重建能力，算法應(yīng)將解出的人臉子空間正交化，可稱這種流形學(xué)習(xí)算法為正交判別的線性局部切空間排列(orthogonal discriminant linear local tangent space alignment，ODLLTSA)。21由于用于特征值分解的矩陣的階數(shù)等于樣本點(diǎn)數(shù)，因此，當(dāng)樣

40、本點(diǎn)集較大時(shí)將無法處理，此外，該方法不能有效處理新來的樣本點(diǎn)。一種基于劃分的局部切空間排列方法（partitional local tangent space alignment ,PLTSA）22被提出以改善這些缺點(diǎn)，它建立在主成分分析算法和LTSA方法的基礎(chǔ)上，解決了主成分分析算法不能求出整體低維坐標(biāo)和 LTSA 中大規(guī)模矩陣的特征值分解問題，能夠有效處理新來的樣本點(diǎn)。PLTSA是一種非監(jiān)督的流形學(xué)習(xí)方法，不能充分利用數(shù)據(jù)的類別信息，而在人臉識別中數(shù)據(jù)樣本的類別信息是非常重要的資源。為了提高算法的識別能力，需要對PLTSA算法進(jìn)行改進(jìn)，以增加判別信息的限定，使無監(jiān)督的學(xué)習(xí)方法發(fā)展為有監(jiān)督的

41、學(xué)習(xí)方法。因此提出了一種基于劃分的有監(jiān)督局部切空間排列法（partitional supervised local tangent space alignment PSLTSA）23。4.拉普拉斯特征映射法 LE (Laplacian Eigenmap) 24LE方法將微分流形、譜圖論的知識應(yīng)用于降維之中，使人們對降維過程的認(rèn)識產(chǎn)生了又一個(gè)新的飛躍，拓展了實(shí)際中降維方法的應(yīng)用?；舅枷胧牵涸诟呔S空間中距離相隔很近的點(diǎn)投影到低維空間中像也應(yīng)該相距很近，最終求解歸結(jié)到求拉普拉斯算子的廣義特征值問題。（8）實(shí)際上是使用有權(quán)圖的 Laplace矩陣來逼近 空間中的 Laplace Beltrami 算

42、子，以期達(dá)到最優(yōu)投影的降維算法算法步驟：第一步，構(gòu)造近鄰圖G。在數(shù)據(jù)集X中，計(jì)算每個(gè)樣本點(diǎn)同其余樣本點(diǎn)之間的歐式距離，構(gòu)造近鄰圖。尋找相對于每個(gè)樣本點(diǎn)的歐式距離最近的k個(gè)樣本點(diǎn)規(guī)定為所求點(diǎn)的近鄰點(diǎn)，若數(shù)據(jù)點(diǎn)與是鄰接的，則圖中點(diǎn)與之間存在一條邊。第二步，選擇權(quán)值，構(gòu)造權(quán)值矩陣W。在近鄰圖中，為每一條邊選擇一個(gè)權(quán)值，構(gòu)造權(quán)值矩陣W。權(quán)值的選擇有兩種選擇方式：1）若點(diǎn)與是鄰接的，則設(shè)邊的權(quán)值為，否則設(shè)=0；t是一個(gè)比例參數(shù)。2）若點(diǎn)與是鄰接的，則設(shè)變得權(quán)值為=1，否則設(shè)=0。在方法1）中，需要選擇比例參數(shù)t，方法2）不用選擇比例參數(shù)t，比較簡單。第三步，進(jìn)行特征映射，計(jì)算d維嵌入。對數(shù)據(jù)集X構(gòu)造的近

43、鄰圖G，映射到一條直線，用y表示，使得鄰接的點(diǎn)盡可能的靠近。設(shè)是一個(gè)未知的投影，可以通過在一定約束下，使得下面的目標(biāo)函數(shù)達(dá)到最小來求解。用D表示對一個(gè)對角矩陣，它的每個(gè)對角元素為權(quán)值矩陣W的每行所有元素的和，即，L=D-W是鄰接圖的Laplacian矩陣。對任意的y有給定約束條件=1，以消除坐標(biāo)尺度對映射y的影響，最小化上式的和函數(shù)，利用矩陣跡的性質(zhì)和拉格朗日乘子法，即可求解。相當(dāng)于利用下式計(jì)算特征值和特征向量的問題上述特征方程的最小的d個(gè)非零特征值對應(yīng)的特征向量，則數(shù)據(jù)X的低維嵌入表示為LE是局部的非線性方法，其突出特點(diǎn)是與譜圖理論有著很緊密的聯(lián)系。從算法描述中可以看到，拉普拉斯映射和LLE

44、算法類似，待定參數(shù)相同，求解的是稀疏矩陣的廣義特征值問題，它能使輸入空間中離得很近的點(diǎn)在低維空間也離得很近，故可用于聚類。（12）缺點(diǎn)類似LLE。LPP局部保留投影（Locality preserving projection，LPP）LPP局部保留投影（Locality preserving projection，LPP）作為LE的線性化是其中最早提出的算法。25LPP算法的主要問題在于建立k近鄰域圖，使它能很好地表現(xiàn)數(shù)據(jù)流形的局部結(jié)構(gòu)。然后，根據(jù)建立的k鄰圖來獲得圖像的投影，最終在投影得到的子空問中進(jìn)行特征識別。算法把非線性變換轉(zhuǎn)換成了近似的線性形式。所以，一個(gè)測試樣本要轉(zhuǎn)換到新空間中去，

45、只要乘以從訓(xùn)練集計(jì)算得到的線性矩陣即可。這解決了LLE、LE等算法不能顯式表示的問題，實(shí)際上這種顯式轉(zhuǎn)換是非線性流行空間的一種線性回歸和近似。與前述全局最優(yōu)算法相比，這些算法保持了局部信息，同時(shí)給出了簡便的變換形式，可以說是全局最優(yōu)和局部最優(yōu)間的折衷。算法步驟：1近鄰選擇，構(gòu)造鄰接圖G2計(jì)算近鄰相似度W3計(jì)算投影向量：a求低維坐標(biāo)對應(yīng)近鄰重建的目標(biāo)函數(shù)最小化，即b代入線性變換,得c 其中L=D-W,而對角矩陣D的對角線元素d求解下列廣義特征方程的d個(gè)最小特征值對應(yīng)的特征向量作為d個(gè)投影向量：故由上述特征方程的d個(gè)最小特征值對應(yīng)特征向量，構(gòu)成保持近鄰重建特性的線性變換矩陣。5. Hessian等

46、距映射(HLLE) 26Dohono等人拓展了局部線性嵌入(LLE)方法，提出了Hessian LLE方法，能夠發(fā)現(xiàn)流形上局部的潛在等距映射參數(shù)。HLLE先通過估計(jì)鄰域上的Hessian而構(gòu)建一矩陣，然后在此矩陣上運(yùn)用特征值分解而得到最終的低維坐標(biāo)。Donoho等人認(rèn)為Isomap算法要求參數(shù)空間的概率測度有凸支撐，進(jìn)行全局等距映射這個(gè)條件過于嚴(yán)格，而局部等距更加合理，從而提出來一種Hessian特征映射算法(Hessian Eigenmap，簡稱HLLE)。Hessian特征映射與Laplacian特征映射的理論框架非常相似，只是使用Hessian算子代替了Laplacian算子。算法步驟：

47、1選擇鄰域。2獲得切空間坐標(biāo)。對每個(gè)樣本點(diǎn)的鄰域，計(jì)算中心化矩陣的最大d個(gè)奇異值對應(yīng)的右奇異向量，并將這d個(gè)右奇異向量組成矩陣。這里是一個(gè)全1的列向量。3估計(jì)Hessian矩陣。4構(gòu)造二次型。利用每個(gè)鄰域的Hessian矩陣，來構(gòu)造對稱矩陣H，它的元素為5計(jì)算H的零空間。計(jì)算H的最小d+1特征值對應(yīng)的特征向量，去掉對應(yīng)0特征值的常數(shù)向量，剩下的d個(gè)向量即為所求零空間。6計(jì)算嵌入結(jié)果。記矩陣其中表示某個(gè)樣本點(diǎn)的鄰域。則為嵌入結(jié)果。Hessian特征映射具有如下優(yōu)點(diǎn)：首先，計(jì)算較簡單，因其考慮局部鄰近信息，求解過程為稀疏矩陣的特征值問題，且其解能反映數(shù)據(jù)集所在低維流形上的內(nèi)在局部幾何信息；其次，其

48、出發(fā)點(diǎn)就是針對局部等距于低維歐氏空間中開連通的子集的流形，同時(shí)對于這樣的開子集并沒有要求是凸的。對于這樣的流形，HLLE可以恢復(fù)出與流形等距的低維嵌入。該算法合理性建立在其與Laplacian特征映射的關(guān)系上，僅使用2階的Hessian算子代替了Laplacian算子。HLLE也有一些缺點(diǎn)：HLLE獲取切空間坐標(biāo)時(shí)需要知道流形的本征維數(shù)d；對噪聲比較敏感，因其使用二階的Hessian算子，需要估計(jì)局部鄰域內(nèi)的二階導(dǎo)，這對于高維數(shù)據(jù)樣本是很困難的，當(dāng)流形噪聲分布不一致或流形局部低維特征不明顯時(shí)，獲取的切空間坐標(biāo)可能有較大的偏差，從而影響嵌入結(jié)果。由于HLLE選取零空間中一組在某個(gè)鄰域內(nèi)保持正交性

49、的基作為嵌入結(jié)果，對于不同的鄰域，嵌入結(jié)果有可能不同。5.最大方差展開(maximum variance unfolding，MVU) 27該算法可看成是PCA和MDS的思想推廣后提出的一種非線性流形學(xué)習(xí)算法。主要思想是：使得遠(yuǎn)離的數(shù)據(jù)點(diǎn)其低維坐標(biāo)展開得盡可能的遠(yuǎn)，并且約束保持局部近鄰點(diǎn)的歐氏距離不變；這個(gè)目標(biāo)可以通過半定規(guī)劃(SDP)技術(shù)學(xué)習(xí)一個(gè)Gram內(nèi)積矩陣，然后對這個(gè)內(nèi)積矩陣進(jìn)行特征分解獲得全局低維坐標(biāo)。算法步驟：1計(jì)算鄰接圖。2通過計(jì)算半定規(guī)劃（SDP）求內(nèi)積矩陣K。設(shè)輸入觀測到的高維數(shù)據(jù)，目標(biāo)輸入為低維坐標(biāo)，要使得遠(yuǎn)離的數(shù)據(jù)點(diǎn)其低維坐標(biāo)展開的盡可能遠(yuǎn)，并且約束保持局部近鄰點(diǎn)的距離，

50、最直觀的目標(biāo)函數(shù)定義為使得地位坐標(biāo)保持局部近鄰的距離而最大化任意兩點(diǎn)間的距離之和，即：化簡優(yōu)化問題轉(zhuǎn)化為：保證局部等度規(guī)、中心化和半正定等3個(gè)約束條件下使得內(nèi)積矩陣的跡最大化，即通過半定規(guī)劃(SDP)學(xué)習(xí)內(nèi)積矩陣丘使得保持局部近鄰距離和低維數(shù)據(jù)點(diǎn)中心在原點(diǎn)，實(shí)現(xiàn)最大方差展開，如上式。3對內(nèi)積矩陣K進(jìn)行特征分解求內(nèi)在低維坐標(biāo)：求K的最大的d個(gè)特征值(令)對應(yīng)的特征向量,則d維坐標(biāo)為。優(yōu)點(diǎn)：首先，MVP忠實(shí)的保存了類間幾何特征和類內(nèi)幾何特征，該算法是基于流形學(xué)習(xí)的算法。其次，MVP具備判別能力，適用于分類問題。缺點(diǎn)：MVU在SDP步的時(shí)間復(fù)雜度大，數(shù)據(jù)點(diǎn)數(shù)就2000個(gè)時(shí)目前普通的PC機(jī)也要計(jì)算幾個(gè)

51、小時(shí)1491。6.非負(fù)矩陣分解（Non-negative Matrix actorization，NMF）由于實(shí)際問題中矩陣數(shù)據(jù)很龐大，其中存放的信息分布往往不均勻，因此直接處理這樣的矩陣效率低下，就失去了實(shí)用意義。為高效處理這些通過矩陣存放的數(shù)據(jù)，一個(gè)關(guān)鍵的必要步驟便是對矩陣進(jìn)行分解操作。通過矩陣分解，一方面將矩陣的維數(shù)進(jìn)行削減，另一方面也可以對大量的數(shù)據(jù)進(jìn)行壓縮和概括。NMF 直接將非負(fù)分解問題作為帶約束的非線性規(guī)劃問題。NMF 子空間要求子空間的基以及樣本在子空間上的投影系數(shù)都是非負(fù)的，這一約束限制了投影到子空間的數(shù)據(jù)只能是子空間基的加性組合，而不存在減運(yùn)算。因此，所獲得的對數(shù)據(jù)表示的非

52、負(fù)基所張成的子空間是非正交的和部分無界的，這使得其對數(shù)據(jù)的表示更為緊湊和更少冗余，表示效率更高，即對數(shù)據(jù)具有更好的夾逼性，從而更有利于對數(shù)據(jù)的表示。NMF具有下列特點(diǎn)：(1) 分解的結(jié)果不含負(fù)值，具有明確的物理意義和可解釋性，非常適合非負(fù)數(shù)據(jù)處理；(2)能夠發(fā)現(xiàn)數(shù)據(jù)內(nèi)部潛在結(jié)構(gòu)特征，還能夠降低數(shù)據(jù)特征的維數(shù)，節(jié)省存儲和計(jì)算資源，這在處理高維數(shù)據(jù)時(shí)就有很明顯的優(yōu)勢；(3) NMF的心理學(xué)和生理學(xué)構(gòu)造依據(jù)是人眼對整體的感知是由對部分的感知組成的(純加性的)，即整體是部分的非負(fù)線性組合，因此具有智能數(shù)據(jù)描述的特性；(4)非負(fù)性的限制還導(dǎo)致分解結(jié)果具有一定的稀疏性，相對稀疏的表示方式能夠在一定程度上抑

53、制外界變化(部分遮擋、光照變化、圖像旋轉(zhuǎn))給特征提取帶來的不利影響。此外，將NMF和一些常用的流行學(xué)習(xí)方法結(jié)合會在分類問題上取得較好的結(jié)果。如Ruicong Zhi等考慮原始面部圖像稀疏表征和鄰近結(jié)構(gòu)保留，為面部特征提取提出了一種新算法GSNMF（Graph-Preserving Sparse Nonnegative Matrix Factorization），利用了局部保留投影算法LPP，保留局部結(jié)構(gòu)，加上不可控制的稀疏性約束，在人臉識別中提高了識別率。對圖像識別任務(wù)主要就是為了獲得更好的分類，將原始數(shù)據(jù)通過基矩陣進(jìn)行投影映射，因此就是對基矩陣產(chǎn)生了約束，獲得更好的局部特征。與有監(jiān)督算法需要

54、用到所有訓(xùn)練樣本的先驗(yàn)信息(如樣本所屬類別、樣本低維坐標(biāo)等信息)不同，半監(jiān)督學(xué)習(xí)算法只需要用到部分樣本的類別或其低維信息，更接近實(shí)際中的問題，因此與有監(jiān)督算法相比具有一定優(yōu)勢。但也因?yàn)槿绱?，其算法的推廣也有一定難度，目前的研究還比較有限。拉普拉斯特征映射算法的作者Belkin等2l將拉普拉斯特征映射算法推廣到了半監(jiān)督學(xué)習(xí)問題中，首先利用拉普拉斯特征映射算法求出低維嵌入流形，然后在流形上利用標(biāo)記樣本訓(xùn)練分類器進(jìn)行分類，其對手寫字體識別和文本分類的實(shí)驗(yàn)證明了算法的有效性。XinYang等22給出了半監(jiān)督的LLE和LTSA算法，在通過傳統(tǒng)算法得到各樣本間的關(guān)系矩陣后，利用可獲得的部分樣本的先驗(yàn)低維坐

55、標(biāo)信息來求解剩余樣本的低維坐標(biāo)，得到了更精確的低維結(jié)果，并驗(yàn)證了該算法解決可視化和視頻序列中人的運(yùn)動手臂跟蹤等問題。ZhenyueZhang等23分析了基于譜方法的半監(jiān)督學(xué)習(xí)，給出了較詳細(xì)的數(shù)學(xué)基礎(chǔ)和推導(dǎo)，分析了LTSA算法中的特征值問題在半監(jiān)督學(xué)習(xí)中的關(guān)系，通過實(shí)驗(yàn)比較了所提出算法與現(xiàn)有算法，證實(shí)了其優(yōu)越性。馮海亮等24將半監(jiān)督的LLE算法用于人臉和人臉表情識別，構(gòu)造樣本間距離矩陣時(shí)利用部分樣本的類別信息來得到一個(gè)更能反映樣本間關(guān)系的矩陣，然后再通過求解該矩陣的特征值、特征向量問題求解低維結(jié)果，取得了優(yōu)于傳統(tǒng)流形學(xué)習(xí)算法的分類效果。四、降維方法總結(jié)高維數(shù)據(jù)集合的降維過程(包括線性、非線性降維

56、)可分解為既相互獨(dú)立又相互關(guān)聯(lián)的三個(gè)階段：1）數(shù)據(jù)集結(jié)構(gòu)的描述；2）數(shù)據(jù)集結(jié)構(gòu)的度量準(zhǔn)則：3）基于結(jié)構(gòu)的降維準(zhǔn)則。降維方法的提出和形成同樣主要包含三個(gè)方面的工作，1）建立研究問題的相應(yīng)數(shù)學(xué)模型，數(shù)據(jù)集結(jié)構(gòu)模型；2）對該模型提出相應(yīng)的度量準(zhǔn)則或選擇規(guī)則；3）建立基于數(shù)據(jù)集結(jié)構(gòu)的降維準(zhǔn)則或損失規(guī)則。（4）如何自動判斷數(shù)據(jù)集的非線性是由內(nèi)在曲率還是映射模型造成的，如何處理斷續(xù)流形與非斷續(xù)流形或者變維數(shù)流形，目前還沒有好的解決方法，這也是流形學(xué)習(xí)中需要進(jìn)一步研究的問題。另外，流形學(xué)習(xí)可以視為數(shù)據(jù)處理的一個(gè)中間過程，要完成最終的目標(biāo)，需要與其他領(lǐng)域的知識或算法相結(jié)合，如與分類算法k-NN，SVM，HMM

57、等相結(jié)合實(shí)現(xiàn)分類識別目的。目前的流形學(xué)習(xí)方法存在的主要不足有：(1) 流形學(xué)習(xí)算法計(jì)算復(fù)雜度高現(xiàn)有流形學(xué)習(xí)的一個(gè)很大瓶頸就是計(jì)算復(fù)雜度太高，這阻礙了其在實(shí)際中的應(yīng)用。雖然其對非線性數(shù)據(jù)具有較好的降維效果，但如何有效降低計(jì)算量，甚至推廣其線性化算法是一個(gè)研究熱點(diǎn)。線性化是一個(gè)很好的方法，但是線性化以后對于高度的非線性問題也一樣束手無策。如何得到可處理非線性數(shù)據(jù)的線性化流形學(xué)習(xí)方法值得進(jìn)一步研究。(2) 流形學(xué)習(xí)算法的分類能力較弱在處理分類問題時(shí)，多數(shù)情況下流形學(xué)習(xí)算法的性能較傳統(tǒng)方法要差。因?yàn)?，流形學(xué)習(xí)算法在恢復(fù)內(nèi)在不變量時(shí)采用了局部鄰域思想，算法本身的穩(wěn)定性與鄰域選擇有關(guān)，如何在分類意義下獲得適當(dāng)?shù)泥徲騾?shù)需要進(jìn)一步的研究。另外，算法中采用了k-NN來獲得流形結(jié)構(gòu)在觀測空間的有限描述，這一方法假定了數(shù)據(jù)集不存在異常噪聲，如果噪聲較大時(shí)，算法可能覆蓋過多的非支撐域以外的空間，從而使得隨后的分類算法產(chǎn)生錯誤的幾何投影距離。(3) 本征維數(shù)的估計(jì)我們對流形學(xué)習(xí)方法的非參數(shù)化問題進(jìn)行了研究，如何自適應(yīng)的確定流形學(xué)習(xí)算法中需要的參數(shù)，而不是依據(jù)經(jīng)驗(yàn)或人為設(shè)定，也是需要解決的問題。在非線性降維過程中，原始數(shù)據(jù)本征維數(shù)d都是由經(jīng)驗(yàn)已知或人為設(shè)定的，其設(shè)定值的大小對低維空間的映射結(jié)果有很大影響。d值過大使映射結(jié)果含有過多噪聲；d值