流形學(xué)習(xí)降維算法中一種新動態(tài)鄰域選擇方法

徐勝超

(廣州華商學(xué)院 數(shù)據(jù)科學(xué)學(xué)院，廣東 廣州 511300)

0 引 言

目前許多高維數(shù)據(jù)(如金融信用信息、智能電網(wǎng)大數(shù)據(jù)信息等)需要降低到低維的空間才方便用戶觀察分析使用。降維算法的核心價值體現(xiàn)在將原本高維數(shù)據(jù)空間里面存在的樣本數(shù)據(jù)揭示出固有的組成特性，同時尋找數(shù)據(jù)的低維的、復(fù)雜的、多樣式的參數(shù)空間描述。降維最常見的算法是ISOMAP和LLE。

ISOMAP是通過計算數(shù)據(jù)點之間的測量距離(geodetic distance)來獲得全局的最優(yōu)幾何形狀結(jié)果。近幾年ISOMAP衍生了多類的改進算法。對于局部線性嵌入方法而言，LLE主要在特定范圍內(nèi)維持幾何形狀不發(fā)生改變，數(shù)據(jù)點根據(jù)同樣的尺寸大小來選擇相鄰區(qū)域，同時避免局部最小值來實現(xiàn)高維數(shù)據(jù)降維?？傮w來說，上述算法在把數(shù)據(jù)由高維降到低維的映射過程中都有比較好的效果。

局部線性嵌入降維算法在高維數(shù)據(jù)是均勻分布的時候，數(shù)據(jù)點根據(jù)同樣的尺寸來選擇相鄰區(qū)域，盡管近年來提出了不少改進方法，難以處理非均勻的數(shù)據(jù)分布;主成分分析方法中的相鄰區(qū)域選擇由于參數(shù)太多而應(yīng)用受限；當(dāng)前有一種比較好的數(shù)據(jù)降維算法是使用黑塞變換的局部線性嵌入方法(Hessian LLE)，它可以處理大多數(shù)包括非均勻分布的高維數(shù)據(jù)問題，Hessian LLE方法的不足之處是數(shù)據(jù)點的相鄰區(qū)域選擇問題需要優(yōu)化。

該文提出了一種流形學(xué)習(xí)降維算法中新的動態(tài)鄰域選擇方法Mod-HLLE。該方法參考了黑塞局部線性嵌入方法HLLE，通過在每個數(shù)據(jù)點中動態(tài)地選擇局部相鄰區(qū)域的尺寸，使其在一個開放的、連接的子集中。Mod-HLLE方法還定義了高維空間任意兩個數(shù)據(jù)點的測量距離(geodetic distance)，通過建立局部相鄰區(qū)域圖的最短路徑尋找過程來計算測量距離。在這個基礎(chǔ)上，在每個數(shù)據(jù)點中通過使用局部測量距離和局部歐幾里德距離來選擇相鄰區(qū)域的尺寸。進而借助實驗來針對Mod-HLLE方法進行分析和驗證。在高維數(shù)據(jù)降維中，選擇了無噪聲的數(shù)據(jù)樣本和有噪聲干擾的非均勻分布的數(shù)據(jù)樣本。實驗結(jié)果表明，Mod-HLLE可以獲得很好的幾何直觀效果，在性能和穩(wěn)定性方面都比常見的降維方法好。

1 動態(tài)相鄰區(qū)域選擇方法Mod-HLLE

1.1 局部線性嵌入的鄰域選擇

首先介紹帶監(jiān)督的SLLE局部線性嵌入方法及其鄰域選擇過程。

假設(shè)

X

={

x

,

x

,…,

x

}是在R空間中的

N

個樣本的數(shù)據(jù)集，其中

x

∈R(

i

=1,2,···,

N

)，

D

是數(shù)據(jù)集的維度。

L

為數(shù)據(jù)類型數(shù)目，

N

個數(shù)據(jù)點即為

Y

(

Y

∈R,

i

∈[1,

N

])。SLLE算法主要包含如下三個步驟：步驟1：針對各樣本點

x

對應(yīng)的

k

個近鄰進行尋找，對于相鄰區(qū)域則是借助計算數(shù)據(jù)點之間對應(yīng)的非線性監(jiān)督距離來實現(xiàn)。步驟2：通過每個數(shù)據(jù)點的相鄰區(qū)域點來計算樣本點的局部重構(gòu)的權(quán)重矩陣,在此計算過程中，需要最小化代價函數(shù)。

