林強(qiáng)　董平　林嘉宇

摘要：本文針對目前的流形學(xué)習(xí)算法進(jìn)行分析研究，介紹了流形學(xué)習(xí)算法的主要算法，特別是對其中的ISOMAP算法進(jìn)行詳細(xì)的分析，并針對其存在的缺點(diǎn)進(jìn)行算法改進(jìn)，最后通過Swiss Roll和Swiss hole兩種數(shù)據(jù)集實(shí)驗(yàn)比較MDS、PCA、ISOMAP、LLE、Hessian LLE、Laplaclan、InLLE和本文提出InISOMAP算法的優(yōu)劣。

關(guān)鍵詞：流形學(xué)習(xí) PCA 增量算法

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2015）05-0000-00

1 引言

隨著科技的發(fā)展進(jìn)步，存儲(chǔ)技術(shù)的發(fā)展，信息數(shù)據(jù)呈爆炸式增長，維度帶來的災(zāi)難使得很多傳統(tǒng)的方法都難以在有效的時(shí)間內(nèi)處理這些大數(shù)據(jù)。因此，降維算法得到了很多研究人員的關(guān)注。經(jīng)典的降維算法有主成分分析（Principal Component Analysis， PCA）、多維尺度映射 （Multi-dimensional Scaling， MDS）和Fisher判別分析（FDA）等[1]只能處理具有線性結(jié)構(gòu)的數(shù)據(jù)。非線性降維算法就引起研究學(xué)者的關(guān)注。

Tenebaum等人從保持高維數(shù)據(jù)的全局角度出發(fā)，在同期的《科學(xué)》期刊上提出了ISOMAP算法[2]；而Roweis從局部幾何結(jié)構(gòu)入手，提出了LLE算法[3]。這兩種不同的算法開創(chuàng)了兩類不同的流形方法——全局保持算法和局部保持算法，推動(dòng)了流形學(xué)習(xí)成為數(shù)據(jù)分析、機(jī)器學(xué)習(xí)和人工智能等領(lǐng)域的熱點(diǎn)研究課題。近年來，流形學(xué)習(xí)得到了一定的發(fā)展，涌現(xiàn)了一些方法，如拉普拉斯特征映射（LE）算法[4]、局部切空間排列（LTSA）算法[5]、最大方差展開（MVU）[6]、Hessian特征映射[7]、局部樣條嵌入（LSE）[8]等，這些方法通過使用譜方法求解矩陣的最大（或最小）的特征值所對應(yīng)的特征向量，再將高維數(shù)據(jù)映射到特征向量空間上。這些方法有兩個(gè)重要的特點(diǎn)：一是它們都是全局最優(yōu)解，由于它們可以轉(zhuǎn)換成凸優(yōu)化問題求解，因而不會(huì)陷入局部最優(yōu)解；二是都能在多項(xiàng)式時(shí)間內(nèi)求解出來，就算最復(fù)雜的MDS算法也只需要O（n3）的時(shí)間，因此這對于流形學(xué)習(xí)的實(shí)時(shí)性有一定的意義。不過，流形學(xué)習(xí)存在一些問題，比如流形學(xué)習(xí)算法都是根據(jù)已知數(shù)據(jù)的結(jié)構(gòu)來求得它在低維空間上的最優(yōu)解的。此外，流形學(xué)習(xí)的算法都要求得到每一點(diǎn)的鄰接點(diǎn)，近鄰參數(shù)的選擇直接影響了低維空間中的數(shù)據(jù)結(jié)構(gòu)，如果近鄰選取過多，會(huì)造成“短路”線性，選取過少，會(huì)導(dǎo)致出現(xiàn)大量的非連通的區(qū)域等等一些問題。不管在理論上還是應(yīng)用上，這些問題都值得進(jìn)一步研究。

2 流形學(xué)習(xí)算法介紹

以下按照發(fā)展的時(shí)間順序簡要介紹一些重要的流形學(xué)習(xí)算法。

