基于隨機游走的流形學(xué)習(xí)與可視化邵超萬春紅張嘯劍

計算機與信息工程學(xué)院河南財經(jīng)政法大學(xué)河南鄭州2021/6/8

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

引言數(shù)據(jù)降維及其可視化的重要性提高人們對高維海量數(shù)據(jù)的洞察力提高后續(xù)數(shù)據(jù)分析算法的有效性和執(zhí)行效率流形學(xué)習(xí)——一類非常有效的非線性降維算法等距映射

(isometricmapping,ISOMAP)局部線性嵌入

(locallylinearembedding,LLE)拉普拉斯特征映射(Laplacianeigenmap,LE)海森特征映射(Hessianeigenmap,HE)局部切空間排列(localtangentspacealignment,

LTSA)……

引言現(xiàn)有這些流形學(xué)習(xí)算法能否成功應(yīng)用嚴(yán)重依賴于其鄰域圖能否正確表達(dá)數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，這取決于所采用的鄰域大小參數(shù)是否合適。然而，目前該參數(shù)在實際中還難以高效選取，另外，數(shù)據(jù)中的噪音對鄰域大小參數(shù)的合適性也會產(chǎn)生一定的影響。究其原因，主要是基于歐氏距離的鄰域圖創(chuàng)建方法。作為一種線性度量，歐氏距離并沒有考慮到數(shù)據(jù)可能存在的非線性幾何結(jié)構(gòu)，容易在鄰域圖中引入“短路”邊，從而使這些流形學(xué)習(xí)算法對鄰域大小參數(shù)和噪音都比較敏感，魯棒性較低。

引言為使鄰域圖能正確反映數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，多數(shù)算法基于殘差(residualvariance)來選取合適的鄰域大小參數(shù)，但這需要多次運行整個流形學(xué)習(xí)算法以計算相應(yīng)的殘差，時間復(fù)雜度過大，這也使該參數(shù)在實際中難以高效選取。針對現(xiàn)有這些流形學(xué)習(xí)算法對難以高效選取的鄰域大小參數(shù)依然比較敏感的問題通過減輕流形學(xué)習(xí)算法對鄰域大小參數(shù)的敏感程度集成不同鄰域大小參數(shù)得到的多個運行結(jié)果識別并刪除鄰域圖中可能存在的“短路”邊通過組合最小生成樹來創(chuàng)建鄰域圖為每個數(shù)據(jù)點自適應(yīng)地選取不同的鄰域大小參數(shù)

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

動機通勤時間距離

(commutetimedistance)基于鄰域圖上的隨機游走(randomwalk)理論以概率的形式綜合考慮了鄰域圖上2點間的所有連接路徑,不但比單一的最短路徑距離更加魯棒(對鄰域圖中可能存在的“短路”邊不太敏感)，而且還能在一定程度上表達(dá)數(shù)據(jù)的非線性幾何結(jié)構(gòu)，這一特點使其比線性的歐氏距離更適合于創(chuàng)建鄰域圖。

因此,和傳統(tǒng)的基于歐氏距離的鄰域圖創(chuàng)建方法相比,采用通勤時間距離來創(chuàng)建鄰域圖能更好地避免“短路”邊,從而獲得比傳統(tǒng)流形學(xué)習(xí)算法更高的魯棒性。

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

隨機游走模型和通勤時間距離數(shù)據(jù)點之間的相似度——數(shù)據(jù)分析的基礎(chǔ)由此得到描述該數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)的鄰域圖

當(dāng)且僅當(dāng)或為該鄰域圖的鄰接矩陣或相似矩陣

隨機游走模型和通勤時間距離可視為鄰域圖G上的1個Markov轉(zhuǎn)移概率矩陣

，其中，為數(shù)據(jù)點

的度(degree)。從數(shù)據(jù)點

出發(fā),跳轉(zhuǎn)到

的概率為由此便定義了鄰域圖G上的1個隨機游走模型

隨機游走模型和通勤時間距離平均首次命中時間(averagefirsthittingtime)

為從

出發(fā)，以概率

跳轉(zhuǎn)到

，以此類推，最終首次到達(dá)

的期望步數(shù)：該度量以概率的形式綜合考慮了從

到

的所有連接路徑，在刻畫

和

之間相異度方面比最短路徑距離更加魯棒，即受鄰域圖G中“短路”邊的影響比較小，從而能在一定程度上表達(dá)數(shù)據(jù)的非線性幾何結(jié)構(gòu)，據(jù)此創(chuàng)建的鄰域圖不容易產(chǎn)生“短路”邊。該度量并不對稱，對稱化之后即為通勤時間距離。

隨機游走模型和通勤時間距離通勤時間距離(commutetimedistance)

