保持整體的局部線性嵌入算法

【摘 要】LLE算法是一種有效的非線性數(shù)據(jù)降維方法，但是直接LLE降維后的數(shù)據(jù)比原始數(shù)據(jù)小的很多，不能保持原始數(shù)據(jù)的整體特征，本文在LLE的基礎(chǔ)上提出了一種能夠保持原始流行整體結(jié)構(gòu)的LLE算法，實驗表明本算法在降維的同時還保持了原始流行的大小。是對LLE的有效改進。

【關(guān)鍵詞】LLE（Locally linear embedding）；數(shù)據(jù)降維

1.引言

LLE（Locally Linear Embedding）[1-3]是一種效果顯著的非線性數(shù)據(jù)降維方法。在模式識別、數(shù)據(jù)挖掘、流行學(xué)習(xí)等方面都有廣泛應(yīng)用。但是LLE算法本身的特點，它是采樣權(quán)重矩陣的近似零空間來表示嵌入坐標(biāo)的，因為權(quán)重矩陣的近似零空間里的向量比較小，不能夠保持原流行的整體大小。從而在降維的時候丟失一些信息，我們提出的保持整體特性的LLE試圖從LLE的降維效果中恢復(fù)出原流行的大小，從而保持了原始流行的整體特性。

2.局部線性嵌入（LLE）

局部線性嵌入是Saul先生與Roweis先生在2000年時創(chuàng)造性的提出的一種非線性降維理論。非線性降維理論的思想是用局部的線性來逼近全局的非線性，不改變局部的幾何結(jié)構(gòu)，通過相互重疊的局部鄰域得出整體的信息，進而保持整體的幾何性質(zhì)。但是不能保持整體流行的大小，設(shè)表示均勻采樣自維流行的個數(shù)據(jù)點組成的數(shù)據(jù)矩陣。LLE算法就是以為輸入，輸出一個由個維向量組成的矩陣，其中的第列對應(yīng)的第列。算法分為三個步驟：

第一步：選鄰域。關(guān)于高維空間中的每個樣本點，計算得到它和其他個樣本點之間的距離，根據(jù)距離的大小，找到與最近的K個點當(dāng)做其近鄰點，一般使用歐氏距離來計算兩個點之間的距離，即：。

第二步：計算每個點和它的鄰域點之間的權(quán)重，即最小化誤差函數(shù)：

當(dāng)不屬于的鄰點集時，有，權(quán)重矩陣應(yīng)該滿足：。

第三步：按照高維空間中的樣本和它的近鄰之間的權(quán)重來計算低維嵌入空間中的數(shù)值。并固定權(quán)重W，在低維空間中盡量保持高維空間中的局部線性結(jié)構(gòu)不變，最小化損失函數(shù)：

求的最優(yōu)解，的列表示低維數(shù)據(jù)點。

下面是在各個流行上取1500個點10個鄰域的實驗結(jié)果（見圖1）。

從結(jié)果的坐標(biāo)中看出，直接LLE降維后的嵌入結(jié)果和原始流行大小相差太多，不能很好的體現(xiàn)出原始流行的整體性，為此我們提出了整體保持的LLE。

3.整體保持的LLE

LLE and Linear Mapping在理論上用的d個向量作為低維嵌入坐標(biāo)是可行的，而且可以找到保持局部距離的。由于，而且在實際中的維數(shù)往往為1，從而不能滿足實際降維的需要，下表給出了常用流行上的數(shù)據(jù)點和對應(yīng)的的維數(shù)。

圖1

表1 常用流行上的數(shù)據(jù)點和對應(yīng)的的維數(shù)

點

名稱50080010000150020002500

Swissroll111111

Swiss hole111111

Punctured sphere111111

Two peaks111111

3D clusters221321

Toroidal Helix111233

Gaussian111111

表2 常用流行上的數(shù)據(jù)點和對應(yīng)的的維數(shù)

點

名稱5008001000150020002500

Swissroll111111

Swiss hole111111

Punctured sphere111111

Two peaks111111

3D clusters221321

Toroidal Helix111131

Gaussian111111

從表2中的實驗結(jié)果可以看出的維數(shù)太小不能滿足降維需要，為此我們在LLE的基礎(chǔ)上利用的近似零空間給出了保持整體的LLE，即下面的第四步，Step4：設(shè)表示均勻采樣自維流行的個數(shù)據(jù)點組成的數(shù)據(jù)矩陣。為了找到保持整體的，表示兩點之間的距離。設(shè)表示的K個鄰域，令：

命題：設(shè)是一個實對稱矩陣，則二次型可表示為：

令為實對稱半正定，則對于每個低維嵌入。

有上述命題可得：

令表示的偽逆，從而令：

再由計算出對稱矩陣，即對進行SVD分解，從而取，即保持整體距離的降維嵌入為。

4.實驗結(jié)果

保持整體的LLE在各個流行上的實驗結(jié)果和LLE結(jié)果的比較（見圖2）。

圖2

5.結(jié)束語

本文在LLE的基礎(chǔ)上通過引入局部保距映射，給出了保持原始流行整體大小的LLE。

參考文獻：

[1]余肖生，周寧.高維數(shù)據(jù)降維方法研究[J].情報科學(xué)，2007，

25（8）：1248-1251.

[2]S.Roweis，L.Saul.Nonlinear dimensionality reduction by locally linear embedding.Science，290（2000）：2323-2326.

[3]陳莉，焦李成.文檔挖掘與降維技術(shù)[J].西北大學(xué)學(xué)報（自然科學(xué)版），2003（3）：267-271.