高小方,劉杰飛

(山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)

面向等維獨立多流形的增量學(xué)習(xí)算法IMM-ISOMAP

高小方,劉杰飛

(山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)

流形學(xué)習(xí)是機器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域的一個重要研究方向。其經(jīng)典算法總是假設(shè)高維數(shù)據(jù)批量存在于單一流形,且不能有效處理增量式出現(xiàn)的高維多流形數(shù)據(jù)。針對等維獨立多流形提出一種增量學(xué)習(xí)算法IMM-ISOMAP。首先在對新樣本增量地更新動態(tài)鄰域時,僅修改關(guān)鍵路徑,避免重新計算全部鄰域關(guān)系,以提高算法整體效率。然后通過擴展切空間的方法將新樣本依次劃分到各子流形,實現(xiàn)新樣本的增量式分類算法。最后對各子流形計算低維嵌入并進(jìn)行合并。實驗結(jié)果表明,該算法可以有效地應(yīng)用于人造多流形數(shù)據(jù)和實際得多流形圖像數(shù)據(jù)。

流形學(xué)習(xí);增量學(xué)習(xí);等維獨立多流形;動態(tài)鄰域;切空間;IMM-ISOMAP

0 引言

流形學(xué)習(xí)是目前機器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域中一個重要的研究課題,其目的在于根據(jù)有限的離散樣本學(xué)習(xí)和發(fā)現(xiàn)嵌入在高維空間中的低維光滑流形,實現(xiàn)非線性維數(shù)約簡。但是,其經(jīng)典算法,比如ISOMAP[1]、LLE[2]等,總是假設(shè)高維數(shù)據(jù)位于單一流形上,且不能處理增量式出現(xiàn)的高維數(shù)據(jù)。在現(xiàn)實生活中,大量的高維數(shù)據(jù)位于多流形上。比如數(shù)字識別中每個數(shù)字的手寫體均會在特征空間中各自形成不同于其他數(shù)字的獨特流形;再比如人臉圖像識別中不同的人臉圖像在特征空間中也總是位于不同的流形上。而且這些高維數(shù)據(jù)往往是連續(xù)獲得、不斷增加的,例如視頻監(jiān)控數(shù)據(jù)與語音識別數(shù)據(jù)。目前,流形學(xué)習(xí)的研究并沒有實現(xiàn)對大數(shù)據(jù)環(huán)境下不斷增長的高維多流形數(shù)據(jù)的非線性維數(shù)約簡,但是針對多流形識別[4-12]和增量學(xué)習(xí)[14-20]分別提出了一些算法。

多流形的識別在流形學(xué)習(xí)研究中是一個重要的組成。大多數(shù)針對多流形的識別方法是基于聚類[4-7]或者M(jìn)anifold Clustering[8-10]的思想,并沒有考慮基于流形的拓?fù)浣Y(jié)構(gòu),而且必須事先知道存在的流形個數(shù)。Fan等人[12]則是利用MPE算法的梯度下降法來進(jìn)行多流形的降維,但是并不能進(jìn)行子流形的識別。而面向等維獨立多流形的DC-ISOMAP算法[11],是基于擴展切空間的思想,依據(jù)流形自身的拓?fù)浣Y(jié)構(gòu)來分解子流形,有效地解決了等維獨立多流形的識別問題。增量學(xué)習(xí)是流形學(xué)習(xí)從研究走向?qū)嵱没年P(guān)鍵問題之一。尤其是在大數(shù)據(jù)環(huán)境下,數(shù)據(jù)樣本動態(tài)變化,將原來已經(jīng)計算得到的信息丟棄掉再重新計算,不僅造成計算資源的極大浪費,而且其處理方式也是不現(xiàn)實的[3]。為了盡量避免對海量數(shù)據(jù)的重復(fù)計算,一些針對經(jīng)典流形學(xué)習(xí)算法的增量學(xué)習(xí)算法[14-20]被提出。這些算法雖然能夠有效地實現(xiàn)增量數(shù)據(jù)的計算和更新,但由于鄰域關(guān)系和特征矩陣的計算量巨大,其效率并不高。Li等人提出的incremental k-VC方法[20]會嚴(yán)重受其模型算法如網(wǎng)絡(luò)流算法的影響。在基于動態(tài)K-NN的ISOMAP增量學(xué)習(xí)算法[3]中,動態(tài)K-NN算法和“短路”識別算法能夠快速有效地更新鄰域關(guān)系,Dijkstra算法和沖突路徑更新算法也能近似無損地計算和更新測地距離矩陣,高效地實現(xiàn)ISOMAP的增量學(xué)習(xí)能力。

