顧艷春，馬爭鳴，梁宇滔

(1. 佛山科學(xué)技術(shù)學(xué)院電子與信息工程學(xué)院, 廣東 佛山 528000； 2.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院, 廣東 廣州 510220)

流形學(xué)習(xí)是一種有效的非線性降維方法。近年來，流形學(xué)習(xí)方法在數(shù)據(jù)挖掘、機器學(xué)習(xí)、圖像處理和計算機視覺等多個研究領(lǐng)域吸引了廣泛的關(guān)注。典型的流形學(xué)習(xí)方法有Isometric Feature Mapping (ISOMap)[1]、Locally Linear Embedding (LLE)[2]、Hessian Eigenmaps (HLLE)[3]、Local Tangent Space Alignment (LTSA)[4]、Laplacian Eigenmaps (LE)[5]等。這些算法具有一個共同的特征：找出每個數(shù)據(jù)點周圍的局部性質(zhì)，并將這些局部性質(zhì)信息映射到一個低維空間中。顯然，局部幾何結(jié)構(gòu)信息的保持和恢復(fù)程度決定了流形學(xué)習(xí)算法的優(yōu)劣。在獲取流形的局部信息時，流形學(xué)習(xí)算法假定流形在一個很小的范圍內(nèi)，局部同胚于一個歐式空間的一個連通開集，這就決定了流形學(xué)習(xí)算法在選擇鄰域時，要盡可能保證鄰域內(nèi)的點滿足局部同胚條件。而當(dāng)樣本點較為稀疏時，鄰域內(nèi)的樣本點很難保持局部同胚條件，從而導(dǎo)致上述流形學(xué)習(xí)算法在處理稀疏數(shù)據(jù)集時會造成較大的誤差，甚至失效。

針對流形學(xué)習(xí)算法無法有效處理樣本點稀疏的問題，目前主要有三種解決方法。一類是根據(jù)樣本點的稀疏程度，自適應(yīng)的改變鄰域大小，從而盡可能的使鄰域內(nèi)的樣本點滿足同胚條件[6-8]。在樣本點比較稀疏時，此種方法會使得鄰域相對較小，這很容易造成在將局部坐標(biāo)信息排列成全局坐標(biāo)時由于交疊不夠而使算法效果難以令人滿意的現(xiàn)象。第二種方法是改變鄰域內(nèi)的局部信息選取方式，例如，Wu等[9]求取鄰域時，首先對樣本點集做預(yù)處理，去除樣本集中的“短路”邊，然后利用最短路徑算法迭代出樣本點間的測地線距離來選取鄰域；Song等[10]通過最小化鄰域內(nèi)樣本點間的梯度值來實現(xiàn)高維數(shù)據(jù)的局部線性逼近。此類方法計算復(fù)雜，受流形本身形狀影響較大從而穩(wěn)定性較差。另一類比較有效的做法是添加一些虛擬樣本點，使得樣本點相對稠密，從而改善降維效果。例如，Zhan等[11]利用樣本點到鄰域內(nèi)其他兩個點組成連線的垂足來添加樣本點，提出了基于鄰域線的LLE算法。但該方法并沒有考慮流形本身的性質(zhì)和曲率等因素對降維的影響，添加的虛擬樣本點與原樣本點之間為線性關(guān)系，因此，效果有限，只能針對特定的流形。

