張韜

摘 要：流形學(xué)習(xí)的目的就是對(duì)高維樣本點(diǎn)集進(jìn)行非線性降維，從中挖掘出樣本點(diǎn)集的有效特征。本文主要對(duì)流形學(xué)習(xí)算法的研究現(xiàn)狀進(jìn)行分析，從中指出其存在的潛在問題，以及對(duì)未來的研究方向進(jìn)行分析探討。

關(guān)鍵詞： 流形學(xué)習(xí);樣本點(diǎn)集;降維;算法

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2019）14-0203-03

0 引言

隨著社會(huì)的發(fā)展， 目前已經(jīng)進(jìn)入到數(shù)據(jù)時(shí)代， 大數(shù)據(jù)這個(gè)概念被很多的人所認(rèn)識(shí)。數(shù)據(jù)時(shí)代我們面臨的數(shù)據(jù)量越來越大， 且數(shù)據(jù)的復(fù)雜度越來越高。這樣存在一個(gè)很突出的問題， 當(dāng)我們對(duì)大數(shù)據(jù)進(jìn)行處理時(shí)， 會(huì)造成處理的時(shí)間及成本代價(jià)很高。另外， 通常在對(duì)數(shù)據(jù)進(jìn)行學(xué)習(xí)之前， 需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理， 即對(duì)數(shù)據(jù)進(jìn)行清洗。所謂清洗， 就是將無用的信息剔除掉， 將有用的信息保留。常用的方法就是對(duì)數(shù)據(jù)集進(jìn)行特征提取， 根據(jù)學(xué)習(xí)的需求， 從中提取有用信息。

通常情況下， 數(shù)據(jù)點(diǎn)集的維度很高， 每個(gè)維度都表示數(shù)據(jù)的一個(gè)特征， 從多個(gè)特征中提取少量特征， 其實(shí)質(zhì)就是對(duì)樣本點(diǎn)集進(jìn)行降維。常見的降維方法有線性降維算法， 其主要目的是通過學(xué)習(xí)一個(gè)線性降維映射， 將高維樣本點(diǎn)集投影到低維空間。常見的線性降維算法有P C A [ 9 ] 、MDS[8]、LDA[10]。主成分分析法（PCA）是最著名的線性降維算法， 其采用統(tǒng)計(jì)學(xué)的思想， 通過構(gòu)造樣本點(diǎn)集之間的協(xié)方差矩陣來分析樣本點(diǎn)的分布特點(diǎn)。通過對(duì)協(xié)方差矩陣進(jìn)行特征值分解， 按照特征值的大小對(duì)特征向量進(jìn)行排列。最大的特征值所對(duì)應(yīng)的特征向量表示第一主成分， 它表明，樣本點(diǎn)集沿著此方向分布最多。依次可以構(gòu)造第二主成分， 第三主成分等。通過這樣的方式， 可以達(dá)到對(duì)樣本點(diǎn)集進(jìn)行降維的目的。多維尺度分析（ M D S ） 是另一類比較經(jīng)典的線性降維算法， 其采用幾何學(xué)的知識(shí)， 希望在降維過程中保持高維樣本點(diǎn)之間的歐氏距離， 也就是說降維后， 低維樣本點(diǎn)之間的歐氏距離與對(duì)應(yīng)的高維樣本點(diǎn)之間的距離保持一致。因此M D S 算法的關(guān)鍵是求解樣本點(diǎn)之間的距離矩陣。第三個(gè)比較經(jīng)典的線性降維算法是線性判別分析法（ L D A ） ， 這個(gè)算法主要用在分類學(xué)習(xí)中。對(duì)于帶有標(biāo)簽信息的樣本點(diǎn)集， L D A 算法的目的是讓同一類的樣本點(diǎn)映射后距離較近， 而不同類樣本點(diǎn)映射后距離盡可能的遠(yuǎn)。這三類樣本點(diǎn)在處理樣本點(diǎn)呈現(xiàn)出線性分布結(jié)構(gòu)時(shí)， 它們的降維效果非常的好。然而現(xiàn)實(shí)生活中， 由于通常處理的數(shù)據(jù)量非常的大， 而且數(shù)據(jù)的維數(shù)非常的高， 因此樣本點(diǎn)集在高維空間中呈現(xiàn)出高度非線性分布結(jié)構(gòu)。而針對(duì)這種分布特點(diǎn)的樣本點(diǎn)集， 常見的線性降維算法已經(jīng)無法精確的來提取其有效特征。因此， 基于此目的， 研究者提出一類非線性降維方法。