本文基于DC-ISOMAP算法[11]和基于動態(tài)K-NN的ISOMAP增量學(xué)習(xí)算法[3],提出了面向等維獨立多流形的增量學(xué)習(xí)算法IMM-ISOMAP。首先通過動態(tài)鄰域算法[13]計算新增樣本的鄰域關(guān)系,并且通過擴展切空間的方法將新樣本依次劃分到各子流形。然后計算每個新子流形的低維嵌入,同時檢測并更新各子流形中新增樣本可能造成的“短路”或者沖突路徑。最后依據(jù)各子流形的鄰接關(guān)系拼接出整個樣本集合的低維嵌入,實現(xiàn)其數(shù)據(jù)集的可視化。

1 相關(guān)工作

經(jīng)典的流形學(xué)習(xí)算法通常包括三個步驟:構(gòu)建鄰域關(guān)系圖以近似模擬流形的拓?fù)浣Y(jié)構(gòu)、構(gòu)建特征矩陣以保留高維數(shù)據(jù)的特征信息、計算低維嵌入結(jié)果。

1.1 面向等維獨立多流形的DC-ISOMAP算法

面向等維獨立多流形的DC-ISOMAP算法[11]主要從構(gòu)建鄰域關(guān)系圖著手,由計算動態(tài)鄰域形成的切空間擴展子流形,以識別出不同的子流形,直至等維獨立多流形全數(shù)分解。然后對各子流形分別構(gòu)建特征矩陣并計算低維嵌入,最后依據(jù)各子流形的鄰近關(guān)系合并低維嵌入。

本論文在前期工作中提出了通過采樣密度和曲率計算切空間并確定動態(tài)鄰域的算法[13]。首先通過樣本數(shù)的正比關(guān)系估算出僅包含xi的d維超球半徑T1(xi):

(1)

如果xi的鄰近點xj與其切空間T1(M)的夾角為θj,θj的定義如下:

(2)

當(dāng)θj小于一個較小的閾值時,認(rèn)為xj屬于xi的近鄰。在逐個增加xi的近鄰時,其切空間不斷更新,直到

(3)

在DC-ISOMAP算法中,節(jié)點xi和xj之間的切空間偏差可以定義為:

(4)

xj=argminj(vij) .

(5)

1.2 基于動態(tài)K-NN的ISOMAP增量學(xué)習(xí)算法

在增量學(xué)習(xí)算法中,隨著數(shù)據(jù)的不斷積累,充分利用原始數(shù)據(jù)的計算結(jié)果,并提高大規(guī)模數(shù)據(jù)的算法效率成為首要任務(wù)?；趧討B(tài)K-NN的ISOMAP增量學(xué)習(xí)算法[3]仍然是基于單流形的假設(shè),在充分保留并利用原有的中間結(jié)果的同時,如鄰域矩陣、測地距離矩陣、前置矩陣,計算新增批量數(shù)據(jù)的低維嵌入。相對于經(jīng)典的ISOMAP算法,基于動態(tài)K-NN的ISOMAP增量學(xué)習(xí)算法增加了三個主要功能:動態(tài)K-NN、“短路”判斷算法judgeShortCircuits和沖突路徑判斷算法updateShortCircuits。

動態(tài)K-NN算法是基于K-NN的動態(tài)鄰域算法。當(dāng)獲取新增批量數(shù)據(jù)后,在原有鄰域關(guān)系中增加新的K-NN關(guān)系,使得鄰域關(guān)系包含新增K-近鄰,但是并不刪除不屬于新K-NN的原有鄰域關(guān)系。也就是說,在動態(tài)K-NN鄰域關(guān)系中,樣本點的近鄰個數(shù)大于等于K,而不是一定等于K。同時,為了保證在增加新樣本后,動態(tài)K-NN算法能夠具有與K-NN算法一樣的克服原有“短路”的能力,該增量學(xué)習(xí)算法給出了短路判斷算法judgeShortCircuits[3]。該“短路”判斷算法主要針對“鄰域切片”中增加新樣本C為近鄰的舊樣本A。如果該新近鄰C到該舊樣本A的其他一個舊近鄰B的距離CB大于原距離AB與“鄰域切片”最大“半徑”之和,則判斷舊樣本A、B之間存在短路。動態(tài)K-NN算法和“短路”判斷算法保證了增量學(xué)習(xí)算法中鄰域關(guān)系的快速更新,而且盡量保證原有鄰域關(guān)系避免發(fā)生變動。這是整個增量學(xué)習(xí)算法的基礎(chǔ),因為每一組鄰域關(guān)系的變動,都可能會引發(fā)多條測地距離的更新,但并不一定會大幅提高整體算法的精度。

