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

顧艷春，馬爭(zhēng)鳴，梁宇滔

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

流形學(xué)習(xí)是一種有效的非線性降維方法。近年來(lái)，流形學(xué)習(xí)方法在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像處理和計(jì)算機(jī)視覺(jué)等多個(gè)研究領(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]等。這些算法具有一個(gè)共同的特征：找出每個(gè)數(shù)據(jù)點(diǎn)周?chē)木植啃再|(zhì)，并將這些局部性質(zhì)信息映射到一個(gè)低維空間中。顯然，局部幾何結(jié)構(gòu)信息的保持和恢復(fù)程度決定了流形學(xué)習(xí)算法的優(yōu)劣。在獲取流形的局部信息時(shí)，流形學(xué)習(xí)算法假定流形在一個(gè)很小的范圍內(nèi)，局部同胚于一個(gè)歐式空間的一個(gè)連通開(kāi)集，這就決定了流形學(xué)習(xí)算法在選擇鄰域時(shí)，要盡可能保證鄰域內(nèi)的點(diǎn)滿足局部同胚條件。而當(dāng)樣本點(diǎn)較為稀疏時(shí)，鄰域內(nèi)的樣本點(diǎn)很難保持局部同胚條件，從而導(dǎo)致上述流形學(xué)習(xí)算法在處理稀疏數(shù)據(jù)集時(shí)會(huì)造成較大的誤差，甚至失效。

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

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

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

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

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

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

圖1 樣本點(diǎn)稀疏程度不同時(shí)的鄰域點(diǎn)集Fig.1 Selected neighborhood with different denseness of the sample points

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

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

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

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

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

2.1 Biharmonic樣條插值

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

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

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

(1)

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

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

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

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

2.2 插值點(diǎn)的選取

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

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

2.3 BbMLA算法框架

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

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

表1 BbMLA算法過(guò)程Table 1 Pseudo-code of BbMLA

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

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

3.1 插值點(diǎn)效果對(duì)比

我們首先對(duì)線性插值和非線性插值方法得到的插值點(diǎn)的效果進(jìn)行了對(duì)比。

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

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

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

插值算法可以應(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處免費(fèi)下載。

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

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

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

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

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

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

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

圖8 Mani數(shù)據(jù)集插值前后LTSA算法效果對(duì)比圖(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算法效果對(duì)比圖。與在Mani數(shù)據(jù)集上基本類(lèi)似，當(dāng)樣本點(diǎn)較為稀疏時(shí)，插值算法取得了較好的效果。多個(gè)數(shù)據(jù)集上的效果，說(shuō)明了我們的算法的健壯性和魯棒性。

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

參考文獻(xiàn)：

[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.