主成分曲線（principal curves）和流形給出了一個(gè)自然簡潔的非線性降維的框架，它通過標(biāo)準(zhǔn)的幾何映射將PCA算法推廣到構(gòu)建高維數(shù)據(jù)的嵌入流形。通常情況下，主成分流形被視為一個(gè)優(yōu)化問題的最優(yōu)解，評價(jià)函數(shù)則要考慮數(shù)據(jù)結(jié)構(gòu)的近似度以及要對使流形變形的情況進(jìn)行懲罰。最初的估測數(shù)據(jù)算法主要是線性PCA，SOM或自動(dòng)編碼機(jī)。更具彈性的算法有期望最大值算法。

高斯過程潛在變量模型（， GPLVM）[9]是一種隨機(jī)降維方法，即使用高斯過程計(jì)算出高維數(shù)據(jù)的低維非線性嵌入坐標(biāo)。它是PCA的統(tǒng)計(jì)模型的推廣。如同KPCA（kernel PCA）算法，GPLVM也使用一個(gè)核函數(shù)來計(jì)算非線性映射。

曲線成分分析（ CCA）[10]的主要思想在輸出空間尋找盡可能保持原有數(shù)據(jù)間距離的點(diǎn)，同時(shí)十分重視輸出空間中比較小的距離的點(diǎn)。必須要注意的是，使用迭代算法實(shí)現(xiàn)CCA時(shí)，剛開始關(guān)注比較大的距離，然后逐步關(guān)注較小的距離，較小距離的信息會(huì)代替較大距離的信息。

等規(guī)度變換（ISOMAP）算法是Flyoed算法和經(jīng)典的多維尺度化（MDS）算法的結(jié)合。經(jīng)典的MDS算法以各個(gè)數(shù)據(jù)點(diǎn)之間的距離矩陣作為輸入，然后計(jì)算各個(gè)點(diǎn)的坐標(biāo)。ISOMAP假設(shè)僅僅知道相鄰數(shù)據(jù)點(diǎn)的距離，使用Floyd算法計(jì)算不相鄰點(diǎn)之間的距離。Floyd算法可以高效的計(jì)算出所有數(shù)據(jù)點(diǎn)之間的距離。最后ISOMAP算法使用MDS算法降維后的所有點(diǎn)的坐標(biāo)。

局部線性嵌入（LLE）算法與ISOMAP算法是同時(shí)提出來的，它相對ISOMAP來說有一些優(yōu)勢，由于利用了稀疏矩陣算法的一些性質(zhì)使得LLE算法比ISOMAP更快，此外，LLE算法解決許多問題時(shí)相比ISOMAP具有更好地結(jié)果。HLLE（Hessian LLE）與LLE相似，都是基于稀疏矩陣算法。它能產(chǎn)生比LLE精確得多的結(jié)果，但是代價(jià)是時(shí)間復(fù)雜度很高。因此，密集采樣的數(shù)據(jù)很少采用這種方法降維。

3 ISOMAP算法

Isomap算法的主要思想是：局部使用歐式距離，而各個(gè)局部之間的連接信息通過測地線距離表示，測地線距離利用鄰接圖上的最短距離來近似，對測地線距離矩陣?yán)肕DS算法在輸入空間與低維空間建立等距離映射，保持測地線距離不變，從而獲得數(shù)據(jù)對應(yīng)的低維空間坐標(biāo)。

標(biāo)準(zhǔn)Isomap算法的基本步驟如下：

（1）構(gòu)建空間X中流形M上所有數(shù)據(jù)點(diǎn) 的鄰接圖G，距離定義為歐式距離 ，鄰接關(guān)系定義為 球或k最近鄰（k-NN）。

（2）利用Dijkstra算法（或Floyd算法）計(jì)算鄰接圖G上兩點(diǎn)間的最短路徑 近似流形M上的測地線距離 ，得到近似測地線距離矩陣 。

對測地線矩陣 采用MDS算法，獲得d維內(nèi)蘊(yùn)流形上的坐標(biāo) 。

但是，Isomap具有一定的缺陷，例如計(jì)算復(fù)雜度較高為O（n3）；還有，它對噪聲很敏感，當(dāng)近鄰點(diǎn)選取較寬松時(shí)，會(huì)造成短路，即由于流形曲面的彎曲使得兩個(gè)測地線距離較遠(yuǎn)的區(qū)域由于歐式距離較近而被誤連在一起。可見，Isomap抗噪能力較弱，一個(gè)點(diǎn)的出錯(cuò)會(huì)改變整個(gè)輸出結(jié)果的結(jié)構(gòu)。

