流形學習及其算法分析

馮靈清+劉艷紅+劉宇晶

（山西農業(yè)大學信息科學與工程學院， 山西 太谷 030801）

摘 要： 流形學習作為機器學習、數(shù)據(jù)挖掘及模式識別領域近年來的一個研究熱點，其本質在于找出嵌入在高維空間中的低維光滑流形，揭示隱藏在高維數(shù)據(jù)中的內在低維結構，以實現(xiàn)非線性降維。介紹了流形學習的基本思想，分析、比較了等距映射（Isomap），局部線性嵌入算法（LLE），拉普拉斯特征映射算法（Laplacian Eigenmap）和局部保留投影等幾種常用流形學習算法的研究成果及優(yōu)缺點，提出了流形學習中的一些問題，以利于更好地進行數(shù)據(jù)的降維與分析。

關鍵詞： 流形學習； 等距離映射； 局部線性嵌入； 拉普拉斯特征映射； 局部保留投影

中圖分類號：TP301 文獻標志碼：A 文章編號：1006-8228（2017）04-01-04

Abstract： In recent years， manifold learning has become a hot issue in the field of machine learning， data mining and pattern recognition. The essence is to find the low dimensional smooth manifold embedded in the high-dimensional data space， reveal the intrinsic low dimensional structures in high dimensional data， in order to realize the nonlinear dimensionality reduction. This paper introduces the fundamental ideas， analyzes and compares the research results and the advantages and disadvantages of four manifold learning algorithms， such as Isomap， Locally Linear Embedding， Laplacian Eigenmap and Locality Preserving Projection， and puts forward some problems in manifold learning. The purpose is to understand the characteristics of these manifold learning algorithms in order to better reduce the data dimension.

Key words： manifold learning； Isomap； Locally Linear Embedding； Laplacian Eigenmap； Locality Preserving Projection

0 引言

隨著信息科學技術的發(fā)展和信息時代的到來，信息量越來越大，信息種類越來越復雜，信息數(shù)據(jù)的維數(shù)也越來越高，如何快速的對信息進行有效的處理并能夠提取出有效的信息是當今社會的一個重要研究課題。如今數(shù)據(jù)降維在許多領域起著越來越重要的作用。流形學習的主要思想就是將高維的數(shù)據(jù)映射到低維，使該低維的數(shù)據(jù)能夠反映原高維數(shù)據(jù)的某些本質結構特征。流形學習（Manifold learning）是機器學習、模式識別中的一種方法，在維數(shù)約簡方面具有廣泛的應用[1]。

1 流形和流形學習

1.1 流形

流形是線性子空間的一種非線性推廣，是一個局部可坐標化的拓撲空間。流形是拓撲學的一個概念，拓撲空間是拓撲學最基本的研究對象：設集合X上的拓撲τ是X的滿足以下性質的子集族①τ對屬于它的任意多元素的并集是封閉的；②τ對屬于它的有限多元素的交集是封閉的；③φ∈τ且X∈τ則稱（X，τ）是一個拓撲空間。如果對空間（X，τ）中的任意兩點x≠y存在A∈和B∈使得A∩B=φ，則稱（X，τ）是一個Hausdorff拓撲空間。設M是一個Hausdorff拓撲空間，若對每一點p∈M都有P的一個開領域U和Rn的一個開子集同胚，則稱M為n維拓撲流形，簡稱為n維流形[2]。

1.2 流形學習

在對流形的定義理解的基礎上，我們可以簡單概括流形學習這一個降維的過程：假設數(shù)據(jù)是均勻采樣于一個高維歐氏空間中的低維流形，流行學習就是從高維采樣數(shù)據(jù)中恢復低維流形結構，并求出相應的嵌入映射，以實現(xiàn)數(shù)據(jù)降維。用數(shù)學語言描述如下：設Y∈Rd是一個低維流形，f：Y→RD是一個光滑嵌入，其中D>d。數(shù)據(jù)集{yi}是隨機生成的，且經過f映射為觀察空間的數(shù)據(jù){x=f（yi）}。流形學習就是在給定觀察樣本{xi}集的條件下重構f和{yi}[3]。如圖1所示。