為此，我們提出了一種新的基于Biharmonic樣條插值的流形學(xué)習(xí)算法BbMLA，通過非線性的獲取插值點來有效改善鄰域內(nèi)樣本點的稠密程度，同時插值點又能忠實的保持流形本身的結(jié)構(gòu)和性質(zhì)。在本文提到的算法中，我們利用Biharmonic樣條插值算法[12]，首先在樣本點的各鄰域內(nèi)做曲面插值，而后根據(jù)流形本身的特點和性質(zhì)，從插值曲面中非線性的選取插值點；然后利用這些插值點與原樣本點一起組成新的樣本點集，并求取其低維坐標(biāo)；最后，將原樣本點的坐標(biāo)抽離和表示出來，最終得到原樣本點集的低維坐標(biāo)值。通過對插值點的圖示，我們說明了算法得到的插值點與流形的本質(zhì)結(jié)構(gòu)較為匹配，而且插值點考慮了流形的密度和曲率等因素。在將本文提到的插值算法應(yīng)用到經(jīng)典的流形學(xué)習(xí)算法如LTSA、LLE后，實驗結(jié)果證實了我們的算法的有效性和穩(wěn)定性。

1 流形學(xué)習(xí)中的樣本點稀疏問題

流形學(xué)習(xí)的方法可以分為兩類：一類是全局方法(如Isomap)，另一類是局部方法(如LLE、LE、HLLE、LTSA等)。由于局部方法只需要考慮流形臨近點之間的關(guān)系，無須要求流形所對應(yīng)的低維空間為凸，且計算復(fù)雜度較低，因此局部方法有著更廣泛的適用對象[13]。

局部保持的流形學(xué)習(xí)方法正是通過保持鄰域內(nèi)的局部近鄰結(jié)構(gòu)來構(gòu)造全局低維表示，所以，鄰域結(jié)構(gòu)的表示和保持程度將直接影響最終的嵌入效果。在刻畫流形的局部幾何特性時，需要盡可能的保證局部鄰域能夠同胚于歐氏空間的一個連通開集。顯然，鄰域越小，鄰域的低維結(jié)構(gòu)越明顯，近鄰結(jié)構(gòu)越容易忠實保持。另一方面，鄰域之間需要有足夠的交疊以保證全局排列時有足夠的聯(lián)系，這又使得鄰域不能過小。這種矛盾一直伴隨著流形學(xué)習(xí)算法，當(dāng)樣本點比較稀疏時，鄰域內(nèi)的局部同胚條件更加難以保持，這就造成了目前絕大多數(shù)流形學(xué)習(xí)算法在樣本點較為稀疏時的失效。

圖1標(biāo)示了樣本點稀疏程度不同時某一點的鄰域結(jié)構(gòu)，稀疏程度不同時，鄰域內(nèi)的線性程度也不同。其中，采樣點數(shù)據(jù)來自于Swiss Roll，星點為從Swiss Roll隨機選擇的某一個樣本點，實心點為采樣點為800個點時的鄰域點，空心圓點為采樣點為100時的鄰域點(鄰域值為8，鄰域包括自身點)。顯然，當(dāng)采樣點比較密集時，我們可以認(rèn)為其局部同胚于一個歐式空間，此時，樣本點在由鄰域點線性表出時的誤差較小。而當(dāng)采樣點較為稀疏時，局部同胚條件較難保持，此時刻畫和表示的鄰域內(nèi)的結(jié)構(gòu)信息，便帶有較大的誤差，從而導(dǎo)致算法效果變差乃至失效。

圖1 樣本點稀疏程度不同時的鄰域點集Fig.1 Selected neighborhood with different denseness of the sample points

對于流形學(xué)習(xí)算法不能有效處理稀疏樣本點集的問題，目前常用的解決方法，是通過插值增加一些新的樣本點以使樣本點密集。具體來說，是利用樣本點有限的鄰域點插值出新的鄰域點，然后再由這些原有的鄰域點和插值出的新的鄰域點張成一個線性子空間去逼近原樣本點。例如，NL3E方法利用樣本點到鄰域內(nèi)其他兩個點組成連線的垂足來添加樣本點。