(1)

步驟3：針對局部數(shù)據(jù)點對應(yīng)權(quán)重矩陣重構(gòu)，并且配合相鄰位置區(qū)域點針對輸出值進行計算。在低維空間將所有樣本點予以映射，同時對應(yīng)的映射條件需要滿足如下內(nèi)容：

(2)

其中，=(-)(-)以及

Y

均由特征向量構(gòu)成，根據(jù)自小而大的順序來針對對應(yīng)特征值進行排列。Y的取值為M對應(yīng)最小非零特征值對應(yīng)的特征向量，從多數(shù)情況來看，首個特征值接近于0，選取的低維嵌入為2～

d

+1個特征向量。圖1顯示了一個典型的利用SLLE算法將3D降低到2D數(shù)據(jù)局部嵌入結(jié)果。

圖1 SLLE算法將3D降低到2D數(shù)據(jù)局部嵌入結(jié)果

1.2 流形學(xué)習(xí)與黑塞局部線性嵌入

如若存在某個參數(shù)空間，Φ∈

R

以及對應(yīng)的光滑映射關(guān)系

φ

：Φ→

R

，當(dāng)嵌入空間存在

R

使得

n

>

d

，那么則將

M

=

φ

(Φ)稱作流形。針對流形進行學(xué)習(xí)的根本目的在于結(jié)合數(shù)據(jù)來針對參數(shù)空間進行確定，即Φ∈

R

。

ISOMAP采用等距嵌入和等角嵌入來實現(xiàn)流形學(xué)習(xí)。其基本假設(shè)是:

(1)等距，即指的是確保等距嵌入映射保持一定情況下的測地距離，在等距嵌入不斷變換的情況下，流形上任意兩個點之間的測地距離獲取的歐幾里德空間里面依舊維持了

G

(

x

,

y

)=‖

α

-

β

‖，

x

∈,

y

∈，

α

∈Φ，

β

∈Φ。(2)凸性，即代表的是參數(shù)空間里面Φ∈

R

是屬于凸的。同時針對任何滿足

α

，

β

∈Φ，此時線段{

α

(1-

t

)+

βt

,

t

(0,1)}仍然屬于Φ。

Hessian通過局部線性方法來完成流行學(xué)習(xí)。此方法僅僅要求局部等距映射對應(yīng)的子集屬于連通且開的狀態(tài)，同時并非凸的。對應(yīng)理論基礎(chǔ)是流形切空間上存在的黑塞編環(huán)。

針對Hessian局部線性嵌入算法而言，主要在于將低維歐幾里德空間里面子集生成坐標(biāo)予以恢復(fù)，同時此子集需要是開連通的，借助領(lǐng)域來針對每個點切空間進行計算，同時借助領(lǐng)域點對應(yīng)投影坐標(biāo)來針對各點Hessian系數(shù)矩陣進行估算，進而針對Hessian矩陣對應(yīng)二次型展開計算，同時借助此二次型零空間來針對數(shù)據(jù)點低維嵌入進行獲取。

黑塞矩陣本質(zhì)上代表的是通過多元函數(shù)對應(yīng)二階偏導(dǎo)構(gòu)成的矩陣，并且針對函數(shù)局部曲率進行了描述。

(3)

黑塞局部嵌入算法運行流程如下：

(1)選取近鄰點。

(2)獲取切空間坐標(biāo)。

(3)估計Hessian矩陣。

=[1,

V

,(

V

(:,

s

)⊙

V

(:,

l

))1≤≤≤]∈

R

*(1++(+1)2)

(4)

上述矩陣里面包含的列數(shù)(1+

d

+

d

(

d

+1)

/

2)個，其中排在前面(

d

+1)列由分量是1的列向量以及分量是

V

的列向量構(gòu)成；

V

(:,

s

)⊙

V

(:,

l

)指的是

V

某個

s

或者

l

列對應(yīng)向量的Hadamard積。

R

((+1)2)*

好心當(dāng)成驢肝肺，又挨了頓搶白，老伴卻并不惱，都生活了大半輩子了，誰還能不知道對方的那點兒牛脾氣？再說蔣利學(xué)也不是總愛發(fā)脾氣，這陣子他不是忙嗎。要不是這樣，她也不會這段時間每天都變著花樣地給蔣利學(xué)做好吃的了。

(5)

(4)構(gòu)造二次型。

借助黑塞矩陣(其中

i

=1,2,…,

n

)來組成對稱陣，即∈

R

