流形學(xué)習(xí)及其算法分析

1、流形學(xué)習(xí)及其算法分析流形學(xué)習(xí)及其算法分析隨著信息科學(xué)技術(shù)的發(fā)展和信息時(shí)代的到來(lái)，信息量越來(lái)越大，信息種類越來(lái)越復(fù)雜，信息數(shù)據(jù)的維數(shù)也越來(lái)越高，如何快速的對(duì)信息進(jìn)行有效的處理并能夠提取出有效的信息是當(dāng)今社會(huì)的一個(gè)重要研究課題。如今數(shù)據(jù)降維在許多領(lǐng)域起著越來(lái)越重要的作用。流形學(xué)習(xí)的主要思想就是將高維的數(shù)據(jù)映射到低維，使該低維的數(shù)據(jù)能夠反映原高維數(shù)據(jù)的某些本質(zhì)結(jié)構(gòu)特征。流形學(xué)習(xí)（Manifoldlearning）是機(jī)器學(xué)習(xí)、模式識(shí)別中的一種方

2、法，在維數(shù)約簡(jiǎn)方面具有廣泛的應(yīng)用[1]。1流形和流形學(xué)習(xí)1.1流形流形是線性子空間的一種非線性推廣，是一個(gè)局部可坐標(biāo)化的拓?fù)淇臻g。流形是拓?fù)鋵W(xué)的一個(gè)概念，拓?fù)淇臻g是拓?fù)鋵W(xué)最基本的研究對(duì)象：設(shè)集合X上的拓?fù)洇邮荴的滿足以下性質(zhì)的子集族①τ對(duì)屬于它的任意多元素的并集是封閉的；②τ對(duì)屬于它的有限多元素的交集是封閉的；③φ∈τ且X∈τ則稱（X，τ）是一個(gè)拓?fù)淇臻g。如果對(duì)空間（X，τ）中的任意兩點(diǎn)x≠y存在A∈和B∈使得A∩B=φ，則稱（X，τ）

3、是一個(gè)Hausdff拓?fù)淇臻g。設(shè)M是一個(gè)Hausdff拓?fù)淇臻g，若對(duì)每一點(diǎn)p∈M都有P的一個(gè)開領(lǐng)域U和Rn的一個(gè)開子集同胚，則稱M為n維拓?fù)淞餍?，?jiǎn)稱為n維流形[2]。低維嵌入以及利用數(shù)據(jù)降維的方法避免“維數(shù)災(zāi)難”的發(fā)生。Isomap主要是通過(guò)分析現(xiàn)有的高維流形，得到高維流形所對(duì)應(yīng)的低維嵌入，從而讓高維流形上數(shù)據(jù)點(diǎn)間的近鄰結(jié)構(gòu)在低維嵌入中得到較完整的重現(xiàn)。該算法以MDS（MultidimensionalScaling）算法為分析工具，主

4、要思想是：先計(jì)算流形上的測(cè)地線距離，然后利用計(jì)算出來(lái)的測(cè)地線來(lái)代替歐氏距離，應(yīng)用MDS算法，從而發(fā)現(xiàn)嵌入在高維空間里的低維坐標(biāo)，這樣Isomap就通過(guò)數(shù)據(jù)間的測(cè)地線距離，保留了數(shù)據(jù)固有的幾何分布結(jié)構(gòu)。Isomap中的測(cè)地線距離則使用的是最近鄰接圖中的最短路徑[4]。算法流程如下。⑴確定流形M上哪些點(diǎn)是鄰近的，兩點(diǎn)（i，j）之間距離用Dx（i，j）表示；i，j點(diǎn)皆屬于空間X；Dx（i，j）距離定義為Euclidean距離[5]，鄰接關(guān)系可

5、以設(shè)為固定的半徑e或K最近鄰。⑵通過(guò)計(jì)算圖G上兩點(diǎn)間的最短路徑DG（i，j）估計(jì)流形M上測(cè)地線距離DM（i，j）。應(yīng)用經(jīng)典MDS構(gòu)建一個(gè)在d維歐氏空間Y中保留最為完整的內(nèi)在嵌入流形幾何[5]。Isomap算法的優(yōu)點(diǎn)是利用了流形上的測(cè)地線距離來(lái)代替歐氏距離，可以較好的保留數(shù)據(jù)的空間結(jié)構(gòu)，適用于學(xué)習(xí)內(nèi)部平坦的低維流形；缺點(diǎn)是Isomap算法具有拓?fù)洳环€(wěn)定性；若產(chǎn)生短環(huán)路則會(huì)嚴(yán)重影響其執(zhí)行；并且對(duì)流形具有一定的限制要求，不適于學(xué)習(xí)有較大內(nèi)在曲