郝晨輝

摘 要：流形學習是借助幾何學中子流形的概念，利用流形的結果和性質來挖掘嵌入在高維空間中的數(shù)據(jù)集的真實的低維結構。本文在介紹流形學習具體算法的基礎上，通過MATLAB分析了不同算法的特點，對不同算法之間的關系進行了比較?；诖朔治觯覀儗ΜF(xiàn)有流行學習的缺點及局限提出了優(yōu)化方法及改進方法。

關鍵詞：流形學習；算法；映射；數(shù)據(jù)集

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1671-2064（2018）01-0219-04

1 引言

對于如今的機器學習來說，面臨著所需處理的數(shù)據(jù)量、數(shù)據(jù)特征遞增的趨勢，但是有效的數(shù)據(jù)特征相對較少，為了減輕不必要的時間消耗，在處理數(shù)據(jù)之前都要對數(shù)據(jù)的特征進行稀疏化，一種方法是直接對數(shù)據(jù)的維數(shù)進行降維，來達到重要特征提取的目的。另一種是對數(shù)據(jù)的特征進行稀疏化，把沒用的特征信息都設置為零，從而達到特征稀疏的目的。本文主要從降維這個角度來進行探討。

早期主要的降維方法是線性降維算法主成分分析法PCA[6]，其主要過程是研究一個線性降維映射，將高維空間中的樣本點集投影到低維空間中。PCA[6]通過最大化數(shù)據(jù)點集之間的協(xié)方差矩陣來選取數(shù)據(jù)點集分布的最主要的特征，從而達到降維的目的。這種算法適用于處理的數(shù)據(jù)集呈現(xiàn)線性分布。但是針對分布呈現(xiàn)復雜的非線性分布，PCA很難達到較好的降維效果。非線性分布的高維樣本點集，其所在的非線性空間可以看成是嵌入在高維空間的低維非線性子空間。在機器學習中通常采用kernel函數(shù)的方法來進行處理，稱之為kernel PCA[7]。這種算法存在的問題是很難選擇一個合適的kernel函數(shù)，如果kernel選擇的不合適反而會對學習過程造成很大的影響，增加學習的時間消耗，且最終的降維效果也不會很好。

針對復雜的非線性分布的數(shù)據(jù)點集，雖然全局結構無法獲得，但我們可以看出數(shù)據(jù)點集的很小的局部鄰域結構還是呈現(xiàn)出線性分布結構。對于這種局部呈現(xiàn)出線性結構而全局呈現(xiàn)出非線性結構的數(shù)據(jù)點，我們將其假設成分布在某個流形上，其降維過程稱為流形學習。

流形學習是一類借鑒拓撲流形概念的降維方法?！傲餍巍笔窃诰植颗c歐氏空間同胚的空間，直觀上來說“流形”的局部鄰域可以近似的看成是歐氏空間結構。根據(jù)流形的這個性質所設計出的流形學習算法都是從流形的局部結構出發(fā)通過保持流形的局部線性結構來對高維樣本點集進行降維。當然流形的全局結構也是從局部結構出發(fā)來獲取全局的結構。流形學習算法，大致可以分為兩大類，都是在假設流形的局部鄰域為線性空間基礎上進行的。一類是保持全局結構的非線性降維算法，如Isomap[2]：Isomap又稱為等距映射算法，目的是保持降維前后任意兩點之間的真實的距離結構。在流形上，任意兩點之間的真實的距離不是兩點之間的歐氏距離，而是兩點之間的測地線距離。所以Isomap旨在保持任意兩點之間的測地線距離。另一類是保局部結構的降維算法，如LLE[1]，LEP[3]，LPP[9]，LTSA[5]，HLLE[4]等。LLE算法旨在保持樣本點局部鄰域的線性組合結構，通過假設高維樣本點的局部鄰域是線性結構，然后計算每個樣本點與其鄰域點之間的線性相關系數(shù)，由此在低維空間中鄰域點之間還保持相同的線性相關性。LEP算法旨在保持局部樣本點之間的結構，降維的主要思想是距離較近的點降維后還是距離較近，在算法設計中通過建立樣本點集之間的局部鄰域圖結構，任意兩點之間的邊賦予相應的權重，通過權重來體現(xiàn)局部鄰域點之間的距離關系。LPP繼承了LEP算法的思想，給出保持局部結構的線性降維算法。LTSA算法也是將流形的局部鄰域假設成線性空間，然后在局部鄰域上利用PCA進行降維。