4 基于增量ISOMAP算法

ISOMAP的一個(gè)缺點(diǎn)是它不能將新的點(diǎn)嵌入到低維內(nèi)蘊(yùn)流形上，因?yàn)樗鼘τ谳斎霐?shù)據(jù)來說的是固定的。在數(shù)據(jù)空間 中，采樣點(diǎn)集 包含 個(gè)點(diǎn)，假設(shè)新增加一個(gè)采樣點(diǎn) 不改變新的數(shù)據(jù)點(diǎn)集的低維內(nèi)蘊(yùn)流形空間。為了獲得新采樣點(diǎn)集 的嵌入坐標(biāo)，最簡單的方法就是對新的點(diǎn)集 運(yùn)行一次ISOMAP算法，新的點(diǎn)集中每一點(diǎn)的 近鄰點(diǎn)以及每一對點(diǎn)之間的測地線距離都要重新計(jì)算一遍。這個(gè)過程的時(shí)間復(fù)雜度為 。為了提高它的效率，我們從輸入數(shù)據(jù)中選擇一些“界標(biāo)點(diǎn)”，當(dāng)有新的數(shù)據(jù)加入時(shí)，不需要計(jì)算對所有的點(diǎn)重新使用一次ISOMAP算法，而是只要保持新的數(shù)據(jù)點(diǎn)與界標(biāo)點(diǎn)之間的測地線距離就行。低維內(nèi)蘊(yùn)空間中的界標(biāo)點(diǎn)個(gè)數(shù) 滿足條件 。

獲取一個(gè)新的輸入數(shù)據(jù)在低維內(nèi)蘊(yùn)空間的坐標(biāo)的算法如下：

（1）使用一種合適的方法從輸入數(shù)據(jù)中選取 個(gè)界標(biāo)點(diǎn)。

（2）搜取新數(shù)據(jù)點(diǎn) 在輸入數(shù)據(jù) 中的 近鄰點(diǎn)集，并且計(jì)算新數(shù)據(jù)點(diǎn) 與每個(gè)界標(biāo)點(diǎn)的測地線距離。

（3）將界標(biāo)點(diǎn)和新數(shù)據(jù)點(diǎn) 合并為點(diǎn)集 ， 包含 個(gè)點(diǎn)。對 運(yùn)行ISOMAP算法，獲取 嵌入低維內(nèi)蘊(yùn)流形上的坐標(biāo)。

為了計(jì)算新加入數(shù)據(jù)點(diǎn)的對應(yīng)嵌入坐標(biāo)，首先要計(jì)算它與界標(biāo)點(diǎn)之間的測地線距離。當(dāng)有新的數(shù)據(jù)點(diǎn)輸入時(shí)，假設(shè)所有輸入數(shù)據(jù)的 近鄰點(diǎn)都保持不變，這就意味著所有輸入數(shù)據(jù)點(diǎn)之間的測地線距離未發(fā)生改變。設(shè)新的數(shù)據(jù)點(diǎn) 近鄰點(diǎn)集為 。根據(jù)Dijkstra算法，新的數(shù)據(jù)點(diǎn)與界標(biāo)點(diǎn)之間的測地線距離可有以下方程得到：

，

其中 和 分別表示兩點(diǎn)組合 間的測地線距離和歐式距離。為了使得計(jì)算測地線距離更加高效，可以保存輸入數(shù)據(jù)點(diǎn)集的 近鄰圖，即一個(gè) 的矩陣。

在以上的算法中，計(jì)算搜取新增點(diǎn)的 近鄰點(diǎn)至多只需要 的時(shí)間，而計(jì)算它們的測地線距離需要 的時(shí)間。MDS算法對于估計(jì) 的矩陣特征值來說時(shí)間復(fù)雜度為 ，因此計(jì)算新增點(diǎn)的低維嵌入坐標(biāo)的時(shí)間復(fù)雜度是 。

5幾種流形算法性能對比

本節(jié)對比了經(jīng)典的流形學(xué)習(xí)算法MDS、PCA、ISOMAP、LLE、Hessian LLE、Laplaclan、InLLE和本文提出InISOMAP算法。下面通過兩種數(shù)據(jù)集對各種算法進(jìn)行比較。