首先針對(duì)非線性分布的樣本點(diǎn)集， S c h o l k o p f等人引入核函數(shù)的思想， 提出核化主成分分析法（ K P C A ） [ 1 1 ] ， 這個(gè)方法的主要思想是將核函數(shù)加入到樣本點(diǎn)集上， 首先利用核函數(shù)， 將初始樣本點(diǎn)集映射到更高維空間中， 使得樣本點(diǎn)集在更高維空間中呈現(xiàn)出線性分布特征， 然后再利用P C A算法對(duì)更高維的樣本點(diǎn)集進(jìn)行線性特征提取。這個(gè)方法存在的問題是， 如何選擇非線性核函數(shù)是算法的難點(diǎn)。因此，為了避免這個(gè)方法的局限性， 在2 0 0 0 年《科學(xué)》雜志上提出了流形學(xué)習(xí)的思想， 也就是假設(shè)一組非線性分布的高維樣本點(diǎn)集分布在一個(gè)低維子流形上， 然后利用流形的性質(zhì)對(duì)樣本點(diǎn)集進(jìn)行特征提取。從直觀上理解， 流形是局部具有歐氏空間性質(zhì)的幾何空間， 也就是流形上每一點(diǎn)的局部鄰域與歐氏空間的某個(gè)子集之間存在同胚映射關(guān)系， 因此從局部上借助于歐氏空間的性質(zhì)對(duì)高維樣本點(diǎn)集進(jìn)行降維。流形學(xué)習(xí)首次引入了局部化的思想。

1 流形學(xué)習(xí)

下面我們對(duì)幾類經(jīng)典的流形學(xué)習(xí)算法進(jìn)行分析， 從中來分析其存在的一些優(yōu)點(diǎn)及局限性。流形學(xué)習(xí)首次將局部化的思想引入到機(jī)器學(xué)習(xí)中。其基本思想是從樣本點(diǎn)集的局部鄰域出發(fā)來獲取其潛在的有效特征。因此流形學(xué)習(xí)的首要任務(wù)是對(duì)高維樣本點(diǎn)集進(jìn)行鄰域劃分， 常見的鄰域劃分的方法有兩種， 一種是K - 近鄰法， 一種是ε- 球鄰域法。（ 1 ） K -近鄰法[ 7 ]的基本思想如下： 首先任意選取一個(gè)樣本點(diǎn)， 其次計(jì)算其與其余樣本點(diǎn)之間的歐氏距離， 然后對(duì)這組歐氏距離進(jìn)行排序， 選擇距離最近的K 個(gè)樣本點(diǎn)作為其最近鄰點(diǎn)。

（ 2 ）ε-球鄰域法的基本思想如下： 首先仍然是任意選取一個(gè)樣本點(diǎn)， 然后以這個(gè)樣本點(diǎn)為中心， ε為球半徑做一個(gè)球面， 球面內(nèi)部的樣本點(diǎn)就稱為此樣本點(diǎn)的球鄰域點(diǎn)。為了分析的方便， 在此假設(shè)高維樣本點(diǎn)集表示為{ x 1 ，x 2 ， …， x N} ， x i∈R D ，其中N表示樣本點(diǎn)集的個(gè)數(shù)， D 表示樣本點(diǎn)集的維度。降維后對(duì)應(yīng)的低維空間的樣本點(diǎn)集表示為{ y 1，y 2，…，y N} ，y i∈Rd，d表示低維空間的維度。

1.1 等度量映射（ISOMAP）