這類插值方法一定程度上改善了樣本點稀疏時的算法效果。但是這些方法都采用線性插值的方法去產(chǎn)生新的樣本點，也就是說，新的鄰域點都是原有鄰域點的線性組合，從線性代數(shù)的理論來說，由插值點和原有鄰域點張成的線性子空間與原有鄰域點張成的子空間是一樣的，因此，也不會改善線性逼近的誤差。而且，插值點并沒有反應(yīng)出流形的本質(zhì)結(jié)構(gòu)和特征，從理論上背離了數(shù)據(jù)降維的目的。為此，我們利用Biharmonic樣條插值法非線性的獲取插值點。此時，插值出的樣本點不會被原有鄰域點線性表示，也就是說，新插值出的樣本點不會落在原鄰域點張成的線性子空間里，因此，由插值點和原有鄰域點張成的線性子空間是原有鄰域點張成子空間的真擴展。如圖2所示，線性插值方法是從原鄰域點張成的子空間內(nèi)選取合適的樣本點作為插值點，而非線性插值方法是從高維空間逼近的角度選取插值點，由這個子空間去逼近樣本點會更有效的減少逼近誤差。另外，由于是從鄰域內(nèi)曲面重建中非線性的獲取插值點，插值出的點能夠更好的反映流形的曲面性質(zhì)而不是平面性質(zhì)，從而更好的保持和揭示了流形的本質(zhì)特征。

圖2 線性插值與非線性插值方法選取插值點的不同F(xiàn)ig.2 The difference of interpolation points chosen by linear and non-linear interpolation method

2 基于Biharmonic樣條插值的流形學(xué)習(xí)算法

算法主要用于解決樣本點稀疏問題，對于稀疏樣本點，根據(jù)其本質(zhì)結(jié)構(gòu)特點，利用Biharmonic樣條插值方法在樣本點的鄰域內(nèi)構(gòu)造插值曲面，并從插值曲面中選取一定數(shù)目的樣本點作為插值點。而后，利用這些插值點與原樣本點一起作為新的樣本點集。待利用各種經(jīng)典的流形學(xué)習(xí)算法求得樣本點的全局低維坐標(biāo)后，取出原樣本點集的低維坐標(biāo)。

2.1 Biharmonic樣條插值

解決樣本點稀疏問題的有效方法之一，是根據(jù)流形特點，添加新的插值點。為了合理的構(gòu)造插值點，我們首先需要用一個光滑的曲面來逼近這些無規(guī)則的散亂抽樣數(shù)據(jù)點，即曲面擬合問題；然后從擬合的曲面上選取合適的點作為新樣本點。流形上散亂數(shù)據(jù)的曲面擬合，其難點在于，如何得到鄰近點間正確的拓?fù)溥B接關(guān)系，而正確的拓?fù)溥B接關(guān)系將有效的揭示散亂數(shù)據(jù)集所蘊涵的本質(zhì)形狀和拓?fù)浣Y(jié)構(gòu)。

在眾多的曲面擬合算法中，Biharmonic樣條插值方法[12]是一種效果較好的曲面構(gòu)造方法。與其他曲面擬合算法如雙三次樣條插值和B樣條插值算法相比，Biharmonic樣條插值方法擬合的曲面較為光滑，局部性能較好，能夠根據(jù)散亂數(shù)據(jù)點發(fā)現(xiàn)和保持曲面的本質(zhì)結(jié)構(gòu)和特征，而且算法計算量較小，效率較高[14]。

Biharmonic樣條可以對散亂分布的數(shù)據(jù)進行曲面插值。插值產(chǎn)生的曲面是以各數(shù)據(jù)點為中心的Green函數(shù)的線性組合[12]。Biharmonic方程在不同維空間中的解就是不同維的Green函數(shù)。對于D維空間中散亂分布的K個控制點xk,k=1,2,…,K，Biharmonic樣條D維插值問題轉(zhuǎn)化為對公式(1)的求解

(1)

其中，▽4為Biharmonic算子，δ為單位沖擊函數(shù)，W(X)為X位置處的值。

圖3為在Twin Peaks樣本集上做Biharmonic樣條插值方法后從插值曲面上選取部分插值點的圖示。

