??PCA的降維原則是最小化投影損失，或者是最大化保留投影后數(shù)據(jù)的方差。在談到其缺點(diǎn)的時(shí)候，我們說(shuō)這一目標(biāo)并不一定有助于數(shù)據(jù)的分類，換句話說(shuō)，原本在高維空間中屬于兩類的樣本，降維后可能反而不可分了。這時(shí)一種經(jīng)典的降維方法是LDA，其原理是使降維后的數(shù)據(jù)間類內(nèi)距離盡可能小，類間距離盡可能大。
?? 使用LDA有個(gè)條件，就是要知道降維前數(shù)據(jù)分別屬于哪一類，而且還要知道數(shù)據(jù)完整的高維信息。然而在Data Mining的很多應(yīng)用下，我們是不知道數(shù)據(jù)的具體特征的（也就是高維信息），而僅僅知道數(shù)據(jù)與數(shù)據(jù)之間的相似程度。比如，在文本聚類的時(shí)候我們可以輕松知道兩句話之間多么相似，但是卻不一定設(shè)計(jì)出每句話應(yīng)抽取什么樣的特征形式。在這種應(yīng)用場(chǎng)景下，我們要對(duì)數(shù)據(jù)進(jìn)行降維，必然要盡可能保證原本相似的數(shù)據(jù)在降維后的空間中依然相似，而不相似的數(shù)據(jù)盡可能還是距離很遠(yuǎn)。解決這一問(wèn)題可以采用的方法是MDS，LE，LLE等。這里我就總結(jié)總結(jié)LE（Laplacian Eigenmaps）。
??還要強(qiáng)調(diào)一次，不是說(shuō)后面每一個(gè)算法都比前面的好，而是每一種算法的降維目標(biāo)都不一樣，都是從不同角度去看問(wèn)題。
?? Laplacian Eigenmaps看問(wèn)題的角度和LLE十分相似。它們都用圖的角度去構(gòu)建數(shù)據(jù)之間的關(guān)系。圖中的每個(gè)頂點(diǎn)代表一個(gè)數(shù)據(jù)，每一條邊權(quán)重代表數(shù)據(jù)之間的相似程度，越相似則權(quán)值越大。并且它們還都假設(shè)數(shù)據(jù)具有局部結(jié)構(gòu)性質(zhì)。LE假設(shè)每一點(diǎn)只與它距離最近的一些點(diǎn)相似，再遠(yuǎn)一些的數(shù)據(jù)相似程度為0，降維后相近的點(diǎn)盡可能保持相近。而LLE假設(shè)每一個(gè)點(diǎn)都能通過(guò)周圍鄰域數(shù)據(jù)的線性組合來(lái)描述，并且降維后這一線性關(guān)系盡可能保持不變。不過(guò)這里我不主要介紹LLE，主要介紹LE，因?yàn)樗?a target="_blank" rel="nofollow">spectral clustering中被使用。

首先要構(gòu)建圖的權(quán)值矩陣。構(gòu)建方法為：

• 通過(guò)設(shè)置一個(gè)閾值，相似度在閾值以下的都直接置為零，這相當(dāng)于在一個(gè) -領(lǐng)域內(nèi)考慮局部性；
• 對(duì)每個(gè)點(diǎn)選取 k 個(gè)最接近的點(diǎn)作為鄰居，與其他的點(diǎn)的相似性則置為零。這里需要注意的是 LE 要求相似度矩陣具有對(duì)稱性，因此，我們通常會(huì)在 屬于 的 k 個(gè)最接近的鄰居且/或反之的時(shí)候，就保留 的值，否則置為零；
• 全連通。

??以上三種方法構(gòu)成的矩陣W都是對(duì)稱的。按理說(shuō)3會(huì)更讓大家接受，但是1和2能夠保證矩陣的稀疏性，而稀疏的矩陣對(duì)求特征值是十分方便的。不小心劇透了一下，LE的求解最終還是一個(gè)特征值分解問(wèn)題。不過(guò)它和PCA不一樣。怎么不一樣，后面慢慢說(shuō)。
??LE同樣把降維考慮為一種高維到低維的映射，則一個(gè)好的映射應(yīng)該使連通的點(diǎn)靠的更近（作者注：不連通的點(diǎn)按理應(yīng)該靠遠(yuǎn)點(diǎn)）。設(shè)xi映射后的點(diǎn)為yi，則LE的目標(biāo)就是最小化以下函數(shù)：