*，它的元素為：

(6)

(5)計算的零空間。針對最小(

d

+1)個特征值進行計算，同時得出各特征值對應(yīng)向量，所對應(yīng)的特征向量為

u

,

u

,…,

u

+1，那么

U

=[

u

,

u

,…,

u

+1]∈

R

*代表的是目標(biāo)計算零空間。

(6)計算低維嵌入。

定義矩陣=(

R

)*,它的元素為：

(7)

其中，

U

,代表的是

H

零空間對應(yīng)矩陣里面某個第

l

行第

r

列的元素值，其中

J

代表的是具體的樣本點，同時

T

=-12屬于低維嵌入結(jié)果。

1.3 Mod-HLLE描述

現(xiàn)階段，局部線性嵌入算法均使用的是全局且統(tǒng)一的相鄰區(qū)域參數(shù)，它不能處理一些非均勻的、多樣化的流形數(shù)據(jù)。

當(dāng)前和領(lǐng)域相關(guān)的存在三個類別，其一，針對連通領(lǐng)域圖進行構(gòu)造；其二、依靠新測速來針對領(lǐng)域點進行選擇，其中最具代表性的案例便是擁有監(jiān)督功能的SLLE，同時借助分類信息來針對新的測度進行構(gòu)造。由于需要分類信息，那么選擇的替代策略便是借助自動聚類的方法來針對分類信息進行確定。與此同時，能夠借助圖代數(shù)的方式來針對新測度進行定義，同時針對領(lǐng)域優(yōu)化；其三便是設(shè)計領(lǐng)域大小以及領(lǐng)域大小自適應(yīng)確定算法等相關(guān)問題的研究。文中工作屬于第2類，主要借助局部估計測地距離來針對領(lǐng)域進行確定，進而降低領(lǐng)域受到來自流行彎曲產(chǎn)生的影響。

因為數(shù)據(jù)點帶有大量的相鄰區(qū)域參數(shù)信息，文中的動態(tài)相鄰區(qū)域選擇方法正好使用這個思路，通過歐幾里德距離以及測量距離來針對各數(shù)據(jù)點對應(yīng)相鄰區(qū)域大小進行動態(tài)選擇。

如若觀察的數(shù)據(jù)維度很大，那么便涉及十分繁瑣的計算過程，并且需要各點領(lǐng)域具有線性特點，如若領(lǐng)域高度呈現(xiàn)彎曲狀態(tài)，此時出現(xiàn)短路的概率則較高。根據(jù)圖2，

A

和

B

點之間曲線

AEB

對應(yīng)的測量長度值用

L

表示，而

A

和

B

點之間的歐幾里德距離則代表過

A

點和

B

點的線段長度

D

。很明顯可以看出，

D

/

L

<

D

/

L

,而且有曲線

AEB

的彎曲率大于曲線CFD的彎曲率。因此可以得出，測量距離和歐幾里德距離比值越小，這2個數(shù)據(jù)點之間流形數(shù)據(jù)的曲線就越彎曲，相鄰區(qū)域參數(shù)的大小就應(yīng)該越小。

圖2 歐幾里德距離和測量距離比值與流形曲線的關(guān)系

當(dāng)領(lǐng)域里面任意點均屬于一個線性空間，那么在領(lǐng)域點越多的情況下，需要選取大領(lǐng)域參數(shù)。在使用相鄰區(qū)域參數(shù)時需要首先針對距離進行測量。如若將各輸入數(shù)據(jù)對應(yīng)距離直接進行計算，則涉及到的計算量以及計算復(fù)雜程度較高。

經(jīng)典的ISOMAP計算測地距離主要包括兩個步驟：

步驟1：根據(jù)觀察數(shù)據(jù)

x

和鄰域大小

k

構(gòu)造鄰域權(quán)重圖

G

=(

V

,

E

)，

V

指的是

x

里面存在的觀察數(shù)據(jù)，

E

指的是將兩點進行連接的對應(yīng)邊集合，(

x

,

x

)∈

E

，如若

x

屬于

x

里面和

k

最近鄰，

x

和

x

的歐幾里德距離則表示為de(

x

,

x

)。步驟2：針對

G

里面任意某兩個點對應(yīng)最短距離進行計算，并以此為基礎(chǔ)來針對所有流行上任意點對測地距離進行估計，用dg(

x

,

x

)表示。(1)初始化，如果(

x

,

x

)∈

E

