Laplacian Eigenmaps?

繼續(xù)寫(xiě)一點(diǎn)經(jīng)典的降維算法，前面介紹了PCA,LDA，LLE，這里講一講Laplacian Eigenmaps。其實(shí)不是說(shuō)每一個(gè)算法都比前面的好，而是每一個(gè)算法都是從不同角度去看問(wèn)題，因此解決問(wèn)題的思路是不一樣的。這些降維算法的思想都很簡(jiǎn)單，卻在有些方面很有效。這些方法事實(shí)上是后面一些新的算法的思路來(lái)源。

Laplacian Eigenmaps[1] 看問(wèn)題的角度和LLE有些相似，也是用局部的角度去構(gòu)建數(shù)據(jù)之間的關(guān)系。

它的直觀思想是希望相互間有關(guān)系的點(diǎn)（在圖中相連的點(diǎn)）在降維后的空間中盡可能的靠近。Laplacian Eigenmaps可以反映出數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu)。

Laplacian Eigenmaps也通過(guò)構(gòu)建相似關(guān)系圖（對(duì)應(yīng)的矩陣為）來(lái)重構(gòu)數(shù)據(jù)流形的局部結(jié)構(gòu)特征。Laplacian Eigenmaps算法的主要思想是，如果兩個(gè)數(shù)據(jù)實(shí)例i和j很相似，那么i和j在降維后目標(biāo)子空間中應(yīng)該盡量接近。設(shè)數(shù)據(jù)實(shí)例的數(shù)目為n，目標(biāo)子空間的維度為m。定義大小的矩陣，其中每一個(gè)行向量是數(shù)據(jù)實(shí)例i在目標(biāo)m維子空間中的向量表示，Laplacian Eigenmaps要優(yōu)化的目標(biāo)函數(shù)如下

定義對(duì)角矩陣，對(duì)角線上位置元素等于矩陣的第i行之和，經(jīng)過(guò)線性代數(shù)變換，上述優(yōu)化問(wèn)題可以用矩陣向量形式表示如下：

其中矩陣是圖拉普拉斯矩陣。限制條件保證優(yōu)化問(wèn)題有解，并且保證映射后的數(shù)據(jù)點(diǎn)不會(huì)被“壓縮”到一個(gè)小于m維的子空間中。使得公式最小化的Y的列向量是以下廣義特征值問(wèn)題的m個(gè)最小非0特征值（包括重根）對(duì)應(yīng)的特征向量：

?

使用時(shí)算法具體步驟為：

步驟1：構(gòu)建圖

使用某一種方法來(lái)將所有的點(diǎn)構(gòu)建成一個(gè)圖，例如使用KNN算法，將每個(gè)點(diǎn)最近的K個(gè)點(diǎn)連上邊。K是一個(gè)預(yù)先設(shè)定的值。

步驟2：確定權(quán)重

確定點(diǎn)與點(diǎn)之間的權(quán)重大小，例如選用熱核函數(shù)來(lái)確定，如果點(diǎn)i和點(diǎn)j相連，那么它們關(guān)系的權(quán)重設(shè)定為：

另外一種可選的簡(jiǎn)化設(shè)定是如果點(diǎn)i，j相連，否則。

步驟3：特征映射

計(jì)算拉普拉斯矩陣L的特征向量與特征值：

其中D是對(duì)角矩陣，滿足，。

使用最小的m個(gè)非零特征值對(duì)應(yīng)的特征向量作為降維后的結(jié)果輸出。

前面提到過(guò)，Laplacian Eigenmap具有區(qū)分?jǐn)?shù)據(jù)點(diǎn)的特性，可以從下面的例子看出：

圖1 Laplacian Eigenmap實(shí)驗(yàn)結(jié)果

見(jiàn)圖1所示，左邊的圖表示有兩類數(shù)據(jù)點(diǎn)（數(shù)據(jù)是圖片），中間圖表示采用Laplacian Eigenmap降維后每個(gè)數(shù)據(jù)點(diǎn)在二維空間中的位置，右邊的圖表示采用PCA并取前兩個(gè)主要方向投影后的結(jié)果，可以清楚地看到，在此分類問(wèn)題上，Laplacian Eigenmap的結(jié)果明顯優(yōu)于PCA。

?

圖2 roll數(shù)據(jù)的降維

圖2說(shuō)明的是，高維數(shù)據(jù)（圖中3D）也有可能是具有低維的內(nèi)在屬性的（圖中roll實(shí)際上是2D的），但是這個(gè)低維不是原來(lái)坐標(biāo)表示，例如如果要保持局部關(guān)系，藍(lán)色和下面黃色是完全不相關(guān)的，但是如果只用任何2D或者3D的距離來(lái)描述都是不準(zhǔn)確的。

下面三個(gè)圖是Laplacian Eigenmap在不同參數(shù)下的展開(kāi)結(jié)果（降維到2D），可以看到，似乎是要把整個(gè)帶子拉平了。于是藍(lán)色和黃色差的比較遠(yuǎn)。

?

?

Reference

[1] Belkin, M., Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering.?Advances in neural information processing systems. 2002, 1585-592.

總結(jié)

以上是生活随笔為你收集整理的Laplacian Eigenmaps 拉普拉斯特征映射的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。