四大機(jī)器學(xué)習(xí)降維算法：PCA、LDA、LLE、Laplacian Eigenmaps

1、機(jī)器學(xué)習(xí)領(lǐng)域中所謂的降維就是指采用某種映射方法，將原高維空間中的數(shù)據(jù)點(diǎn)映射到低維度的空間中。降維的本質(zhì)是學(xué)習(xí)一個(gè)映射函數(shù) f : x->y，其中x是原始數(shù)據(jù)點(diǎn)的表達(dá)，目前最多使用向量表達(dá)形式。 y是數(shù)據(jù)點(diǎn)映射后的低維向量表達(dá)，通常y的維度小于x的維度（當(dāng)然提高維度也是可以的）。f可能是顯式的或隱式的、線性的或非線性的。目前大部分降維算法處理向量表達(dá)的數(shù)據(jù)，也有一些降維算法處理高階張量表達(dá)的數(shù)據(jù)。之所以使用降維后的數(shù)據(jù)表示是因?yàn)樵谠嫉母呔S空間中，包含有冗余信息以及噪音信息，在實(shí)際應(yīng)用例如圖像識(shí)別中造成了誤差，降低了準(zhǔn)確率；而通過(guò)降維,我們希望減少冗余信息所造成的誤差,提高識(shí)別（或其他應(yīng)用

2、）的精度。又或者希望通過(guò)降維算法來(lái)尋找數(shù)據(jù)內(nèi)部的本質(zhì)結(jié)構(gòu)特征。在很多算法中，降維算法成為了數(shù)據(jù)預(yù)處理的一部分，如PCA。事實(shí)上，有一些算法如果沒(méi)有降維預(yù)處理，其實(shí)是很難得到很好的效果的。主成分分析算法（PCA）Principal Component Analysis(PCA)是最常用的線性降維方法，它的目標(biāo)是通過(guò)某種線性投影，將高維的數(shù)據(jù)映射到低維的空間中表示，并期望在所投影的維度上數(shù)據(jù)的方差最大，以此使用較少的數(shù)據(jù)維度，同時(shí)保留住較多的原數(shù)據(jù)點(diǎn)的特性。通俗的理解，如果把所有的點(diǎn)都映射到一起，那么幾乎所有的信息（如點(diǎn)和點(diǎn)之間的距離關(guān)系）都丟失了，而如果映射后方差盡可能的大，那么數(shù)據(jù)點(diǎn)則會(huì)分散開(kāi)

3、來(lái)，以此來(lái)保留更多的信息。可以證明，PCA是丟失原始數(shù)據(jù)信息最少的一種線性降維方式。（實(shí)際上就是最接近原始數(shù)據(jù)，但是PCA并不試圖去探索數(shù)據(jù)內(nèi)在結(jié)構(gòu)）設(shè)n維向量w為目標(biāo)子空間的一個(gè)坐標(biāo)軸方向（稱為映射向量），最大化數(shù)據(jù)映射后的方差，有：其中m是數(shù)據(jù)實(shí)例的個(gè)數(shù)， xi是數(shù)據(jù)實(shí)例i的向量表達(dá)， x拔是所有數(shù)據(jù)實(shí)例的平均向量。定義W為包含所有映射向量為列向量的矩陣，經(jīng)過(guò)線性代數(shù)變換，可以得到如下優(yōu)化目標(biāo)函數(shù)：其中tr表示矩陣的跡，A是數(shù)據(jù)協(xié)方差矩陣。容易得到最優(yōu)的W是由數(shù)據(jù)協(xié)方差矩陣前k個(gè)最大的特征值對(duì)應(yīng)的特征向量作為列向量構(gòu)成的。這些特征向量形成一組正交基并且最好地保留了數(shù)據(jù)中的信息。PCA的輸出

4、就是Y = WX，由X的原始維度降低到了k維。PCA追求的是在降維之后能夠最大化保持?jǐn)?shù)據(jù)的內(nèi)在信息，并通過(guò)衡量在投影方向上的數(shù)據(jù)方差的大小來(lái)衡量該方向的重要性。但是這樣投影以后對(duì)數(shù)據(jù)的區(qū)分作用并不大，反而可能使得數(shù)據(jù)點(diǎn)揉雜在一起無(wú)法區(qū)分。這也是PCA存在的最大一個(gè)問(wèn)題，這導(dǎo)致使用PCA在很多情況下的分類效果并不好。具體可以看下圖所示，若使用PCA將數(shù)據(jù)點(diǎn)投影至一維空間上時(shí)，PCA會(huì)選擇2軸，這使得原本很容易區(qū)分的兩簇點(diǎn)被揉雜在一起變得無(wú)法區(qū)分；而這時(shí)若選擇1軸將會(huì)得到很好的區(qū)分結(jié)果。Discriminant Analysis所追求的目標(biāo)與PCA不同，不是希望保持?jǐn)?shù)據(jù)最多的信息，而是希望數(shù)據(jù)在降

5、維后能夠很容易地被區(qū)分開(kāi)來(lái)。后面會(huì)介紹LDA的方法，是另一種常見(jiàn)的線性降維方法。另外一些非線性的降維方法利用數(shù)據(jù)點(diǎn)的局部性質(zhì)，也可以做到比較好地區(qū)分結(jié)果，例如LLE，Laplacian Eigenmap等。以后會(huì)介紹。LDALinear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一種有監(jiān)督的（supervised）線性降維算法。與PCA保持?jǐn)?shù)據(jù)信息不同，LDA是為了使得降維后的數(shù)據(jù)點(diǎn)盡可能地容易被區(qū)分！假設(shè)原始數(shù)據(jù)表示為X，（m*n矩陣，m是維度，n是sample的數(shù)量）既然是線性的，那么就是希望找到映射向量a， 使得 aX后