2 流形學習中的經典算法及分析

數(shù)據(jù)降維方法可以分為兩種：線性降維方法和非線性降維方法。線性降維理論主要有Fisher判別分析（FDA）、主成分分析（PCA）、多維尺度分析（MDS）、獨立分量分析（ICA）之類。線性方法相對于非線性流形方法計算相對簡單，但對于那些非線性結構的數(shù)據(jù)就無法得到有效的答案。非線性流形方法則可以對非線性結構進行分析計算，產生較可靠的結果。流形學習作為非線性降維的主要方法其研究和發(fā)展的空間很大，下面著重介紹等距映射（Isomap）、局部線性嵌入（Locally linear embedding）、拉普拉斯特征映射（Laplacian Eigenmap）、局部保留投影（Locality Preserving Projections）等幾種典型的流形學習算法。

2.1 等距離映射

等距離映射（Isomap）算法可以高效且有效地進行高維數(shù)據(jù)的低維嵌入以及利用數(shù)據(jù)降維的方法避免“維數(shù)災難”的發(fā)生。Isomap主要是通過分析現(xiàn)有的高維流形，得到高維流形所對應的低維嵌入，從而讓高維流形上數(shù)據(jù)點間的近鄰結構在低維嵌入中得到較完整的重現(xiàn)。該算法以MDS（Multidimensional Scaling）算法為分析工具，主要思想是：先計算流形上的測地線距離，然后利用計算出來的測地線來代替歐氏距離，應用MDS算法，從而發(fā)現(xiàn)嵌入在高維空間里的低維坐標，這樣Isomap就通過數(shù)據(jù)間的測地線距離，保留了數(shù)據(jù)固有的幾何分布結構。Isomap中的測地線距離則使用的是最近鄰接圖中的最短路徑[4]。

算法流程如下。

⑴ 確定流形M上哪些點是鄰近的，兩點（i，j）之間距離用Dx（i，j）表示；i，j點皆屬于空間X；Dx（i，j）距離定義為Euclidean距離[5]，鄰接關系可以設為固定的半徑e或K最近鄰。

⑵ 通過計算圖G上兩點間的最短路徑DG（i，j）估計流形M上測地線距離DM（i，j）。應用經典MDS構建一個在d維歐氏空間Y中保留最為完整的內在嵌入流形幾何[5]。

Isomap算法的優(yōu)點是利用了流形上的測地線距離來代替歐氏距離，可以較好的保留數(shù)據(jù)的空間結構，適用于學習內部平坦的低維流形；缺點是Isomap算法具有拓撲不穩(wěn)定性；若產生短環(huán)路則會嚴重影響其執(zhí)行；并且對流形具有一定的限制要求，不適于學習有較大內在曲率的流形，若流形不是凸的，則會發(fā)生變形；另外，若有空洞出現(xiàn)在流形上，Isomap算法也不能解決這個問題[6-7]。

2.2 局部線性嵌入

局部線性嵌入（LLE）是一種非線性降維算法[8]，與Isomap算法不同，局部線性嵌入（LLE）是一種局部算法，LLE假設采樣數(shù)據(jù)所在的低維流形局部是線性的，并假設每個采樣點均可以利用其近鄰樣本進行線性重構表示。LLE的學習目標是：低維空間中保持每個鄰域中的重構權值不變；在嵌入映射為局部線性的條件下，最小化重構誤差；最終形式化為特征值分解問題。它能夠使降維后的數(shù)據(jù)較好地保持原有流形結構。LLE可以說是流形學習方法最經典的工作之一。很多后續(xù)的流形學習、降維方法都與LLE有密切聯(lián)系。如圖2所示，使用LLE將三維數(shù)據(jù)（B）映射到二維（C）之后，映射后的數(shù)據(jù)仍能保持原有的數(shù)據(jù)流形（紅色的點互相接近，藍色的也互相接近），說明LLE有效地保持了數(shù)據(jù)原有的流行結構。