,dg(

x

,

x

)=de(

x

,

x

)，否則dg(

x

,

x

)=∞。(2)利用所有的

t

，進行迭代計算：dg(

x

,

x

)=min(dg(

x

,

x

),dg(

x

,

x

)+dg(

x

,

x

))

(8)

ISOMAP算法主要借助等距嵌入具有的不變性來針對測地距離進行構(gòu)造。具體方法是假設(shè)在兩個點之間距離十分接近的情況下，此時歐幾里德距離和測地距離之間等價，但是針對距離較遠點而言，點對測地距離通過測地距離累加來完成。如若數(shù)據(jù)集本身十分密集且參數(shù)空間屬于凸，那么ISOMAP可以在參數(shù)空間能夠針對空間歐幾里德距離進行獲取的過程中需要應(yīng)對的問題包含如下：對于諸多情況而言，參數(shù)空間本身并非凸的，進而無法獲得準確結(jié)論。借助ISOMAP算法來針對測地距離進行計算，對應(yīng)時間復(fù)雜度約等于

O

(

x

),復(fù)雜度太高。

因此，Mod-HLLE方法在這里修改了計算策略。該方法中對于任意的兩個數(shù)據(jù)點及其相鄰區(qū)域，只粗略計算它們之間的測量距離,使用它作為相鄰區(qū)域參數(shù)的尺寸大小。文中通過相鄰區(qū)參數(shù)能夠針對黑塞局部線性嵌入方法進行動態(tài)改變，可以稱為Mod-HLLE。Mod-HLLE方法不僅可以改善數(shù)據(jù)降維性能，而且可以降低時間復(fù)雜度。

下面開始具體描述Mod-HLLE方法，它主要是通過計算每個數(shù)據(jù)點的相鄰區(qū)域尺寸大小Neighborhood_Sizes(

X

,

k

)來完成。輸入：

X

是高維空間的數(shù)據(jù)集；

k

是數(shù)據(jù)點的相鄰區(qū)域的初始的尺寸大小；輸出：對于每個

x

∈

X

，第

i

個數(shù)據(jù)點的相鄰區(qū)域的初始的尺寸大小

k

的輸出結(jié)果

x

。步驟1：針對某個數(shù)據(jù)點

x

，在

k

個相鄰區(qū)域里面獲得歐幾里德距離，這樣就組成了有

k

個相鄰區(qū)域的局部數(shù)據(jù)集

X

。步驟2：借助ISOMAP方法，針對

X

中的任意點計算測量距離，包括如下2個步驟：(1)根據(jù)

X

和

k

在

k

個相鄰區(qū)域中選擇，組成權(quán)重圖

G

=(

V

,

E

)，

V

表示數(shù)據(jù)

X

，

E

表示連接到

X

的兩條邊的集合，這里(

x

,

x

)∈

E

。如果

x

與

x

都是屬于

k

個最接近的相鄰節(jié)點，此時

x

和

x

對應(yīng)的歐幾里德距離可以用de(

x

,

x

)表示。(2)通過搜索圖

G

，尋找任意點對最小距離并且用來評價

X

的流形數(shù)據(jù)組成情況。凡是在圖

G

中的任意兩個點，上面的尋找最短路徑的操作要完成。完成評價

X

后，該測量距離定義為dg(

x

,

x

)。如果(

x

,

x

)∈

E

，dg(

x

,

x

)=de(

x

,

x

)；否則，令dg(

x

,

x

)=∞；對于所有的參數(shù)

t

，迭代計算dg(

x

,

x

)，具體如下：dg(

x

,

x

)=min{dg(

x

,

x

),dg(

x

,

x

),dg(

x

,

x

)}步驟3：當(dāng)

x

∈

X

，針對

X

中的任意數(shù)據(jù)點，針對局部測量距離總數(shù)和歐幾里德距離總數(shù)之間的比值進行計算，公式如下：

(9)

步驟4：計算

x

的相鄰區(qū)域參數(shù)，即針對各數(shù)據(jù)點

λ

對應(yīng)平均值進行計算，這里

k

是用來計算相鄰區(qū)域的參數(shù)。那么對于其他數(shù)據(jù)點而言，也需要將

k

作為中心來進行調(diào)整。

(10)

該算法的步驟1中使用了初始的歐幾里德距離來選擇初始的相鄰區(qū)域，將此種方法和經(jīng)過改進的局部線性嵌入進行對比。步驟2中僅僅只計算所有數(shù)據(jù)點

k

個相鄰區(qū)域的測量距離，因為