ISOMAP[2 ]是在20 00年提出的流形學(xué)習(xí)算法，它引入了流形學(xué)習(xí)的概念。其基本思想是以線性降維M D S 算法為基礎(chǔ)， 通過獲取高維樣本點(diǎn)集之間真實(shí)的測(cè)地線距離來代替兩點(diǎn)之間的歐氏距離。在流形上， 任意兩點(diǎn)之間的真實(shí)距離通過測(cè)地線距離來表示。因此I S O M A P 算法的主要思想是獲取任意兩個(gè)樣本點(diǎn)之間的測(cè)地線距離， 然后利用M D S算法， 在低維空間重構(gòu)一組樣本點(diǎn)集， 使得在低維空間任意兩點(diǎn)之間的歐氏距離等于高維樣本點(diǎn)之間的測(cè)地線距離。算法的具體步驟表示如下：

第一步： 利用鄰域劃分算法對(duì)高維樣本點(diǎn)集{ x 1 ，x 2 ，…， x N} 進(jìn)行鄰域劃分。

第二步： 在樣本點(diǎn)集上構(gòu)造局部鄰接圖， 利用D i j k s t r a算法[ 6 ] 計(jì)算任意兩點(diǎn)之間的最短路徑， 鄰域點(diǎn)之間的最短路徑表示為兩點(diǎn)之間的歐氏距離。

第三步： 利用M D S 算法以及第二步求得的樣本點(diǎn)之間的距離矩陣，在低維空間重構(gòu)一組樣本點(diǎn)集{ y 1 ，y 2 ，…，y N}。

1.2 局部線性嵌入（LLE）

LLE[2]算法與ISOMAP算法同年發(fā)表在《科學(xué)》雜志上的另一篇流形學(xué)習(xí)算法。它與I S OM A P算法的出發(fā)點(diǎn)不同， 它的主要目的是在降維過程中保持樣本點(diǎn)集之間的局部幾何結(jié)構(gòu)。因此它屬于保局部結(jié)構(gòu)的算法。L L E 算法的基本思想是假設(shè)流形的局部鄰域?yàn)榫€性空間， 鄰域內(nèi)的中心點(diǎn)可以由它的鄰域點(diǎn)集進(jìn)行線性表示， 其對(duì)應(yīng)的線性相關(guān)系數(shù)表示鄰域點(diǎn)之間的局部幾何結(jié)構(gòu)。L L E 降維的目的是在低維空間重構(gòu)一組樣本點(diǎn)集， 使得樣本點(diǎn)集對(duì)應(yīng)的局部鄰域樣本點(diǎn)之間仍然滿足這個(gè)線性相關(guān)系數(shù)。下面給出算法的具體步驟：

第一步： 仍然是利用鄰域劃分方法對(duì)高維樣本點(diǎn)集進(jìn)行劃分。

第二步： 以樣本點(diǎn)x i 的鄰域?yàn)槔齺碚f明， 計(jì)算鄰域中心點(diǎn)與其鄰域點(diǎn)之間的線性相關(guān)表示系數(shù)。

第三步： 在低維空間重構(gòu)一組樣本點(diǎn)集， 使得對(duì)應(yīng)的鄰域點(diǎn)之間滿足高維樣本點(diǎn)之間的線性相關(guān)性。

1.3 拉普拉斯特征映射（LEM）

L E M [ 3 ]是另一類經(jīng)典的流形學(xué)習(xí)算法， 它也屬于保局部特征的降維學(xué)習(xí)算法。其基本思想是希望降維后距離較近的點(diǎn)仍然距離很近， 因此在鄰域點(diǎn)之間賦予權(quán)值， 利用權(quán)值來表示兩點(diǎn)之間的相似度， 權(quán)值越大表示兩點(diǎn)之間的相似度越高。算法的基本步驟表示如下：

第一步： 利用鄰域劃分方法對(duì)高維樣本點(diǎn)集進(jìn)行鄰域劃分。

