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

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

1.引言

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

2.局部線性嵌入（LLE）

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

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

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

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

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

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

下面是在各個(gè)流行上取1500個(gè)點(diǎn)10個(gè)鄰域的實(shí)驗(yàn)結(jié)果（見圖1）。

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

3.整體保持的LLE

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

圖1

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

點(diǎn)

名稱50080010000150020002500

Swissroll111111

Swiss hole111111

Punctured sphere111111

Two peaks111111

3D clusters221321

Toroidal Helix111233

Gaussian111111

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

點(diǎn)

名稱5008001000150020002500

Swissroll111111

Swiss hole111111

Punctured sphere111111

Two peaks111111

3D clusters221321

Toroidal Helix111131

Gaussian111111

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

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

令為實(shí)對(duì)稱半正定，則對(duì)于每個(gè)低維嵌入。

有上述命題可得：

令表示的偽逆，從而令：

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

4.實(shí)驗(yàn)結(jié)果

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

圖2

5.結(jié)束語

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

參考文獻(xiàn)：

[1]余肖生，周寧.高維數(shù)據(jù)降維方法研究[J].情報(bào)科學(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é)報(bào)（自然科學(xué)版），2003（3）：267-271.