k

是一個常量，所以其時間復(fù)雜度只有

O

(

x

)。算法的步驟3階段和步驟4階段的時間復(fù)雜度都是

O

(

x

)，所以整體來計算，Mod-HLLE的四個步驟相鄰區(qū)域動態(tài)選擇方法的累積時間復(fù)雜度也是

O

(

x

),時間消耗很少。

2 實驗與性能分析

在稠密非凸性、非噪音條件下，針對三種數(shù)據(jù)降維算法對應(yīng)性能展開了對比分析。使用的樣本數(shù)據(jù)集是從3維Swiss Hole數(shù)據(jù)集中獲取的有2 000個數(shù)據(jù)點規(guī)模的流形數(shù)據(jù)。使用黑塞HLLE等三種降維方法進行分析，結(jié)合圖3(a)至圖3(d)分析結(jié)果能夠發(fā)現(xiàn)，雖然黑塞HLLE可以使數(shù)據(jù)更好地嵌入到低維的數(shù)據(jù)空間，但是HLLE還不是足夠穩(wěn)定，經(jīng)常使移出的區(qū)域太多的擴張，也許還會保留一些被扭曲的數(shù)據(jù)點。

(a)3維的Swiss hole數(shù)據(jù)集

(b)LLE方法3維到2維的降維效果

(c)HLLE方法3維到2維的降維效果

(d)Mod-HLLE方法3維到2維的降維效果 圖3 幾個局部線性嵌入降維方法效果比較

LLE是性能最差的，它的降維效果在大部分情況下具有不正確的結(jié)果。Mod-HLLE是最穩(wěn)定的，在大多數(shù)情況下，數(shù)據(jù)都可以比較完整地嵌入到2維數(shù)據(jù)空間，中心有一個小矩形正好反映了2維數(shù)據(jù)空間的嵌入，該實驗結(jié)果使Mod-HLLE方法在數(shù)據(jù)降維性能上優(yōu)于LLE和HLLE得到了初步驗證。

在數(shù)據(jù)密集型場景，存在噪聲干擾的情況下，繼續(xù)測試了幾種數(shù)據(jù)降維方法的性能。選擇了Twin peaks Surface數(shù)據(jù)集中的三維3D數(shù)據(jù)集，隨機選取了2 000個數(shù)據(jù)點。把高斯噪聲的參數(shù)按照均值0、方差為0.6進行改變。根據(jù)圖4(a)至圖4(d)的結(jié)果能夠得知，HLLE和LLE因為在相鄰區(qū)域動態(tài)選擇方法中沒有優(yōu)化，所以數(shù)據(jù)降維嵌入結(jié)果不佳。因為區(qū)域膨脹移進而導(dǎo)致剩余數(shù)據(jù)點被扭曲。Mod-HLLE方法可以把數(shù)據(jù)很好地嵌入到2維的數(shù)據(jù)空間。

(a)3維的Twin peaks數(shù)據(jù)集

(b)LLE方法3維到2維的降維效果

(c)HLLE方法3維到2維的降維效果

(d)Mod-HLLE方法3維到2維的降維效果 圖4 3D Twin peaks數(shù)據(jù)集的降維嵌入結(jié)果

實驗結(jié)果還表明各類方法都會受到噪聲的影響，都不是很穩(wěn)定，在某些情況下，LLE、HLLE方法在數(shù)據(jù)降維的時候都不是很好地嵌入到低維數(shù)據(jù)空間。這都是因為LLE、HLLE在動態(tài)相鄰區(qū)域選擇過程中受到干擾，降維效果出現(xiàn)誤差，所以去噪聲干擾也是高維數(shù)據(jù)降維中重要的因素。

3 結(jié)束語

該文提出了一種流形學(xué)習(xí)降維算法中的新動態(tài)鄰域選擇方法Mod-HLLE。該方法參考了黑塞局部線性嵌入方法HLLE，主要通過計算每個數(shù)據(jù)點的局部相鄰區(qū)域參數(shù)的方式來完成測量距離和歐幾里德距離的評測，再通過相鄰區(qū)域的尺寸大小來動態(tài)選擇新的局部相鄰區(qū)域。在噪聲干擾以及非噪聲干擾兩種不同的條件下，對兩類典型3D高維數(shù)據(jù)集上的降維測試結(jié)果表明，Mod-HLLE的降維效果優(yōu)于HLLE和LLE的降維效果，是一種比較穩(wěn)定的降維方法。