圖3 Biharmonic樣條插值方法選取的插值點Fig.3 Effect by Biharmonic spline interpolation algorithm

其中，圖3(b)中空心圓點為原樣本點(原樣本點數(shù)目為200)，實心點為從插值曲面上選取的部分插值點。由圖3可以看出，Biharmonic樣條插值法得到的曲面，與原流形曲面較為匹配，比較忠實的體現(xiàn)了原流形的特征和結(jié)構(gòu)，并且，插值函數(shù)本身動態(tài)的考慮了流形的曲率和密度變化等因素。

2.2 插值點的選取

插值點的選取是指從插值曲面上，取合適的點作為新的樣本點，并放入樣本集中。為了提高插值精度，我們要產(chǎn)生盡可能多的點來逼近原流形曲面。但是，過多的插值點參與到流形學(xué)習(xí)算法會很嚴(yán)重的影響算法的效率。而且，按照文獻[11]的理論，為每一個樣本點插入不少于其維數(shù)的插值點即可。從直觀上考慮，樣本點稀疏處，應(yīng)選擇較多的插值點，曲率較大處，應(yīng)選擇較多的插值點。通常，插值點的選取有兩種方法，一種為從插值曲面上均勻采樣，另一種是根據(jù)流形及樣本集本身的特點(如樣本稠密度和曲率的不同)來抽取樣本點。由于Biharmonic樣條插值法在插值時，已經(jīng)考慮了流形局部的密度和曲率等因素，因此，我們只需要選取合適數(shù)目的樣本點作為插值點。

選出的插值點，有兩種利用方式。一種是讓插值點和原樣本點集組合起來，一起參與流形學(xué)習(xí)算法；另一種是只利用局部范圍內(nèi)的插值點，來修正每個樣本點的局部坐標(biāo)，但這種方法，不能有效的處理鄰域間交疊不夠的問題。本文中，我們選取第一種方法。

2.3 BbMLA算法框架

為了解決流形學(xué)習(xí)算法不能有效處理稀疏樣本點的問題，針對線性插值方法的不足，我們提出了基于Biharmonic樣條插值的流形學(xué)習(xí)算法，即BbMLA算法。算法首先選取生成插值點的鄰域，然后利用Biharmonic樣條插值方法在樣本點的鄰域內(nèi)構(gòu)造插值曲面，并從中選取一定數(shù)目的樣本點作為插值點。選取插值點后，將插值點并入原樣本點集中并利用經(jīng)典的流形學(xué)習(xí)算法獲取新的樣本點集的低維坐標(biāo)；而后，將原樣本點集分離出來從而得到最終的原樣本點集得低維坐標(biāo)。算法過程如表1所示：

算法中，X為原始樣本點集，V為新插入點的樣本集，L為Biharmonic樣條插值時的鄰域選取參數(shù)，為了保證鄰域內(nèi)的點滿足同胚條件，可根據(jù)樣本點密度或曲率變化動態(tài)調(diào)整L。λ為從重建曲面中采樣時選取的新樣本點個數(shù)，可為每一個樣本點選取不同個數(shù)的插值點。MLA為調(diào)用流形學(xué)習(xí)算法得到低維坐標(biāo)，可選擇多種流形學(xué)習(xí)算法如LLE、ISOMAP、LE、HLLE、LTSA等。

表1 BbMLA算法過程Table 1 Pseudo-code of BbMLA

3 實驗及分析

為了更好的比較和分析插值前后算法的效果差異，我們設(shè)計了以下實驗。實驗中，CPU頻率為1.86GHz，內(nèi)存容量為2GB，運行環(huán)境為Matlab 7.0。

3.1 插值點效果對比

我們首先對線性插值和非線性插值方法得到的插值點的效果進行了對比。