經(jīng)證明，通勤時間距離可通過Laplacian矩陣的廣義逆(Moore-Penrosepseudoinverse)矩陣計算得到:

為該鄰域圖G的總度

為Laplacian矩陣

的廣義逆矩陣

隨機游走模型和通勤時間距離通勤時間距離(commutetimedistance)

隨機游走模型和通勤時間距離通勤時間距離(commutetimedistance)隨著2點間的連接路徑增多,或其中某些連接路徑的長度變短,其通勤時間距離就會相應(yīng)減小。因此,單純依靠通勤時間距離的低維嵌入(如CTE(CommuteTimeEmbedding)算法，亦稱為圖上的主成分分析算法)雖然有利于聚類,但在流形學(xué)習(xí)與可視化時會在一定程度上扭曲數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)。

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

RW-ISOMAP算法為了更好地保持?jǐn)?shù)據(jù)的全局幾何結(jié)構(gòu)，提高數(shù)據(jù)可視化效果，應(yīng)該像ISOMAP算法那樣保持流形上有意義的全局度量——測地距離。然而，ISOMAP算法用來逼近測地距離所采用的單一的最短路徑距離具有比較差的魯棒性，鄰域圖中可能存在的“短路”邊就會使之徹底失去逼近相應(yīng)測地距離的能力。究其原因，主要是用來計算最短路徑距離的鄰域圖是基于線性的歐氏距離來進(jìn)行創(chuàng)建的。

RW-ISOMAP算法通勤時間距離會隨著連接路徑增多或某些連接路徑變短而逐步減小，因此，單純依靠通勤時間距離可能會漏掉其中的某些最近鄰點，從而難以確保測地距離的良好逼近。圖1由k-最近鄰法(k=2)得到的數(shù)據(jù)集{A,B,C,D}的鄰域圖，如細(xì)實線表示，其中，數(shù)據(jù)點A的兩個最近鄰點為B和C。然而，如果單純使用通勤時間距離來確定最近鄰點，則數(shù)據(jù)點A的兩個最近鄰點為C和D，如粗虛線表示，這是因為D和A之間存在多條相對較短的連接路徑，如(A,D)和(A,C,D)

RW-ISOMAP算法為了確保測地距離的良好逼近，從而更真實地展現(xiàn)數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，本文首先采用能使鄰域圖連通的最小k值(記為km)來創(chuàng)建鄰域圖(稱為最小連通鄰域圖，記為

，該鄰域圖能為每個數(shù)據(jù)點都保留若干個最近鄰點，并能在最大程度上避免“短路”邊)；然后，在此基礎(chǔ)上使用通勤時間距離為每個數(shù)據(jù)點增加更多的最近鄰點。由于通勤時間距離考慮了數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，能在避免“短路”邊的情況下使鄰域圖足夠稠密，從而使測地距離得以更加精確的逼近。

RW-ISOMAP算法輸入：數(shù)據(jù)

，用于計算通勤時間距離的鄰域大小參數(shù)k1和參數(shù)t，用于創(chuàng)建鄰域圖的鄰域大小參數(shù)k2輸出：數(shù)據(jù)

的低維嵌入

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

CTD-ISOMAP算法

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

實驗結(jié)果——完整流形的實驗結(jié)果Swissroll和S-curve數(shù)據(jù)集

Swissroll數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果Swissroll數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果S-curve數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果S-curve數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果加入噪音的Swissroll數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果加入噪音的Swissroll數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果加入噪音的S-curve數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果加入噪音的S-curve數(shù)據(jù)集上的實驗結(jié)果

實驗結(jié)果——完整流形的實驗結(jié)果殘差(residualvariance)對比

實驗結(jié)果——完整流形的實驗結(jié)果帶有空洞的Swissroll數(shù)據(jù)集

實驗結(jié)果——不完整流形的實驗結(jié)果帶有空洞的Swissroll數(shù)據(jù)集

實驗結(jié)果——不完整流形的實驗結(jié)果帶有空洞的Swissroll數(shù)據(jù)集

實驗結(jié)果——不完整流形的實驗結(jié)果

實驗結(jié)果——人臉數(shù)據(jù)集的實驗結(jié)果

實驗結(jié)果——人臉數(shù)據(jù)集的實驗結(jié)果

提綱引言動機隨機游走模型和通勤時間距離RW-ISOMAP算法實驗結(jié)果結(jié)束語

結(jié)束語由隨機游走模型得到的通勤時間距離具有良好的魯棒性，且考慮了數(shù)據(jù)的非線性幾何結(jié)構(gòu)，因此，本文提出了基于隨機游走的流形學(xué)習(xí)算法—