基于隨機(jī)游走擴(kuò)散映射的降維算法

薛艷鋒 王三虎 高志娥 高永強(qiáng)

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)2(山西大學(xué)復(fù)雜系統(tǒng)研究所 山西 太原 030006)3(呂梁學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 山西 呂梁 033000)

0 引 言

降維是通過線性或非線性的映射關(guān)系將高維數(shù)據(jù)轉(zhuǎn)換到低維數(shù)據(jù)的過程，且該低維數(shù)據(jù)代表原始高維數(shù)據(jù)的主要成分，并能描述原始高維數(shù)據(jù)的空間分布結(jié)構(gòu)。一般情況下，由于降維后的數(shù)據(jù)更易于被分類、識(shí)別、可視化、存儲(chǔ)等，故降維在機(jī)器學(xué)習(xí)[1]以及數(shù)據(jù)可視化[2-3]領(lǐng)域受到越來越多的關(guān)注。

現(xiàn)有的降維算法主要分為線性降維和流形學(xué)習(xí)降維，其中：線性降維僅對(duì)于數(shù)據(jù)維數(shù)相對(duì)較低且具有全局線性結(jié)構(gòu)的數(shù)據(jù)有著良好的降維效果，代表算法包括主成分分析[4-5]、線性判別分析[6-7]、多尺度分析[8]算法等；流形學(xué)習(xí)降維主要是把高維空間的內(nèi)在結(jié)構(gòu)或本質(zhì)特征在低維空間盡量得以保留，代表算法包括局部線性嵌入[9]、核主成分分析[10]、ISOMAP[11]算法等。然而，在實(shí)際的科學(xué)研究中，需要一種統(tǒng)一的降維算法，使得線性降維效果與線性降維算法相當(dāng)(本文選擇的參照對(duì)象為主成分分析算法)，同時(shí)流形學(xué)習(xí)降維效果盡可能合理(參照對(duì)象為局部線性嵌入)。

為此，本文利用數(shù)據(jù)點(diǎn)屬性之間的歐氏距離定義了數(shù)據(jù)隨機(jī)游走的轉(zhuǎn)移概率矩陣A，然后通過歸一化矩陣A得到馬爾可夫轉(zhuǎn)移矩陣M(該矩陣M描述數(shù)據(jù)的離散擴(kuò)散過程)，其次通過該矩陣M得到對(duì)應(yīng)的拉普拉斯矩陣L，最后按照該矩陣L的特征值升序排列對(duì)應(yīng)的特征向量，按照累積特征值比例，原始數(shù)據(jù)依次投射到對(duì)應(yīng)特征向量(從第2個(gè)特征向量開始)上。通過實(shí)驗(yàn)結(jié)果表明，在線性降維方面，本文算法與主成分分析算法相當(dāng)，而局部線性嵌入失?。辉诹餍螌W(xué)習(xí)降維方面，主成分分析算法失敗，而本文算法雖然不及局部線性嵌入，但反映的內(nèi)在結(jié)構(gòu)一致。

1 算法描述

1.1 局部線性嵌入算法

局部線性嵌入的核心思想是假設(shè)數(shù)據(jù)在較小的局部是線性的，也就是說一個(gè)數(shù)據(jù)可以由它鄰域的幾個(gè)樣本來線性表示。具體過程如下：假設(shè)有樣本x1，在該樣本的原始鄰域中用K近鄰思想找到其中的K(超參數(shù))個(gè)樣本x2,x3,…,xk+1且可以由它們線性表示：

x1=w1,2x2+w1,3x3+…+w1,k+1xk+1

(1)

(2)

最后，通過均方差定義損失函數(shù)并求其權(quán)重系數(shù)：

(3)

1.2 隨機(jī)游走擴(kuò)散映射算法

局部線性嵌入的局部線性關(guān)系只在樣本附近起作用，離樣本遠(yuǎn)的樣本對(duì)該樣本的線性關(guān)系沒有影響且影響樣本點(diǎn)是確定的。隨機(jī)游走擴(kuò)散映射的思想是K近鄰思想的擴(kuò)展，即所有其他樣本都起作用，只是距離較近的樣本比距離較遠(yuǎn)的樣本影響更大且影響樣本點(diǎn)是隨機(jī)的。