所有的測地距離都是由鄰域關(guān)系計算出最短路徑的距離估計而得。在鄰域關(guān)系中增加了新樣本點后,測地距離矩陣中的數(shù)據(jù)需要重新計算。雖然大多數(shù)被更新的“測地距離”使得距離實際距離更“近”了一點,但并不能大幅提高整體算法的精度,而且時間復(fù)雜度將會隨著樣本點的增大而大幅增加。這些需要更新的測地距離中只有以下兩種是必須的:由“短路”計算出的錯誤距離、沖突路徑計算出的距離。沖突路徑,即從樣本I到J的路徑信息與從J到I的路徑信息不一致,主要由新增樣本引發(fā)?；趧討B(tài)K-NN的ISOMAP增量學(xué)習(xí)算法中僅更新了這兩種測地距離,雖然使得測地距離矩陣的計算精度在一定程度上受到了損失,但提高了整體算法的效率。

2 面向等維獨立多流形的增量學(xué)習(xí)算法IMM-ISOMAP

本文提出的面向等維獨立多流形的增量學(xué)習(xí)算法IMM-ISOMAP主要實現(xiàn)多流形數(shù)據(jù)的增量學(xué)習(xí)能力并進(jìn)行多流形識別和非線性維數(shù)約簡。顧名思義,增量學(xué)習(xí)就是在有新增數(shù)據(jù)情況下能夠利用原有計算結(jié)果對新增數(shù)據(jù)進(jìn)行學(xué)習(xí)。不需要對整個數(shù)據(jù)集重新計算,僅做由新增數(shù)據(jù)引起的更新。整個增量學(xué)習(xí)的時間代價通常遠(yuǎn)低于重新計算整個數(shù)據(jù)集所需的代價。

在算法IMM-ISOMAP中,首先通過動態(tài)鄰域算法[13]計算新增樣本的動態(tài)鄰域;然后找到與原始子流形具有較小切空間偏差的新樣本,并將新樣本劃分到對應(yīng)子流形,形成新的子流形;最后計算每個新子流形的低維嵌入,同時利用DC-ISOMAP算法[11]中合并嵌入結(jié)果的方法計算各個新子流形的鄰近關(guān)系以確定各新子流形的位置關(guān)系,拼接出整體數(shù)據(jù)的最終嵌入結(jié)果。具體算法參見算法1。

算法1：IMM-ISOMAP算法描述

if?xj(xj∈X)∩(xj∈Ninew)∩(xj∈sXk) if?s(s∈X)∩(s∈Ninew)∩(s∈sXg) sXk=sXk∪sXg;sXg=?;sXk=sXk∪{xinew}; 擴展xinew的新增樣本近鄰; else sXk=sXk∪{xinew} 擴展xinew的新增樣本近鄰; endif;else 選擇下一個被擴展的新樣本點xinew和原有樣本xj; ifxj不存在 在剩余所有新樣本中建立新的子流形集合sXi; endif; endif;4.增量計算新樣本低維嵌入: 調(diào)用judgeShortCircuits檢測sXi中的“短路”并在N、G、P中刪除與其相關(guān)的信息; 利用Dijkstra算法計算被刪除的測地距離及其相關(guān)信息; 調(diào)用updateShortCircuits更新sXi中的沖突路徑; 計算各子流形sXi的低維嵌入sYi;5.計算各子流形的鄰近關(guān)系并將各子流形的sYi拼接成Y={y1…yn+m};

2.1 更新鄰域關(guān)系

為了得到較準(zhǔn)確的拓?fù)淞餍谓Y(jié)構(gòu),鄰域關(guān)系要在整體數(shù)據(jù)集上進(jìn)行計算,不僅包含原數(shù)據(jù)集,還要包含新增樣本數(shù)據(jù)。由于多流形數(shù)據(jù)混雜在一起,由K-NN算法計算鄰域關(guān)系時,無法避免不同子流形上的點鄰域關(guān)系混雜在一起，IMM-ISOMAP算法采用基于采樣密度和曲率的動態(tài)鄰域方法來計算鄰域和切空間[13]，以進(jìn)一步提高算法精度。

2.2 更新子流形的劃分

整個劃分的過程是從與原樣本具有最小切空間偏差的新增樣本開始,因為切空間偏差最小可以保證起始樣本的劃分出錯概率最小。

當(dāng)新增樣本的兩個或兩個以上近鄰(原樣本)分別屬于不同子流形時,說明隨著樣本的增加,原來不相連的子流形拼接成一個新的子流形,即子流形相融合;當(dāng)新增樣本存在的近鄰僅屬于同一個子流形時,將該新增樣本劃分到同一子流形中;否則該新樣本或者因為其新樣本近鄰被擴展,或者與其他新樣本構(gòu)建成獨立的子流形。

2.3 更新低維嵌入