6、的數(shù)據(jù)點(diǎn)能夠保持以下兩種性質(zhì)：1、同類的數(shù)據(jù)點(diǎn)盡可能的接近（within class）2、不同類的數(shù)據(jù)點(diǎn)盡可能的分開(kāi)（between class）所以呢還是上次PCA用的這張圖，如果圖中兩堆點(diǎn)是兩類的話，那么我們就希望他們能夠投影到軸1去（PCA結(jié)果為軸2），這樣在一維空間中也是很容易區(qū)分的。接下來(lái)是推導(dǎo)，因?yàn)檫@里寫(xiě)公式很不方便，我就引用Deng Cai老師的一個(gè)ppt中的一小段圖片了：思路還是非常清楚的，目標(biāo)函數(shù)就是最后一行J（a)，（一飄）就是映射后的中心用來(lái)評(píng)估類間距，s（一瓢）就是映射后的點(diǎn)與中心的距離之和用來(lái)評(píng)估類內(nèi)距。J(a)正好就是從上述兩個(gè)性質(zhì)演化出來(lái)的。因此兩類情況下：加上a

7、a=1的條件（類似于PCA）可以拓展成多類：以上公式推導(dǎo)可以具體參考pattern classification書(shū)中的相應(yīng)章節(jié)，講fisher discirminant的OK，計(jì)算映射向量a就是求最大特征向量，也可以是前幾個(gè)最大特征向量組成矩陣A=a1,a2,.ak之后，就可以對(duì)新來(lái)的點(diǎn)進(jìn)行降維了：y = AX（線性的一個(gè)好處就是計(jì)算方便?。┛梢园l(fā)現(xiàn)，LDA最后也是轉(zhuǎn)化成為一個(gè)求矩陣特征向量的問(wèn)題，和PCA很像，事實(shí)上很多其他的算法也是歸結(jié)于這一類，一般稱之為譜（spectral）方法。線性降維算法我想最重要的就是PCA和LDA了，后面還會(huì)介紹一些非線性的方法。局部線性嵌入（LLE）Local

8、ly linear embedding（LLE）是一種非線性降維算法，它能夠使降維后的數(shù)據(jù)較好地保持原有流形結(jié)構(gòu)。LLE可以說(shuō)是流形學(xué)習(xí)方法最經(jīng)典的工作之一。很多后續(xù)的流形學(xué)習(xí)、降維方法都與LLE有密切聯(lián)系。見(jiàn)圖1，使用LLE將三維數(shù)據(jù)（b）映射到二維（c）之后，映射后的數(shù)據(jù)仍能保持原有的數(shù)據(jù)流形（紅色的點(diǎn)互相接近，藍(lán)色的也互相接近），說(shuō)明LLE有效地保持了數(shù)據(jù)原有的流行結(jié)構(gòu)。但是LLE在有些情況下也并不適用，如果數(shù)據(jù)分布在整個(gè)封閉的球面上，LLE則不能將它映射到二維空間，且不能保持原有的數(shù)據(jù)流形。那么我們?cè)谔幚頂?shù)據(jù)中，首先假設(shè)數(shù)據(jù)不是分布在閉合的球面或者橢球面上。圖1 LLE降維算法使用實(shí)例

9、LLE算法認(rèn)為每一個(gè)數(shù)據(jù)點(diǎn)都可以由其近鄰點(diǎn)的線性加權(quán)組合構(gòu)造得到。算法的主要步驟分為三步：(1)尋找每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)；（2）由每個(gè)樣本點(diǎn)的近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的局部重建權(quán)值矩陣；（3）由該樣本點(diǎn)的局部重建權(quán)值矩陣和其近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的輸出值。具體的算法流程如圖2所示：圖 2 LLE算法步驟Laplacian Eigenmaps 拉普拉斯特征映射繼續(xù)寫(xiě)一點(diǎn)經(jīng)典的降維算法，前面介紹了PCA,LDA，LLE，這里講一講Laplacian Eigenmaps。其實(shí)不是說(shuō)每一個(gè)算法都比前面的好，而是每一個(gè)算法都是從不同角度去看問(wèn)題，因此解決問(wèn)題的思路是不一樣的。這些降維算法的思想都很簡(jiǎn)單，卻在

10、有些方面很有效。這些方法事實(shí)上是后面一些新的算法的思路來(lái)源。Laplacian Eigenmaps1 看問(wèn)題的角度和LLE有些相似，也是用局部的角度去構(gòu)建數(shù)據(jù)之間的關(guān)系。它的直觀思想是希望相互間有關(guān)系的點(diǎn)（在圖中相連的點(diǎn)）在降維后的空間中盡可能的靠近。Laplacian Eigenmaps可以反映出數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu)。使用時(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è)定為：使用最小的m個(gè)非零特征值對(duì)應(yīng)的特征向量作為降維后的結(jié)果輸出。前面提到過(guò)，Laplacian Eigenmap具有區(qū)分?jǐn)?shù)據(jù)點(diǎn)的特性，可以從下面的例子看出：見(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）也有可能