算法流程如下。

⑴ 計算每一個點的近鄰點，一般采用K近鄰或者ε鄰域。

⑵ 計算權值Wij使得把Xi用它的K個近鄰點線性表示的誤差最小，即通過最小化來求出。

⑶ 保持權值Wij不變，求Xi在低維空間的象Xj，使得低維重構誤差最小。。

LLE算法的優(yōu)點是該算法可以學習任意維的局部線性的低維流形并能夠歸結為稀疏矩陣特征值計算，計算復雜度相對較小。但是LLE在有些情況下并不適用，如果數(shù)據(jù)分布在整個封閉的球面上，LLE則不能將它映射到二維空間，且不能保持原有的數(shù)據(jù)流形。那么我們在處理數(shù)據(jù)中，首先假設數(shù)據(jù)不是分布在閉合的球面或者橢球面上。

2.3 拉普拉斯特征映射

拉普拉斯特征映射（LE）[9]算法的基本思想是，在高維空間中離得很近的點投影到低維空間中的象也應該離得很近，LE算法就是將處于流形上的數(shù)據(jù)，在盡量保留原數(shù)據(jù)間相似度的情況下，映射到低維下表示。該算法可以反映出數(shù)據(jù)內在的流形結構。其求解方法就是求解圖拉普拉斯算子的廣義特征值問題。

Laplacian Eigenmap算法流程如下。

⑴ 從樣本點構建一個近鄰圖，圖的頂點為樣本點，離得很近兩點用邊相連（K近鄰或ε鄰域）。

⑵ 給每條邊賦予權值，如果第i個點和第j個點不相連，權值為0，否則Wij=1。

⑶ 計算圖拉普拉斯算子的廣義特征向量，求得低維嵌入。令D為對角矩陣，L=D-W，L是近鄰圖上的拉普拉斯算子，求解廣義特征值問題Lf=λDf。

LE（Laplacian Eigenmap）算法的優(yōu)點是局部非線性方法，與譜圖理論有很緊密的聯(lián)系；算法通過求解稀疏矩陣的特征值問題，解析地求出整體最優(yōu)解，效率非常高；算法使原空間中離得很近的點在低維空間也離得很近，可以用于聚類。LE算法的缺點是同樣對算法參數(shù)和數(shù)據(jù)采樣密度較敏感，不能有效地保持流形的全局幾何結構。

Isomap，LLE，Laplacian Eigenmap算法有效的原因是它們都是非參數(shù)的方法，不需要對流形的很多的參數(shù)假設。它們是非線性的方法，都基于流形的內在幾何結構，更能體現(xiàn)現(xiàn)實中數(shù)據(jù)的本質。它們的求解簡單，都轉化為求解特征值問題，而不需要用迭代算法。

2.4 局部保留投影

局部保留投影（LPP）算法[10]是在LE算法的基礎上，假設一個從原空間到流形空間的映射矩陣P，然后通過某種方法求出P，最后得到一個顯示的投影映射。LPP是一種新的子空間分析方法，它是非線性方法Laplacian Eigenmap 的線性近似，既解決PCA等傳統(tǒng)線性方法難以保持原始數(shù)據(jù)非線性流形的缺點，又解決了非線性方法難以獲得新樣本點低維投影的缺點。在受控環(huán)境的人臉識別中獲得了成功的應用。局部保持投影LPP和PCA、LDA等方法類似，局部保持投影（LPP）通過一定的性能目標來尋找線性變換w以實現(xiàn)對高維數(shù)據(jù)的降維。下面簡單介紹其實現(xiàn)過程。