基于動態(tài)K-NN的ISOMAP增量學(xué)習(xí)算法[3]在更新鄰域關(guān)系時,采用了動態(tài)K-NN。在更新測地距離矩陣時,僅更新了短路引起的錯誤測地距離和存在沖突路徑的測地距離。IMM-ISOMAP算法對每個子流形做同樣處理。

針對每個子流形,如果有新增樣本的加入,則鄰域關(guān)系已經(jīng)發(fā)生變化。由新增樣本引發(fā)的“短路”和沖突路徑可以通過judgeShortCircuits和updateShortCircuits算法[3]檢測和修正。如果沒有新增樣本的加入,則原計算結(jié)果無須更新。如果是新增子流形,則通過經(jīng)典ISOMAP算法計算。

2.4 更新最終嵌入結(jié)果

在計算出所有子流形的低維嵌入后,要利用DC-ISOMAP算法[11]對這些嵌入結(jié)果拼接合并。首先要選出每個子流形的一些標(biāo)準(zhǔn)點以確定該子流形在整體數(shù)據(jù)集合中的位置關(guān)系。然后通過ISOMAP算法對這些標(biāo)準(zhǔn)點計算出最終嵌入結(jié)果的“框架”。最后利用這些標(biāo)準(zhǔn)點將各個子流形坐標(biāo)轉(zhuǎn)化,“嵌”入最終嵌入結(jié)果中。

2.5 時間復(fù)雜度分析

假定原樣本集合有n個數(shù)據(jù),新樣本集合有m個數(shù)據(jù)。基于經(jīng)典的ISOMAP算法提出的DC-ISOMAP算法,首先需要在原樣本與新樣本的基礎(chǔ)上通過擴展切空間分解子流形,重新構(gòu)建近鄰圖,再重新計算全部樣本之間的新的測地距離,最后通過各子流形的低維嵌入與外層節(jié)點信息確定子流形的位置關(guān)系并最終組合得到新的低維嵌入。因此其時間復(fù)雜度為Ο((n+m)log(n+m)+(n+m)+k(n+m)2log(n+m)+(n+m)3),其中k為鄰域大小所設(shè)定的參數(shù);而IMM-ISOMAP算法在計算動態(tài)鄰域時只需要計算新樣本的動態(tài)鄰域,其時間復(fù)雜度為Ο(mlog(n+m))。在將新樣本重新劃分到新子流形及處理新子流形中可能出現(xiàn)的“短路”情況或沖突路徑時,其時間復(fù)雜度為Ο(mn+m(nq+nq2)+|C|+|S|log|S|+q|S|),其中q為增加新節(jié)點后鄰域圖上所有點的最大的度,其中|C|,|S|分別為沖突路徑與“短路”路徑的數(shù)量,且|S|一般較小可忽略。最后計算新子流形的低維嵌入時其時間復(fù)雜度為Ο((n+m)2)。故IMM-ISOMAP算法整體的時間復(fù)雜度近似為Ο(mlog(n+m)+mn+mnq2+|C|+(n+m)2)。由于新樣本集的規(guī)模一般是遠(yuǎn)遠(yuǎn)小于原樣本集的規(guī)模,即m?n,則IMM-ISOMAP算法的時間復(fù)雜度要小于重新運行全部數(shù)據(jù)的DC-ISOMAP算法的時間復(fù)雜度。

3 實驗結(jié)果及分析

分別進(jìn)行了三組實驗,第一組實驗通過數(shù)據(jù)比較了IMM-ISOMAP算法通過擴展切空間分解多流形與K-means、D-C[4]、SMMC[5]、DC-ISOMAP[11]等算法分解相同多流形數(shù)據(jù)的精度及所需的時間。第二組實驗是隨著多流形數(shù)據(jù)的不斷增長,可視化地展示了IMM-ISOMAP算法與ISOMAP、D-C和DC-ISOMAP算法得到的低維嵌入結(jié)果之間的差異。第三組實驗則可視化地比較了IMM-ISOMAP算法與ISOMAP、D-C和DC-ISOMAP算法分別在UMist-Cropped人臉數(shù)據(jù)集上的結(jié)果以及隨著多流形數(shù)據(jù)的不斷增加,運行以上算法分解子流形的精度變化和所消耗時間的變化。由于除了IMM-ISOMAP算法具有增量能力,其余算法均不具有增量能力,因此在計算這些算法所消耗的時間時采用的是這些算法單次執(zhí)行所消耗的時間。

3.1 分解子流形的精度及效率實驗