2 基本知識介紹

流形學習算法的共有的前提假設是，所要降維的高維樣本點集分布在某個非線性流形F上，此流形是嵌入在高維歐氏空間中的一個子流形。流形學習的目的是從高維空間中挖掘出子流形F的真實的低維表示結構。為了算法的需求，我們假設高維樣本點集表示為{x1，x2，…，xN}∈FRD，其中N表示樣本點集的個數(shù)，D表示高維樣本點集的維數(shù)。對應的低維樣本點集表示為{y1，y2，…，yN}∈YRd，其中d表示低維樣本點集的維數(shù)?；诖四康模覀兘o出流形學習的形式化定義。

流形學習的目的是挖掘高維樣本點集產生的機制，表示為映射f，具體的表示形式如下：f：Y→FRD。

在降維過程中，流形的全局或局部幾何結構得到保持。

3 算法描述

3.1 等距映射

Isomap[2]又稱等距映射算法，其目的是保持降維前后所有樣本點集之間的全局距離結構。Isomap借助MDS[8]來挖掘高維樣本點集之間真實的內在結構。MDS[8]是保持降維后高維樣本點集之間的歐氏距離結構。而Isomap旨在保持樣本點集之間真實的距離結構。在流形上，兩點之間真實的距離不是歐氏距離，而是兩點之間的測地線距離。在此算法中，通過構造樣本點之間的局部圖結構，然后任意兩點之間的測地線距離通過尋找兩點之間的最短路徑來獲得。

算法步驟如下：

（1）確定原空間每個點的鄰域點（找樣本點的近鄰點方法有兩種：1）是規(guī)定k的值即取距離樣本點最近的k個近鄰點。2）是規(guī)定一個球的半徑E，以樣本點為球心，找出這個球覆蓋的樣本點。）

（2）估算測地線距離（高維空間中較近點之間的測地線距離用歐式距離代替，較遠點距離用測地線距離，最短路徑逼近，計算公式為dG（i，j）=min{dG（i，k）+dG（k，j）}，其中dG（i，j）表示點i與點j之間的歐氏距離），從而構造所有數(shù)據(jù)點之間的距離矩陣D。

（3）用MDS在低維歐式空間找到點間距符合第一步中距離的點{y1，y2，…，yN}∈Rd。

MDS算法：

輸入主對角線元素為零的距離矩陣D。endprint

（2）計算B矩陣的譜分解

（3）通過求出形成矩陣

（4），我們取矩陣X的前d個列向量所組成的矩陣XN×d作為低維輸出。

其中H是半正定矩陣，D是非負對稱矩陣，B是格拉姆矩陣

此種算法的優(yōu)點是：1）具有估計低維空間維數(shù)的作用，不用給定低維空間的維數(shù)。2）整體等距映射到低維空間，無需考慮局部坐標之間的相容性。3）很好的識別了非線性流形結構。

3.2 局部線性嵌入映射

LLE[1]又稱局部線性嵌入映射，此算法假設樣本點所在的子流形的局部鄰域是線性結構。與Isomap算法不同，LLE算法旨在保持樣本點集的局部鄰域的線性結構，其基本思想可以簡單的表示如下：流形上任意數(shù)據(jù)點p∈M，都可以用其K-鄰域內的K個鄰近點近似線性表示，然后在低維歐式空間中重構一組低維樣本點表示{y1，y2，…，yN}，使得這些低維樣本點集的局部鄰域點之間也滿足原始數(shù)據(jù)點之間的線性組合關系。