圖4標(biāo)示了樣本點數(shù)為200，鄰域值取8時的插值點效果對比圖，其中(a),(a′),(a″),(a?)為原始樣本點集圖，(b)，(b′),(b″),(b?)為線性插值(NL3E為例)后的樣本點集圖，(c),(c′),(c″),(c?)為Biharmonic插值算法得到的樣本點集圖。(b),(b′),(b″),(b?)、(c),(c′),(c″),(c?)圖中紅色圈點為原始樣本點，藍色實點為選取的插值點(并非改變原采樣點的顏色向量，在此只是為了區(qū)分原采樣點和新插值點)。由圖4可以看出，通過非線性插值方法插值后的樣本點集，較好的保持了流形的本質(zhì)特征。與線性插值方法相比，得到的插值點更加忠實于流形本身。

圖4 插值點效果對比(N=200, L=8)Fig.4 Interpolation points by linear and nonlinear methods(N=200, L=8)

3.2 插值前后流形學(xué)習(xí)算法效果對比

插值算法可以應(yīng)用到數(shù)據(jù)集。我們首先Mani程序中的數(shù)據(jù)集(Swiss Roll、Punctured Sphere和Twin Peaks)，Mani數(shù)據(jù)集是一種在流形學(xué)習(xí)中廣泛使用的數(shù)據(jù)集，可以方便的從http://www. math.ucla.edu/～wittman/mani/index.html處免費下載。

圖5標(biāo)示了在原樣本點數(shù)目為400，鄰域取8時，原LTSA算法的效果圖以及相應(yīng)的在插入插值點后的算法效果圖。其中(a),(a′),(a″)為原始流形采樣圖；(b),(b′),(b″)為插值后的采樣圖，其中紅色圈點為原始樣本點，藍色實點為選取的插值點；(c),(c′),(c″)為原LTSA算法效果圖；(d),(d′),(d″)為插值后的LTSA算法效果圖。由圖5可以看出，插值后的算法效果跟原始算法效果相比基本相同，這主要是因為原始采樣點比較密集，鄰域內(nèi)基本滿足局部同胚關(guān)系，故雖然插入的樣本點基本保持了流形本身的形狀且使得樣本點集更為稠密，但對整體效果的影響有限。

圖6標(biāo)示了在原樣本點數(shù)目為200，鄰域取8時，原LTSA算法的效果圖以及相應(yīng)的在插入插值點后的算法效果圖。由圖6可以看出，原始的LTSA算法得到的降維圖，效果已顯著下降，這主要是因為原始采樣點比較稀疏，鄰域值取8時，鄰域內(nèi)的樣本點已難以滿足局部同胚關(guān)系，故得到的降維效果欠佳。插值后，新插入的樣本點較好的保持了原流形的本質(zhì)結(jié)構(gòu)，鄰域內(nèi)的樣本點重新較好的滿足了局部同胚關(guān)系，故插值后的算法取得了較好的效果。

圖7標(biāo)示了在原樣本點數(shù)目為100，鄰域取8時，原LTSA算法的效果圖以及相應(yīng)的在插入插值點后的算法效果圖。由圖7可以看出，原始的算法已基本失效，而插值后的算法仍保持了較好的效果。這主要是由于插值前的樣本非常稀疏，局部很難保持同胚條件，而插值后的新的樣本點集有效的克服了這一現(xiàn)象。

當(dāng)樣本點較為稀疏時，為了保持局部同胚關(guān)系，我們可適當(dāng)?shù)慕档袜徲蛑?。但太小的鄰域值會使得鄰域間缺乏足夠的交疊，從而使得全局排列受到較大影響，甚至導(dǎo)致算法失效。圖8標(biāo)示了在原樣本點數(shù)目為100，鄰域取4時，原LTSA算法的效果圖以及相應(yīng)的在插入插值點后的算法效果圖。由圖8可以看出，原LTSA算法由于鄰域間缺乏足夠的交疊，導(dǎo)致算法失效，而插值后的算法，由于添加了樣本點，使得鄰域間的同胚關(guān)系得到較好保持的同時，也增強了鄰域間的交疊關(guān)系，從而使得算法效果有了較為明顯的改善。