LPP在一定程度上能夠反映數(shù)據(jù)分布的非線性特征。LPP算法有著明晰的投影矩陣，這個性質對于解決新樣本的特征提取是非常重要的。因此可以首先用訓練樣本求取投影矩陣，然后將樣本投影到這個矩陣上即可完成特征提取。然而LPP方法仍然屬于無監(jiān)督學習方法，未能有效的利用樣本的類別信息，因此 Yang等提出了一種基于非局部保持投影（Non-locality Preserving Projecting，NLPP）的特征抽取方法。2006年，龐彥偉等[11]提出了一種新的基于核子空間的方法用于人臉識別特征抽取，即基于核的非局部保持投影（KNLPP）。2008 年，Li 等[12]提出了一種有效的克服了小樣本和樣本外點問題的局部線性判別嵌入法（LLDE）。

3 流形學習算法中有待進一步研究的問題

隨著人們對流形學習研究的不斷深入和推廣，從解決實際問題的角度，流形學習方法為探索非線性流形分布數(shù)據(jù)的內在結構提供了一種有效的途徑。然而在實際應用中，流形學習方法仍然存在一些問題有待進一步研究[13]。

⑴ 流形學習算法中的噪聲問題有待解決；

⑵ 如何將流形學習推廣到半監(jiān)督以及有監(jiān)督的情況用于模式識別等多領域；

⑶ 當采樣數(shù)據(jù)很稀疏時，怎樣進行有效的學習；

⑷ 本征維數(shù)的確定仍是流形學習算法中的一個研究難點；

⑸ 如何將統(tǒng)計學習理論引入流形學習對其泛化性能進行研究；

⑹ 如何確定低維目標空間的維數(shù)；

這些也將是非線性降維研究的主要方向。

4 結束語

流形學習方法作為一類新興的非線性維數(shù)約簡方法，主要目標是獲取高維觀測數(shù)據(jù)的低維緊致表示，探索事物的內在規(guī)律和本征結構，已經成為數(shù)據(jù)挖掘、模式識別和機器學習等領域的研究熱點。本文介紹了幾種主要的流形學習算法，并對其優(yōu)缺點作了算法分析，并探討了其在理論和應用中有待進一步研究的問題。

參考文獻（References）：

[1] 王自強，錢旭，孔敏.流形學習算法綜述[J].計算機工程與應用，

2008.44（35）：9-12

[2] M Berger， B Gostiaux. Differential Geometry： Manifolds，

Curves and Surfaces， GTM115. Springer-Verlag，1974.

[3] 陳維桓，微分流形初步（第二版）[M].高等教育出版社，2001.

[4] 趙連偉，羅四維，趙艷敞等.高維數(shù)據(jù)流形的低維嵌入及嵌入

維數(shù)研究[J].軟件學報，2005.16（8）：1423-1430

[5] Roweis ST，Saul LK.Nonlinear dimensionality analysis by

locally linear embedding.Science，2000.290（12）：323-2326

[6] J.B.Tenenbaum，V.de Silva and J.C.Langford，A Global

Geometric Framework for Nonlinear Dimensionality Reduction.Science，2000.290（5500）：2319-2323

[7] 吳曉婷，閆德勤.數(shù)據(jù)降維方法分析與研究[J].計算機應用研

究，2009.8：2833-3835

[8] Roweis S，Saul LK. Nonlinear dimensionality reduction by

local-y linear embedding. Science，2000.290：2323-2326

[9] Belkin M，Niyogi P. Laplacian eigenmaps for dimensionality

re-duction and data representation. Neural Computation，2003.15（6）：1373-1396

[10] He X， Yan S， Hu Y， Niyogi P， and Zhang H J. Face

recognition using Laplacian faces. IEEE Trans. on Pattern Anal. Machine Intelli.，2005.27（3）：328-340

[11] 龐彥偉， 俞能海， 沈道義， 劉政凱.基于核鄰域保持投影的

人臉識別[J].電子學報，2006.34（8）：1542-1544

[12] Bo Li， D.S.Huang. Locally linear discriminant embedding：

An efficient method for facerecognition. Pattern Recognition，2008.41（12）：3813-3821

[13] 高小方.流形學習方法中的若干問題分析[J].計算機科學，

2009.36（4）：25-28