表1中的數(shù)據(jù)展示了IMM-ISOMAP算法與其他算法分解多流形數(shù)據(jù)的精度以及各自所消耗的運行時間之間的比較。表中的三組數(shù)據(jù)分別是從Swiss-roll、UMist-Cropped與ORL-Cropped裁剪后作為實驗數(shù)據(jù)集,由于實驗環(huán)境的限制,其中UMist-Cropped與ORL-Cropped數(shù)據(jù)集分別是從UMist人臉數(shù)據(jù)集與ORL人臉數(shù)據(jù)集上選擇部分人臉數(shù)據(jù)通過手工剪裁來作為實驗數(shù)據(jù)。

實驗結(jié)果顯示:(1)IMM-ISOMAP算法與DC-ISOMAP、SMMC算法在分解精度方面比其他算法明顯要高,可以精確的分解開子流形;(2)K-means算法不適用于高維非線性數(shù)據(jù),因此精度較低。另外精度雖然較高的SMMC算法,卻需要事先設(shè)定聚類的個數(shù),而且由表中數(shù)據(jù)可知SMMC算法在處理維度較高的數(shù)據(jù)時其運算所需時間會急劇增大,因此也不適用于高維增量數(shù)據(jù);(3)IMM-ISOMAP算法不僅不需要預(yù)先設(shè)定子流形個數(shù),而且可以像DC-ISOMAP算法一樣準(zhǔn)確分解子流形。另外由于DC-ISOMAP算法不具備增量能力,在處理新數(shù)據(jù)時需要將全部數(shù)據(jù)集重新計算,浪費了大量的計算資源,使得其在運行時會消耗大量的時間;(4)相比于其他不具備增量能力的算法,IMM-ISOMAP算法可以在保障較高分解精度的情況下,其運算所消耗的時間與新增樣本數(shù)據(jù)之間呈線性相關(guān)。實驗結(jié)果還顯示,相對于維度更高的數(shù)據(jù)UMist-Cropped與ORL-Cropped,IMM-ISOMAP算法消耗的時間相對更少,也就是說IMM-ISOMAP算法更適用于高維數(shù)據(jù)。這也就證明了IMM-ISOMAP算法有很高的效率,可以很好的應(yīng)用于大規(guī)模數(shù)據(jù)。

3.2 人造數(shù)據(jù)上的增量學(xué)習(xí)實驗

Swiss-rollwith5parts數(shù)據(jù)集是從Swiss-roll數(shù)據(jù)集中截取的五塊相互之間獨立的子流形數(shù)據(jù)集。從Swiss-rollwith5parts中隨機選取1 400個點,其中900個點作為原始數(shù)據(jù)集,其余500個點分為五個子集作為新增數(shù)據(jù)集。分別運行IMM-ISOMAP算法與ISOMAP、D-C方法與DC-ISOMAP四種算法,隨著多流形數(shù)據(jù)的不斷增加,不同算法運行得到的低維嵌入結(jié)果的可視化結(jié)果如圖1顯示。圖2顯示了隨著多流形數(shù)據(jù)的不斷增加,ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在Swiss-rollwith5parts數(shù)據(jù)集上分解子流形精度的變化以及所消耗時間的變化。

表1 比較三組數(shù)據(jù)分解子流形的精度(均值 標(biāo)準(zhǔn)差，后面括號中為最高精度)和平均運算時間(s)

Fig.1 Comparison of ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP on the embedded results of Swiss-roll block dataset圖1 ISOMAP、D-C方法、DC-ISOMAP與算法IMM-ISOMAP對Swiss-roll分塊數(shù)據(jù)的嵌入結(jié)果的比較

Fig.2 Comparison between ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP on the accuracy and consumption time of sub-manifolds on the Swiss-roll block dataset圖2 ISOMAP、D-C、DC-ISOMAP與算法IMM-ISOMAP在Swiss-roll分塊數(shù)據(jù)上分解子流形精度與消耗時間的比較

