流形學習降維算法中一種新動態鄰域選擇方法

徐勝超

(廣州華商學院 數據科學學院，廣東 廣州 511300)

0 引 言

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

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

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

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

1 動態相鄰區域選擇方法Mod-HLLE

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

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

假設

X

={

x

,

x

,…,

x

}是在R空間中的

N

個樣本的數據集，其中

x

∈R(

i

=1,2,···,

N

)，

D

是數據集的維度。

L

為數據類型數目，

N

個數據點即為

Y

(

Y

∈R,

i

∈[1,

N

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

x

對應的

k

個近鄰進行尋找，對于相鄰區域則是借助計算數據點之間對應的非線性監督距離來實現。步驟2：通過每個數據點的相鄰區域點來計算樣本點的局部重構的權重矩陣,在此計算過程中，需要最小化代價函數。

(1)

步驟3：針對局部數據點對應權重矩陣重構，并且配合相鄰位置區域點針對輸出值進行計算。在低維空間將所有樣本點予以映射，同時對應的映射條件需要滿足如下內容：

(2)

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

Y

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

d

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

圖1 SLLE算法將3D降低到2D數據局部嵌入結果

1.2 流形學習與黑塞局部線性嵌入

如若存在某個參數空間，Φ∈

R

以及對應的光滑映射關系

φ

：Φ→

R

，當嵌入空間存在

R

使得

n

>

d

，那么則將

M

=

φ

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

R

。

ISOMAP采用等距嵌入和等角嵌入來實現流形學習。其基本假設是:

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

G

(

x

,

y

)=‖

α

-

β

‖，

x

∈,

y

∈，

α

∈Φ，

β

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

R

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

α

，

β

∈Φ，此時線段{

α

(1-

t

)+

βt

,

t

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

Hessian通過局部線性方法來完成流行學習。此方法僅僅要求局部等距映射對應的子集屬于連通且開的狀態，同時并非凸的。對應理論基礎是流形切空間上存在的黑塞編環。

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

黑塞矩陣本質上代表的是通過多元函數對應二階偏導構成的矩陣，并且針對函數局部曲率進行了描述。

(3)

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

(1)選取近鄰點。

(2)獲取切空間坐標。

(3)估計Hessian矩陣。

=[1,

V

,(

V

(:,

s

)⊙

V

(:,

l

))1≤≤≤]∈

R

*(1++(+1)2)

(4)

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

d

+

d

(

d

+1)

/

2)個，其中排在前面(

d

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

V

的列向量構成；

V

(:,

s

)⊙

V

(:,

l

)指的是

V

某個

s

或者

l

列對應向量的Hadamard積。

R

((+1)2)*

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

(5)

(4)構造二次型。

借助黑塞矩陣(其中

i

=1,2,…,

n

)來組成對稱陣，即∈

R

*，它的元素為：

(6)

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

d

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

u

,

u

,…,

u

+1，那么

U

=[

u

,

u

,…,

u

+1]∈

R

*代表的是目標計算零空間。

(6)計算低維嵌入。

定義矩陣=(

R

)*,它的元素為：

(7)

其中，

U

,代表的是

H

零空間對應矩陣里面某個第

l

行第

r

列的元素值，其中

J

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

T

=-12屬于低維嵌入結果。

1.3 Mod-HLLE描述

現階段，局部線性嵌入算法均使用的是全局且統一的相鄰區域參數，它不能處理一些非均勻的、多樣化的流形數據。

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

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

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

A

和

B

點之間曲線

AEB

對應的測量長度值用

L

表示，而

A

和

B

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

A

點和

B

點的線段長度

D

。很明顯可以看出，

D

/

L

<

D

/

L

,而且有曲線

AEB

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

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

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

經典的ISOMAP計算測地距離主要包括兩個步驟：

步驟1：根據觀察數據

x

和鄰域大小

k

構造鄰域權重圖

G

=(

V

,

E

)，

V

指的是

x

里面存在的觀察數據，

E

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

x

,

x

)∈

E

，如若

x

屬于

x

里面和

k

最近鄰，

x

和

x

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

x

,

x

)。步驟2：針對

G

里面任意某兩個點對應最短距離進行計算，并以此為基礎來針對所有流行上任意點對測地距離進行估計，用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算法主要借助等距嵌入具有的不變性來針對測地距離進行構造。具體方法是假設在兩個點之間距離十分接近的情況下，此時歐幾里德距離和測地距離之間等價，但是針對距離較遠點而言，點對測地距離通過測地距離累加來完成。如若數據集本身十分密集且參數空間屬于凸，那么ISOMAP可以在參數空間能夠針對空間歐幾里德距離進行獲取的過程中需要應對的問題包含如下：對于諸多情況而言，參數空間本身并非凸的，進而無法獲得準確結論。借助ISOMAP算法來針對測地距離進行計算，對應時間復雜度約等于

O

(

x

),復雜度太高。

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

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

X

,

k

)來完成。輸入：

X

是高維空間的數據集；

k

是數據點的相鄰區域的初始的尺寸大??；輸出：對于每個

x

∈

X

，第

i

個數據點的相鄰區域的初始的尺寸大小

k

的輸出結果

x

。步驟1：針對某個數據點

x

，在

k

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

k

個相鄰區域的局部數據集

X

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

X

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

X

和

k

在

k

個相鄰區域中選擇，組成權重圖

G

=(

V

,

E

)，

V

表示數據

X

，

E

表示連接到

X

的兩條邊的集合，這里(

x

,

x

)∈

E

。如果

x

與

x

都是屬于

k

個最接近的相鄰節點，此時

x

和

x

對應的歐幾里德距離可以用de(

x

,

x

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

G

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

X

的流形數據組成情況。凡是在圖

G

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

X

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

x

,

x

)。如果(

x

,

x

)∈

E

，dg(

x

,

x

)=de(

x

,

x

)；否則，令dg(

x

,

x

)=∞；對于所有的參數

t

，迭代計算dg(

x

,

x

)，具體如下：dg(

x

,

x

)=min{dg(

x

,

x

),dg(

x

,

x

),dg(

x

,

x

)}步驟3：當

x

∈

X

，針對

X

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

(9)

步驟4：計算

x

的相鄰區域參數，即針對各數據點

λ

對應平均值進行計算，這里

k

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

k

作為中心來進行調整。

(10)

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

k

個相鄰區域的測量距離，因為

k

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

O

(

x

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

O

(

x

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

O

(

x

),時間消耗很少。

2 實驗與性能分析

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

(a)3維的Swiss hole數據集

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

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

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

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

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

(a)3維的Twin peaks數據集

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

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

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

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

3 結束語

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