在格物匯之前的文章中，我們系統(tǒng)性的介紹了特征抽取的經(jīng)典算法——主成分分析PCA與線性判別分析LDA的原理、應(yīng)用場景，以及這兩種算法的局限性和改進(jìn)方法。今天的格物匯要給大家介紹一種新的機(jī)器學(xué)習(xí)算法——流形學(xué)習(xí)。

流形學(xué)習(xí)

流形學(xué)習(xí)是一類借鑒了拓?fù)淞餍胃拍畹慕稻S方法，與核PCA的目的一樣，它想要在低維空間中盡量保持在高維空間中的結(jié)構(gòu)。一個(gè)形象的流形降維過程如下圖，我們有一塊卷起來的布，我們希望將其展開到一個(gè)二維平面，我們希望展開后的布能夠在局部保持布結(jié)構(gòu)的特征，其實(shí)也就是將其展開的過程，就像兩個(gè)人將其拉開一樣。

流形學(xué)習(xí)方法有很多種，但是他們具有一些共同的特征：首先構(gòu)造流形上樣本點(diǎn)的局部鄰域結(jié)構(gòu)，然后用這些局部鄰域結(jié)構(gòu)來將樣本點(diǎn)全局的映射到一個(gè)低維空間。它們之間的不同之處主要是在于構(gòu)造的局部鄰域結(jié)構(gòu)不同，以及利用這些局部鄰域結(jié)構(gòu)來構(gòu)造全局的低維嵌入方法的不同。下面我們簡要介紹兩種最常見的流形學(xué)習(xí)方法：Isomap和LLE。

Isomap

高維數(shù)據(jù)結(jié)構(gòu)可能太過于抽象，很難去理解。我們先來看一個(gè)具體的實(shí)例：在上一篇文章中，我們所看到的三維空間上的數(shù)據(jù)是呈現(xiàn)”S”型，假設(shè)我們想尋找圖中兩點(diǎn)的測地距離（延曲面距離），就不能用這兩點(diǎn)坐標(biāo)所計(jì)算的歐式距離，如下圖（a）黑色線所示，因?yàn)楹谏€所構(gòu)成的路徑延曲面不可達(dá)。而應(yīng)該使用其沿著“S”形曲面所生成的距離，想象一下一只螞蟻在數(shù)據(jù)曲面上爬行，它不能脫離曲面行走，行走的路徑如下圖（a）紅色線所示。下圖（b）則顯示的是兩條線本真二維結(jié)構(gòu)上所顯示的路徑，很明顯紅色的線更加真實(shí)的反映了兩個(gè)數(shù)據(jù)點(diǎn)在三維數(shù)據(jù)上的距離。

上述這種尋找數(shù)據(jù)曲面測算距離的方法稱為Isomap（等度量映射），它是流形學(xué)習(xí)中的一種方法。它是如何實(shí)現(xiàn)的呢？它假設(shè)數(shù)據(jù)點(diǎn)與K個(gè)最近鄰的點(diǎn)可以構(gòu)成一個(gè)子集，這個(gè)子集可以用普通的歐式距離來衡量，而這個(gè)子集中的點(diǎn)又與其他子集中的點(diǎn)相連，這樣兩個(gè)目標(biāo)點(diǎn)的距離就可以分解成若干子集的歐式距離疊加來近似得到，最后這些相連的點(diǎn)可以降維到低維空間中展現(xiàn)出來。

局部線性嵌入（LLE）

流形學(xué)習(xí)另外一個(gè)典型案例是局部線性嵌入（LLE）。Isomap假設(shè)近鄰的測地距離可以用歐式距離來表示。而LLE則假設(shè)在近鄰內(nèi)可以用線性加權(quán)互相表達(dá)。比如對于任意一個(gè)樣本x0，我們都可以用他附近的幾個(gè)點(diǎn)x1 x2 x3 x4的線性組合表示出來，即

經(jīng)過LLE降維投影后，原來的點(diǎn)x0 x1 x2 x3 x4，投影變成了

LLE降維的想法是，降維后盡量去保留高維時(shí)的線性組合關(guān)系：

如何求解呢？我們需要先求出線性組合的權(quán)重w，對于樣本x0我們需要找到其最近的k個(gè)其他樣本點(diǎn)，假設(shè)為x1 x2 x3 x4，我們根據(jù)線性表示誤差最小來求出w：

根據(jù)上式確定出線性組合的w以后，我們還需要讓其在低維空間也能盡可能滿足線性組合的表達(dá)關(guān)系式，也就是說對于x0 x1 x2 x3 x4……的低維投影點(diǎn)z0 z1 z2 z3 z4……滿足：

兩個(gè)優(yōu)化目標(biāo)函數(shù)類型很像，但需要明確的是第一個(gè)目標(biāo)函數(shù)優(yōu)化的是權(quán)重w，而第二個(gè)目標(biāo)函數(shù)優(yōu)化的是降維后的坐標(biāo)z。經(jīng)過優(yōu)化即可得出樣本集在低維空間上的投影坐標(biāo)。

總的來說，對于不在某一個(gè)點(diǎn)x0鄰域內(nèi)的其他點(diǎn)A，不管A怎么變動，都不會影響到點(diǎn)x0，這種變動局部限制的思想在很多地方都有用，此外LLE盡可能的保存了局部線性信息，使得其在局部能反映出數(shù)據(jù)原本的結(jié)構(gòu)。它的流程大致如下圖所示：

小結(jié)

LLE是廣泛使用的圖形圖像降維方法，它實(shí)現(xiàn)簡單，但是對數(shù)據(jù)的流形分布特征有嚴(yán)格的要求。比如不能是閉合流形，不能是稀疏的數(shù)據(jù)集，不能是分布不均勻的數(shù)據(jù)集等等，這限制了它的應(yīng)用。

優(yōu)點(diǎn)

1、可以學(xué)習(xí)任意維的局部線性的低維流形

2、算法歸結(jié)為稀疏矩陣特征分解，計(jì)算復(fù)雜度相對較小，實(shí)現(xiàn)容易

缺點(diǎn)

1、算法所學(xué)習(xí)的流行只能是不閉合的，且樣本集是稠密均勻的

2、算法對最近鄰樣本數(shù)的選擇敏感，不同的最近鄰數(shù)對最后的降維結(jié)果有很大影響