結(jié)果顯示:(1)從圖2中分解精度的比較可以看出,相較于其他算法,ISOMAP算法的分解精度是最低的,這是由于ISOMAP算法并不考慮子流形之間的位置關(guān)系,使得新子流形的低維嵌入相互重疊,如圖1所示。因此ISOMAP算法實際上無法有效的分解子流形;(2)D-C方法主要用來分解多聚類流形,但是當(dāng)多聚類流形中出現(xiàn)折疊扭曲、易于發(fā)生“短路”的情況時,該方法就不太適用。而且根據(jù)圖1中實驗結(jié)果來看,隨著多流形數(shù)據(jù)的不斷增加,該算法并不能很好的處理子流形之間的融合。而且由于沒有考慮各子流形間的位置關(guān)系,使得最終的低維嵌入并不能很好地展現(xiàn)出數(shù)據(jù)本身的流形拓?fù)浣Y(jié)構(gòu);(3)從圖2分解精度的比較可以看出,D-C方法相較于其他算法,隨著多流形數(shù)據(jù)的增加,其分解子流形的精度有一定的提高,但這種精度的提高是建立在消耗大量時間的代價上的,因此并不適合大規(guī)模數(shù)據(jù)環(huán)境。而且從圖2可以看出隨著多流形數(shù)據(jù)的增加,D-C方法的分解精度在降低;(4)DC-ISOMAP與IMM-ISOMAP算法都能通過各自的方法計算出各子流形之間的全局相對位置并得到各子流形的低維嵌入。圖1 顯示隨著多流形數(shù)據(jù)的增加,這兩種算法都可以得到很好的可視化結(jié)果,不僅展現(xiàn)出等維獨立多流形數(shù)據(jù)本身的拓?fù)浣Y(jié)構(gòu),而且很好地處理了子流形間的融合情況;(5)從圖2中分解精度的比較可以看出IMM-ISOMAP算法的分解精度始終稍低于DC-ISOMAP算法,這是由于IMM-ISOMAP算法在處理新增數(shù)據(jù)的時候,并不是在全部數(shù)據(jù)集上重新構(gòu)建近鄰圖,因此造成了精度上的損失;(6)從圖2中消耗時間的比較可以看出,ISOMAP算法、D-C方法、DC-ISOMAP算法由于不具有增量能力,隨著多流形數(shù)據(jù)的不斷增加,其消耗的時間會大幅增加。其中DC-ISOMAP算法由于計算復(fù)雜度最高,其消耗的時間最高。而IMM-ISOMAP算法在多流形數(shù)據(jù)線性增加的情況下,其消耗的時間基本保持不變。也就是說IMM-ISOMAP算法比DC-ISOMAP算法有更高的效率,更適用于大規(guī)模數(shù)據(jù)。

此實驗證明了IMM-ISOMAP算法在多流形增量數(shù)據(jù)集上,隨著多流形數(shù)據(jù)的不斷增加,不僅能夠準(zhǔn)確分解子流形,而且相較于其他算法消耗的時間更少,大大提高了算法的效率,驗證了算法在增量數(shù)據(jù)上的可行性。

3.3 實際人臉數(shù)據(jù)上的增量實驗

從UMist數(shù)據(jù)上剪裁來的UMist-Cropped人臉數(shù)據(jù),每張圖片像素為112×92,因此每個圖像可以認(rèn)為是112×92維的高維空間中的一個點。由于實驗環(huán)境的限制,從UMist-Cropped數(shù)據(jù)中僅選出其中的8組人臉數(shù)據(jù)作為實驗數(shù)據(jù),圖3分別顯示了ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在UMist-Cropped數(shù)據(jù)集上運行的可視化實驗結(jié)果。圖4顯示了隨著多流形數(shù)據(jù)的不斷增加,ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在UMist-Cropped數(shù)據(jù)集上分解子流形精度的變化以及所消耗時間的變化。

Fig.3 Comparison of ISOMAP, D-C , DC-ISOMAP and IMM-ISOMAP algorithm for low dimensional embedding of UMist_Cropped data with incremental variation圖3 ISOMAP、D-C、DC-ISOMAP與算法IMM-ISOMAP對增量變化的UMist_Cropped數(shù)據(jù)的低維嵌入結(jié)果比較

Fig.4 Comparison of ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP in incremental variation of UMist_Cropped data on the accuracy of the sub-manifold and consumption time圖4 ISOMAP、D-C方法、DC-ISOMAP與算法IMM-ISOMAP在增量變化的UMist_Cropped數(shù)據(jù)上分解子流形精度與消耗時間的比較