其中D_ij = ∑_jW_ij ，L=D-W，L就叫做Laplacian Matrix。
于是，我們的最小化問(wèn)題可以等效為：

這個(gè)公式是不是就似曾相識(shí)了？和PCA的目標(biāo)函數(shù)十分相似，只不過(guò)現(xiàn)在的目標(biāo)函數(shù)是求最小值，而PCA是求最大值，約束條件也小小地變形了一下。這個(gè)目標(biāo)的求解就是一個(gè)廣義特征值分解問(wèn)題：

說(shuō)到這里，還有一個(gè)問(wèn)題沒(méi)有解決，就是剛才提到的“y為一個(gè)各維相同的常量”的情況。我們看，L和D都個(gè)半正定矩陣，因此特征值都應(yīng)該大于等于0。可以很快證明，特征值為0時(shí)，y的取值（如果有之一的話）是一個(gè)全1的向量（可以把矩陣乘積展開(kāi)來(lái)計(jì)算一下，左邊因?yàn)長(zhǎng)=D-W的減號(hào)作用，結(jié)果顯然也是0的），也就是我們剛才懷疑到的這種情況。
因此，對(duì)于 0 = λ₀ <= λ₁ <= ... <= λ_K-1，我們將特征值從小到大排序后，選擇第二小的特征值到第m+1小的特征值對(duì)應(yīng)的特征向量（共m個(gè)），組成一個(gè)Nxm的矩陣，矩陣的每一行就是原來(lái)的數(shù)據(jù)降維后得到的m維特征。你會(huì)不會(huì)覺(jué)得很神奇，原本我們只知道數(shù)據(jù)與數(shù)據(jù)之間的相似程度，結(jié)果竟然把降維后的特征求出來(lái)了！ 其實(shí)求出的特征不過(guò)是個(gè)相對(duì)特征罷了，他們之間相對(duì)的距離的遠(yuǎn)近才是實(shí)際重要的，慢慢體會(huì)目標(biāo)函數(shù)你就會(huì)理解了。
還要再說(shuō)說(shuō)這里的特征值。如果僅有一個(gè)特征值為0，那么這個(gè)graph一定是全通的。關(guān)于這個(gè)結(jié)論我們可以這樣證明：
假設(shè)f是特征值0對(duì)應(yīng)的特征向量，那么：

如果兩個(gè)頂點(diǎn)是連通的，那么wij>0，為了滿足上式只要讓fi=fj。如果graph是連通的話，就能找到一系列w1i,wij,wjk……大于0(其中ijk….分別屬于234…N中的一個(gè)數(shù))，這樣就成立了f1=fj=fk=…..。換句話說(shuō)，f是一個(gè)全為一個(gè)數(shù)的向量，與全1的向量是同一個(gè)向量。又因?yàn)閮H有這一個(gè)向量滿足條件，所以僅有一個(gè)特征值0滿足全通的假設(shè)。就證明好了。
將這個(gè)結(jié)論做點(diǎn)推廣，就是如果一個(gè)graph可以分為k個(gè)連通區(qū)域，那么特征值分解后就有k個(gè)為0的特征值。
Laplacian Eigenmap具有區(qū)分?jǐn)?shù)據(jù)點(diǎn)的特性，可以從下面的例子看出：

Laplacian Eigenmap實(shí)驗(yàn)結(jié)果。左邊的圖表示有兩類數(shù)據(jù)點(diǎn)（數(shù)據(jù)是圖片），中間圖表示采用Laplacian Eigenmap降維后每個(gè)數(shù)據(jù)點(diǎn)在二維空間中的位置，右邊的圖表示采用PCA并取前兩個(gè)主要方向投影后的結(jié)果，可以清楚地看到，在此分類問(wèn)題上，Laplacian Eigenmap的結(jié)果明顯優(yōu)于PCA。
事實(shí)上，LE和LLE都假設(shè)數(shù)據(jù)分布在一個(gè)嵌套在高維空間中的低維流形上。Laplacian Matrix其實(shí)是流形的 Laplace Beltrami operator的一個(gè)離散近似。關(guān)于流型和Laplace Beltrami operator我也沒(méi)有怎么研究過(guò)，這里就給這么一個(gè)結(jié)論給大家。大家可以參考下面給出的兩篇參考文獻(xiàn)做進(jìn)一步閱讀。

Further Readings：

1. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
2. A Tutorial on Spectral Clustering

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