算法步驟如下：

（1）找每個樣本點{x1，x2，…，xN}的近鄰點（方法同Isomap）。

（2）計算高維鄰域點之間的局部權值矩陣Wij，其中xij為xi的k個近鄰點。滿足代價函數(shù)并滿足約束條件。

定義一個誤差函數(shù)，如下：

誤差函數(shù)值越小，說明局部權值矩陣重建的越好，說明xi越接近其近鄰點的線性組合的點。

（3）在低維空間重構一組樣本點{y1，y2，…，yN}，使得其保持高維鄰域點之間的線性相關關系。

此種算法的優(yōu)點是：1）算法中建立的權值矩陣是一個稀疏矩陣，計算量較??；2）算法具有整體最優(yōu)解（低維歐式空間所對應的所有數(shù)據(jù)點表示），不需要迭代，減少了計算的復雜性。

3.3 拉普拉斯特征映射

拉普拉斯特征映射（LEM）[3]借助Laplace矩陣的性質來對高維樣本點集進行降維。其與LLE算法思想基本相似，保持高維樣本點集的局部幾何結構。LEM的目的就是尋找原始數(shù)據(jù)流形在低維歐式空間的對應表示，LEP算法有著很直觀的降維目標，即在高維空間中離得很近的點投影到低維空間中的像也應該離得很近，這能夠保持局部幾何結構不變?；诖?，LEM算法所要優(yōu)化的目標函數(shù)為。

其中Y表示低維數(shù)據(jù)點集的矩陣表示形式，矩陣L=D-W是拉普拉斯矩陣。限制條件YTY=I保證優(yōu)化問題有非奇異解，并且保證映射后的數(shù)據(jù)點不會被“壓縮”到一個小于m維的子空間中?；谶@樣的算法思想，我們給出LEP算法的基本步驟。

算法步驟：

（1）根據(jù)K-鄰域法選擇每一點處的k個近鄰點集。

（2）將每個樣本點的k個近鄰點連接成鄰接圖。

（3）構造數(shù)據(jù)點集上的權值矩陣W，W的每個分量表示相應兩點之間的權重。

（4）計算拉普拉斯矩陣L的特征向量與特征值。

使用最小的d個非零特征值對應的特征向量作為降維后的輸出結果，其中d表示低維空間的維數(shù)。

此種算法的優(yōu)點是：通過求解稀疏矩陣的特征值可以求出整體最優(yōu)解。

4 算法實踐及分析

分別選取兩類數(shù)據(jù)集對各類流形學習算法的降維效果進行對比分析。一類數(shù)據(jù)集為仿真數(shù)據(jù)集，我們分別選取兩組仿真數(shù)據(jù)集：Swiss Roll和Punctured Sphere。另一類數(shù)據(jù)集為真實世界中的數(shù)據(jù)集，USPS手寫體識別數(shù)據(jù)集。首先對仿真數(shù)據(jù)集進行實驗分析，然后對USPS數(shù)據(jù)集進行分析。

4.1 仿真數(shù)據(jù)集

Swiss Roll以及Punctured Sphere為兩組三維數(shù)據(jù)點集，其每一個數(shù)據(jù)點都是由一個三維向量進行表示。在本實驗中，我們分別采取800個Swiss Roll數(shù)據(jù)點以及1000個Puncture Sphere數(shù)據(jù)點進行實驗。所有這些數(shù)據(jù)點所在的非線性流形是嵌入在三維空間中的二維流形。我們分別采用三種流形學習算法對這兩組數(shù)據(jù)集進行降維，將其降維到二維空間中。這三類算法分別為等距映射（Isomap）、局部線性嵌入（LLE）、拉普拉斯特征映射（LEP）。由于這三類算法都受局部鄰域因子K值的影響，所以在實驗階段，我們分別選取不同的K值，然后來分析在不同的K值下三類算法的降維效果。