圖5 Mani數(shù)據(jù)集插值前后LTSA算法效果對比圖(N=400, K=8)Fig.5 Processed results by LTSA with the interpolation algorithm(N=400, K=8)

圖6 Mani數(shù)據(jù)集插值前后LTSA算法效果對比圖(N=200, K=8)Fig.6 Processed results by LTSA with the interpolation algorithm (N=200, K=8)

圖7 Mani數(shù)據(jù)集插值前后LTSA算法效果對比圖(N=100, K=8)Fig.7 Processed results by LTSA with the interpolation algorithm(N=100, K=8)

圖8 Mani數(shù)據(jù)集插值前后LTSA算法效果對比圖(N=100, K=4)Fig.8 Processed results by LTSA with the interpolation algorithm (N=100, K=4)

圖9標(biāo)示了插值前后在SCurve數(shù)據(jù)集上LTSA算法效果對比圖。與在Mani數(shù)據(jù)集上基本類似，當(dāng)樣本點較為稀疏時，插值算法取得了較好的效果。多個數(shù)據(jù)集上的效果，說明了我們的算法的健壯性和魯棒性。

我們的插值算法也適用于其他經(jīng)典流形學(xué)習(xí)算法如LLE、HLLE、Diffusion Maps等。圖10標(biāo)示了插值前后LLE算法效果對比圖。由圖10可以看出，我們的插值算法在LLE等其他流形學(xué)習(xí)算法中也取得了較好的效果。

同時，我們也做了其他一些高維數(shù)據(jù)集的實驗，如Frey Faces和Handwritten Digits等。算法同樣能取得較好的效果。

圖9 SCurve數(shù)據(jù)集插值前后LTSA算法效果對比圖Fig.9 Processed results by LTSA to SCurve with the interpolation algorithm

圖10 插值前后LLE算法效果對比圖(N=200, K=8)Fig.10 Processed results by LLE with the interpolation algorithm(N=200, K=8)

3.3 參數(shù)調(diào)整及時間復(fù)雜度分析

將BbMLA算法應(yīng)用到實際問題時，可以根據(jù)不同流形的特點，調(diào)整參數(shù)來獲得更好的算法效果。在BbMLA算法中，主要有如下幾個參數(shù)：

λ，插值點個數(shù)。從每個插值曲面選取的插值點數(shù)目可以不同，插值點數(shù)目越多，插值點便越能忠貞的體現(xiàn)流形本身的結(jié)構(gòu)，但過多的插值點會大大增加算法運行的時間。而且，按照文獻[11]的理論，為每一個樣本點插入不少于其維數(shù)的插值點即可。

我們提出的算法中，由于需要對每個樣本點做曲面插值和插值點的選擇，并最終擴展了樣本點集來參與流形學(xué)習(xí)算法，這導(dǎo)致算法的運行時間較長。表2中，我們比較了幾種流形學(xué)習(xí)算法插值前后的運行時間(s)，其中數(shù)據(jù)集取自Swiss Roll流形，采樣點為200，鄰域為8。由表2可以看出，插值算法和增加的插值點大大增加了算法的運行時間。可行的解決辦法，一是選擇合適的標(biāo)志點而不是所有數(shù)據(jù)點的鄰域來做曲面插值，二是選擇插值點時在保持較好降維效果的同時盡可能選擇較少的點；三是插值后的流形學(xué)習(xí)算法設(shè)定合適的鄰域值，適當(dāng)?shù)臏p小鄰域會降低算法的運行時間。

表2 不同插值點時幾種流形學(xué)習(xí)算法運行時間對比Table 2 Comparison of running time with different interpolation points

4 結(jié) 論