第二步： 構(gòu)造鄰域點(diǎn)之間的權(quán)值， 在此利用高斯函數(shù)來計(jì)算鄰域點(diǎn)權(quán)值。對(duì)于非鄰域點(diǎn)之間的權(quán)值賦予零。第三步： 利用第二步求得的鄰域點(diǎn)之間的權(quán)值， 在低維空間重構(gòu)樣本點(diǎn)集， 使得距離越近的點(diǎn)， 在低維空間中仍然距離越近。

2 流形學(xué)習(xí)現(xiàn)存問題分析

第二節(jié)， 我們只對(duì)流形學(xué)習(xí)的三個(gè)經(jīng)典的算法進(jìn)行了詳細(xì)的介紹， 由于流形學(xué)習(xí)屬于無監(jiān)督學(xué)習(xí)的范疇， 因此在這十幾年當(dāng)中， 流形學(xué)習(xí)得到了迅速的發(fā)展， 除了這三類經(jīng)典的算法以外， 流形學(xué)習(xí)又發(fā)展了一系列經(jīng)典的算法，例如HLLE[1 4]、LTSA[1 2]、LPP[1 3]算法等。下面我們來分析一下這些算法所存在的一些問題。

通過對(duì)這些算法進(jìn)行分析可以看出， 流形學(xué)習(xí)算法的一個(gè)共有的前提假設(shè)是所處理的高維樣本點(diǎn)集分布在某個(gè)低維子流形上， 這個(gè)子流形是嵌入在高維空間中的。除此之外， 針對(duì)每個(gè)算法又有各自特有的假設(shè)條件。例如I S O M A P 算法假設(shè)所處理的流形為一個(gè)無洞的凸子集， 并且流形是與歐氏空間之間等距同胚的。另外L L E 以及H L L E 、L T S A 等算法假設(shè)樣本點(diǎn)的局部鄰域是線性空間。這些假設(shè)存在如下一系列問題。

（ 1 ） 針對(duì)分布呈現(xiàn)出非線性結(jié)構(gòu)的流形， 例如球面， 假設(shè)局部鄰域?yàn)榫€性空間就會(huì)存在問題。

（ 2 ） 在進(jìn)行鄰域劃分的時(shí)候， 是在每個(gè)點(diǎn)都進(jìn)行鄰域劃分， 這樣就導(dǎo)致鄰域集的個(gè)數(shù)與樣本點(diǎn)的個(gè)數(shù)保持一樣。對(duì)于大數(shù)據(jù)級(jí)別的數(shù)據(jù)量， 會(huì)導(dǎo)致構(gòu)造的鄰域的個(gè)數(shù)過大， 使得算法的復(fù)雜度非常的高。

（ 3 ） 在對(duì)子流形的低維維度進(jìn)行估計(jì)時(shí)， 由于假設(shè)局部鄰域?yàn)榫€性空間， 這樣會(huì)導(dǎo)致估計(jì)存在偏差。

針對(duì)以上存在的這些問題， 近些年來， 已經(jīng)有一些改進(jìn)的算法，例如MLLE算法[5]是對(duì)LLE算法進(jìn)行改進(jìn)，使得所選取的鄰域點(diǎn)更合理。TCIE算法[4 ]是對(duì)ISOMAP算法進(jìn)行改進(jìn)， 這個(gè)算法消除了I S OM A P算法對(duì)流形凸假設(shè)的條件。盡管又發(fā)展了一系列改進(jìn)的算法， 但是這些算法本身仍然存在一些未被解決的問題。例如， 已有的流形學(xué)習(xí)算法仍然未考慮流形局部的彎曲程度， 即曲率信息。在對(duì)鄰域進(jìn)行劃分時(shí)并未考慮樣本點(diǎn)的分布特點(diǎn)。因此， 在接下來的工作中， 可以將流形本身的拓?fù)浣Y(jié)構(gòu)加入到流形學(xué)習(xí)算法中， 從本身的結(jié)構(gòu)出發(fā)來設(shè)計(jì)算法。

3 實(shí)驗(yàn)分析