4.1.1 實驗過程

首先給出Swiss Roll數(shù)據(jù)集的實驗過程。此數(shù)據(jù)集包含800個三維數(shù)據(jù)點，我們分別選取鄰域因子K=8，12，16。其對應的降維結果如下圖1所示，其中圖中第一行表示K=8時三個算法的降維結果，第二行表示K=12時的降維結果，第三行表示K=16時的降維結果。

Puncture Sphere數(shù)據(jù)集是一組采樣與二維球面上的三維數(shù)據(jù)點集。我們采取1000個數(shù)據(jù)點，與Swiss Roll相同，我們分別選取K=8，12，16。其相應的降維結果如圖2所示。

4.1.2 實驗結果

由Swiss Roll圖可知，Isomap降維的效果明顯好于其他兩種算法。LLE和LEP這兩種方法降維后的圖形較為相似，這是由于兩種算法都是假設樣本點所在的子流形的局部鄰域是線性結構。但我們并不能從LLE和LE兩種方法降維后的圖形辨認出原始流形，之所以瑞士卷降維后呈現(xiàn)這樣的圖形是因為這兩種算法只是保持了流形的局部結構，對于全局結構沒有得到很好的保持，所以降維后的結果只是在局部鄰域中效果比較好，從算法來看，這兩種算法對流形的全局結構并沒有做約束。當K值增大到16時，這兩種局部線性嵌入方法降維后的準確度降低，降維的效果變得不好。這是因為K是局部鄰域的大小，當K增大時，局部鄰域范圍就會變大，所以表面上局部鄰域已經不呈現(xiàn)出線性結構，但潛在的原因是降維過程中并沒有考慮到局部鄰域的曲率結構，所以會出現(xiàn)這些結果。

針對Puncture Sphere數(shù)據(jù)集，LEP算法的降維效果明顯好于其余兩個算法。且隨著K值的增加，LEP的降維效果并沒有明顯的降低。從算法本身分析其結果我們可以看出，LLE算法目的是要保持降維前后數(shù)據(jù)點鄰域的線性結構，而針對Puncture Sphere數(shù)據(jù)集，其是采樣與球面的數(shù)據(jù)集，所以每個數(shù)據(jù)點的局部鄰域的線性結構非常的弱。而針對Isomap算法，其是為了保持樣本點集降維前后的全局結構，所以從降維結果可以看出，雖然在全局上，降維后的流形依然保持球面的整體結構，但是每個數(shù)據(jù)點的局部鄰域結構在降維過程中并沒有得到很好的保持。endprint

4.2 真實世界數(shù)據(jù)集

對流形學習的算法做進一步實驗，用局部線性嵌入（LLE）、主成分分析（PCA）以及拉普拉斯特征映射（LEP）三種方法對USPS手寫體的圖像數(shù)據(jù)集進行降維，然后再對降維后的數(shù)據(jù)點進行分類識別。USPS手寫體數(shù)據(jù)集包含9298個數(shù)據(jù)點，每個數(shù)據(jù)點都由一張手寫體數(shù)字圖像表示。此數(shù)據(jù)集一共包含十類手寫體分別為從0到9，每張圖像像素經過處理表示為16×16的像素矩陣。所以在降維階段，我們將每個像素矩陣按行排列成一個256維的行向量來表示一張圖像的特征。

4.2.1 實驗過程

實驗過程主要分為兩步進行。第一步是利用降維算法對數(shù)據(jù)集進行降維，在本實驗中我們分別采用三類降維算法：PCA，LLE，LEP對數(shù)據(jù)集進行降維。其中降維后的低維空間維數(shù)選擇為d=10。第二步是對降維后的數(shù)據(jù)集進行分類識別，在此步中我們采用K近鄰分類器來進行訓練，然后采用交叉驗證法來進行測試。由于在降維過程中，流形學習算法受鄰域因子取值的影響。所以在此實驗中，我們同樣采取不同的鄰域因子K的值來進行實驗，其中K=1：5：31。其相應的實驗結果表示如下圖3所示。