結(jié)果顯示:(1)從圖3分解結(jié)果看出ISOMAP算法并不能將8組人臉數(shù)據(jù)準(zhǔn)確地分解成8個單一人臉的子流形拓?fù)浣Y(jié)構(gòu),只能得到一個簡單的無實際意義的低維嵌入。從圖4中分解精度的比較中也可以看出ISOMAP算法的分解精度最低;(2)D-C方法在該數(shù)據(jù)集上的分解結(jié)果與其參數(shù)有關(guān),實驗表明在參數(shù)較大時候,分解效果反而不好。圖3的可視化結(jié)果是在參數(shù)最小即k=3的情況下得到的,結(jié)果顯示其中仍有部分人臉的數(shù)據(jù)沒有分解開。而且D-C方法分解得到的子流形大量聚集在中心部分,相互交叉折疊嚴(yán)重,其可視化效果并不好。(3)從圖4中分解精度的比較也可以看出,隨著多流形數(shù)據(jù)的增加,D-C方法的精度會慢慢降低。從圖4中消耗時間的比較也可以看出,D-C方法消耗的時間要少于DC-ISOMAP算法,這是由于D-C方法是基于K-NN構(gòu)建近鄰圖,因此其計算復(fù)雜度要小于基于動態(tài)鄰域構(gòu)建近鄰圖的DC-ISOMAP算法;(4)圖3顯示DC-ISOMAP算法與IMM-ISOMAP算法都能夠?qū)⑷四様?shù)據(jù)集準(zhǔn)確地分解成8個相互獨立的子流形,各個子流形用不同的顏色與線型加以區(qū)分,可以看出其分解效果要明顯優(yōu)于ISOMAP算法與D-C方法;(5)從圖4中分解精度的比較可以看出DC-ISOMAP算法的分解精度要高于IMM-ISOMAP算法,這是由于IMM-ISOMAP算法在處理新數(shù)據(jù)時,并不在全部數(shù)據(jù)集上重新計算近鄰關(guān)系,造成了精度上的些微損失,但是這樣大大提高了IMM-ISOMAP算法的效率。從圖4中消耗時間的比較中可以很明顯地看出DC-ISOMAP算法在多流形數(shù)據(jù)線性增加的時候,其消耗的時間幾乎呈指數(shù)級增加。如此高的計算成本,很難滿足目前大規(guī)模數(shù)據(jù)的計算需求;(6)從圖4中消耗時間的比較可以看出IMM-ISOMAP算法在多流形數(shù)據(jù)不斷增加的情況下,消耗的時間基本不變。

此實驗進(jìn)一步證明IMM-ISOMAP算法在實際數(shù)據(jù)的情況下,隨著多流形數(shù)據(jù)的不斷增加,仍能夠準(zhǔn)確分解的子流形,而且相較于其他算法消耗的時間更少。也就是說IMM-ISOMAP算法具有更高的效率,可以更好地應(yīng)用于大規(guī)模數(shù)據(jù)環(huán)境，驗證了算法在實際增量數(shù)據(jù)上的可行性。

4 結(jié)論

本文針對等維獨立多流形提出了增量學(xué)習(xí)算法IMM-ISOMAP。該算法首先對新樣本計算動態(tài)鄰域,通過擴展切空間的方法將新樣本依次劃分到各子流形,實現(xiàn)對新樣本的分類并計算最終的低維嵌入。

實驗結(jié)果表明IMM-ISOMAP算法在人造數(shù)據(jù)集與實際數(shù)據(jù)集上均驗證了其算法的有效性。相較于其他多流形識別方法,IMM-ISOMAP算法對于等維獨立多流形數(shù)據(jù)能保證一個較高的分解精度。相較于目前一些針對經(jīng)典流形學(xué)習(xí)算法提出的增量算法,IMM-ISOMAP算法可以有效處理等維獨立多流形數(shù)據(jù)。該算法的增量學(xué)習(xí)能力,使得算法的時間復(fù)雜度大大降低,未來可以很好的應(yīng)用于大數(shù)據(jù)環(huán)境。但是IMM-ISOMAP算法目前仍有一點不足在于對相交多流形數(shù)據(jù)的處理,其效果并不理想。該算法將繼續(xù)改進(jìn),以致最終能夠?qū)崿F(xiàn)準(zhǔn)確分解相交多流形數(shù)據(jù)、非線性維數(shù)約簡及其增量學(xué)習(xí)算法。

[1]TenenbaumJB,DeSV,LangfordJC.AGlobalGeometricFrameworkforNonlinearDimensionalityReduction[J].Science,2000,290(5500):2319-2323.DOI:10.1126/science.290.5500.2319.

[2]RoweisST,SaulLK.NonlinearDimensionalityReductionbyLocallyLinearEmbedding[J].Science,2000,290(5500):2323-6.

[3]GaoX,LiangJ.AnImprovedIncrementalNonlinearDimensionalityReductionforIsometricDataEmbedding[J].Information Processing Letters,2015,115(4):492-501.DOI:http:∥dx.doi.org/10.1016/j.ipl.2014.12.004.

