降維系列：

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

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

??????

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)f是特征值0對應(yīng)的特征向量，那么：

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

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

?

??????? Laplacian Eigenmap具有區(qū)分數(shù)據(jù)點的特性，可以從下面的例子看出：

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

?

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

?

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

from:?http://blog.csdn.net/jwh_bupt/article/details/8945083

總結(jié)

以上是生活随笔為你收集整理的降维（一）----说说主成分分析(PCA)的源头的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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