4.2.2 實驗結果

從圖3可以看出，三種方法中LLE和LEP的識別準確率都隨著K值的增大而減小，而PCA算法的準確率則隨著Knn的值增大而呈現(xiàn)穩(wěn)定的狀態(tài)，其具體的實驗分析如下。

LLE算法識別準確率的趨勢較為明顯，當Knn初始值為5時識別準確率的值為0.9800，隨著Knn值的增大識別準確率逐漸降低一直到0.9200（Knn=25）。LEP算法在Knn=5的情況下，數(shù)據(jù)集的分類準確率最高。而隨著鄰域因子的增大，其實別準確率也呈現(xiàn)出下降的趨勢。PCA算法的目的是學習一個全局的線性降維映射，所以其算法過程與鄰域因子之間沒有任何關系，所以其在不同的鄰域因子下分類的準確率基本上保持不變。

5 結論與展望

本文主要給出了流形學習的三類算法，通過三組實驗結果來分析了不同降維算法的降維效果。通過對各個算法的理論分析以及實驗結果分析可以看出，這些流形學習算法雖然有很多優(yōu)點，但是其本身還存在很多的缺點。（1）三類算法都對鄰域因子K非常的敏感，當K值非常大的時候，三類算法的降維效果就非常的差。（2）三類算法對流形真實的維度不能進行很好的估計，很多情況下都需要我們事先給定低維維度的取值。這對于挖掘流形真實的幾何結構非常的不利。造成這些局限性的一個重要的原因是，這三類算法并沒有準確的挖掘流形真實的局部幾何結構。如Swiss Roll數(shù)據(jù)集，當K值非常大的時候，三類算法的降維效果都非常的差，造成這種結果的一個很重要的原因是，三類算法都假定流形的局部鄰域為線性空間，而并沒有考慮流形真實的曲率結構。

所以針對這些局限性，我們接下來的工作將會嘗試設計新的算法，挖掘流形的局部曲率結構，來對傳統(tǒng)的流形學習算法進行修正。

參考文獻

[1]Roweis， S. And Saul， L. “Nonlinear dimensionality reduction by locally linear embedding”.Science，290（5500）：2323-2326，2000.

[2]Tenenbaum， J.， de Silva， V.， and Langford， J.“A global geometric framework for nonlinear dimensi-onreduction”.Science，290（5500）：2319-2323，2000.

[3]Belkin， M. and Niyogi， P.“Laplacian eigenmaps and spectral technique for embedding and clusteri-ng”.In Advances in Neural Information Processing Systems 14， pp. 585-591，2001.

[4]Donoho，D.L. And Grimes，C.E.“Hessian eigenmaps： Locally linear embedding techniques for hig-h-dimensional data”.Proceedings of the National Academy of Sciences of the United States of America，100（10）：5591-5596，2003.

[5]Z， Zhang and H，Zha.“Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment”.SIAM J. ScientificComputing， vol. 26， no. 1， pp. 313-338， 2005.

[6]Jolliffe， I.T. “Principal Component Analysis”. Springer-Verlag， New York， 1989.

[7]Scholkopf， B.， A. Smola and K.-R. Muller.“Nonlinear component analysis as a kernel eigenvalue problem”， Neural Computation，10（5）：1299-1319.

[8]Cox T. F. and M. A. Cox. “Multidimensional Scaling”. Chapman & Hall/CRC， London， UK.

[9]Xiaofei He，ParthaNiyogi.“Locality Preserving Projections”，Int. Conf. Advances in Neural Information Processing Systems，2003.endprint