5.1 Swiss Roll

Swiss Roll是經(jīng)典的流形結(jié)構(gòu)，由于它具有“卷”的結(jié)構(gòu)，所以可以用它采樣的數(shù)據(jù)來測試各種算法對測地線距離的保持性能。如圖1可知，MDS算法和ISOMAP算法非常緩慢，HLLE算法次之，PCA算法最快。PCA算法和MDS算法不能展開Swiss Roll，因?yàn)樵诹餍紊?，黃點(diǎn)和藍(lán)點(diǎn)是距離最遠(yuǎn)的，而MDS算法沒有保持結(jié)構(gòu)這種結(jié)構(gòu)，PCA算法上出現(xiàn)了重疊。LE、LLE和InLLE算法都不能保持原有的幾何結(jié)構(gòu)，只有ISOMAP、HLLE和InISOMAP能夠較好地在嵌入空間保持了流形的幾何結(jié)構(gòu)。綜合速度來看，InISOMAP勝出。

5.2 Swiss hole

Swiss hole是在Swiss roll上挖一個(gè)“孔”，這就破壞了流形的部分局部結(jié)構(gòu)，一次測試各種算法對數(shù)據(jù)是否均勻采樣的依賴性。從圖2中可以看到，只有HLLE、InISOMAP能夠成功處理這種具有非凸結(jié)構(gòu)的流形，ISOMAP、LLE發(fā)生了一定的變形，而其他算法都失敗了。

6結(jié)語

流形學(xué)習(xí)作為一種新興的非線性降維技術(shù)正在受到研究者們越來越多的關(guān)注，它并非一種全新的理論，本文對ISOMAP不適合動(dòng)態(tài)的數(shù)據(jù)系統(tǒng)的缺陷做出改進(jìn)，得到基于增量的算法InISOMAP。實(shí)驗(yàn)表明，這種方法在動(dòng)態(tài)的數(shù)據(jù)系統(tǒng)中性能優(yōu)于ISOMAP算法。

本文只對流形學(xué)習(xí)算法中的ISOMAP算法進(jìn)行了研究，并提出了改進(jìn)的算法，但沒有深入研究流形學(xué)習(xí)算法的實(shí)用價(jià)值。當(dāng)前，由于大數(shù)據(jù)的持續(xù)火熱，對數(shù)據(jù)降維技術(shù)的需求在持續(xù)增加，將流形學(xué)習(xí)引入到模式識別是一個(gè)非常誘人的想法，而且也有研究人員對這方面進(jìn)行了研究，但是目前還沒有非常成功的案例。未來工作中，可以考慮將對流形學(xué)習(xí)和人臉識別進(jìn)行深度融合。

參考文獻(xiàn)

[1]王靖.流形學(xué)習(xí)的理論與方法研究[D].浙江大學(xué)，2006

[2]Tenenbaum J B， De Silva V， Langford J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science， 2000， 290（5500）： 2319-2323.

[3]Roweis S T， Saul L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science， 2000， 290（5500）： 2323-2326.

[4]Belkin M， Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering [C]//NIPS. 2001， （14）： 585-591.

[5]Zhang Z， Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment [J]. Journal of Shanghai University （English Edition）， 2004， 8（4）： 406-424.

[6]Weinberger K Q， Saul L K. An introduction to nonlinear dimensionality reduction by maximum variance unfolding [C]//AAAI. 2006， （6）： 1683-1686.

[7]Donoho D L， Grimes C. Hessian eigenmaps： Locally linear embedding techniques for high-dimensional data [J]. Proceedings of the National Academy of Sciences， 2003， 100（10）： 5591-5596.

[8]Xiang S， Nie F， Zhang C， et al. Nonlinear dimensionality reduction with local spline embedding [J]. Knowledge and Data Engineering， IEEE Transactions on， 2009， 21（9）： 1285-1298.

[9]Lawrence N D. Gaussian process latent variable models for visualisation of high dimensional data [J]. Advances in neural information processing systems， 2004， 16（3）： 329-336.

[10]Demartines P， Hérault J. Curvilinear component analysis： A self-organizing neural network for nonlinear mapping of data sets [J]. Neural Networks， IEEE Transactions on， 1997，8（1）：148-154.