[4]MengD,LeungY,FungT,et al.NonlinearDimensionalityReductionofDataLyingontheMulticlusterManifold[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,2008,38(4):1111-1122.DOI:10.1109/TSMCB.2008.925663.

[5]WangY,JiangY,WuY,et al.SpectralClusteringonMultipleManifolds[J].IEEE Transactions on Neural Networks,2011,22(7):1149-1161.DOI:10.1109/TNN.2011.2147798.

[6]WangY,JiangY,WuY,et al.LocalandStructuralConsistencyforMulti-manifoldClustering[C]∥InternationalJointConferenceonArtificialIntelligence.AAAIPress, 2011:1559-1564.DOI: 10.5591/978-1-57735-516-8/IJCAI11-262.

[7]AllabK,LabiodL,NadifM.Multi-ManifoldMatrixTri-FactorizationforTextDataClustering[M]∥NeuralInformationProcessing,2015.DOI:10.1007/978-3-319-26532-2-78.

[8]CaiW.AManifoldLearningFrameworkforBothClusteringandClassification[J].Knowledge-Based Systems,2015,89(C):641-653.DOI:10.1016/j.knosys.2015.09.010.

[9]SouvenirR,PlessR.ManifoldClustering[C]∥TenthIEEEInternationalConferenceonComputerVision.IEEEComputerSociety,2005:648-653Vol. 1.DOI:10.1109/ICCV.2005.149.

[10]BabaeianA,BabaeeM,BayestehtashkA,et al.NonlinearSubspaceClusteringusingCurvatureConstrainedDistances☆[J].Pattern Recognition Letters,2015,68:118-125.http:∥dx.doi.org/10.1016/j.patrec.2015.09.001.

[11] 高小方,梁吉業(yè).基于等維度獨立多流形的DC-ISOMAP算法[J].計算機研究與發(fā)展,2013，50(8):1690-1699.

[12]FanM,ZhangX,QiaoH,et al.EfficientIsometricMulti-manifoldLearningbasedontheSelf-organizingMethod[J].Information Sciences,2016,345(C):325-339.DOI:10.1016/j.ins.2016.01.069.

[13]GaoX,LiangJ.TheDynamicalNeighborhoodSelectionbasedontheSamplingDensityandManifoldCurvatureforIsometricDataEmbedding[J].Pattern Recognition Letters,2011,32(2):202-209.DOI:10.1016/j.patrec.2010.08.005.

[14]KouroptevaO,OkunO,Pietik?inenM.IncrementalLocallyLinearEmbeddingAlgorithm[J].Pattern Recognition,2005,38(10):1764-1767.DOI:10.1007/11499145-53.

[15]LawMHC,JainAK.IncrementalNonlinearDimensionalityReductionbyManifoldLearning[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(3):377-391.DOI:10.1109/TPAMI.2006.56.

[16]JiaPeng,YinJunsong.IncrementalLaplacianEigemapsbyPreservingAdjacentInformationbetweenDataPoints[J].Pattern Recognition Letters,2009,30:1457-1463.

[17]LiuX,YinJ,FengZ,et al.IncrementalManifoldLearningViaTangentSpaceAlignment[J].Lecture Notes in Computer Science,2006,4087:107-121.DOI:10.1007/11829898-10.

[18]LiH,JiangH,BarrioR,et al.IncrementalManifoldLearningbySpectralEmbeddingMethods[J].Pattern Recognition Letters,2011,32(10):1447-1455.DOI:10.1016/j.patrec.2011.04.004.

[19]ZhaoD,YangL.IncrementalIsometricEmbeddingofHigh-DimensionalDataUsingConnectedNeighborhoodGraphs[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,31(1):86-98.DOI:10.1109/TPAMI.2008.34.

[20]YangL,WangX.OnlineAppearanceManifoldLearningforVideoClassificationandClustering[M].ComputationalScienceandItsApplications2016.SpringerInternationalPublishing,2016.DOI:10.1007/978-3-319-42108-7-43.10.

Incremental Learning Algorithm IMM-ISOMAP for Well-separated Multi-manifolds with Same Intrinsic Dimension

GAO Xiaofang,LIU Jiefei

(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China)

Manifold learning is an important research issne in the fields of machine learning and data mining. The classical algorithms always assume that the high dimensional batched data exist in a single manifold, and can not effectively deal with the high dimensional multi-manifold data.We propose an incremental learning algorithm IMM-ISOMAP for equal dimension independent multi-manifolds.The algorithm computes the dynamic neighborhood of the new sample, and then divides the new samples into sub-manifolds by extending the tangent space.Finally it realizes the classification of the new samples and calculates the final low dimensional embedding.The experimental results show that the proposed algorithm can be effectively applied to artificial data and real image data.

manifold learning;incremental learning;equal dimension independent multi-manifolds;dynamic neighborhood;tangent space;IMM-ISOMAP

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.02.008

2016-10-09；

2016-11-28

國家自然科學(xué)基金(61303091；61201453)；高等學(xué)校博士學(xué)科點專向科研基金(20131401120004)；山西省回國留學(xué)人員科研資助項目(2016-002)；山西省自然科學(xué)基金(2015021091)；山西省基礎(chǔ)研究計劃項目(2014021022-2)；山西省高?？萍紕?chuàng)新項目(2015108；2015109)

高小方(1978-),女,山西安澤人,博士,副教授,主要研究方向:數(shù)據(jù)挖掘與機器學(xué)習(xí),E-mail:gxfhtp@sxu.edu.cn

TP181

A

0253-2395(2017)02-0234-10