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

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

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

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

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

5、中，由于線性方法具有簡單性、易解釋性、可延展性等優(yōu)點，使得線性降維在高維數(shù)據(jù)處理中是一個主要研究方向。已有的線性維數(shù)約簡方法，主要包括主成分分析(Principal Component Analysis，PCA)16、獨立成分分析(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)等。這些方法實際是在不同優(yōu)化準則之下，尋求最佳線性模型，這也是線性維數(shù)約簡方法的共性。（10）通過消除數(shù)據(jù)建模過程中的全局線性假設，Sammon提出了一種非線性映射，即Sammon映射(SM)，該算法能夠保持輸入樣本之間的相關距離；Hastie提出了principal curves(PC)，其定義為通過概率分布或數(shù)據(jù)中間的光滑曲線；Kohonen基于自組織神經(jīng)網(wǎng)絡提出了self-organizing map(SOM)用來保存數(shù)據(jù)空間的拓撲屬性；Scholkopf等應用Mercer核將PCA擴展為Kernel PCA(KPCA)，該算法在高維

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

8、來維數(shù)約減的非線性方法，并且依靠它們在探測嵌入在高維空間中低維流形的能力和靈活性而被廣泛應用。具有代表性的流形學習算法包括等距映射 (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運用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、，就會導致鄰域圖不連通，如果選擇的鄰域太大，又可能導致短路。(3)使用Isomap算法恢復非線性流形的幾何結構的時候，所需的計算時間比較多，這主要是花在計算樣本點之間的最短路徑上。由于已有的流形學習算法對噪音和算法參數(shù)都比較敏感，詹德川、周志華14針對Isomap算法，提出了一種新方法，通過引入集成學習技術，擴大了可以產(chǎn)生有效可視化結果的輸入?yún)?shù)范圍，并且降低了對噪音的敏感性。另外，趙連偉15等人完善了Isomap的理論基礎，給出了連續(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)系，并實驗比較了2種著名流形學習算法(Isomap和LLE)的性能。文獻17中，作者提出了一種基于Isomap的監(jiān)督算法Weightedlso。在分類問題中，理想情況下屬于同一類的樣本在測量空間中應離得近一些，反之，不同類的樣本則離得遠一些。因此，作者在基本Isomap算法的第一步，計算各樣本點間的歐氏距離時引進了一個常量參數(shù)，用來重新度量同一類樣本間的距離，使它們離得更近。Weightedlso算法雖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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