隨機(jī)游走擴(kuò)散映射算法的具體步驟如下：

2) 使用這些距離來定義數(shù)據(jù)上的隨機(jī)游走，從點(diǎn)i到點(diǎn)j的跳躍概率為：

(4)

M=Σ-1A

(5)

設(shè)原始數(shù)據(jù)點(diǎn)降維的映射關(guān)系為f，則f(i)(i=1,2,…,N)為低維空間的坐標(biāo)點(diǎn),通過目標(biāo)函數(shù)Φ(f)求其映射關(guān)系f：

(6)

4) 令f=[f(1)f(2) …f(n)]T且fTf=1，并求其馬爾可夫轉(zhuǎn)移矩陣M的拉普拉斯矩陣L=I-M，則式(6)可化為如下矩陣形式：

(7)

即轉(zhuǎn)化為求特征值問題Lf=λf，其中λ表示拉普拉斯矩陣L的任一特征值。

5) 按照拉普拉斯矩陣L的定義以及對(duì)稱矩陣的性質(zhì)可知，存在最小的特征值λ1=0。按照特征值升序排序λ1≤…≤λN,則任一數(shù)據(jù)x映射到q維實(shí)數(shù)空間的坐標(biāo)為：

(8)

2 實(shí) 驗(yàn)

2.1 人造數(shù)據(jù)(線性降維)

該人造數(shù)據(jù)集為小世界網(wǎng)絡(luò)[12-13]，通過Python庫NetwordX[14]下面watts_strogatz_graph(n,k,p)函數(shù)生成，其中：n表示節(jié)點(diǎn)個(gè)數(shù)；k表示環(huán)狀的鄰居個(gè)數(shù)；p表示每條邊的重連概率。本文選擇節(jié)點(diǎn)個(gè)數(shù)n為100，k從{2,4,6,8,10,12,14,16,18,20}中等概率隨機(jī)選擇，p從{10-1,10-2,10-3,10-4,10-5,10-6,10-7}中等概率隨機(jī)選擇，重復(fù)執(zhí)行該函數(shù)生成2 000個(gè)小世界網(wǎng)絡(luò)，每個(gè)網(wǎng)絡(luò)的特征表示為三元組(邊密度，開三元組密度，閉三元組密度)[13]，最后依據(jù)該特征刪除重復(fù)數(shù)據(jù)最終得到實(shí)驗(yàn)數(shù)據(jù)1 317條。該三元組特征降為1維后，為了更好可視化降維效果，需要經(jīng)過歸一化處理且在散點(diǎn)圖中以縱坐標(biāo)軸顯示，左右總鄰居數(shù)以橫坐標(biāo)軸顯示。其中各個(gè)標(biāo)題名稱括號(hào)里的數(shù)字為超參數(shù)設(shè)置，比如圖1(b)括號(hào)中數(shù)字為擴(kuò)散映射的軟閾值帶寬，圖1(c)和圖1(d)括號(hào)中數(shù)字為局部線性嵌入的最近鄰個(gè)數(shù)。

從圖1可知，主成分分析與擴(kuò)散映射降維之后的特征與小世界網(wǎng)絡(luò)的左右總鄰居數(shù)有著嚴(yán)格的對(duì)應(yīng)關(guān)系，這是由于watts_strogatz_graph(n,k,p)函數(shù)生成的邊數(shù)k是確定的，而重連概率p雖然是隨機(jī)值，但由于有開三元組密度和閉三元組密度對(duì)該生成的小世界網(wǎng)絡(luò)進(jìn)行描述，故降維之后仍能保持與小世界網(wǎng)絡(luò)左右總鄰居數(shù)的嚴(yán)格對(duì)應(yīng)關(guān)系，而局部線性嵌入降維之后無法刻畫這種嚴(yán)格的對(duì)應(yīng)關(guān)系。而且，主成分分析算法與擴(kuò)散映射的累積方差貢獻(xiàn)率分別為98.95、98.93，定量說明了隨機(jī)游走擴(kuò)散映射算法在線性降維方面與主成分分析算法效果相當(dāng)。

(a) 主成分分析 (b) 擴(kuò)散映射(5)

2.2 真實(shí)數(shù)據(jù)(線性降維)