近年來，流形學(xué)習(xí)方法在數(shù)據(jù)挖掘、機器學(xué)習(xí)、圖像處理和計算機視覺等多個研究領(lǐng)域吸引了廣泛的關(guān)注并取得了長足的發(fā)展。但當(dāng)樣本點較為稀疏時，這些流形學(xué)習(xí)算法往往效果變差甚至失效。解決此問題的有效方法，是根據(jù)流形特點增加一些插值點。但已有的算法均采用線性插值的方法獲取插值點。從線性代數(shù)的理論來說，由插值點和原有鄰域點張成的線性子空間與原有鄰域點張成的子空間是一樣的，新的插值點不會改善線性逼近的誤差。而且，插值點并沒有反應(yīng)出流形的本質(zhì)結(jié)構(gòu)和特征，從理論上背離了數(shù)據(jù)降維的目的。本文利用Biharmonic樣條插值法非線性的獲取插值點，新的插值點能有效的改善稀疏樣本集的局部結(jié)構(gòu)，并且插值點能較好的體現(xiàn)流形本身的結(jié)構(gòu)和性質(zhì)。在將本文提到的插值算法應(yīng)用到經(jīng)典的流形學(xué)習(xí)算法如LTSA、LLE后，實驗結(jié)果證實了我們的算法的有效性和穩(wěn)定性。

值得注意的是，我們提出的算法中，由于需要對每個樣本點做曲面插值和插值點的選擇，并最終擴展了樣本點集來參與流形學(xué)習(xí)算法，這導(dǎo)致算法的運行時間較長，尤其是對于較高維數(shù)的樣本集，算法的運行時間更加難以接受。由此，如何有效的提高算法的執(zhí)行效率將是本文未來的研究內(nèi)容。

參考文獻：

[1] TENENBAUM J B, SILVA V DE, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science, 2000, 290(5000): 2219-2323.

[2] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science, 2000, 290(5000): 2323-2326.

[3] DONOHO D, GRIMES C. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data [J]. Proceedings of the National Academy of Sciences, 2003, 100(10): 5591-5599.

[4] ZHANG Z Y, ZHA H Y. Principal manifolds and nonlinear dimension reduction via local tangent space alignment [J]. SLAM Journal of Scientific Computing， 2004, 26(1): 313-338.

[5] BELKIN M, NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation [J]. Neural Computation, 2002, 15: 1373-1396.

[6] KARBAUSKAITЁ R, KURASOVA O, DZEMYDA G. Selection of the number of neighbors of each data point for the locally linear embedding algorithm [J]. Information Technology and Control, 2007, 36: 359-364.

[8] WEN G, JIANG L, WEN J, et al. Performing locally linear embedding with adaptable neighborhood size on manifold [C]// 9th Pacific Rim International Conference on Artificial Intelligence, Springer Verlag, 2006: 985-989.

[9] WU S, QUAN X W, CHEN X C. CN-isomap algorithm for nonlinear dimensionality reduction of sparse data [J]. Mathematics in Practice and Theory, 2010, 17(40): 182 -188.

[10] SONG X, YE S W. Data dimensionality reduction algorithm when source data is spare [J]. Computer Engineering and Application, 2007, 43(28): 181-183.

[11] ZHAN D C, ZHOU Z H. Neighbor line-based locally linear embedding [J]. PAKDD, Springer Verlag, 2006: 806-815.

[12] SANDWELL D T. Biharmonic spline interpolation of GEOS-3 and SEASAT altimeter data [J]. Geophysical Research Letters, 1987, 2: 139-142.

[13] ZHANG T H, TAO D C, LI X L. A unifying framework for spectral analysis based dimentionality reduction [C]//International Joint Conference Neural Networks, 2008: 1670-1677.

[14] WANG Y T, DONG L F, NI K. Image morphing algorithm based on Biharmonic spline interpolation and its implementation [J]. Journal of Image and Graphics, 2007, 12(12): 2189-2194.