降維系列：

• 降維（一）----說說主成分分析(PCA)的源頭
• 降維（二）----Laplacian Eigenmaps

---------------------???

??????

????????前一篇文章中介紹了主成分分析。PCA的降維原則是最小化投影損失，或者是最大化保留投影后數據的方差。在談到其缺點的時候，我們說這一目標并不一定有助于數據的分類，換句話說，原本在高維空間中屬于兩類的樣本，降維后可能反而不可分了。這時一種經典的降維方法是LDA，其原理是使降維后的數據間類內距離盡可能小，類間距離盡可能大。

??????? 使用LDA有個條件，就是要知道降維前數據分別屬于哪一類，而且還要知道數據完整的高維信息。然而在Data Mining的很多應用下，我們是不知道數據的具體特征的（也就是高維信息），而僅僅知道數據與數據之間的相似程度。比如，在文本聚類的時候我們可以輕松知道兩句話之間多么相似，但是卻不一定設計出每句話應抽取什么樣的特征形式。在這種應用場景下，我們要對數據進行降維，必然要盡可能保證原本相似的數據在降維后的空間中依然相似，而不相似的數據盡可能還是距離很遠。解決這一問題可以采用的方法是MDS，LE，LLE等。這里我就總結總結LE（Laplacian Eigenmaps）。

??????? 還要強調一次，不是說后面每一個算法都比前面的好，而是每一種算法的降維目標都不一樣，都是從不同角度去看問題。

??????? Laplacian Eigenmaps看問題的角度和LLE十分相似。它們都用圖的角度去構建數據之間的關系。圖中的每個頂點代表一個數據，每一條邊權重代表數據之間的相似程度，越相似則權值越大。并且它們還都假設數據具有局部結構性質。LE假設每一點只與它距離最近的一些點相似，再遠一些的數據相似程度為0，降維后相近的點盡可能保持相近。而LLE假設每一個點都能通過周圍鄰域數據的線性組合來描述，并且降維后這一線性關系盡可能保持不變。不過這里我不主要介紹LLE，主要介紹LE，因為它在spectral clustering中被使用。

??????? 首先要構建圖的權值矩陣。構建方法為：

• 1）通過設置一個閾值，相似度在閾值以下的都直接置為零，這相當于在一個 -領域內考慮局部性；
• 2）對每個點選取 k 個最接近的點作為鄰居，與其他的點的相似性則置為零。這里需要注意的是 LE 要求相似度矩陣具有對稱性，因此，我們通常會在? 屬于? 的 k 個最接近的鄰居且/或反之的時候，就保留? 的值，否則置為零；
• 3）全連通。

??????? 以上三種方法構成的矩陣W都是對稱的。按理說3會更讓大家接受，但是1）和2）能夠保證矩陣的稀疏性，而稀疏的矩陣對求特征值是十分方便的。不小心劇透了一下，LE的求解最終還是一個特征值分解問題。不過它和PCA不一樣。怎么不一樣，后面慢慢說。

??????? LE同樣把降維考慮為一種高維到低維的映射，則一個好的映射應該使連通的點靠的更近（作者注：不連通的點按理應該靠遠點）。設xi映射后的點為yi，則LE的目標就是最小化以下函數：

??????? 如果采用1）和2）的方法構造矩陣，不連通的兩點Wij為0，所以降維對它們沒有影響。感覺有點不太合理，這不是容忍他們胡作非為么？！按理來說3）應該是更合理一些，但是3）構成的矩陣不是稀疏的╮(╯▽╰)╭。這就是一個trade-off了。而另一方面，靠的近的兩個點對應的Wij大，如果降維后他們距離遠了，受到的懲罰就會很大。

??????? 聰明的話你會一眼看出來：不對啊，降維后如果所有的y都等于同一個值，目標函數顯然是最小的，那還搞個屁啊？當然，我們會在后面求解的時候加上這一限制條件，不允許y為一個各維相同的常量。

??????? 我們快速對目標函數進行一下整理：

??????? 其中?，L=D-W，L就叫做Laplacian Matrix。

??????? 于是，我們的最小化問題可以等效為：

????????這個公式是不是就似曾相識了？和PCA的目標函數十分相似，只不過現在的目標函數是求最小值，而PCA是求最大值，約束條件也小小地變形了一下。這個目標的求解就是一個廣義特征值分解問題：

??????? 說到這里，還有一個問題沒有解決，就是剛才提到的“y為一個各維相同的常量”的情況。我們看，L和D都個半正定矩陣，因此特征值都應該大于等于0。可以很快證明，特征值為0時，y的取值（如果有之一的話）是一個全1的向量（可以把矩陣乘積展開來計算一下，左邊因為L=D-W的減號作用，結果顯然也是0的），也就是我們剛才懷疑到的這種情況。

??????? 因此，對于，我們將特征值從小到大排序后，選擇第二小的特征值到第m+1小的特征值對應的特征向量（共m個），組成一個Nxm的矩陣，矩陣的每一行就是原來的數據降維后得到的m維特征。你會不會覺得很神奇，原本我們只知道數據與數據之間的相似程度，結果竟然把降維后的特征求出來了！其實求出的特征不過是個相對特征罷了，他們之間相對的距離的遠近才是實際重要的，慢慢體會目標函數你就會理解了。

??????? 還要再說說這里的特征值。如果僅有一個特征值為0，那么這個graph一定是全通的。關于這個結論我們可以這樣證明：

假設f是特征值0對應的特征向量，那么：

??????? 如果兩個頂點是連通的，那么wij>0，為了滿足上式只要讓fi=fj。如果graph是連通的話，就能找到一系列w1i,wij,wjk……大于0(其中ijk….分別屬于234…N中的一個數)，這樣就成立了f1=fj=fk=…..。換句話說，f是一個全為一個數的向量，與全1的向量是同一個向量。又因為僅有這一個向量滿足條件，所以僅有一個特征值0滿足全通的假設。就證明好了。

??????? 將這個結論做點推廣，就是如果一個graph可以分為k個連通區域，那么特征值分解后就有k個為0的特征值。

?

??????? Laplacian Eigenmap具有區分數據點的特性，可以從下面的例子看出：

???????Laplacian Eigenmap實驗結果。左邊的圖表示有兩類數據點（數據是圖片），中間圖表示采用Laplacian Eigenmap降維后每個數據點在二維空間中的位置，右邊的圖表示采用PCA并取前兩個主要方向投影后的結果，可以清楚地看到，在此分類問題上，Laplacian Eigenmap的結果明顯優于PCA。

?

???????? 事實上，LE和LLE都假設數據分布在一個嵌套在高維空間中的低維流形上。Laplacian Matrix其實是流形的 Laplace Beltrami operator的一個離散近似。關于流型和Laplace Beltrami operator我也沒有怎么研究過，這里就給這么一個結論給大家。大家可以參考下面給出的兩篇參考文獻做進一步閱讀。

?

Further Readings：

1.? Laplacian Eigenmaps for Dimensionality Reduction and Data Representation

2.? A Tutorial on Spectral Clustering

?

-----------------

jiang1st2010

原文地址：http://blog.csdn.net/jiang1st2010/article/details/8945083

總結

以上是生活随笔為你收集整理的降维（二）----Laplacian Eigenmaps的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。