出于可視化的考慮，真實(shí)數(shù)據(jù)集為鳶尾花數(shù)據(jù)集，數(shù)據(jù)降為2維，且每一類數(shù)據(jù)通過散點(diǎn)圖分別以不同的形狀顯示。如圖2所示，主成分分析與擴(kuò)散映射算法把“setosa”類與其他兩類明顯分開，局部線性嵌入算法也達(dá)到同等的分類效果；同時(shí)，主成分分析與擴(kuò)散映射算法基本把剩余兩類(versicolor與virginica類)基本分開，而局部線性嵌入把這兩類嵌入到二維空間的同一坐標(biāo)，即分類失敗。

(a) 主成分分析 (b) 擴(kuò)散映射(10)

2.3 人造數(shù)據(jù)(流形學(xué)習(xí)降維)

該人造數(shù)據(jù)集為S-curve數(shù)據(jù)集[15]，即流形數(shù)據(jù)集(一個(gè)不閉合的曲面)，三維顯示如圖3(a)所示(括號(hào)中數(shù)字為數(shù)據(jù)點(diǎn)數(shù)量)，流形曲面具有數(shù)據(jù)分布比較均勻且比較稠密的特征，流形學(xué)習(xí)降維就是將流形從高維到低維的映射過程，在該降維過程中，流形的高維特征盡可能在低維空間得以保留。在本文，就相當(dāng)于把S-curve數(shù)據(jù)集從三維空間投影到二維空間，即把S-curve數(shù)據(jù)集展開到二維空間，展開的過程就是流形學(xué)習(xí)降維的過程，就像兩個(gè)人拉開一樣(如圖4所示)。

(a) S-curve數(shù)據(jù)集(1 000) (b) 局部線性嵌入(110)

圖4 流形學(xué)習(xí)降維示意圖

由圖3(b)可知，局部線性嵌入降維基本成功，即成功展開到二維平面。雖然左右兩端沒有展開，即在二維平面內(nèi)有數(shù)據(jù)點(diǎn)重疊現(xiàn)象，但是設(shè)想從左右兩邊觀察S-curve數(shù)據(jù)集的話，確實(shí)最下面與最上面互相重疊，且把三維空間下面的數(shù)據(jù)點(diǎn)映射到二維空間的左面，上面的數(shù)據(jù)點(diǎn)映射到二維空間的右面符合人的直觀認(rèn)識(shí)。由圖3(c)可知，主成分分析算法流形學(xué)習(xí)降維失敗，雖然“S”型輪廓從3維空間可以前后觀察得到，但流形學(xué)習(xí)降維的目的是展開該數(shù)據(jù)集，且主成分分析算法把上面的數(shù)據(jù)集映射到二維空間左面，下面的數(shù)據(jù)集映射到二維空間右面不符合人的直觀認(rèn)識(shí)。圖3(d)為擴(kuò)散映射的降維效果，從展開效果看，不及局部線性嵌入，但對(duì)比局部線性嵌入算法，擴(kuò)散映射降維算法左右兩端對(duì)稱的V字結(jié)構(gòu)與原始S-curve數(shù)據(jù)集從三維空間左右觀察有數(shù)據(jù)點(diǎn)重疊一致，且二維空間展開效果與人的直觀認(rèn)識(shí)一致。最后，三個(gè)算法就流形學(xué)習(xí)降維的效果比較如表1所示。

表1 流形學(xué)習(xí)降維效果比較

3 結(jié) 語

本文算法在線性降維效果方面，與主成分分析算法相當(dāng)，局部線性嵌入完全失敗；而在流形學(xué)習(xí)降維方面，對(duì)標(biāo)局部線性嵌入，主成分分析算法在展開效果與直觀認(rèn)識(shí)上全面失敗，而擴(kuò)散映射在展開效果上雖然不理想，但與左右兩端數(shù)據(jù)點(diǎn)重疊結(jié)果相一致，且符合直觀認(rèn)識(shí)。

今后的研究方向是改進(jìn)擴(kuò)散映射算法，使它在流形學(xué)習(xí)降維效果有所提升，比如設(shè)計(jì)隨機(jī)游走的路徑以及步長，設(shè)計(jì)更合理的距離度量以及轉(zhuǎn)移概率等。