流形學(xué)習(xí)是一種借助拓?fù)淞餍胃拍畹慕稻S方法，流形是指在局部與歐式空間同胚的空間，即在局部與歐式空間具有相同的性質(zhì)，能用歐氏距離計(jì)算樣本之間的距離。這樣即使高維空間的分布十分復(fù)雜，但是在局部上依然滿足歐式空間的性質(zhì)，基于流形學(xué)習(xí)的降維正是這種**“鄰域保持”**的思想。其中**等度量映射試圖在降維前后保持鄰域內(nèi)樣本之間的距離，而局部線性嵌入（LLE）則是保持鄰域內(nèi)樣本之間的線性關(guān)系**
等度量映射的基本出發(fā)點(diǎn)是：高維空間中的直線距離具有誤導(dǎo)性，因?yàn)橛袝r(shí)高維空間中的直線距離在低維空間中是不可達(dá)的。**因此利用流形在局部上與歐式空間同胚的性質(zhì)，可以使用近鄰距離來(lái)逼近測(cè)地線距離**，即對(duì)于一個(gè)樣本點(diǎn)，它與近鄰內(nèi)的樣本點(diǎn)之間是可達(dá)的，且距離使用歐式距離計(jì)算，這樣整個(gè)樣本空間就形成了一張近鄰圖，高維空間中兩個(gè)樣本之間的距離就轉(zhuǎn)為最短路徑問(wèn)題?？刹捎弥?*Dijkstra算法**或**Floyd算法**計(jì)算最短距離，得到高維空間中任意兩點(diǎn)之間的距離后便可以使用MDS算法來(lái)其計(jì)算低維空間中的坐標(biāo)
從MDS算法的描述中我們可以知道：MDS先求出了低維空間的內(nèi)積矩陣B，接著使用特征值分解計(jì)算出了樣本在低維空間中的坐標(biāo)，但是并沒(méi)有給出通用的投影向量w，因此對(duì)于需要降維的新樣本無(wú)從下手，只能利用已知高/低維坐標(biāo)的樣本作為訓(xùn)練集學(xué)習(xí)出一個(gè)“投影器”，便可以用高維坐標(biāo)預(yù)測(cè)出低維坐標(biāo)。Isomap算法流程如下圖
對(duì)于近鄰圖的構(gòu)建，常用的有兩種方法：1.指定近鄰點(diǎn)個(gè)數(shù)**，像kNN一樣選取k個(gè)最近的鄰居；2指定鄰域半徑**，距離小于該閾值的被認(rèn)為是它的近鄰點(diǎn)。但兩種方法均會(huì)出現(xiàn)下面的問(wèn)題
?若鄰域范圍指定過(guò)大，則會(huì)造成“短路問(wèn)題，即本身距離很遠(yuǎn)卻成了近鄰，將距離近的那些樣本扼殺在搖籃
若鄰域范圍指定過(guò)小，則會(huì)造成“斷路問(wèn)題，即有些樣本點(diǎn)無(wú)法可達(dá)了，整個(gè)世界村被劃分為互不可達(dá)的小部落
不同于Isomap算法去保持鄰域距離，LLE算法試圖去保持鄰域內(nèi)的線性關(guān)系，假定樣本xi的坐標(biāo)可以通過(guò)它的鄰域樣本線性表出
LLE算法分為兩步走，第一步根據(jù)近鄰關(guān)系計(jì)算出所有樣本的鄰域重構(gòu)系數(shù)w
接著根據(jù)鄰域重構(gòu)系數(shù)不變，去求解低維坐標(biāo)**
利用矩陣M優(yōu)化問(wèn)題可以重寫為
M特征值分解后最小的d個(gè)特征值對(duì)應(yīng)的特征向量組成Z，LLE算法的具體流程如下圖所示