在本實(shí)驗(yàn)中， 我們主要采用一組三維合成數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)， 從中分析已有的流形學(xué)習(xí)算法所存在的一些問題。在此， 我們主要選取了兩組數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)， 一組是分布呈現(xiàn)出瑞士卷結(jié)構(gòu)的三維數(shù)據(jù)集（Swis s Roll），一組是球面數(shù)據(jù)集（Punctured Sphere）。

在實(shí)驗(yàn)設(shè)計(jì)中，我們主要采用I S OMAP、L LE以及L EM三個(gè)流形學(xué)習(xí)算法對(duì)這兩組數(shù)據(jù)集進(jìn)行降維， 從中分析算法的降維效果。具體的可視化結(jié)果表示如圖1 ， 圖2 所示。每個(gè)圖有四個(gè)子圖， 從左到右分別表示初始數(shù)據(jù)集， I S O M A P算法降維效果， L L E 算法降維效果， L E M 算法降維效果。從這兩個(gè)圖可以看出， 它們的降維效果并沒有達(dá)到最好， 例如，針對(duì)Swis s Roll數(shù)據(jù)集，LLE算法以及LEM算法的降維效果就不好， 究其原因是因?yàn)樵诮稻S過程中并未考慮樣本集分布的彎曲程度。

4 結(jié)語

本文主要對(duì)流形學(xué)習(xí)的幾類算法進(jìn)行解釋， 從中分析不同算法所存在的主要問題。在實(shí)驗(yàn)方面， 選取了兩組數(shù)據(jù)集在不同的流形學(xué)習(xí)算法上進(jìn)行實(shí)驗(yàn)， 實(shí)驗(yàn)結(jié)果也印證了我們所分析的當(dāng)前流形學(xué)習(xí)所存在的問題。

參考文獻(xiàn)

[1] S. Roweis and L. Saul， Nonlinear dimensionality reductionby locally linear embedding. Science， vol.290，2000.

[2] J. B. Tenenbaum， V. de Silva and J. C. Langford， Aglobal geometric framework for nonlinear dimensionalityreduction. Science， vol.290，2000.

[3] M. Belkin and P. Niyogi， Laplacian eigenmaps and spectraltechniques for embedding and clustering. In proc.Int. Conf. Advances in Neural Information ProcessingSystems，2001.

[4] G. Rosman， M.M Bronstein， A.M. Bronstein， and R. Kimmel.Nonlinear dimensionality reduction by topologically constrainedisometric embedding. Int. J. Comput. Vis.89：56-68，2010.

[5] Z. Zhang， J. Wang. Mlle： modified locally linear embeddingusing multiple weights. NIPS 19：1593-1600，2006.

[6] E.W. Dijkstra. A note on two problems in connectionwith graphs. Numerische Mathematic， 1：269-271. Doi：10.1007/BF01386390.

[7] T.M. Cover and P. E. Hart. Nearest neighbor patternclassification. IEEE Transactions on Information Theory，13（1）：21-27，1967.

[8] M.A.A. Cox， T.F. Cox， Multidimensional scaling. In： Handbookof Data Visulization，315-347，2008.

[9] Lindsay T Smith. A tutorial on principal componentsanalysis. February 26，2002.

[10] R. A. Fisher. The use of multiple measurements intaxonomic problems. Annales of Eugenics，7（2）：179-188，1936.

[11] J. Yang， A.F. Frangi， J.-Y. Yang， D. Zhang， and Z. Jin.KPCA plus LDA： a complete kernel Fisher discriminantframework for feature extraction and recognition. IEEETrans Pattern Analysis and Machine Intelligence， vol. 27，no.2，pp. 230-244，2005.

[12] Z. Zhang， H. Zha. Principal manifolds and nonlineardimension reduction via local tangent space alignment.SIAM J. Sci. Comput.26：313-338，2004.

[13] Xiaofei He and Partha Niyogi. Locality preservingprojection. Int. Conf Advances in Neural Information ProcessingSystems，2003.

[14] D.L. Donoho， C.E. Crimes. Hessian eigenmaps： locallylinear embedding techniques for high-dimensional data.Proc. Nati. Acad. Sci. USA 100：5591-5596，2003.